A. Red Versus Blue

解法1:(思维题)

思路分析:由题目可知,R的数量一定大于B的数量.
即题目本意为：numB个B字符将整个只含有R和B字符的字符串分成numB+1个部分
求将总字符串分成num[B]+1个部分的所有方案中，
对于每一个方案中的(每个部分中R字符数量的最大值)进行比较
输出比较所得的最小值

时间复杂度:O(b+1)
代码描述:

#include<bits/stdc++.h>
using namespace std;
int t,n,r,b;
const int N=110;
int q[N];
void solve(){
    memset(q,0,sizeof q);
    cin>>n>>r>>b;
    int mark=b+1;
    int remain=r/(mark);
    int mod=r%mark;
    for(int i=1;i<=mark;i++)q[i]+=remain;
    for(int i=1;i<=mod;i++)q[i]++;
    for(int i=1;i<=mark;i++){
    for(int j=1;j<=q[i];j++)cout<<'R';
        if(i!=mark)cout<<'B';
    }
    cout<<endl;
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

B. Bit Flipping

解法1:(思维题)

思路分析:由题目可知,设每个点改变的值为f,总的改变次数为k,当前可支配的改变次数为num则
对于每个点来说，其位置的字符是否翻转取决于(k-f)的数值为奇数还是偶数
若(k-f)为odd，则此位置上的字符发生翻转
若(k-f)为even,则此位置上的字符不发生翻转
(ps:每一次翻转使得num的数值减1)
根据贪心的思想，为了使得经过k次改变后的字符串在所有翻转可能的
字符串中字典序最大，则应该从左到右遍历在可以使用的改变次数num>0的情况下
将0翻转为1;
最后对于剩余的翻转次数num,全部将其加至最后一位即可

易错点分析:
特判写错一个字符调试一个小时............

时间复杂度:O(N)
代码描述:

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
int n,k;
string s;
int t;

void solve(){
    cin>>n>>k>>s;
    vector<int>q(n,0);
    int num=k;
    string ans;
    if(k==0){
        cout<<s<<endl;
        for(int i=0;i<s.size();i++)cout<<q[i]<<" ";
        cout<<endl;
        return ;
    }
    for(int i=0;i<n && num;i++){
        if(k%2==s[i]-'0'){
            q[i]++;
            num--;
        }
    }
    q[n-1]+=num;
    for(int i=0;i<n;i++){
        if((k-q[i])%2==1){
            s[i]='1'-(s[i]-'0');
        }
    }
    cout<<s<<endl;
    for(int i=0;i<n;i++)cout<<q[i]<<" ";
    cout<<endl;
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin>>t;
    while(t--){
            solve();                    
        }
    return 0;
}

C. Line Empire

解法1:(前缀和/递推/二分)
//我承认这个二分挺牵强的.....

思路分析:

即题目本意为：求取某个皇帝在占领除了自己的宫殿外的其他所有王国所消耗的”资源”的最小值
初始：本王国在下标为0的位置,其他王国的位置沿着数轴依次被呈现
限制条件如下:(1)占领某个其他王国并不会导致本王国迁都
(2)在占领第i个王国前不能占领第i+1及以后的王国
(3)迁都所消耗的”资源”为a(q[i]-q[i-1]);
占领所消耗的”资源”为b(q[i]-q[i-1]);

易错点分析:
没注意在乘法的原理想当然的以为使用了局部long long在类型转换时int就会自动转换为long long


时间复杂度:O(N)
代码描述:

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=2e5+10;
LL f[N],f1[N],f2[N],sum[N];
int q[N];
int n,a,b,t;
bool check(int x){
    if(f1[x]+f2[x]+sum[x]<=f1[x+1]+f2[x+1]+sum[x+1])return true;
    else return false;
}
void solve(){
        cin>>n>>a>>b;
        memset(f,0,sizeof f);
        memset(q,0,sizeof q);
        memset(sum,0,sizeof sum);
        memset(f1,0,sizeof f1);
        memset(f2,0,sizeof f2);
        memset(q,0,sizeof q);
        for(int i=1;i<=n;i++)cin>>q[i];
        for(int i=1;i<=n;i++){
            f1[i]=f1[i-1]+a*(q[i]-q[i-1]);
            f2[i]=f2[i-1]+b*(q[i]-q[i-1]);
        }
        for(int i=n-1;i>=0;i--){
            f[i]=f[i+1]+b*(q[i+1]-q[i]);
            sum[i]=sum[i+1]+(n-i)*(f[i]-f[i+1]);
        }
        int l=0,r=n;
        while(l<r){
            int mid=(l+r)/2;
            if(check(mid))r=mid;
            else l=mid+1;
        }
        LL ans=f2[l]+f1[l]+sum[l];
        cout<<ans<<endl;
}
signed main(){
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}