Codeforces Round 1005 (Div. 2) A-C题解

比赛链接：https://codeforces.com/contest/2064
赛时只做出了前三题，感觉是贪心Round.

A. Brogramming Contest

从前往后遍历s，遇到0和1的交界处，就把1以及后面的移到t中，然后在t中从前往后遍历，遇到1和0的交界处就把0以及后面放回s中，以此类推。也就是只需要找有多少个0和1交界处。特别的，当s以1开头的时候，要先直接把s整体移到t，也就是要多花一步。

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        string s,t;
        cin>>s;
        int cnt=0;
        if(s[0]=='1') cnt++;
        for(int i=0;i<n-1;i++){
            if(s[i]!=s[i+1]) cnt++;
        }
        cout<<cnt<<"\n";
    }
	return 0;
}  

B. Variety is Discouraged

根据得分计算公式，只有删除只出现1次的元素是不会使得分降低的，如果删除了出现2次及以上的元素，数组长度减少得比不同元素的个数减少得多，导致得分反而降低。同时题目要求在得分相同的情况下，数组长度最小。因此，我们要删掉连续的只出现一次的元素，并让删除的这一段长度尽可能长。

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        vector<int> a(n);
        map<int,int> mp;
        for(int i=0;i<n;i++){
            cin>>a[i];
            mp[a[i]]++;
        }
        int ansl=0,maxlen=0;
        //只删除唯一出现的元素
        for(int i=0;i<n;i++){
            if(mp[a[i]]==1){
                int len=1;
                while(i+len<n&&mp[a[i+len]]==1){
                    len++;
                }
                if(len>maxlen){
                    maxlen=len;
                    ansl=i+1; //因为题目要求的是1索引
                }
                i=i+len-1; //减1，因为for循环还会加1，让下一次从i+len开始
            }
        }
        if(ansl==0) cout<<0<<"\n";
        else cout<<ansl<<" "<<ansl+maxlen-1<<"\n"; 
    }
	return 0;
}  

C. Remove the Ends

我们要尽可能获得多的硬币，也就是尽可能多选数组中的元素进行对应操作。如果选择元素是一个正数，那前面的正数都可以从前往后先选；如果是负数，那后面的负数都可以从后往前先选。那我们只需要枚举正负数交界处和两端，把前面的正数和后面的负数的绝对值之和加起来，就能得到相应的一次答案，再对每次答案取最大值，就是最终答案。

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        vector<int> a(n+1),lsum(n+1,0),rsum(n+2,0); 
        //lsum[i]表示以a[i]结尾的前缀中正数的和，rsum[i]表示以a[i]开头的后缀中负数的绝对值和
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(a[i]>0) lsum[i]=lsum[i-1]+a[i];
            else lsum[i]=lsum[i-1];
        }
        for(int i=n;i>=1;i--){
            if(a[i]<0) rsum[i]=rsum[i+1]-a[i];
            else rsum[i]=rsum[i+1];
        }
        int ans=abs(a[1]);
        for(int i=1;i<=n;i++){
            ans=max(ans,lsum[i]+rsum[i]); 
            //其实答案只会产生在正数和负数之间的交界处，以及两端。不过这样写更好写，时间复杂度也是O(n).
        }
        cout<<ans<<"\n";
    }
	return 0;
}