Codeforces Round 855 (Div. 3) A-E题解

A.Is It a Cat?

? ? ? ? 第一题可用暴力依次枚举，此处提供一个用unique函数的方法。（unique函数的使用方法请参考CSDN上其他大佬的解释）

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5;
int a[N];

void solve(){
    int n;cin>>n;
    string s;cin>>s;

    for(int i=0;i<n;i++){
        s[i]=tolower(s[i]);//全部变为小写
    }
    s.erase(unique(s.begin(),s.end()),s.end());//将所有重复的字母移到后面并删除

    if(s=="meow") cout<<"YES"<<endl;
    else cout<<"NO"<<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

? ? ? ? 思维题。首先将大小写字母进行分离，并用桶统计出每个字母大小写的数量。若某一个字母大小写数量相同，则对答案贡献大写（或小写）字母的数量；若不同，则用变量tem先记录可以配对的数量，随后再加上在减去已配对的数量后，运用特殊能力组成的对数。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5;
int a[N];

int u[26],l[26];//u存大写字母，l存小写字母

void solve(){
    memset(u,0,sizeof u);//每次开始前初始化
    memset(l,0,sizeof l);

    int n,m;cin>>n>>m;
    string s;cin>>s;
    for(int i=0;i<n;i++){
        if(s[i]>='a'&&s[i]<='z') l[s[i]-'a']++;
        else if(s[i]>='A'&&s[i]<='Z') u[s[i]-'A']++;
    }
    int ans=0;
    for(int i=0;i<26;i++){
        if(u[i]==l[i]){
            ans+=u[i];
            continue;
        }

        int tem=min(u[i],l[i]);
        u[i]-=tem,l[i]-=tem;
        ans+=tem;

        tem=min(m,max(u[i],l[i])/2);//记录剩余能用特殊能力组成的对数
        m-=tem,ans+=tem;
    }
    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;
}

C.Powering the Hero (hard version)

? ? ? ? C1与C2本质上是一道题，这里给出Hard版本的代码。

? ? ? ? 模拟、贪心。读题发现，对于每张英雄牌力量的贡献与牌堆的顺序有关，即找出在某一张英雄牌前所有奖励牌的最大值。因此，为了维护奖励牌堆的值，我们可以使用大根堆进行维护，即优先队列。在摸出每一张英雄牌时，加上优先队列的队首即可，若摸出奖励牌，则加入队列。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5;
int a[N];

priority_queue<int> pq;//定义优先队列
void solve(){
    while(!pq.empty()) pq.pop();//每次开始前清空队列

    int n;cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        if(x==0){//当摸出英雄牌时，若队列不为空则加上队列队首
            if(!pq.empty()){
                ans+=pq.top();
                pq.pop();
            }
            else continue;
        }
        pq.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

? ? ? ? 思维题。模拟删除字符后可得到规律：以三个字符组成的子串中，若首尾字母相同，则不管如何删除两个连续字符，最终得到的字符串都是一样的，因此，只能获得一个字符串。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5;
int a[N];

void solve(){
	int n;cin>>n;
	string s;cin>>s;
	int ans=1;//即使什么都不考虑，也能获得满足题意的一串字符串，故初始化为1
	for(int i=1;i<n-1;i++){
		if(s[i-1]!=s[i+1]) ans++;
	}
	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;
}

E.Unforgivable Curse (hard version)

? ? ? ? E1与E2本质上是一道题，这里给出Hard版本的代码。

? ? ? ? 模拟、暴力枚举。以Easy版本给的m=3为例，可以模拟得出规律：设位置为pos，则当pos+m超出字符长度并且pos-m小于0时，此时该位置上的字符，无论怎么交换，都无法移动，因此，该区间我们可以视为不可变区间。故原始字符串若想变为目标字符串，比较不可变区间即可。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5;
int a[N];

int num1[26],num2[26];

void solve(){
    memset(num1,0,sizeof num1);
    memset(num2,0,sizeof num2);
	int n,m;cin>>n>>m;
    string s;cin>>s;
    string ts;cin>>ts;
    for(int i=0;i<n;i++){
        num1[s[i]-'a']++;
        num2[ts[i]-'a']++;
    }

    //先进行特判，字母数量不相同的直接判NO
    for(int i=0;i<26;i++){
        if(num1[i]!=num2[i]){
            cout<<"NO"<<endl;
            return;
        }
    }

    //给出约束条件，进行枚举
    for(int i=0;i<n;i++){
        if(i+m>=n&&i-m<0){
            if(s[i]!=ts[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;
}