「LAOI-4」Colors 题解

Anemones · 2024-02-05 16:33:08 · 题解

结论：操作二次后字符串不会继续被改变。

• 若 A_{i-1}=A_{i+1}，则称 A_i 为 「可消除的」。

这句话我们可以把它理解成 \texttt{121} 结构，那么一轮消除了所有 \texttt{121} 结构后，剩下的便是形似 \texttt{111} 这样的结构，\texttt{111} 这样结构再经过消除就没有了。

//luogu uid:YuZeAn 736184
#include<bits/stdc++.h>
#include<ext/rope>
using namespace __gnu_cxx;
#define dbg puts("-------------------DWT AK IOI--------------------")
#define int long long
#define mod 998244353
#define end putchar('\n')
#define sp putchar(' ')
using namespace std;
inline int read(){
    char c=getchar(),f=0;int t=0;
    for(;c<'0'||c>'9';c=getchar()) if(!(c^45)) f=1;
    for(;c>='0'&&c<='9';c=getchar()) t=(t<<1)+(t<<3)+(c^48);
    return f?-t:t;
}
inline void write(int x){
    static int t[25];int tp=0;
    if(x==0) return(void)(putchar('0'));else if(x<0) putchar('-'),x=-x;
    while(x) t[tp++]=x%10,x/=10;
    while(tp--) putchar(t[tp]+48);
}
signed main(){
    int T=read(),id=read();
    while(T--){
        int n=read(),k=read();
        string s,s1;
        cin>>s;
        k=min(2ll,k);
        if(k==0||n<=2){
            cout<<s<<endl;
            continue;
        }
        s1=s[0];
        for(int i=0;i<n-2;i++){
            if(s[i]!=s[i+2]) s1+=s[i+1];
        }
        //if(n-2!=0) s1+=s[n-2];
        if(n-1!=0)s1+=s[n-1];
        //cout<<s1<<endl;
        if(k==2){
            cout<<s1[0];
            for(int i=0;i<s1.size()-2;i++){
                if(s1[i]!=s1[i+2]) cout<<s1[i+1];
            }
            //if(s1.size()-2!=0) cout<<s1[n-2];
            if(s1.size()-1!=0) cout<<s1[s1.size()-1];
            cout<<endl;
        }
        else cout<<s1<<endl;
    }
    return 0;
}