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

bison_henry · 2025-09-13 15:04:45 · 题解

原题在这儿

非常简单的一道字符串题，看似可以暴力，实则的确可以，直接枚举字符串变化就行了，like this：

        for (int i = 1; i <= k; i++)
        {
            ans = max(ans, cx(s));
            s += s[0], s = s.substr(1);
        }

超时严重，再加上优化：

nanjing只有7字符长度，给定样例anjingananjingqqn，这时左移6位可得到最大数量，这已经是最坏情况，所以枚举范围可降为枚举k和6之间的最小值次

AC代码：

#include <bits/stdc++.h>
using namespace std;
long long cx(string s);
int main()
{
    long long t;
    cin >> t;
    while (t--)
    {
        long long n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        long long ans = -1;
        for (int i = 1; i <= min(6ll, k); i++)//有可能k比6还要小
        {
            if (ans * 8 > n)//如果不可能有更优答案则退出
                break;
            ans = max(ans, cx(s));
            s += s[0], s = s.substr(1);
        }
        ans = max(ans, cx(s));//最后要再查一次
        cout << ans << '\n';
    }
}

//查询
long long cx(string s)
{
    long long st = 0, sum = 0;
    while (s.find("nanjing", st) != -1)//不断找nanjing出现的位置
        sum++, st = s.find("nanjing", st) + 7;//移动查找的起点
    return sum;
}

AC记录