L. Controllers - 题解

比赛与标签

比赛: SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred) 标签: binary search, math 难度: *1500

喵喵，题目在说什么呀？

你好呀，指挥官！这道题是说，我们来到了一个古老的游戏世界，喵~。

游戏有 n 个回合，每个回合屏幕上会显示一个 + 号或者 - 号。我们的手柄有两个按钮，上面分别写着数字 a 和 b。

在每个回合，我们必须选择按下一个按钮。如果我们按了写着数字 x 的按钮：

如果屏幕是 + 号，我们的分数就增加 x。
如果屏幕是 - 号，我们的分数就减少 x。

我们的目标是，在所有 n 个回合结束后，让最终的分数恰好等于 0！

现在我们有很多很多个手柄（q 个），每个手柄的 a 和 b 值都不同。对于每一个手柄，我们都要判断一下，用它能不能赢得游戏（也就是让最终分数为0）呢？

简单来说，就是给你一串 + 和 - 的序列，以及 q 对 (a, b)，问每一对 (a, b) 能不能通过合理安排按键，使得最终得分是0，的说。

猫猫的思考小径~

这道题看起来有点复杂，但别怕，让本猫娘带你一步步把它解开，喵~

1. 建立数学模型

首先，我们来数一数 + 和 - 的个数。设 + 号有 p 个，- 号有 m 个。总的回合数 n = p + m。

现在，假设在游戏过程中：

我们在 + 回合按了 p_a 次 a 按钮和 p_b 次 b 按钮。
我们在 - 回合按了 m_a 次 a 按钮和 m_b 次 b 按钮。

那么，最终的总分就是： Score = (p_a * a + p_b * b) - (m_a * a + m_b * b)

我们要让 Score = 0，也就是： p_a * a + p_b * b = m_a * a + m_b * b

这个方程里变量太多啦，不好处理！我们来简化一下。我们知道：

p_a + p_b = p (所有 + 回合的总次数)
m_a + m_b = m (所有 - 回合的总次数)

把 p_b = p - p_a 和 m_b = m - m_a 代入到我们的得分方程里： a * (p_a - m_a) + b * ((p - p_a) - (m - m_a)) = 0a * (p_a - m_a) + b * (p - m - p_a + m_a) = 0a * (p_a - m_a) - b * (p_a - m_a) + b * (p - m) = 0(a - b) * (p_a - m_a) + b * (p - m) = 0

哇！这个方程是不是清爽多啦？我们令 D_a = p_a - m_a， d = p - m，方程就变成了： (a - b) * D_a + b * d = 0

2. 求解与约束

现在我们的目标是，看看能不能找到一对整数 (p_a, m_a) 满足这个方程，并且符合物理意义上的约束。

从方程 (a - b) * D_a = -b * d 我们可以解出 D_a： D_a = -b * d / (a - b) = b * d / (b - a)

这里的 D_a 必须是一个整数，因为 p_a 和 m_a 都是整数。所以，如果 b * d 不能被 b - a 整除，那就肯定无解啦，可以直接说 "NO"。

同时，我们还要考虑一些特殊情况：

如果 p == m，那么 d = 0。此时方程变为 (a - b) * D_a = 0。我们可以让 p_a = p, m_a = m，这样 D_a = 0。也可以让 p_a = 0, m_a = 0，D_a = 0。总之，只要我们对所有 + 回合都按 a，所有 - 回合也都按 a，得分就是 p*a - m*a = (p-m)*a = 0。所以 p == m 时，一定有解！
如果 a == b，那么 b - a = 0。如果此时 d != 0，那么 b * d != 0。方程就变成了 0 = 非零数，这显然是不可能的。所以当 a == b 且 d != 0 时，无解。

排除了这些特殊情况后，我们就算出了一个整数 D_a。但这还不够，我们还需要确保能找到符合条件的 p_a 和 m_a。

设我们总共按了 k_a 次 a 按钮，那么 k_a = p_a + m_a。我们现在有两个关于 p_a 和 m_a 的方程：

p_a + m_a = k_a
p_a - m_a = D_a

解这个方程组得到：

2 * p_a = k_a + D_a
2 * m_a = k_a - D_a

因为 p_a 和 m_a 必须是整数，所以 k_a + D_a 和 k_a - D_a 都必须是偶数。这等价于 k_a 和 D_a 的奇偶性必须相同！

同时，p_a 和 m_a 还要满足它们的定义域：

0 <= p_a <= p => 0 <= k_a + D_a <= 2p => -D_a <= k_a <= 2p - D_a
0 <= m_a <= m => 0 <= k_a - D_a <= 2m => D_a <= k_a <= 2m + D_a
0 <= k_a <= n (总共按 a 的次数不能超过总回合数 n)

把这些约束合在一起，k_a 必须满足： max(|D_a|, 0) <= k_a <= min(n, 2p - D_a, 2m + D_a) 由于 k_a = p_a + m_a >= |p_a - m_a| = |D_a|，所以 max(|D_a|, 0) 就是 |D_a|。所以 k_a 的取值范围是 [|D_a|, min(n, 2p - D_a, 2m + D_a)]。

3. 最终的判断

我们的任务就是判断，是否存在一个整数 k_a，它既在上面这个范围里，又和 D_a 有相同的奇偶性。

这很简单！我们先计算出 k_a 的下界 lower = |D_a| 和上界 upper = min(n, 2p - D_a, 2m + D_a)。如果 lower > upper，说明范围是空的，肯定无解。否则，我们找到这个范围里最小的、且和 D_a 奇偶性相同的数。这个数就是 lower（如果奇偶性匹配）或者 lower + 1（如果不匹配）。如果这个找到的数不大于 upper，那就说明存在这样的 k_a，我们就能赢！回答 "YES"。否则，就是 "NO" 啦。

总结一下步骤：

统计 + 的数量 p 和 - 的数量 m。计算 d = p - m。
对于每个查询 (a, b):
如果 d == 0，输出 "YES"。
如果 a == b (此时 d != 0)，输出 "NO"。
计算 num = b * d, den = b - a。如果 num 不能被 den 整除，输出 "NO"。
计算 D_a = num / den。
计算 k_a 的可行范围 [lower, upper]。
如果 lower > upper，输出 "NO"。
检查在 [lower, upper] 中是否存在与 D_a 奇偶性相同的整数。如果存在，输出 "YES"，否则输出 "NO"。

搞定！是不是思路清晰多啦？喵~

看我的代码魔法！

cpp

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

void solve() {
    // 使用快速 IO，让程序跑得更快，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    // 1. 统计 '+' 和 '-' 的数量
    int p = 0;
    for (char c : s) {
        if (c == '+') {
            p++;
        }
    }
    int m = n - p;
    // d = p - m，这是我们推导出的关键值
    long long d = p - m;

    int q;
    std::cin >> q;
    while (q--) {
        long long a, b;
        std::cin >> a >> b;

        // 2. 处理特殊情况
        // 如果 '+' 和 '-' 数量相等，d=0，总能构造出0分
        if (d == 0) {
            std::cout << "YES\n";
            continue;
        }
        
        // 如果 a 和 b 相等，但 d != 0，总分永远是 d*a != 0，不可能为0
        if (a == b) {
            std::cout << "NO\n";
            continue;
        }
        
        // 3. 根据公式 D_a = b*d / (b-a) 进行计算
        long long num = b * d;
        long long den = b - a;

        // D_a 必须是整数，所以 num 必须能被 den 整除
        if (num % den != 0) {
            std::cout << "NO\n";
            continue;
        }

        long long D_a = num / den;

        // 4. 计算 k_a 的可行范围 [lower_k_a, upper_k_a]
        // lower_k_a = |D_a|
        long long lower_k_a = std::abs(D_a);
        // upper_k_a = min(n, 2p - D_a, 2m + D_a)
        long long upper_k_a = std::min({(long long)n, 2LL * p - D_a, 2LL * m + D_a});
        
        // 如果下界大于上界，说明范围无效，无解
        if (lower_k_a > upper_k_a) {
            std::cout << "NO\n";
            continue;
        }

        // 5. 检查是否存在一个 k_a 满足奇偶性约束
        // 找到范围中第一个和 D_a 奇偶性相同的数
        long long start_k_a = lower_k_a;
        if ((start_k_a % 2 + 2) % 2 != (D_a % 2 + 2) % 2) {
            start_k_a++;
        }
        
        // 如果这个数在范围内，那么就存在解
        if (start_k_a <= upper_k_a) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
    }
}

int main() {
    solve();
    return 0;
}

时间与空间的魔法消耗

时间复杂度: O(N + Q) 的说。
- 首先，我们需要 O(N) 的时间来遍历一次字符串 s，计算出 p 和 m 的值。
- 之后，我们有一个循环处理 Q 次查询。在循环内部，我们只进行了一些常数时间的算术运算和比较。所以每个查询是 O(1) 的。
- 总的时间复杂度就是 O(N + Q)，非常高效呢！
空间复杂度: O(N) 的说。
- 我们需要一个 O(N) 的空间来存储输入的字符串 s。除此之外，我们只用了一些常数个变量，所以空间主要消耗在输入上。

小猫咪的知识宝库

这道题真有趣，它把一个游戏策略问题变成了一个优美的数学问题，喵~

数学建模是关键：解题的第一步，也是最重要的一步，就是把问题的条件和目标用数学语言表达出来。一旦我们推导出 (a - b) * (p_a - m_a) + b * (p - m) = 0 这个核心方程，问题就解决了一大半啦！
约束条件分析：解出方程只是开始，我们还要回头看这些变量的物理意义。p_a, m_a 这些都是次数，必须是非负整数，并且不能超过各自的总数 p 和 m。这些约束条件最终帮我们确定了解的可行范围。
奇偶性分析：k_a 和 D_a 必须同奇偶，这是一个非常巧妙的隐藏条件，来源于 p_a 和 m_a 必须是整数。在处理整数问题时，奇偶性是个非常有用的工具哦！
注意边界情况：像 p == m 或者 a == b 这样的特殊情况，提前处理不仅能简化逻辑，还能避免除以零这样的运行时错误。养成检查边界的好习惯，代码才会更健壮，的说！

希望这篇题解能帮到你，指挥官！继续加油，在算法的世界里探索更多乐趣吧，喵~！

L. Controllers - 题解 ​

比赛与标签 ​

喵喵，题目在说什么呀？ ​

猫猫的思考小径~ ​

1. 建立数学模型 ​

2. 求解与约束 ​

3. 最终的判断 ​

看我的代码魔法！ ​

时间与空间的魔法消耗 ​

小猫咪的知识宝库 ​