Codeforces Round #849 (Div. 4) A~G1

欢乐场hh

A.询问给定串是否是codeforces的子串

void solve(){
    string s="codeforces";
    string a;
    cin>>a;
    string::size_type idx; 
    idx=s.find(a);//在a中查找b.
    if(idx == string::npos )//不存在
        cout <<"NO"<<endl;
    else//存在
        cout <<"YES"<<endl; 
}

B.模拟即可

C.串的两边能加1,0，求原始串最短。

双指针扫一下贪心

void solve(){
    int n;cin>>n;
    string s;cin>>s;
    int l=0,r=n-1;
    if(n==1){
        cout<<1<<endl;return;
    }
    if(n==1){
        cout<<0<<endl;return;
    }
    for(;;){
        if(l==r){
            cout<<1<<endl;return;
        }
        if(l>r){
            cout<<0<<endl;return;
        }
        if(s[l]!=s[r]) {
            l++,r--;
        }
        else {
            cout<<r-l+1<<endl;return;
        }
    }
}

D.定义f（s）为s中出现的不同字符个数，求最大的f(a)+f(b),且a+b==s

预处理前缀和、后缀和然后枚举分段点

void solve(){
    int n;cin>>n;
    string s;cin>>s;
    map<char,int>mp;
    int sum[n+5]={0},sum2[n+5]={0};
    sum[0]=1;
    mp[s[0]]=1;
    for(int i=1;i<n;i++){
        if(mp[s[i]]) sum[i]=sum[i-1];
        else {
            mp[s[i]]=1;
            sum[i]=sum[i-1]+1;
        }
    }
    reverse(s.begin(),s.end());
    mp.clear();
    sum2[0]=1;
    mp[s[0]]=1;
    for(int i=1;i<n;i++){
        if(mp[s[i]]) sum2[i]=sum2[i-1];
        else {
            mp[s[i]]=1;
            sum2[i]=sum2[i-1]+1;
        }
    }
    int ans=sum[0]+sum2[n-2];
    for(int i=1;i<=n-2;i++){
        ans=max(ans,sum[i]+sum2[n-i-2]);
    }
    cout<<ans<<endl;
}

E.每次可以同时交换相邻字符的符号，最大化元素和

观察发现偶数个负号可以消没，奇数个符号可以消得只有一个

特判偶数个，然后奇数个答案为Σabs(ai)-2*abs(a1),a1为绝对值最小的数

F.每次把下标区间在[L,R]里面的数赋为每个数自身的数码和

比如[15,69]->[6,15]

想起一道题花神游历各国，操作次数也不是太多

set存还不是个位数的下标位置暴力修改即可(是个位数的话就不会在变了，一个数在有限少数步里会变成个位数)

一个坑点是迭代器访问set时如果用erase，it会自己++，要判一下。

#include<bits/stdc++.h>
#define IT set<int>::iterator
using namespace std;
typedef long long ll;
int work(int x){
    int tot=0;
    while(x){
        tot+=x%10;x/=10;
    }
    return tot;
}
void solve(){
    int n,q;
    cin>>n>>q;
    int a[n+5];
    set<int>s;
    for(int i=1;i<=n;i++) cin>>a[i],s.insert(i);
    for(int i=1;i<=q;i++){
        int op;cin>>op;
        if(op==2) {
            int x;cin>>x;
            cout<<a[x]<<endl;
        }
        else {
            int l,r;cin>>l>>r;
            for(set<int>::iterator it=s.lower_bound(l);it!=s.end();){
                int id=*it；
                if(id>r) break;
                a[id]=work(a[id]);
                if(a[id]<=9) {
                    it=s.erase(it);
                }
                else it++;
            }
        }
    }
} 
int main(){
    //freopen("lys.in","r",stdin);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}

G1.计算花费为ai+i，排序完贪心即可。

G2,现场想了一个一次考虑两次操作的想法，可以消去新增限制的影响，就是有点麻烦，维护

ai+i+aj+j,ai+i+n-j+1+aj,n-j+1+aj+n-1+ai的最小值,没写出来。