daily 2

CF 1200D

void solve(){
    auto add=[&](int x,int y,int w){
        mp[max(x,1)][max(y,1)]+=w;
    };
    int n,k;
    cin>>n>>k;
    vector<string>a(n+1);
    for(int i=1;i<=n;++i){
        cin>>a[i];
        a[i]=')'+a[i];
    }
    int ans=0;
    //get number of shit on rows
    for(int i=1;i<=n;++i){
        int l=0,r=0;
        for(int j=1;j<=n;++j){
            if(a[i][j]!='B')continue;
            if(l==0){
                l=j;
            }
            r=j;
        }
        if(r==0){
            ++ans;
            continue;
        }
        if(r-l+1>k){
            continue;
        }
        add(i-k+1,r-k+1,1);
        add(i+1,r-k+1,-1);
        add(i-k+1,l+1,-1);
        add(i+1,l+1,1);
    }
    for(int j=1;j<=n;++j){
        int u=0,d=0;
        for(int i=1;i<=n;++i){
            if(a[i][j]!='B')continue;
            if(u==0){
                u=i;
            }
            d=i;
        }
        if(d==0){
            ++ans;
            continue;
        }
        if(d-u+1>k){
            continue;
        }
        add(d-k+1,j-k+1,1);
        add(d-k+1,j+1,-1);
        add(u+1,j-k+1,-1);
        add(u+1,j+1,1);
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            mp[i][j]+=mp[i-1][j];
        }
    }
    int cur_max=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            mp[i][j]+=mp[i][j-1];
            cur_max=max(cur_max,mp[i][j]);
        }
    }
    cout<<ans+cur_max<<'\n';
    return;
}

CF 1328D

int main(){
    // freopen("/Users/yanxinxiang/code/Algorithm/in","r",stdin);
    // freopen("/Users/yanxinxiang/code/Algorithm/out","w",stdout);
    int q,n;
    cin>>q;

    while(q--){
        cin>>n;
        for(int i=1;i<=n;++i)cin>>a[i];
        a[n+1]=a[1];
        bool f1=false,f2=false;
        int x=-1;
        for(int i=1;i<=n;++i){
            if(a[i]==a[i+1]){
                f1=true;
                x=i;
            }else{
                f2=true;
            }
        }
        if(!f2){
            cout<<1<<'\n';
            for(int i=1;i<=n;++i){
                cout<<1<<" \n"[i==n];
            }
        }
        else {
            if(n%2==0){
                cout<<2<<'\n';
                for(int i=1;i<=n;++i){
                    cout<<((i%2)?1:2)<<" \n"[i==n];
                }
            }else if(f1){//至少有一对相邻的相同，断开后交替染色
                cout<<2<<'\n';
                for(int i=1;i<=n;++i){
                    c[(x+i-1)%n+1]=i&1;
                }
                for(int i=1;i<=n;++i){
                    cout<<c[i]+1<<" \n"[i==n];
                }
            }else{
                cout<<3<<'\n';
                for(int i=1;i<=n-1;++i){
                    cout<<((i&1)+1)<<' ';
                }
                cout<<3<<'\n';
            }
        }
    }
    return 0;
}