专栏文章

题解：P14018 [ICPC 2024 Nanjing R] 左移 3

wwyc0607
P14018题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miny3s07
此快照首次捕获于
2025/12/02 10:14
3 个月前
此快照最后确认于
2025/12/02 10:14
3 个月前
查看原文

思路

观察发现，要想存在更多的 nanjing\texttt{nanjing} 子串，首先需要保证原本是 nanjing\texttt{nanjing} 的子串不受影响。其次，唯一的添加方法就是使原来的字符串的部分后缀与部分前缀进行拼接，变成 nanjing\texttt{nanjing}。
所以只需要枚举左移 00 到 min⁡(k,7)\min(k,7) 即可。

代码：

CPP
#include<bits/stdc++.h>
using namespace std;
main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		int n,k;
		cin>>n>>k;
		string s;
		cin>>s;
		int ans=-1;
		for(int i=0;i<=min(k,7);i++){
			string k="";
			for(int j=0;j<=n-1;j++) k+=s[(i+j)%n];
			int res=0;
			for(int j=0;j<=n-7;j++){
				if(k[j]=='n'&&k[j+1]=='a'&&k[j+2]=='n'&&k[j+3]=='j'&&k[j+4]=='i'&&k[j+5]=='n'&&k[j+6]=='g'){
					res++;
				}
			}
			ans=max(ans,res);
		}
		cout<<ans<<'\n';
	}
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...