题解：CF1852D Miriany and Matchstick

happybob · 2024-08-22 15:38:47 · 题解

不妨假设我们要求字典序最小的符合条件的构造。

一个想法是每次能填 A 就填 A，不然填 B。用 DP 记录一段后缀所有能取到的结果。复杂度 O(n^2)。

一个猜测是如果后缀能取到的最小值是 l，最大值是 r，那么 [l,r] 都能取到。但是很遗憾这个是假的，考虑第一行为 AAA，对第二行构造，至少结果为 0，至多为 4。但是无论如何 1 都构造不出来。

于是猜测另一个结论，对于 [l,r] 来说，只有 l+1 和 r-1 可能取不到。手玩若干个发现很对。然后写一个基于这个结论的 DP 就可以通过此题。复杂度线性。

代码：

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

const int N=2e5+5;

int t,n,k;
string s;
set<int> st[N][2];

inline bool check(string t)
{
    int res=0;
    for(int i=1;i<n;i++) res+=(t[i]!=t[i+1]);
    for(int i=1;i<n;i++) res+=(s[i]!=s[i+1])+(s[i]!=t[i]);
    res+=(s[n]!=t[n]);
    return (res==k);
}

int main()
{
    //freopen("fill.in","r",stdin);
    //freopen("fill.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        cin>>s;
        s=" "+s;
        int cnt=0;
        for(int i=1;i<n;i++) cnt+=(s[i]!=s[i+1]);
        if(cnt>k)
        {
            cout<<"NO\n";
            continue;
        }
        for(int i=1;i<=n;i++)
        {
            st[i][0].clear(),st[i][1].clear();
        }
        st[n][0].insert(s[n]!='A');
        st[n][1].insert(s[n]!='B');
        for(int i=n-1;i>=1;i--)
        {
            for(auto&j:st[i+1][0])
            {
                st[i][0].insert(j+(s[i]!=s[i+1])+(s[i]!='A'));
                st[i][1].insert(j+(s[i]!=s[i+1])+1+(s[i]!='B'));
            }
            for(auto&j:st[i+1][1])
            {
                st[i][0].insert(j+(s[i]!=s[i+1])+1+(s[i]!='A'));
                st[i][1].insert(j+(s[i]!=s[i+1])+(s[i]!='B'));
            }
            set<int> rs=st[i][0],rs2=st[i][1];
            st[i][0].clear(),st[i][1].clear();
            if(rs.size()>=1) st[i][0].insert(*rs.begin()),st[i][0].insert(*rs.rbegin());
            if(rs.size()>=2) st[i][0].insert(*(next(rs.begin()))),st[i][0].insert(*(prev(prev(rs.end()))));
            if(rs2.size()>=1) st[i][1].insert(*rs2.begin()),st[i][1].insert(*rs2.rbegin());
            if(rs2.size()>=2) st[i][1].insert(*(next(rs2.begin()))),st[i][1].insert(*(prev(prev(rs2.end()))));
        }
        int x=0;
        string ans=" ";
        for(int i=1;i<n;i++)
        {
            if(i>1) x+=(s[i]!=s[i-1])+(ans[i-1]!=s[i-1]);
            if(i>2) x+=(ans[i-1]!=ans[i-2]);
            int nv=k-x-(i==1?0:(ans[i-1]=='B'));
            // check if can be a
            int l=*st[i][0].begin(),r=*st[i][0].rbegin();
            if((nv>l+1&&nv<r-1)||(st[i][0].count(nv)))
            {
                ans+="A";
            }
            else ans+="B";
        }
        if(check(ans+"A")) 
        {
            cout<<"YES\n";
            string res=ans+"A";
            cout<<res.substr(1)<<"\n";
        }
        else if(check(ans+"B"))
        {
            cout<<"YES\n";
            string res=ans+"B";
            cout<<res.substr(1)<<"\n";
        }
        else cout<<"NO\n";
    }
    return 0;
}