题解：P16444 [XJTUPC 2026] Used to be

· · 题解

考虑把这个东西竖着看。你会发现问号形成了一堆竖着的区间，我们不去管那些头尾相同的区间，然后你会发现我们实际上就是要在所有保留的区间里面找一个位作为翻转的位置。

于是这个问题就变成了：

然后你会发现这是经典贪心。

#include <bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define inf INT_MAX
#define linf LLONG_MAX
#define ninf INT_MIN
#define nlinf LLONG_MIN
#define mod 998244353
#define lwbd lower_bound
#define upbd upper_bound
//#define range
using namespace std;
void read(int &x){
    cin >> x;
    return;
}
void readll(ll &x){
    cin >> x;
    return;
}void readdb(db &x){
    cin >> x;
    return;
}

struct node{
    ll l, r, c;
    bool operator < (const node& oth)const{
        return l < oth.l;
    }
};

ll n, m , t, f[1000005];
vector<string> s;
vector<node> vec;
string res;

void solve(){
    cin >> n >> m;
    s.assign(n, "");
    vec.clear();
    res.assign(m, '0');
    for(int i = 0; i < n; i++){
        cin >> s[i];
        f[i] = -1;
    }

    for(int j = 0; j < m; j++){
        vector<pair<ll, char> > v;
        for(int i = 0; i < n; i++){
            if(s[i][j] != '?'){
                v.push_back({i + 1, s[i][j]});
            }
        }
        if(v.empty()){
            res[j] = '0';
        }
        else{
            res[j] = v[0].second;
            for(int k = 0; k + 1 < v.size(); k++){
                if(v[k].second != v[k + 1].second){
                    vec.push_back({v[k].first, v[k + 1].first - 1, j});
                }
            }
        }
    }

    if(vec.size() > n - 1){
        cout << "No"<< endl;
        return;
    }

    sort(vec.begin(), vec.end());

    priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > > pq;
    ll cur = 0;
    bool ok=true;

    for(int i = 1; i <= n - 1; i++){
        while(cur < vec.size() && vec[cur].l == i){
            pq.push({vec[cur].r, vec[cur].c});
            cur++;
        }
        while(!pq.empty() && pq.top().first < i){
            ok = false;
            break;
        }
        if(!ok){
            break;
        }
        if(!pq.empty()){
            f[i] = pq.top().second;
            pq.pop();
        }
    }

    if(!ok || cur < vec.size() || !pq.empty()){
        cout << "No" << endl;
        return;
    }

    cout << "Yes" << endl;
    cout<< res << endl;
    for(int i = 1; i <= n - 1; i++){
        ll p = f[i];
        if(p != -1){
            res[p] = (res[p] == '0' ? '1' : '0');
        }
        cout << res << endl;
    }
}

//如果再忘记把题目给的1~n变为0~n-1自罚20仰卧起坐
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if(cin >> t){
        while(t--){
            solve();
        }
    }
    return (0 - 0);
}