题解：P9851 [ICPC2021 Nanjing R] Secret of Tianqiu Valley

· · 题解

首先考虑解出每个火把需要被点奇数次还是偶数次。这个是简单的，如果 n 不是 3 的倍数则强行解，如果 n 是 3 的倍数则钦定一个然后强行解即可。

现在每个火把有两个属性：亮还是灭，还要点奇数次还是偶数次。如果场上有本来就还需要点奇数次的火把是灭的，点。该操作是一步干掉一个奇数。

这时候场上没有还需要点奇数次的灭的火把了。如果此时所有火把都亮了自然很好。假设有一个火把没有亮，叫它中间火把，那么必然它还需要被点偶数次，所以左右两侧一定要给它贡献奇数次，所以左右必然有一个还需要点奇数次，假设是右侧，那么肯定是亮的。而由于右侧火把是亮的，需要被贡献偶数次，而中间火把又只能贡献偶数次，所以右侧的右侧必然需要贡献奇数次，因此必然也是亮的。于是四个火把（左、中、右、右的右）依次是未知、灭、亮、亮，且还需点的次数分别是偶、偶、奇、奇。

人类智慧一波，构造一个依次点亮中、右、中、右的右，那么状态会转化为未知（不变）、亮、亮、亮，且还需点的次数为偶、偶、偶、偶。发现使用四步干掉了两个奇数，结合前面的一步干掉一个奇数，总共次数不会超过 2n。

显然每次操作都是 O(1) 的，维护起来相当简单，因此本题时间复杂度 O(n)。

#include<iostream>
char s[1000001];
int a[1000001],b[1000001],e[1000001];
int main()
{
    std::cin.tie(0)->sync_with_stdio(0);
    int t;
    std::cin>>t;
    while(t--)
    {
        int n;
        std::cin>>n>>s;
        for(int i=0;i<n;i++)
            a[i]=s[i]^'0';
        if(n%3)
        {
            b[0]=0;
            for(int i=3;i<3*n;i+=3)
                b[i%n]=b[(i-3)%n]^a[(i-2)%n]^a[(i-1)%n];
            if(a[0]!=b[n-1]^b[0]^b[1]^1)
                for(int i=0;i<n;i++)
                    b[i]^=1;
        }
        else
        {
            b[0]=b[1]=b[2]=0;
            for(int i=3;i<n;i++)
                b[i]=b[i-3]^a[i-2]^a[i-1];
            if(a[0]!=b[n-1]^b[0]^b[1]^1)
                for(int i=0;i<n;i+=3)
                    b[i]^=1;
            bool f=1;
            for(int i=0;f&&i<n;i++)
                if(a[i]^b[i]^b[(i+n-1)%n]^b[(i+1)%n]!=1)
                    f=0;
            if(!f)
            {
                std::cout<<"0\n";
                continue;
            }
        }
        for(int i=0;i<n;i++)
            if(a[i]^b[i]^b[(i+n-1)%n]^b[(i+1)%n]!=1)
                return 1;
        int le=0;
        const auto p=[&](int x){a[x?x-1:n-1]^=1,a[x]^=1,a[x<n-1?x+1:0]^=1,b[x]^=1,e[le++]=x;};
        if(!a[0]&&b[0])
            p(0);
        if(!a[1]&&b[1])
            p(1);
        for(int _=0;_<3;_++)
            for(int i=0;i<n;i++)
                if(!a[(i+2)%n]&&b[(i+2)%n])
                    p((i+2)%n);
                else if(!a[i]&&!b[i]&&a[(i+1)%n]&&b[(i+1)%n]&&a[(i+2)%n]&&b[(i+2)%n])
                {
                    p(i),p((i+1)%n),p(i),p((i+2)%n);
                    for(int j=(i+3)%n;!a[j]&&b[j];j=j<n-1?j+1:0)
                        p(j);
                }
        std::cout<<le;
        for(int i=0;i<le;i++)
            std::cout<<" \n"[!i]<<e[i]+1;
        std::cout<<'\n';
    }
    return 0;
}