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

AA12_G · 2025-09-15 13:23:01 · 题解

思路

先说两个结论。

结论一

左移的次数如果 >6 是没有意义的。

因为，我左移 >6 位的话：

• 如果我可以构成一个新的 nanjing，那么在末尾肯定至少有一个构成它的字母。所以我只需要移动至多 6 位就能了。这个题比较特殊，因为给定的那个字符串，是不能出现重叠的现象的。

• 反之，如果我构不成，那么移动还是不移动都没什么用。反正只看答案。

结论二

如果左移的过程中，破坏了左侧原有的 nanjing 那么一定不优。因为我左移最多额外构成一个，然后我现在还破坏了一个。那么就抵消了，相当于答案没加。况且还不能保证一定能额外构成。

说完结论。

我们来看。怎么写？首先我们可以定义一个最多左移的个数（我写的是 mink，所以这里也用了）。开始先把它定义成 mink=\min(6,k)，因为结论一，还有最多次数的限制。

在求的过程中，我们先求一个原来输入字符串中 nanjing 的个数。每次求得时，令字符 n 的位置（从 1 开始）为 i，则令 mink = \min(mink,i) 因为结论二。

最后，再算一下左移 mink 个后，能够成几个新的 nanjing 即可。

代码

#include <bits/stdc++.h>
using namespace std;
char c[] = {'n', 'a', 'n', 'j', 'i', 'n', 'g'};
void mian()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    s = ' ' + s;
    int mink = min (7, k), notky = 0;
    for (int i = 1; i <= n - 6; i ++)
    {
        bool nj = 1;
        for (int j = 0; j < 7; j ++)
        {
             if (s[i + j] != c[j]) 
             {
                 nj = 0;
                 break;
             }
        }
        if (nj)
        {
            notky ++;
            mink = min (mink, i - 1);
        }
    }
    int ky = 0;
    for (int i = n - 5; i <= n - 6 + mink; i ++)
    {
        bool nj = 1;
        for (int j = 0; j < 7; j ++)
        {
            if (s[(i + j - 1) % n + 1] != c[j])
            {
                nj = 0;
                break;
            }
        }
        if (nj == 1) ky ++;
    }//求构成的新的个数
    cout << notky + ky << endl;
}
int main()
{
    int T;
    cin >> T;
    while (T --) mian();
}

时间复杂度（单个数据）：O(n)。