open judge 特殊的密码锁 贪心

原创
2016/11/11 11:32
阅读数 82

http://noi.openjudge.cn/ch0406/8469/

题面   ↑

这个题目有两次方法可以贪心,第一个开关动还是不动,枚举一下就可以了。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[1000],b[1000],c[1000];
int main()
{
	scanf("%s%s",a+1,b+1);
	int x=strlen(a+1),y=strlen(b+1);
	for(int i=1;i<=x;i++)
	c[i]=a[i];	
	int ans=0,ans2=0;
	ans2++;
	if(c[1]=='0') c[1]='1';
	else c[1]='0';
	if(c[2]=='0') c[2]='1';
	else  c[2]='0';
	for(int i=1;i<=x;i++)
	{
		if(c[i]!=b[i]&&i+1<=x)
		{	
			ans2++;
			c[i]=b[i];
			if(c[i+1]=='0') c[i+1]='1';
			else c[i+1]='0';
			if(c[i+2]=='0') c[i+2]='1';
	 		else c[i+2]='0';
		}
	}
	int h=0,h2=0;
	for(int i=1;i<=x;i++)
	{
		if(c[i]!=b[i])
		{
			h=1;
			break;
		}
	}
	for(int i=1;i<=x;i++)
	{
		if(a[i]!=b[i]&&i+1<=x)
		{
			ans++;
			a[i]=b[i];
			if(a[i+1]=='0') a[i+1]='1';
			else a[i+1]='0';
			if(a[i+2]=='0') a[i+2]='1';
			else a[i+2]='0';
		}
	}
	for(int i=1;i<=x;i++)
	{
		if(a[i]!=b[i])
		{
			h2=1;
			break;
		}
	}
	if(h2==0&&h==0)
	{
		int tq=min(ans,ans2);
		cout<<tq;
	}
	else if(h2==0&&h==1)
		cout<<ans;
	else if(h==0&&h2==1)
		cout<<ans2;
	else  puts("impossible");
	return 0;
}

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部