L. LOL Lovers - 题解

比赛与标签

比赛: 2023-2024 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred) 标签: strings 难度: *800

题目大意喵~

主人 sama，是这样的~ 我们有一长串排成一排的食物，总共有 $n$ 个。这些食物要么是面包 ('L')，要么是洋葱 ('O')。

我们的任务是，把这串食物切成两段。我拿走从左边开始的连续一段（前缀），我的朋友拿走剩下的部分（后缀）。但是，分食物也要讲基本法，有三个规矩必须遵守呐：

我和朋友都必须至少分到一个食物，也就是说，不能有人空手而归！
我手里的面包数量，必须和朋友手里的面包数量不一样。
我手里的洋葱数量，也必须和朋友手里的洋葱数量不一样。

我们需要找到一个切割点 $k$ （也就是我拿走前 $k$ 个食物），使得这三个条件都能满足。如果有很多种切法，随便输出一种就行啦。如果怎么切都无法满足条件，就输出 $-1$ 哦。

解题思路大揭秘！

这道题目的数据范围非常友好呢， $n$ 最大也只有 200。看到这么小的数据，本猫娘的直觉就告诉我：我们可以试一试所有可能的切法呀！就像小猫咪一个个检查小鱼干一样，总能找到最棒的那条！

我们的切割点 $k$ 可以是 1, 2, 3, ..., 直到 $n-1$ 。为什么是到 $n-1$ 呢？因为题目要求我们俩都至少要有一个食物，所以 $k$ 不能是 0 或者 $n$ 啦。

那么，我们的核心思路就是：遍历所有可能的切割点 $k$ 。

对于每一个可能的 $k$ （从 1 到 $n-1$ ），我们来检查一下它是否满足条件：

计算数量：
- 我拿走了前 $k$ 个食物。我们可以数一数这 $k$ 个食物里有多少个 'L' 和 'O'。
- 朋友拿走了剩下的 $n-k$ 个食物。我们也可以数一数他那部分有多少个 'L' 和 'O'。
检查条件：
- 设我有的面包和洋葱数是 my_L, my_O。
- 设朋友有的面包和洋葱数是 friend_L, friend_O。
- 我们只需要判断 my_L != friend_L 并且 my_O != friend_O 是否成立。
找到答案：
- 如果两个条件都成立，那么恭喜！我们找到了一个完美的切割点 $k$ 。因为题目说随便输出一个就行，所以我们直接输出这个 $k$ 然后就可以结束程序啦。
- 如果我们把所有可能的 $k$ 都试了一遍，还是没有找到满足条件的，那就说明不存在这样的切法，只好遗憾地输出 $-1$ 了。

一个优化的小技巧喵~

每次都重新数朋友那部分的食物数量有点慢。我们可以更聪明一点！

首先，我们花点时间，一次性数完整个字符串里总共有多少个面包 total_L 和洋葱 total_O。

然后，当我们遍历 $k$ 的时候，我们只需要维护我手里的面包 my_L 和洋葱 my_O 的数量。那么朋友手里的数量就可以瞬间算出来啦：

friend_L = total_L - my_L
friend_O = total_O - my_O

这样是不是超级快？每次检查都只需要 O(1) 的时间！整个算法的效率就非常高了。

代码实现喵~

下面就是本猫娘精心准备的AC代码，加了详细的注释，希望能帮到主人 sama 理解哦！

cpp

#include <iostream>
#include <string>
#include <vector>
#include <numeric>

// 这个函数包含了解决问题的核心逻辑喵~
void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    // 首先，我们来数一数整条队伍里总共有多少面包('L')和洋葱('O')的说。
    // 题目保证了至少有一个'L'和一个'O'。
    int total_L = 0;
    int total_O = 0;
    for (char c : s) {
        if (c == 'L') {
            total_L++;
        } else {
            total_O++;
        }
    }

    // 我们要遍历所有可能的分割点 k。
    // k 是我从左边拿走的食物数量。
    // k 的范围是 1 到 n-1，因为题目规定我们俩都至少要拿到一个食物。
    
    // my_L 和 my_O 用来记录我这一部分（前缀）的实时数量。
    int my_L = 0;
    int my_O = 0;
    
    for (int k = 1; k < n; ++k) {
        // 在第 k 步，我们考虑长度为 k 的前缀。
        // 新加入我这部分的食物是索引为 k-1 的那个。
        // 我们更新我这部分的计数。
        if (s[k - 1] == 'L') {
            my_L++;
        } else {
            my_O++;
        }

        // 朋友拿走剩下的食物（后缀）。
        // 我们可以用总数减去我的数量，来得到朋友的数量。
        int friend_L = total_L - my_L;
        int friend_O = total_O - my_O;

        // 现在，检查两个关键条件是否满足：
        // 1. 我的面包数和朋友的面包数不能相同。
        // 2. 我的洋葱数和朋友的洋葱数不能相同。
        if (my_L != friend_L && my_O != friend_O) {
            // 如果两个条件都满足，我们就找到了一个合法的分割点！
            // 题目说找到任何一个就行，所以我们打印第一个找到的答案。
            std::cout << k << std::endl;
            return; // 找到答案就收工回家吃小鱼干啦~
        }
    }

    // 如果循环结束了，说明从 1 到 n-1 都没有找到任何一个合法的分割点 k。
    // 这种情况下，根据题目要求，我们输出 -1。
    std::cout << -1 << std::endl;
}

int main() {
    // 这是一个标准的竞赛编程设置，为了让输入输出快一点喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 调用包含解题逻辑的函数。
    // 这道题只有一个测试用例。
    solve();

    return 0;
}

复杂度分析

时间复杂度: O( $n$ ) 的说。我们首先遍历一次字符串来计算总的 'L' 和 'O' 的数量，这需要 O( $n$ ) 的时间。之后，我们再进行一个循环，最多执行 $n-1$ 次，循环体内部的所有操作（更新计数、计算、比较）都是常数时间 O(1) 的。所以总的时间复杂度就是 O( $n$ ) + O( $n$ ) = O( $n$ )，对于这道题来说是飞快哒！
空间复杂度: O( $n$ ) 的说。我们主要需要空间来存储输入的字符串 $s$ ，它占用了 O( $n$ ) 的空间。我们用到的其他变量（如 total_L, my_L 等）都是常数级别的，占用的空间很小，可以看作是 O(1)。所以总的空间复杂度由字符串决定，是 O( $n$ ) 哦。

知识点与总结

这道题虽然简单，但也是一次很好的练习机会呢！本猫娘总结了几个小知识点：

暴力枚举 (Brute-force Enumeration): 当问题的规模（数据范围）不大时，直接遍历所有可能的情况是一种非常有效且容易实现的策略。不要害怕暴力，要学会分析何时可以使用它！
前缀思想: 我们通过预处理计算总和，然后在遍历时维护一个前缀的计数，从而用 O(1) 的时间推算出后缀的计数。这种 "前缀和" 或 "前缀统计" 的思想在算法题中非常非常常用，主人 sama 一定要掌握哦！
仔细读题: 题目的每一个条件都至关重要。"每个人至少一个" 确定了 $k$ 的范围，"数量不同" 则是我们检查的核心。漏掉任何一个都会导致错误。

希望这篇题解能对主人 sama 有所帮助！如果还有不明白的地方，随时可以再来问我哦。一起加油，成为更厉害的算法大师吧，喵~！

L. LOL Lovers - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路大揭秘！ ​

代码实现喵~ ​

复杂度分析 ​

知识点与总结 ​