总时间限制: 1000ms 内存限制: 1024kB 描述 有一种特殊的二进制密码锁，由n个相连的按钮组成（n<30），按钮有凹/凸两种状态，用手按按钮会改变其状态。 然而让人头疼的是，当你按一个按钮时，跟它相邻的两个按钮状态也会反转。当然，如果你按的是最左或者最右边的按钮，该按钮只会影响到跟它相邻的一个按钮。 当前密码锁状态已知，需要解决的问题是，你至少需要按多少次按钮，才能将密码锁转变为所期望的目标状态。 输入 两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。 输出 至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible。
解题策略: 只枚举第一个按或者不按。后面的每个按钮如果和答案不一样，那么就按它的下一个按钮。这样就能保证我按的不会影响之前和答案一样的状态，那么一共就只有两种情况，第一个按钮按或者不按。
#include <algorithm> #include <cmath> #include <cstring> #include <iostream> #include <memory> typedef long long ll; using namespace std; int getbit(int c, int i) { return (c >> i) & 1; } void setbit(int& c, int i, int v) { if (v) { c |= (1 << i); } else { c &= ~(1 << i); } } void flip(int& c, int i) { c ^= (1 << i); } int main() { string a, res; cin >> a >> res; int as = 0; //拷贝锁状态 int intres = 0; //答案状态 int l = a.length(); for (int i = 0; i < l; i++) { setbit(intres, i, res[i] - '0'); } for (int k = 0; k < l; k++) { setbit(as, k, a[k] - '0'); } int anfa = 0; int minanfa = 1<<30; int lock; int button; for (int i = 0; i < 2; i++) { lock = as; anfa = 0; button = i; for (int j = 0; j < l; j++) { if(button) { anfa++; if (j > 0) { flip(lock, j-1); } flip(lock, j); if (j < l - 1) { flip(lock, j+1); } } if (getbit(lock, j)!=getbit(intres,j)) { button = 1; }else{ button = 0; } } if (lock == intres) { minanfa = min(minanfa, anfa); } } if (minanfa == 1<<30) { cout << "impossible" << endl; } else { cout << minanfa << endl; } return 0; }