网络小说网站建设,地产公司做网站维护写代码么,现成的手机网站做APP,WordPress管理员邮件描述
有一种特殊的二进制密码锁#xff0c;由n个相连的按钮组成#xff08;n30#xff09;#xff0c;按钮有凹/凸两种状态#xff0c;用手按按钮会改变其状态。
然而让人头疼的是#xff0c;当你按一个按钮时#xff0c;跟它相邻的两个按钮状态也会反转。当然由n个相连的按钮组成n30按钮有凹/凸两种状态用手按按钮会改变其状态。
然而让人头疼的是当你按一个按钮时跟它相邻的两个按钮状态也会反转。当然如果你按的是最左或者最右边的按钮该按钮只会影响到跟它相邻的一个按钮。
当前密码锁状态已知需要解决的问题是你至少需要按多少次按钮才能将密码锁转变为所期望的目标状态。
输入
两行给出两个由0、1组成的等长字符串表示当前/目标密码锁状态其中0代表凹1代表凸。
输出
至少需要进行的按按钮操作次数如果无法实现转变则输出impossible。
样例输入
011
000
样例输出
1
解题分析
二进制序列按了其中一个数可以让其和其旁边的一个或者两个数取反。
其实这道题的限制条件也很容易发现关键就在于一个分类讨论那就是第一个按钮开始的一个确定序列。什么意思如果前面一个按钮按与不按的状态确定了那么后续的按钮按与不按的状态也都确定了我们只需要枚举第一个按钮的状态即可。这个又可以联想到一个15*15方格的画家图画板的问题或者说是点灯问题这也是很经典的。
我们枚举第一个按钮的状态如果二者第一个数不同我们要想改变第一个数的状态就只有按第一个按钮或者说按第二个按钮。如果我们选择了按第一个按钮那么后续能够影响第二个按钮状态的就只有第三个按钮了如果不按第一个按钮我们就得按第二个按钮然后我们同样地也可以发现能影响第二个按钮的就只有第三个按钮了以此类推。
代码实现
#include iostream
#include cmath
#include iomanip
#include string
#include cstring
#include cstdio
#include algorithm
#include vector
#include map
#include set
#include unordered_map
#include unordered_set
#include list
#include bitset
using namespace std;void press(string s,int i){int ls.size();if(i0){s[i](s[i]1?0:1);s[i1](s[i1]1?0:1);}else if(il-1){s[i](s[i]1?0:1);s[i-1](s[i-1]1?0:1);}else{s[i](s[i]1?0:1);s[i-1](s[i-1]1?0:1);s[i1](s[i1]1?0:1);}
}int main(){string cur,des;int len;int c0;int res1e9;cincurdes;lencur.size();//分类讨论第一个位置按或者不按总共只有这两种情况//之后的每个位置都因为第一个位置按或者不按而确定string cur1cur;press(cur,0);c;for(int i1;ilen;i){if(cur[i-1]des[i-1]){continue;}else{press(cur,i);c;}} if(curdes){resmin(res,c);}c0;for(int i1;ilen;i){if(cur1[i-1]des[i-1]){continue;}else{press(cur1,i);c;}}if(cur1des){resmin(res,c);}if(res1e9){coutimpossibleendl;}else{coutresendl;}return 0;
}
