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

发布时间:2024年01月17日

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;
}

文章来源:https://blog.csdn.net/TaopiTTT/article/details/135592842
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。