题解：CF2264D Dr. Agos's Dark Mode

· · 题解

搞笑题，但是我 vp 的时候用人脑做，做了半个小时意识到可以打表，过完 D 只剩五分钟了，这波唐了。

注意到只有 3 个位置能是 1 于是直接打表。

:::success[code]

namespace my{
    const int N=2e5+5,inf=1000000000;template<typename T>pref T Min(T x,T y){return x<y?x:y;}template<typename T>pref T Max(T x,T y){return x>y?x:y;}template<typename T>pref T Abs(T x){return x<0?-x:x;}
    int n,pw[N];
    int a[N],b[N],mn=inf;
    pref void init(){
        pw[0]=1;up(i,1,N-1)pw[i]=(pw[i-1]+pw[i-1])%3;
    }
    pref int f(){
        int ret=0;
        up(r,1,n){
            int sum=0;
            dn(i,r,1){
                sum=(sum+a[i]*pw[r-i])%3;
                if(sum==0)ret++;
            }
        }
        return ret;
    }
    pref void dfs(int x,int t){
        if(x>n){
            int k=f();
            if(k<=mn){
                up(i,1,n)b[i]=a[i];
                mn=k;
            }
            return ;
        }
        if(t==3)a[x]=0,dfs(x+1,t);
        else {
            a[x]=0;
            dfs(x+1,t);
            a[x]=1;
            dfs(x+1,t+1);   
            a[x]=0;
        }
    }
    pref void SOLVE(){
        for(n=7;n<=50;n++){
            mn=inf,dfs(1,0);
            up(i,1,n)if(b[i])cout<<i<<' ';
            cout<<'\n';
        }
    }
}

:::

为了方便，我找的是字典序最大的。

输出是。

1 4 6
1 4 6
1 4 6
1 5 9
1 5 9
1 5 9
1 6 10
1 6 10
1 6 10
1 7 13
1 7 13
1 7 13
1 8 14
1 8 14
1 8 14
1 9 17
1 9 17
1 9 17
1 10 18
1 10 18
1 10 18
1 11 21
1 11 21
1 11 21
1 12 22
1 12 22
1 12 22
1 13 25
1 13 25
1 13 25
1 14 26
1 14 26
1 14 26
1 15 29
1 15 29
1 15 29
1 16 30
1 16 30
1 16 30
1 17 33
1 17 33
1 17 33
1 18 34
1 18 34

注意到三个三个是一样的，每三个之间的差有两种方式交替，分别是 +0 +1 +1 和 +0 +1 +3 两种，直接带着地推就行了。其实应该有式子，但是我非常地愚蠢。

容易发现这个结论其实就是让这三个一尽量平均的分布。

这个东西感性理解是对的。

稍微严谨一点。

你发现含有一个 1 的区间无论怎样都是合法区间。有两个 1 的时候，如果，它们两个位置 2^{pos} \bmod 3 分别是 1,2 则不合法，所以我们尽量放在三个 2^{pos} \bmod 3 为 1 的位置上，这样只有含三个 1 的区间才是不合法的，于是上面那个是对的。

:::success[code]

namespace my{
    const int N=2e5+5,inf=1000000000;template<typename T>pref T Min(T x,T y){return x<y?x:y;}template<typename T>pref T Max(T x,T y){return x>y?x:y;}template<typename T>pref T Abs(T x){return x<0?-x:x;}
    int a[N][2];
    pref void init(){
        a[7][0]=4,a[7][1]=6;
        for(int i=7;i<=N-1;i+=6){
            a[i+1][0]=a[i+2][0]=a[i][0];
            a[i+1][1]=a[i+2][1]=a[i][1];
            a[i+3][0]=a[i+1][0]+1;
            a[i+3][1]=a[i+1][1]+3;
            a[i+4][0]=a[i+5][0]=a[i+3][0];
            a[i+4][1]=a[i+5][1]=a[i+3][1];
            a[i+6][0]=a[i+4][0]+1;
            a[i+6][1]=a[i+4][1]+1;
        }
    }
    pref void SOLVE(){
        int n;cin>>n;
        if(n==1)return cout<<"1\n",void();
        if(n==2)return cout<<"11\n",void();
        if(n==3)return cout<<"101\n",void();
        if(n==4)return cout<<"1010\n",void();
        if(n==5)return cout<<"10101\n",void();
        if(n==6)return cout<<"101010\n",void();
        cout<<"1";
        up(i,2,n){
            if(i==a[n][0])cout<<"1";
            else if(i==a[n][1])cout<<"1";
            else cout<<"0";
        }
        cout<<'\n';
    }
}

:::