题解 P3677 【[CERC2016]关键的膝盖 Key Knocking】

· · 题解

利用构造法贪心求解。

因为可以操作n次，一共3n个，所以可以把每3个分成一组

一共有8种可能

000

111

011

100

110

001

010

101

对于010 101不用改变

对于011 100换前2个

对于110 001换后2个

对于111 000看前面就行了

#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]);        
    }
}