@TOC

前言

传送门 :
(那天人们又想起了被蓝名支配的恐惧)

A.Red Versus Blue

题意 :
给定你$n,r,b$ 表示 字符长度,$R$的数量,$B$的数量

问使得 连续$R$最少的方案

思路 :
显然,我们一开始都是想到的分组,也就是将$R$分成$B+1$组

但是很多情况我们都无法完全分组,因此我们还需要将剩下的余数塞回我们已经处理的分组之中

然后输出即可

code

const int N = 110;

int n,R,B;

int a[N];
void solve(){
    cin>>n>>R>>B;

    int tail = R/(B+1);
    int remain = R%(B+1);

    for(int i=1;i<=B+1;i ++ ) a[i] = tail;
    for(int i=1;i<=remain;i++) a[i]++;

//  cout<<a[1]<<" "<<a[2]<<endl;

    for(int i=1;i<=B+1;i++){
        for(int j=1;j<=a[i];j ++ )cout<<"R";
        if(i!=B+1)cout<<"B";
    }
    cout<<endl;
}

B. Bit Flipping

题意 :(屎题 真难写)

给定$n,k$表示字符串长度和操作次数

操作描述如下 :

对于给定的$01$字符串,你可以选择一个$i$使得当前位置的数不变,其余翻转

询问操作完成之后的 最大字符串和各个位置的次数

思路 :

这种取反的题,一般都和$2$有关,因为来回两次回到原位

当然对于这种题,我们一般考虑 将多余的操作放到最后一位来回操作

显然
- 如果是奇数的话,我们最后将多余的$1$对最后一位操作,前面的操作都不影响最后一位,当然如果不多于的话,那么最后一位必然取反,因为前面已经有$0$把操作数吃掉了
- 如果是偶数的话,不管怎么操作,最后一位仍然不会变

因此我们只考虑$0-(n-1)$的位置

如果是奇数,我们先对所有数取反(相当于在最后一位操作)

然后转换为偶数的形式,我们再考虑偶数怎么操作

显然我们只需要从高位到地位将所有$0$变为$1$ 即可

因为对于每次操作我们都可以把$0$固定住,然后让前面的$1$全部变为$0$,然后为了保证操作的完全利用,我们在让下次碰到$0$的时候变成$1$即可

总之总结一个字 : 贪心即可

code

void solve(){
    int n,k;cin>>n>>k;
    string s;cin>>s;

    vector<int> ans(n);

    if(k&1){
        for(auto &c : s){
            if(c == '0') c = '1';
            else c = '0';
        }
    }

    for(int i=0;i<n-1;i++){
        if(k>0 && s[i] =='0'){
            ans[i]++;
            s[i] ='1';
            k--;
        }
    }

    ans[n-1]+=k;
    if(k%2){
        if(s.back() == '0') s.back() = '1';
         else s.back() = '0';
    }

    cout<<s<<endl;
    for(auto x  : ans)cout<<x<<" ";
    cout<<endl;


}
int main(){
    int t;cin>>t;while(t--)
    solve();
    return 0 ;
}

C Line Empire

$WizCode$大佬的图,写的很详细了我就不乱添足了

code

const int N = 2e5+10;

ll sum[N];
ll x[N];

void solve(){
    int n;cin>>n;
    ll a,b;cin>>a>>b;

    for(int i=1;i<=n;i++) cin>>x[i];

    sum[n+1] = 0 ;
    for(int i=n;i>=1;i --) sum[i]  = x[i]+sum[i+1];

    ll res = 1e18;
    ll pre = 0;
    ll t ;

    for(int i =0 ;i<=n;i++){
        if(i){
            pre += a*(x[i] - x[i-1]) + b*(x[i] -x[i-1]);
        }
        t = b*(sum[i+1] - x[i]*(n-i));
        res = min(res,pre+t);
    }
    cout<<res<<endl;

}

D.(完全不会,蹲大佬的题解)