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

wyc0607 · 2025-09-10 19:41:37 · 题解

思路

观察发现，要想存在更多的 \texttt{nanjing} 子串，首先需要保证原本是 \texttt{nanjing} 的子串不受影响。其次，唯一的添加方法就是使原来的字符串的部分后缀与部分前缀进行拼接，变成 \texttt{nanjing}。

所以只需要枚举左移 0 到 \min(k,7) 即可。

代码：

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