题解：P16444 [XJTUPC 2026] Used to be

lizihan250 · 2026-05-11 11:35:16 · 题解

给定 n 个 01 串，部分位置缺失。填充缺失位置使得相邻两字符串至多一位不同，或报告无解。

考察每一列。对于每一段连续的问号，若其某一段与边界连接，或者其两端连接相同数字，则一定可以填充数字使得这一串问号中不存在相邻两行的数字不同。否则，必定存在至少一处相邻两行不同。设这段问号串位于第 l 行至第 r 行，则 [l-1,r] 中必有一行在该列上与下一行不同。这样，我们就得到了若干区间，为每个区间选择不重的可用点使得其在该行翻转。这就是经典的区间选点问题。

考虑将所有区间按右端点排序，然后从左往右找到第一个没有被选用的点，将该点给这个区间。由于本题中所有区间的长度之和不超过 nm，所以这部分可以直接暴力扫描。排序使用桶排，总复杂度 O(nm)。

::::success[参考实现]

#include<bits/stdc++.h>
using namespace std;
const int Maxs=1000000;
int T,n,m,k;
int cnt[Maxs+10];
string mp[Maxs+10];
vector<pair<int,int> > nums[Maxs+10];
bitset<Maxs+10> vis;
void solve()
{
    k=0;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>mp[i];
    for(int i=0;i+1<n;i++)
        cnt[i]=0,vis[i]=false,nums[i].clear();
    for(int j=0;j<m;j++)
    {
        int p=-1,l=-1;
        for(int i=0;i+1<n;i++)
        {
            if(mp[i][j]!='?') l=i;
            if(mp[i][j]!='?'&&mp[i+1][j]!='?') {if(mp[i][j]!=mp[i+1][j]) cnt[i]++;}
            else if(mp[i][j]!='?'&&mp[i+1][j]=='?') p=i;
            else if(mp[i][j]=='?'&&mp[i+1][j]!='?')
            {
                if(p!=-1&&mp[p][j]!=mp[i+1][j])
                {
                    nums[i].push_back({p,j});
                    p=-1;
                }
                else
                {
                    for(int x=p+1;x<=i;x++)
                        mp[x][j]=mp[i+1][j];
                    p=-1;
                }
            }
        }
        if(l==-1)
        {
            if(mp[n-1][j]=='?') mp[n-1][j]='0';
            for(int i=0;i+1<n;i++)
                mp[i][j]=mp[n-1][j];
        }
        if(p!=-1)
        {
            for(int i=l+1;i<n;i++)
                mp[i][j]=mp[l][j];
        }
    }
    for(int i=0;i+1<n;i++)
    {
        if(cnt[i]>1)
        {
            cout<<"No\n";
            return;
        }
        vis[i]=cnt[i];
    }
    for(int i=0,c;i+1<n;i++)
    {
        for(pair<int,int> nw:nums[i])
        {
            c=-1;
            for(int j=nw.first;j<=i;j++)
                if(!vis[j])
                {
                    vis[j]=true;
                    c=j;
                    break;
                }
            if(c==-1)
            {
                cout<<"No\n";
                return;
            }
            for(int j=nw.first;j<=c;j++)
                mp[j][nw.second]=mp[nw.first][nw.second];
            for(int j=c+1;j<=i;j++)
                mp[j][nw.second]=mp[nw.first][nw.second]^1;
        }
    }
    cout<<"Yes\n";
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
            cout<<mp[i][j];
        cout<<"\n";
    }
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>T;
    while(T--)
        solve();
    return 0;
}

::::