题解：AT_arc219_e [ARC219E] Equal Distribution

· · 题解

感觉是经典 trick 啊，还是做得慢了。

二维问题先考虑一维怎么做，一维问题就是给你一个环，每个点有 0,1 点权，然后你要找到一个长度为 2hw 的区间，使得这个区间恰好有 hw 个 1，你发现一定会有解，所以直接枚举右端点找到这个区间即可。

那么对于这个二维问题，我们只需要构造一个路径，使得其首尾相接成环，并且任意一个区间的点拿出来都是连通的就可以转化为一维问题，然后你发现这个玩意用脚构造，于是做完了。

#include<bits/stdc++.h>
using namespace std;

const int N=4000010;
vector<char>s[N>>1],ans[N>>1];
int x[N],y[N],val[N],tot;
void add(int i,int j){
    tot++;
    x[tot]=i;y[tot]=j;
    val[tot]=(s[i][j]=='o');
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0); 
    int T;
    cin>>T;
    while(T--){
        int h,w;
        cin>>h>>w;
        int n=2*h,m=2*w;
        for(int i=1;i<=n;i++){
            string t;
            cin>>t;
            s[i].resize(m+1);
            ans[i].resize(m+1);
            for(int j=1;j<=m;j++)
                s[i][j]=t[j-1]; 
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                ans[i][j]='B';
        tot=0;
        for(int i=1;i<=m;i++)add(1,i);
        for(int i=2;i<=n;i++)add(i,m);
        for(int i=n;i>=2;i--){
            if((n-i)&1){
                for(int j=1;j<m;j++)add(i,j);
            }else{
                for(int j=m-1;j>=1;j--)add(i,j);
            }
        }
        for(int i=1;i<=tot;i++)val[i]+=val[i-1];
        for(int i=2*h*w;i<=tot;i++){
            if(val[i]-val[i-2*h*w]==h*w){
                for(int j=i-2*h*w+1;j<=i;j++)
                    ans[x[j]][y[j]]='A';
                break;
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)cout<<ans[i][j];
            cout<<'\n';
        }
        for(int i=1;i<=n;i++){
            s[i].clear();ans[i].clear();
            s[i].shrink_to_fit();
            ans[i].shrink_to_fit();
        }
    }

    return 0;
}