首页 > 代码库 > NOI OpenJudge 8469 特殊密码锁 Label贪心
NOI OpenJudge 8469 特殊密码锁 Label贪心
描述
有一种特殊的二进制密码锁,由n个相连的按钮组成(n<30),按钮有凹/凸两种状态,用手按按钮会改变其状态。
然而让人头疼的是,当你按一个按钮时,跟它相邻的两个按钮状态也会反转。当然,如果你按的是最左或者最右边的按钮,该按钮只会影响到跟它相邻的一个按钮。
当前密码锁状态已知,需要解决的问题是,你至少需要按多少次按钮,才能将密码锁转变为所期望的目标状态。
输入两行,给出两个由0、1组成的等长字符串,表示当前/目标密码锁状态,其中0代表凹,1代表凸。输出至少需要进行的按按钮操作次数,如果无法实现转变,则输出impossible。样例输入
011000
样例输出
1
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 string a,des,fuben; 8 int ans1,ans2,flag1,flag2; 9 void change(int s,int t){10 for(int i=s;i<=t&&i<a.size();i++){11 if(a[i]==‘1‘) a[i]=‘0‘;12 else if(a[i]==‘0‘) a[i]=‘1‘;13 }14 }15 16 int main(){17 // freopen("01.in","r",stdin);18 cin>>a>>des;19 fuben=a;20 21 for(int i=0;i<a.size();i++){22 if(a[i]!=des[i]){23 ans1++;24 if(i==0){change(0,1);}25 else if(i==a.size()-1){flag1=1;}26 else {change(i,i+2);}27 }28 }29 30 a=fuben;31 change(0,1);ans2++;32 for(int i=0;i<a.size();i++){33 if(a[i]!=des[i]){34 ans2++;35 if(i==0){change(0,2);}36 else if(i==a.size()-1){flag2=1;}37 else {change(i,i+2);}38 }39 }40 41 if(flag1==1&&flag2==1) puts("impossible");42 if(flag1==1&&flag2!=1) printf("%d\n",ans2);43 if(flag1!=1&&flag2==1) printf("%d\n",ans1);44 if(flag1!=1&&flag2!=1) printf("%d\n",min(ans1,ans2));45 return 0;46 }请参考 开关问题
值得注意的是Line31 必须写
否则看这组数据
001
000
NOI OpenJudge 8469 特殊密码锁 Label贪心
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。