题目链接&比赛链接

CF1800A Is It a Cat?

洛谷链接

Description

给定一个字符串及其长度，如果满足下列条件输出 YES否则输出 NO。

• 该字符串由四部分组成
• 每部分有且仅有一种字母（不分大小写），依次为 m,e,o,w。

共 \(t\) 组数据。

Solution

条件包含两部分，有且仅有这四种字母出现，并且可以分成四个字母块（每个字母块有且仅有一种字母，且字母块排列必须是给定顺序）。

详见代码。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
int a[10][10];
bool vis[10];
ll read(){
    ll x=0,f=1;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void solve(){
	int n,ans=0;
	string s;
	cin>>n;
	cin>>s;
	memset(a,-1,sizeof(a)); //a[1~4][0/1] 表示四种字母第一个出现的位置和最后一次出现的位置，记得初始化数组
	for(int i=0;i<n;i++){
		if(s[i]=='m'||s[i]=='M'){
			if(a[1][1]==-1) a[1][1]=i; //第一次出现
			a[1][2]=i; //只要是该字母就要更新最后出现的位置
			ans++; //ans记录这四种字母出现的总数
		}else if(s[i]=='e'||s[i]=='E'){
			if(a[2][1]==-1) a[2][1]=i;
			a[2][2]=i;
			ans++;
		}else if(s[i]=='o'||s[i]=='O'){
			if(a[3][1]==-1) a[3][1]=i;
			a[3][2]=i;
			ans++;
		}else if(s[i]=='W'||s[i]=='w'){
			if(a[4][1]==-1) a[4][1]=i;
			a[4][2]=i;
			ans++;
		}
	}
	if(a[1][1]!=0||a[2][1]!=a[1][2]+1||a[3][1]!=a[2][2]+1||a[4][1]!=a[3][2]+1||a[4][2]!=n-1||ans!=n){ //满足条件肯定是四种字母按顺序头连尾，尾连头且ans一定等于n
		cout<<"NO"<<endl;
	}else cout<<"YES"<<endl;
}
int main(){
	t=read();
	while(t--){
		solve();
	}
	return 0;
}

CF1800B Count the Number of Pairs

洛谷链接

Description

给定 \(n\)，\(k\)，长度为 \(n\) 的字符串 \(s\)。

一个大写的字母和一个小写格式的该字母可以合并，合并后消失，且分值加一。

一次操作定义为将一个字母改变其大小写格式（大写转小写，小写转大写）。

求在不超过 \(k\) 次操作后，该字符串的分值的最大值。

共 \(t\) 组数据。

Solution

设 \(a_1,a_2\) 表示字母 a的大小写数量。

为了让分值最大，所以要让大小写数量之差越小，这样才能使能合并的对数越多。

一种字母最多能有 \(\lfloor(a_1+a_2)\div 2\rfloor\) 对大小写能合并，而达到这个数量需要 \(add=\lfloor(a_1+a_2)\div 2\rfloor-\min(a_1,a_2)\)（操作后的对数减去原来就有的对数就是操作中改动的对数）次操作。将二十六种字母的 \(add\) 加起来，与 \(k\) 取较小值（这就是在不超过操作 \(k\) 次能增加的对数）加上原来就有的对数（\(\min(a_1,a_2)+\min(b_1,b_2)+\dots+\min(z_1,z_2)\)），这就是最终答案。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
int a[30],b[30];
ll read(){
    ll x=0,f=1;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void solve(){
	int n=read(),k=read(),ans=0;
	string s;
	cin>>s;
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	for(int i=0;i<n;i++){
		if(s[i]<='z'&&s[i]>='a') a[s[i]-'a'+1]++;
		else if(s[i]>='A'&&s[i]<='Z') b[s[i]-'A'+1]++;
	}
	for(int i=1;i<=26;i++){
		ans+=min(a[i],b[i]);//操作前就有的分值
		ans+=min(abs(a[i]-b[i])/2,k);//操作后增加的分值
		k-=min(abs(a[i]-b[i])/2,k);//减去该字母耗费的操作数
	}
	cout<<ans<<endl;
}
int main(){
	t=read();
	while(t--){
		solve();
	}
	return 0;
}

CF1800C1&C2 Powering the Hero

洛谷链接(easy version)
洛谷链接(hard version)

Description

简单版和困难版的唯一区别在于 \(n\) 和 \(t\) 的数据范围。

桌上有 \(n\) 张牌每张牌都有一个能量值 \(s_i\)，英雄牌的能量值为 \(0\)，加分牌的能量值为正整数。

每次从桌上的牌堆顶部拿一张牌直到无牌可拿。

• 若该牌为加分牌，你可以将其放在加分牌堆的顶部或丢弃此牌。
• 若该牌为英雄牌，那么加分牌堆堆顶的牌的能量值将赋予该英雄牌，英雄牌加入军队，且该加分牌丢弃。

问军队的总能量值的最大值。

共 \(t\) 组数据。

Solution

每次取当前还在加分牌堆顶的最大值即可。

例：1187090

若所有加分牌都加入堆的话第一张英雄牌取得的是 7，而当前最大值为 8，明显在取 7时弃牌即可。

例：1187010

将所有加分牌放入堆时，第一张英雄牌的当前最大值为 8，而想要取到只可能弃 7，此时军队最大值为 15，明显不是最优。其实换个角度想，第一张英雄牌取 7，第二张英雄牌取 8，本质相同。

总结，若第 \(i,j(i<j)\) 两张英雄牌（可以扩展到多张牌），\(j\) 取 \(i\) 前面的牌最优，就说明 \(i,j\) 中没有加分牌能在前 \(i-1\) 张牌中在前二大（例子中第二大为 7而 \(i,j\) 中只有 1，取 \(j\) 时最大为 7，实则为 8），否则说明 \(i,j\) 中有更大的牌，定为 \(j\) 时最大的牌（因为前 \(i-1\) 的最大 8已经取走）。

所以满足取当前加分牌堆最大值的结论，即使当时那张英雄牌取不到（例子二），但后面的英雄牌仍能补上。

取最大值用大根堆维护。

时间复杂度：\(O(n \log n)\)，明显可以过简单版和困难版。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int t;
int a[500500];
ll read(){
    ll x=0,f=1;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void solve(){
	int n=read();
	long long ans=0;
	priority_queue<int> q;
	for(int i=1;i<=n;i++){
		a[i]=read();
		if(a[i]>0) q.push(a[i]);
		else if(a[i]==0) {
			if(q.size()>0){
				ans+=q.top(),q.pop();//记得弹出
			}
		}
	}
	cout<<ans<<endl;
}
int main(){
	t=read();
	while(t--){
		solve();
	}
	return 0;
}

CF1800D Remove Two Letters

洛谷链接

Description

给定 \(n\) 和一个长度为 \(n\) 的字符串 \(s\)。

令 \(s'\) 为 \(s\) 删去两个连续字符后剩余的字符串，问共有多少个不同的 \(s'\)。

共 \(t\) 组数据。

Solution

例：aabacac

可以发现去掉第二三字母和去掉三四字母是一样的。

我们将整个字符串分成 a，aba，cac三个部分，由于只改动二三四这三个字母，所以第一三部分忽略。删二三时，第二部分变成第四个字母 a，而删三四时，第二部分变成 第二个字母 a，所以如果 \(s_i=s_{i+2}\)，那么删 \(i,i+1\) 和 \(i+1,i+2\) 时剩余字母相同。

枚举重复的数量，即 \(s_i=s_{i+2}\) 的数量，再用总数量 \(\left\vert s\right\vert-1\) 减去重复数量即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int t;
int a[3005];
ll read(){
    ll x=0,f=1;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void solve(){
	int n=read(),ans=0;
	string s;
	cin>>s;
	for(int i=2;i<n;i++){
		if(s[i]==s[i-2]) ans++;
	}
	cout<<n-1-ans<<endl;
}
int main(){
	t=read();
	while(t--){
		solve();
	}
	return 0;
}

CF1800E1&E2 Unforgivable Curse

洛谷链接(easy version)
洛谷链接(hard version)

简单版和困难版的唯一区别在于 \(k\) 的数据范围，简单版中，保证 \(k=3\)。

给定 \(n\)，\(k\)，及两个长度为 \(n\) 的字符串 \(a\)，\(b\)。

问能否在通过若干次操作后使 \(a\) 改为 \(b\)。

在一次操作中，你可以交换 \(a_i,a_j(i<j)\) 当且仅当 \(\left\vert i-j\right\vert=k\space or\space k+1\)。

共 \(T\) 组数据。

Solution

我们以 \(k=3\) 来找规律。

首先当 \(n\leq3\) 时，任何字母都无法操作，所以 \(a\) 和 \(b\) 要完全相同才可行。

\(n=4\) 时 \(a_2,a_3\)（以一为字符串开始下标）是无法移动的，而 \(a_1,a_4\) 可以交换。

\(n=5\) 时 \(a_3\) 无法移动，换言之其他字母也无法到 \(a_3\)。其他的位置可以任意交换：

• \(a_1\rightarrow a_2\)：先到 \(a_4\) 再到 \(a_2\)。
• \(a_1\rightarrow a_3\space or\space a_4\)：一步到达，其他位置同理。

\(n=6\) 时，任意字母可以到达任意位置。

如果 \(a_i\rightarrow a_{i+j}\)，向右移 \(4\) 步再往左移 \(3\) 步，重复 \(j\) 次即可，如果越界，适量减少重复次数，调整右移左移步数及顺序，显然可以到达任意位置（\(a_5\) 到 \(a_6\) 的顺序为 \(a_5\rightarrow a_2\rightarrow a_6\)）。\(a_{i-j}\) 同理。

总结规律，只要 \(a_i\) 可以进行操作（\(i-k\geq 1\) 并且 \(i+k\leq n\)），它就可以移到任意字母，任意字母也可以移到这个位置上。

只需判断那些不能移动的位置上更改前和更改后是否相同。

记得保证该字母在 \(a\) 中出现过，记录每种字母修改前后的数量是否一致即可。

简单版和困难版皆可通过。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int t;
int vis1[30],vis2[30];
ll read(){
    ll x=0,f=1;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void solve(){
	int n=read(),k=read();
	string a,b;
	cin>>a>>b;
	memset(vis1,0,sizeof(vis1));
	memset(vis2,0,sizeof(vis2));
	for(int i=0;i<n;i++){
		vis1[a[i]-'a'+1]++;
		vis2[b[i]-'a'+1]++;
	}
	for(int i=1;i<=26;i++) {
		if(vis1[i]!=vis2[i]){//数量不同无法实现
			cout<<"NO"<<endl;
			return ;
		}
	}
	for(int i=0;i<n;i++){
	    if(i+k>=n&&i-k<0){//无法操作
	        if(a[i]!=b[i]){
	            cout<<"NO"<<endl;
	            return ;
	        }
	    }
	}
	cout<<"YES"<<endl;
}
int main(){
	t=read();
	while(t--){
		solve();
	}
	return 0;
}

本栏目推荐文章
• NSSCTF Round#16 Basic WriteUp
• AT_arc125_c [ARC125C] LIS to Original Sequence 题解
• P5321 [BJOI2019] 送别 题解--zhengjun
• P9007 [入门赛 #9] 最澄澈的空与海 (Hard Version) 题解
• P2198 杀蚂蚁 题解
• P3243 [HNOI2015] 菜肴制作 题解
• AT_abc243_g [ABC243G] Sqrt题解
• AT_abc243_g [ABC243G] Sqrt题解
• P9754 题解
• AT_arc167_e 题解

题解 Codeforces Round 855 Divcodeforces round 855 div 题解codeforces round 855 题解codeforces div round 题解codeforces round div2 题解codeforces round div3 codeforces round 911 div codeforces round 864 div codeforces round 887 div codeforces round 863 div codeforces round 913 div