专栏文章

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

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

文章操作

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

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

思路

先说两个结论。

结论一

左移的次数如果 >6>6 是没有意义的。
因为，我左移 >6>6 位的话：
  • 如果我可以构成一个新的 nanjing，那么在末尾肯定至少有一个构成它的字母。所以我只需要移动至多 66 位就能了。这个题比较特殊，因为给定的那个字符串，是不能出现重叠的现象的。
  • 反之，如果我构不成，那么移动还是不移动都没什么用。反正只看答案。

结论二

如果左移的过程中，破坏了左侧原有的 nanjing 那么一定不优。因为我左移最多额外构成一个，然后我现在还破坏了一个。那么就抵消了，相当于答案没加。况且还不能保证一定能额外构成。
说完结论。
我们来看。怎么写？首先我们可以定义一个最多左移的个数（我写的是 minkmink，所以这里也用了）。开始先把它定义成 mink=min⁡(6,k)mink=\min(6,k)，因为结论一，还有最多次数的限制。
在求的过程中，我们先求一个原来输入字符串中 nanjing 的个数。每次求得时，令字符 n 的位置（从 11 开始）为 ii，则令 mink=min⁡(mink,i)mink = \min(mink,i) 因为结论二。
最后，再算一下左移 minkmink 个后，能够成几个新的 nanjing 即可。

代码

CPP
#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)O(n)。

评论

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

正在加载评论...