Codeforces Round 855 (Div. 3)

A. Is It a Cat?

为什么这个A这么麻烦

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

void solve(){
    int n;
    string s;
    cin>>n>>s;
    s = " " + s;
    int cnt1=0,cnt2=0,cnt3=0,cnt4=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='m'||s[i]=='M'){
            cnt1++;
            if(cnt2+cnt3+cnt4>0){
                cout<<"NO"<<endl;
                return;
            }
        }else if(s[i]=='e'||s[i]=='E'){
            cnt2++;
            if(cnt3+cnt4>0){
                cout<<"NO"<<endl;
                return;
            }
        }else if(s[i]=='o'||s[i]=='O'){
            cnt3++;
            if(cnt4){
                cout<<"NO"<<endl;
                return;
            }
        }else if(s[i]=='w'||s[i]=='W'){
            cnt4++;
        }else{
            cout<<"NO"<<endl;
            return;
        }
    }
    if(!cnt1||!cnt2||!cnt3||!cnt4){
        cout<<"NO"<<endl;
        return;
    }
    cout<<"YES"<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

B. Count the Number of Pairs

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

void solve(){
    int n,k;
    string s;
    cin>>n>>k>>s;
    map<int,int> cnt;
    for(int i=0;i<n;i++)
        cnt[s[i]]++;
    int ans=0;
    int x=0;
    for(int i='A';i<='Z';i++){
        int y=min(cnt[i],cnt[i+'a'-'A']);
        ans += y;
        x = max(cnt[i],cnt[i+'a'-'A'])-y;
        if(k >= x/2){
            ans+=x/2;
            k  -=x/2;
        }else{
            ans+=k;
            k=0;
        }
    }
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

C1\2. Powering the Hero

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

void solve(){
    priority_queue<int,vector<int>,less<int>> path;
    int n;
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x==0){
            if(path.size()){
                ans+=path.top();
                path.pop();
            }
        }else path.push(x);
    }
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

D. Remove Two Letters

刚开始开map写了个暴力，结果mle了。

要注意一下，如果s[i-1]==s[i+1]那么就一定会有一次重复。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10;

void solve(){
    int n;
    string s;
    cin>>n>>s;
    int cnt=0;
    for(int i=1;i<s.size()-1;i++)
        if(s[i-1]==s[i+1]) cnt++;
    cout<<n-1-cnt<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

E1\2. Unforgivable Curse

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

void solve(){
    int n,k;
    string s,t;
    cin>>n>>k;
    cin>>s>>t;
    s = " " + s;
    t = " " + t;
    vector<int> cnt1(26,0),cnt2(26,0);
    for(int i=1;i<=n;i++){
        if(i-k<1&&i+k>n)
        {
            if(s[i]!=t[i])
            {
                cout<<"NO"<<endl;
                return;
            }
        }
        else
        {
            cnt1[s[i]-'a']++;
            cnt2[t[i]-'a']++;
        }
    }
    for(int i=0;i<26;i++)
    {
        if(cnt1[i]!=cnt2[i])
        {
            cout<<"NO"<<endl;
            return;
        }
    }
    cout<<"YES"<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

F. Dasha and Nightmares

#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10;
string s;
int a[N] , b[N] ,cnt[1<<26];
int x[26];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        for(int j=0;j<s.size();j++)
        {
            a[i] |= (1<<(s[j]-'a'));
            b[i] ^= (1<<(s[j]-'a'));
        }
    }
    long long ans=0;
    for(int j=0;j<26;j++)
    {
        int target = (1<<26) - 1 - (1<<j);
        for(int i=1;i<=n;i++)
        {
            if(a[i]>>j & 1) continue;
            cnt[b[i]]++;
            ans += cnt[b[i]^target];
            //cout<<ans<<endl;
        }
        for(int i=1;i<=n;i++){
            if(a[i]>>j & 1) continue;
            cnt[b[i]]--;
        }
    }
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--) solve();
    return 0;
}