题解：P12672 「LAOI-8」近期我们注意到有网站混淆视听

题目分析

本题要求我们判断对于给定的字符串，最少需要多少次字符交换操作，使得字符串中不存在同时包含 LGR 子串和 CSP 子串的情况。每次操作可以交换任意两个字符。

关键观察：

CPP

若字符串中不同时存在 LGR 和 CSP 子串，则无需任何操作（答案为 0）
若字符串中同时存在 LGR 和 CSP 子串，则仅需 1 次操作即可满足条件

为什么只需 1 次操作？因为我们可以交换 LGR 中的任意一个字符与 CSP 中的任意一个字符，这样至少会破坏其中一个子串的结构，使得两者无法同时存在。

解题思路

统计子串数量：对于每个输入字符串，统计 "LGR" 子串的出现次数（cl）和 "CSP" 子串的出现次数（cC）。
判断共存情况：如果两种子串不同时存在，不需要任何操作（操作次数为 0）。
计算最小操作次数：若两种子串同时存在，取两者数量的较小值（mv），最小操作次数为 $⌈min_val / 2⌉$ （即 $(min_val + 1)/ 2$ ，通过整数运算实现向上取整）。

复杂度

时间复杂度：

O (T×n)

，其中 T 是测试用例数量，n 是字符串长度。对于每个字符串，我们只需遍历一次即可完成检查。空间复杂度：

O (1)

，仅使用了常数个额外变量。

代码实现

CPP

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int AIAmHere = 0;
    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        int cl = 0, cC = 0;
        int n = s.size();
        
    
        for (int i = 0; i <= n - 3; ++i) {
            string sub = s.substr(i, 3);
            if (sub == "LGR") {
                cl++;
            } else if (sub == "CSP") { 
                cC++;
            }
        }
        
        int ans = 0;

        if (cl > 0 && cC > 0) {
            int mv = min(cl, cC);
            ans = (mv + 1) / 2; 
        }
        
        cout << ans << endl;

    }
    return 0;
}

~~居然真让我找到了可以写题解的红题~~

题解：P12672 「LAOI-8」近期我们注意到有网站混淆视听

文章操作

题目分析

关键观察：

解题思路

复杂度

代码实现

相关推荐

评论

题解：P12672 「LAOI-8」近期我们注意到有网站混淆视听