P14265 [ROI 2015 Day1] 企鹅研究

把一个长度为 \(x\) 的连续段变成一个数 \(x\)，这样就得到了一个序列，每次可以选择连续的 \(3\) 个数 \(a_i,a_{i+1},a_{i+2}\)（或 \(2\) 个），把祂们合成一个数 \(a_i+a_{i+2}-a_{i-1}\)，代价为 \(a_i\)，可以操作无限次，求最小代价让序列长度 \(\le k\)。
直接反悔贪心，输出方案可以用树状数组维护每个数被反转了几次。
发现边上的数（选两个）很烦，考虑如何处理。
可以分类：左边删/不删和右边删/不删，合起来 \(4\) 中情况，都尝试一遍，取最小值。

代码

有点长。

/*
Luogu P14265 [ROI 2015 Day1] 企鹅研究
2026-03-13
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
const int maxn=200010,inf=1000000000;
int n,k,a[maxn],b[maxn],sy[maxn],cnt,len,ans2;
struct node{int l,r,z,real_l,real_r;}l[maxn];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q2;
bool used[maxn];
class BIT{
private:
    int t[maxn];
    int low(int u){return u&-u;}
public:
    void up(int u,int add){u++;while(u<=cnt+1) t[u]+=add,u+=low(u);}
    int query(int u){u++;int ans=0;while(u) ans+=t[u],u-=low(u);return ans;}
    void clear(){for(int i=1;i<=cnt+1;i++) t[i]=0;}
    void fz(BIT&t2){for(int i=1;i<=cnt+1;i++) t[i]=t2.t[i];}
}t,t2;
void work1(){
    if(k<=0){ans2=0;return ;}
    while(!q2.empty()) q2.pop();
    for(int i=2;i<cnt;i++) q2.push({a[i],i});
    int ans=0;
    while(k>0){
        if(q2.empty()){ans2=inf;return ;}
        int u,z;
        z=q2.top().first,u=q2.top().second,q2.pop();
        if(used[u]) continue;
        ans+=z;
        t2.up(l[u].real_l,1);
        if(l[u].real_r<cnt) t2.up(l[u].real_r+1,-1);
        l[u].z=-l[u].z;
        if(l[u].l){
            k--;
            used[l[u].l]=1;
            l[u].real_l=l[l[u].l].real_l;
            l[u].z+=l[l[u].l].z;
            l[u].l=l[l[u].l].l;
            l[l[u].l].r=u;
        }
        if(l[u].r<=cnt){
            k--;
            used[l[u].r]=1;
            l[u].real_r=l[l[u].r].real_r;
            l[u].z+=l[l[u].r].z;
            l[u].r=l[l[u].r].r;
            l[l[u].r].l=u;
        }
        if(l[u].l&&l[u].r<=cnt) q2.push({l[u].z,u});
    }
    ans2=ans;
}
void work2(){
    if(k<=0){ans2=0;return ;}
    if(k<1){ans2=inf;return ;}
    while(!q2.empty()) q2.pop();
    for(int i=2;i<cnt;i++) q2.push({a[i],i});
    int ans=0;
    ans+=a[1];
    t2.up(1,1);
    t2.up(2,-1);
    used[l[1].r]=1;
    l[1].z=l[l[1].r].z-l[1].z;
    l[1].real_r=l[1].r;
    l[1].r=l[l[1].r].r;
    l[l[1].r].l=1;
    k--;
    while(k>0){
        if(q2.empty()){ans2=inf;return ;}
        int u,z;
        z=q2.top().first,u=q2.top().second,q2.pop();
        if(used[u]) continue;
        ans+=z;
        t2.up(l[u].real_l,1);
        if(l[u].real_r<cnt) t2.up(l[u].real_r+1,-1);
        l[u].z=-l[u].z;
        if(l[u].l){
            k--;
            used[l[u].l]=1;
            l[u].real_l=l[l[u].l].real_l;
            l[u].z+=l[l[u].l].z;
            l[u].l=l[l[u].l].l;
            l[l[u].l].r=u;
        }
        if(l[u].r<=cnt){
            k--;
            used[l[u].r]=1;
            l[u].real_r=l[l[u].r].real_r;
            l[u].z+=l[l[u].r].z;
            l[u].r=l[l[u].r].r;
            l[l[u].r].l=u;
        }
        if(l[u].l&&l[u].r<=cnt) q2.push({l[u].z,u});
    }
    ans2=ans;
}
void work3(){
    if(k<=0){ans2=0;return ;}
    if(k<1){ans2=inf;return ;}
    while(!q2.empty()) q2.pop();
    for(int i=2;i<cnt;i++) q2.push({a[i],i});
    int ans=0;
    ans+=a[cnt];
    t2.up(cnt,1);
    used[l[cnt].l]=1;
    l[cnt].z=l[l[cnt].l].z-l[cnt].z;
    l[cnt].real_l=l[cnt].l;
    l[cnt].l=l[l[cnt].l].l;
    l[l[cnt].l].r=cnt;
    k--;
    while(k>0){
        if(q2.empty()){ans2=inf;return ;}
        int u,z;
        z=q2.top().first,u=q2.top().second,q2.pop();
        if(used[u]) continue;
        ans+=z;
        t2.up(l[u].real_l,1);
        if(l[u].real_r<cnt) t2.up(l[u].real_r+1,-1);
        l[u].z=-l[u].z;
        if(l[u].l){
            k--;
            used[l[u].l]=1;
            l[u].real_l=l[l[u].l].real_l;
            l[u].z+=l[l[u].l].z;
            l[u].l=l[l[u].l].l;
            l[l[u].l].r=u;
        }
        if(l[u].r<=cnt){
            k--;
            used[l[u].r]=1;
            l[u].real_r=l[l[u].r].real_r;
            l[u].z+=l[l[u].r].z;
            l[u].r=l[l[u].r].r;
            l[l[u].r].l=u;
        }
        if(l[u].l&&l[u].r<=cnt) q2.push({l[u].z,u});
    }
    ans2=ans;
}
void work4(){
    if(k<=0){ans2=0;return ;}
    if(k<2){ans2=inf;return ;}
    while(!q2.empty()) q2.pop();
    for(int i=2;i<cnt;i++) q2.push({a[i],i});
    int ans=0;
    ans+=a[1];
    t2.up(1,1);
    t2.up(2,-1);
    used[l[1].r]=1;
    l[1].z=l[l[1].r].z-l[1].z;
    l[1].real_r=l[1].r;
    l[1].r=l[l[1].r].r;
    l[l[1].r].l=1;
    ans+=a[cnt];
    t2.up(cnt,1);
    used[l[cnt].l]=1;
    l[cnt].z=l[l[cnt].l].z-l[cnt].z;
    l[cnt].real_l=l[cnt].l;
    l[cnt].l=l[l[cnt].l].l;
    l[l[cnt].l].r=cnt;
    k--;
    k--;
    while(k>0){
        if(q2.empty()){ans2=inf;return ;}
        int u,z;
        z=q2.top().first,u=q2.top().second,q2.pop();
        if(used[u]) continue;
        ans+=z;
        t2.up(l[u].real_l,1);
        if(l[u].real_r<cnt) t2.up(l[u].real_r+1,-1);
        l[u].z=-l[u].z;
        if(l[u].l){
            k--;
            used[l[u].l]=1;
            l[u].real_l=l[l[u].l].real_l;
            l[u].z+=l[l[u].l].z;
            l[u].l=l[l[u].l].l;
            l[l[u].l].r=u;
        }
        if(l[u].r<=cnt){
            k--;
            used[l[u].r]=1;
            l[u].real_r=l[l[u].r].real_r;
            l[u].z+=l[l[u].r].z;
            l[u].r=l[l[u].r].r;
            l[l[u].r].l=u;
        }
        if(l[u].l&&l[u].r<=cnt) q2.push({l[u].z,u});
    }
    ans2=ans;
}
void solve(){
    t.clear(),t2.clear();
    read(n,k);
    for(int i=1;i<=n;i++){
        char x;read(x);
        b[i]=x-'0';
    }
    cnt=0,len=1;
    sy[1]=1;
    for(int i=2;i<=n;i++){
        if(b[i]!=b[i-1]) a[++cnt]=len,len=0;
        sy[i]=cnt+1;
        len++;
    }
    int yk=k,ans;
    a[++cnt]=len;k=cnt-yk;
    for(int i=1;i<=cnt;i++) l[i].l=i-1,l[i].r=i+1,l[i].z=a[i],used[i]=0,l[i].real_l=l[i].real_r=i;
    work1();k=cnt-yk;
    ans=ans2;
    t.fz(t2);
    t2.clear();
    for(int i=1;i<=cnt;i++) l[i].l=i-1,l[i].r=i+1,l[i].z=a[i],used[i]=0,l[i].real_l=l[i].real_r=i;
    work2();k=cnt-yk;
    if(ans>ans2) t.fz(t2),ans=ans2;
    t2.clear();
    for(int i=1;i<=cnt;i++) l[i].l=i-1,l[i].r=i+1,l[i].z=a[i],used[i]=0,l[i].real_l=l[i].real_r=i;
    work3();k=cnt-yk;
    if(ans>ans2) t.fz(t2),ans=ans2;
    t2.clear();
    for(int i=1;i<=cnt;i++) l[i].l=i-1,l[i].r=i+1,l[i].z=a[i],used[i]=0,l[i].real_l=l[i].real_r=i;
    work4();
    if(ans>ans2) t.fz(t2),ans=ans2;
    t2.clear();
    for(int i=1;i<=n;i++){
        if(t.query(sy[i])&1) write(!b[i]);
        else write(b[i]);
    }
    write("\n");
}
signed main(){
    int T;read(T);
    while(T--) solve();
    return 0;
}