专栏文章

题解：P14225 [ICPC 2024 Kunming I] 左移 2

II_am_kunzi
P14225题解参与者 1已保存评论 0

文章操作

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

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

P14225 题解

非常好一道题，使我十遍才过。

题目思路

首先，对于一段长度 ≥2\ge 2 的连续字符串，我们只需要隔一个修改一个，把字符修改为和前后都不同的字符即可。因为字符一共有 2626 种，而算上前后和修改位置的字符，最多只需要 33 种字符，是完全足够的。另外，对于答案处理，我们从相同的字符部分的第二个字符开始隔一个修改一个，这样对于奇数长度的连续字符串，这种修改策略会使这一段的答案更优。例如，对于字符串 aaaaaaa，我们将其从第二个字符开始隔一个修改一个，修改为 abababa，而不是 bababab。
看到这道题，我们一个最暴力的思路就是枚举断点，分别计算前后两段的答案，最后考虑首尾拼接时可能使答案增加 11 的情况。但 nn 极大，导致暴力会超时。
我们发现每次把前后两部分的答案都处理一遍很费时间，所以不妨预处理前缀字符串的答案和后缀字符串的答案。我们还会发现把一个字符串反转之后，它的最小操作次数不变，所以处理后缀字符串直接倒着扫是正确的。
最后我们把首尾拼接对答案的影响计算出来。我们发现只有首一段和尾一段的字符相同时才可能对答案有影响，所以记录下从前面开始和从后面开始最长的和第一个字符相同的长度，这些字符在重新拼接的过程中可能会影响答案。
我们根据这一部分第一段中的策略分析，会发现在首尾两段的连续字符长度都为奇数时，修改后会影响答案，因为在此情况下，我们的策略不会修改第一个字符和最后一个字符，而这两个字符在重新拼接后是相邻的。至于其他三种情况，我们可以修改偶数一段从第一个字符开始修改或者从第二个字符开始修改，这样可以满足首尾字符不同。
但注意一个细节：在拼接的过程中，我们可能会将首一段的连续字符截开或将尾一段的连续字符截开，所以需要将截开两端的长度和连续字符长度取最小值。反例：字符串为 aa，此时首尾最大长度均为 2 2，但无论从哪里截开答案都是 1。而不加这一段的代码从中间截开时不会计算截开后拼接对答案的影响。
具体细节如有不理解，可参考代码实现。

题目代码

CPP
int t;
int qzh[500005] , hzh[500005]; // 前缀答案 / 后缀答案
void solve()
{
    memset(qzh , 0 , sizeof(qzh));
    memset(hzh , 0 , sizeof(hzh));
    string s;
    read(s);
    s = ' ' + s; // 从 1 下标开始，方便写代码
    int n = s.length() - 1;
    for(int i = 2 ; i <= n ; i++) // 按策略从第二个字符开始修改
    {
        qzh[i] = qzh[i - 1];
        if(s[i] == s[i - 1]) // 如果这两个字符相等，那么隔一个修改一个，i++ 直接跳过下一个字符
        {
            qzh[i]++;
            qzh[i + 1] = qzh[i]; // 跳过时注意维护答案
            i++;
        }
    }
    for(int i = n - 1 ; i >= 1 ; i--) // 这一段细节同上
    {
        hzh[i] = hzh[i + 1];
        if(s[i] == s[i + 1])
        {
            hzh[i]++;
            hzh[i - 1] = hzh[i];
            i--;
        }
    }
    int maxl = 0 , maxr = 0; // 首一段最大连续字符长度 / 尾一段最大连续字符长度
    for(int i = 1 ; i <= n ; i++)
    {
        if(s[i] == s[1])
        {
            maxl++;
        }
        else
        {
            break;
        }
    }
    for(int i = n ; i >= 1 ; i--)
    {
        if(s[i] == s[1])
        {
            maxr++;
        }
        else
        {
            break;
        }
    }
    int ans = qzh[n];
    for(int i = 1 ; i < n ; i++)
    {
        ans = min(ans , qzh[i] + hzh[i + 1] + (min(i , maxl) % 2 && min(maxr , n - i) % 2)); // 注意取 min
    }
    printnl(ans);
}
signed main()
{
    read(t);
    while(t--)
    {
        solve();
    }
	return 0;
}

评论

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

正在加载评论...