Codeforces Round #848 (Div. 2) A~C

A.

给出一个-1，1序列，操作是交换相邻位置的符号，一定要操作一次，求最大sum。

只有4种情况，扫一遍判断是否出现即可。

B

题面写得真清楚啊:)

#include<bits/stdc++.h>
using namespace std;
const int maxn=2*1e5+5;
int p[maxn],pos[maxn],a[maxn];
void solve(){
    int n,m,d;
    cin>>n>>m>>d;
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) pos[p[i]]=i;
    for(int i=1;i<=m;i++) cin>>a[i];
    int ans=INT_MAX;
    for(int i=1;i<m;i++){
        int x=pos[a[i]],y=pos[a[i+1]];
        ans=min(ans,y-x);
        if(d<n-1) ans=min(ans,d-(y-x)+1);
    }
    cout<<max(ans,0)<<endl;
}
int main(){
    //freopen("lys.in","r",stdin);
    int t;cin>>t;
    while(t--){
        solve();
    }
}

C.相当于可以选a中的i种字符替换成任何想要的(i<=k)，最大化(l,r)数量使得a[l,r]=b[l,r]

k最多10，类似状态压缩那样的二进制枚举

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
    int n,k;
    cin>>n>>k;
    string a,b;
    cin>>a>>b;
    int cnta=0;
    map<char,int>mp;
    mp.clear();
    for(int i=0;i<n;i++){
        if(!mp[a[i]]){
            mp[a[i]]=++cnta;
        }
    }
    ll out=0;
    for(int i=0;i<(1<<cnta);i++){
        if(__builtin_popcount(i)>k) continue;
        int pre=-1;
        ll num=0;
        ll ans=0;
        for(int j=0;j<n;j++){
            if(a[j]==b[j]||(mp[a[j]]&&(i >> (mp[a[j]]-1) & 1))){
                if(pre==-1) pre=j,num=1;
                else num++;
            }
            else {
                pre=-1;
                ans+=num*(num-1)/2+num;
                num=0;    
            }
        }
        if(pre!=-1) ans+=num*(num-1)/2+num;
        out=max(ans,out);
    }
    cout<<out<<endl;
}
int main(){
    //freopen("lys.in","r",stdin);
    int t;cin>>t;
    while(t--){
        solve();
    }
}