题解 P3677 【[CERC2016]关键的膝盖 Key Knocking】
342zhuyongqi
2018-08-07 10:54:21
利用构造法贪心求解。
因为可以操作n次，一共3n个，所以可以把每3个分成一组
一共有8种可能
000
111
011
100
110
001
010
101
对于010 101不用改变
对于011 100换前2个
对于110 001换后2个
对于111 000看前面就行了
```cpp
#include<stdio.h>
#include<string.h>
int n;
char a[300010];
int ans[100010],ans2;
int idx,sum,t;
#define a1 (i-1)*3+1
#define a2 (i-1)*3+2
#define a3 (i-1)*3+3
int main()
{
scanf("%s",a+1);
int l=strlen(a+1);
for(int i=1;i<=l;i++)
a[i]=a[i]-'0';
for(int i=1;i<=l;i++)
if(a[i]!=a[i+1])
ans2++;
if(ans2>=l/3*2+1)
{
printf("0");
return 0;
}
for(int i=1;i<=l/3;i++)
{
if((a[a1]==a[a2])&&(a[a2]!=a[a3]))
{
sum++;
if(a[a2]==1)
a[a2]=0;
else
a[a2]=1;
if(a[a3]==1)
a[a3]=0;
else
a[a3]=1;
ans[++idx]=a2;
}
else if((a[a1]!=a[a2])&&(a[a2]!=a[a3]))
continue;
else if((a[a1]!=a[a2])&&(a[a2]==a[a3]))
{
sum++;
if(a[a2]==1)
a[a2]=0;
else
a[a2]=1;
if(a[a1]==1)
a[a1]=0;
else
a[a1]=1;
ans[++idx]=a1;
}
else
{
if(a[a1]==a[(i-1)*3])
{
sum++;
if(a[a1]==1)
a[a1]=0;
else
a[a1]=1;
if(a[a2]==1)
a[a2]=0;
else
a[a2]=1;
ans[++idx]=a1;
}
else
{
sum++;
if(a[a3]==1)
a[a3]=0;
else
a[a3]=1;
if(a[a2]==1)
a[a2]=0;
else
a[a2]=1;
ans[++idx]=a2;
}
}
}
printf("%d\n",sum);
for(int i=1;i<=sum;i++)
{
if(i!=sum)
printf("%d ",ans[i]);
else
printf("%d",ans[i]);
}
}
```