P9566 [SDCPC 2023] Difficult Constructive Problem

Lotus_Land · 2025-08-07 16:05:39 · 题解

设满足 1\leq i< n 且 s_i\not=s_{i+1} 的 i 的个数为 cnt。

注意到若一个字符不在开头或结尾，那么反转这个字符造成的 cnt 的变化一定是 0 或 2。若字符在开头或结尾，则会造成 cnt 奇偶性的变化，比较难以处理。所以枚举开头和结尾字符的 2^2 种情况，再对每种情况分别讨论。

对于给定的一个字符串，容易求出 cnt 的下限 l_1 和上限 l_2。如果 m 不在 [l_1,l_2] 这个范围内，或 l_1,l_2 的奇偶性与 m 不同，则为无解。

从前往后贪心，如果一个不确定的位置能填 \texttt{0}，那就填 \texttt{0}，如果不行，再尝试填 \texttt{1}，如果还不行，则为无解。

判断某个位置是否能填 \texttt{0} 或 \texttt{1}，只要重新计算 l_1 和 l_2，判断是否合法即可。

#include<bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define fir first
#define sec second
#define mkpr make_pair
#define lc(p) ((p)*2)
#define rc(p) ((p)*2+1)
using namespace std;
inline LL read() {
    LL x=0;
    bool t=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')t|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=getchar();
    return t?-x:x;
}
const int N=1000006;
int n,m;
string s,st;
int a[N];
int calc1(int l,int r) {
    if(l>r)return 0;
    return (s[l-1]!=s[r+1]);
}
int calc2(int l,int r) {
    if(l>r)return 0;
    if((r-l+1+(s[l-1]!=s[r+1]))&1)return r-l+2;
    return r-l+1;
}
bool check(int l,int r) {
    if((s[1]=='0'+l||s[1]=='?')&&(s[n]=='0'+r||s[n]=='?')) {
        s[1]='0'+l;
        s[n]='0'+r;
        for(int i=n-1; i>=1; i--) {
            if(s[i]=='?') {
                if(s[i+1]=='?')a[i]=a[i+1];
                else a[i]=i;
            } else a[i]=0;
        }
        int lim1=0,lim2=0;
        for(int i=1; i<=n; i++) {
            if(s[i]=='?'&&s[i-1]!='?') {
                lim1+=calc1(i,a[i]);
                lim2+=calc2(i,a[i]);
            }
            if(i!=1&&s[i]!='?'&&s[i-1]!='?'&&s[i]!=s[i-1]) {
                lim1++;
                lim2++;
            }
        }
        if(lim1>m||lim2<m)return 0;
        if((m-lim1)%2||(m-lim2)%2)return 0;
        for(int i=2; i<n; i++) {
            if(s[i]=='?') {
                int t1=lim1,t2=lim2;
                t1-=calc1(i,a[i]);
                t2-=calc2(i,a[i]);
                s[i]='0';
                t1+=calc1(i+1,a[i]);
                t2+=calc2(i+1,a[i]);
                if(s[i]!=s[i-1])t1++,t2++;
                if(s[i+1]!='?'&&s[i]!=s[i+1])t1++,t2++;
                if(m>=t1&&m<=t2&&(m-t1)%2==0&&(m-t2)%2==0) {
                    lim1=t1;
                    lim2=t2;
                } else {
                    t1=lim1,t2=lim2;
                    t1-=calc1(i,a[i]);
                    t2-=calc2(i,a[i]);
                    s[i]='1';
                    t1+=calc1(i+1,a[i]);
                    t2+=calc2(i+1,a[i]);
                    if(s[i]!=s[i-1])t1++,t2++;
                    if(s[i+1]!='?'&&s[i]!=s[i+1])t1++,t2++;
                    if(m>=t1&&m<=t2&&(m-t1)%2==0&&(m-t2)%2==0) {
                        lim1=t1;
                        lim2=t2;
                    } else {
                        return 0;
                    }
                }
            }
        }
        return 1;
    }
    return 0;
}
int T;
int main() {
    cin>>T;
    while(T--) {
        cin>>n>>m>>st;
        st=" "+st;
        bool flg=0;
        for(int i=0; i<=1; i++) {
            for(int j=0; j<=1; j++) {
                s=st;
                if(check(i,j)) {
                    cout<<s.substr(1,n);
                    flg=1;
                    break;
                }
            }
            if(flg)break;
        }
        if(!flg)cout<<"Impossible";
        cout<<"\n";
    }
    return 0;
}