如何建设网站济南兴田德润o团队怎么样/企业员工培训总结

总时间限制: 1000ms 内存限制: 1024kB
描述
有一种特殊的二进制密码锁，由n个相连的按钮组成（n<30），按钮有凹/凸两种状态，用手按按钮会改变其状态。然而让人头疼的是，当你按一个按钮时，跟它相邻的两个按钮状态也会反转。当然，如果你按的是最左或者最右边的按钮，该按钮只会影响到跟它相邻的一个按钮。当前密码锁状态已知，需要解决的问题是，你至少需要按多少次按钮，才能将密码锁转变为所期望的目标状态。输入
两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。
输出
至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible。
样例输入
011
000
样例输出
1

和课上讲的熄灯问题很像，或者说本质上就是把那个问题一排的灯数设为1。

注意到只要确定第一个按钮按不按，就能依次确定后面的按钮按不按了，也就是说只要枚举两次。

可以用课上讲的用一个int变量来存储一个二进制形式的按钮状态。

#include <iostream>
using namespace std;
#define min(x, y) x < y ? x : y
#define max_num 29 //最多可能的按钮数bool GetBit(int x, int i) //取x的第i位
{return (x >> i) & 1;
}
void SetBit(int &x, int i, bool v) //将x的第i位设置为v
{if (v)x |= (1 << i); //或一得一，或零不变elsex &= ~(1 << i); //与零得零，与一不变
}
void Flip(int &x, int i) //将x的第i位取反
{x ^= (1 << i); //异或一得反，异或零不变
}void Convert(string str, int &x) //将二进制形式字符串转化为整型
{for (int i = 0; i < str.length(); i++)SetBit(x, i, str[i] - '0'); //别忘记 -'0'
}int main()
{//读入题目数据int origin = 0, expected = 0;string str1, str2;cin >> str1 >> str2;Convert(str1, origin);Convert(str2, expected);int num = str1.length(); //按钮的个数int count[2] = {0}; //两种情况如果能成功的话总共按下去的按钮个数(若失败则为max_num+1)for (int press_first = 0; press_first <= 1; press_first++){int temp = origin; //准备操作的按钮原状态备份if (press_first){Flip(temp, 0);Flip(temp, 1);count[press_first]++; //别忘了第一次也要算上}for (int i = 1; i < num; i++){if (GetBit(temp, i - 1) ^ GetBit(expected, i - 1)) //如果前一个不对，就只能后一个来调{Flip(temp, i);if (i < num - 1)Flip(temp, i + 1);count[press_first]++;}}if (GetBit(temp, num - 1) != GetBit(expected, num - 1)) //检查这么做能否完成任务count[press_first] = max_num + 1;}if (count[0] == max_num + 1 && count[1] == max_num + 1)cout << "impossible" << endl;elsecout << (min(count[0], count[1])) << endl; //左移运算符优先级高于不等号因此要加括号
}