Moe's CF Life

Appearance

[D. Moving Dots] - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 851 (Div. 2) 标签: binary search, brute force, combinatorics, math, two pointers 难度: *2000

题目大意喵~ ​

主人你好呀~ 这是一道关于数轴上小点点移动的有趣问题！(ฅ'ω'ฅ)

我们有 n 个坐标各不相同的小点点。对于这 n 个点构成的、所有大小至少为2的子集，我们都要玩一个游戏：

  1. 在一个子集里，所有点同时以相同的速度开始移动。
  2. 每个点都会朝向离它最近的另一个点移动。如果有两个点到它的距离一样近，它会选择向左移动。
  3. 当两个或多个点相遇（坐标相同）时，它们就会停下来。
  4. 游戏的结果，就是最终所有点停下来后，形成的稳定坐标点的数量。

我们的任务是，计算所有这些子集的游戏结果的总和，并对 10^9 + 7 取模。

举个栗子，如果子集是 {1, 5, 6, 10}，那么：

  • 点 5 和点 6 会互相靠近并相遇。
  • 点 1 会一直向右移动，最终也加入它们。
  • 点 10 会一直向左移动，最终也和大家汇合。 所以它们最后会停在同一个地方，游戏结果是 1。

如果子集是 {1, 3, 5, 11, 15}，那么：

  • 点 1, 3, 5 会形成一个集群，最终停在 2。
  • 点 11, 15 会形成另一个集群，最终停在 13。 这两个集群永远不会相遇，所以游戏结果是 2。

解题思路喵！ ​

这个问题要求我们对所有子集计算结果并求和，直接模拟所有子集肯定是不行的啦，2^n 的数量级太可怕了！(>ω<) 所以我们需要换个思路，从贡献的角度来思考。

我们要计算的是 ∑ (所有大小≥2的子集 S) Result(S)。

Result(S) 是子集 S 最终形成的稳定点的数量，也就是“点群”的数量。一个点群就是一堆最终会汇集到一起的点。一个子集会被分成若干个这样的点群，它们内部会合并，但不同点群之间永远不会相遇。

那么，什么时候一个子集会分裂成多个点群呢？当子集里存在一个“断点”时！假设我们把子集中的点排好序 p_1, p_2, ..., p_k。如果在 p_m 和 p_{m+1} 之间发生了分裂，那一定是因为 p_m 向左移动，而 p_{m+1} 向右移动，它们之间的距离越来越大，导致它们所属的点群永远无法相遇。

所以，一个子集的 Result(S) 就等于 1 + (S中的分裂点数量)。

我们的总和就变成了： ∑ Result(S) = ∑ (1 + 分裂点数量) = ∑ 1 + ∑ (分裂点数量)

∑ 1 就是大小至少为2的子集数量，即 2^n - n - 1。但这个思路还是太复杂了，因为它需要考虑每个子集内部所有相邻点对。

让我们再换个角度！(ง •̀_•́)ง 总和 ∑ Result(S) 其实就是所有子集中出现的所有点群的总数量。 ∑ Result(S) = ∑ (对所有子集S) ∑ (对S中的每个点群G) 1 我们可以交换求和顺序： = ∑ (对所有可能的点群G) (G出现的次数)

这个“所有可能的点群”还是太抽象了。但是这个思路是正确的：把求和的对象从“子集”变成“点群”。

我们可以用一个“** canonical representation（标准表示）**”来唯一地识别每一个点群。一个点群最终会汇集到一点，我们可以认为这个点群是由某个核心部分“生长”而来的。

让我们来定义一个非常特殊的组合：“孤立相遇点对”。对于原始数组中的一对点 (x_i, x_j)（i < j），我们来数一数，在多少个子集 S 中，它们满足以下条件：

  1. x_i 和 x_j 都在 S 中。
  2. 在 (x_i, x_j) 的开区间内，没有其他 S 中的点。
  3. 在 S 中，x_i 的最近邻是 x_j，因此 x_i 向右移动。
  4. 在 S 中，x_j 的最近邻是 x_i，因此 x_j 向左移动。

为了满足第3和第4点，设 d = x_j - x_i。

  • 对于 x_i，S 中任何在它左边的点 x_k (k<i)，都必须满足 x_i - x_k > d。
  • 对于 x_j，S 中任何在它右边的点 x_k (k>j)，都必须满足 x_k - x_j >= d。（这里是 >= 是因为如果距离相等，x_j 会优先向左移动，符合我们的要求）。

满足这些条件的点，我们称之为“遥远的”点。不满足的称为“靠近的”点。 对于固定的 (i, j)，我们可以确定哪些点是“遥远的”。这些“遥远的”点可以任意选择加不加入子集 S，而 x_i 和 x_j 必须加入，所有“靠近的”点以及 (x_i, x_j) 之间的点都不能加入。

这样，对于每一对 (i, j)，我们都能算出一个贡献值，即 2^(遥远点的数量)。这个值代表了能形成以 (x_i, x_j) 为核心的“孤立相遇点对”的子集数量。

神奇的地方来啦：所有子集的游戏结果总和，恰好就等于所有点对 (i, j) 的这种贡献值之和！∑ Result(S) = ∑_{0≤i<j<n} (以 (x_i, x_j) 为核心的孤立相遇子集数量)

这背后有深刻的组合数学原理，即每个可能的点群都可以被唯一地和一个这样的“核心对” (i, j) 关联起来。我们通过计算这些核心对的贡献，就恰好把所有点群不重不漏地数了一遍。

算法实现:

  1. 预计算 2 的幂次，方便之后使用。
  2. 遍历所有点对 (x_i, x_j)，其中 i < j。
  3. 对于每个点对，计算 d = x_j - x_i。
  4. 找到在 x_i 左边和 x_j 右边的“遥远点”的数量。
    • 左边遥远点：x_k (k < i) 满足 x_i - x_k > d。
    • 右边遥远点：x_k (k > j) 满足 x_k - x_j >= d。
  5. 这个数量可以用二分查找在 O(log n) 时间内找到。但我们可以做得更好！
  6. 双指针优化：我们固定 i，然后遍历 j 从 i+1 到 n-1。
    • 当 j 增大时，d = x_j - x_i 也增大。
    • x_i - d 会减小，所以左边“靠近”的点的范围会扩大，分界线 left 指针只会向左移动（或不动）。
    • x_j + d 会增大，所以右边“靠近”的点的范围也会扩大，分界线 right 指针只会向右移动（或不动）。
    • 这样，对于每个 i，我们用两个指针 left 和 right 可以在均摊 O(n) 的时间内处理所有的 j。
  7. 总的时间复杂度就从 O(n^2 log n) 优化到了 O(n^2)。

现在，我们可以自信地写下代码啦！喵~

代码实现喵~ ​

cpp
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    int x[n];
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }
    // 虽然题目说坐标是递增的，但好习惯是再排一下序~
    sort(x, x + n);

    // 预计算2的幂，MOD一下防止溢出
    ll two[n + 1];
    two[0] = 1;
    for (int i = 1; i <= n; i++) {
        two[i] = (two[i - 1] * 2) % mod;
    }

    ll ans = 0;
    // 遍历所有可能的点对 (i, j) 作为我们分析的核心
    for (int i = 0; i < n; i++) {
        // left 指针表示在 i 左侧，满足 x[i] - x[k] <= d 的最左边的点的下标
        // right 指针表示在 j 右侧，满足 x[k] - x[j] < d 的最右边的点的下标
        int left = i;
        int right = i; // right 指针会随着 j 的移动而更新

        for (int j = i + 1; j < n; j++) {
            int d = x[j] - x[i];

            // 更新 left 指针
            // 当 j 增加时, d 增加, x[i] - d 减小
            // 所以 left 只会向左移动，不会向右，这是双指针优化的关键
            while (left > 0 && x[i] - x[left - 1] <= d) {
                left--;
            }

            // 更新 right 指针
            // 当 j 增加时, d 增加, x[j] + d 增加
            // 所以 right 只会向右移动，不会向左
            // 注意这里的 right 是跟着 j 走的，它从上一个 j 的位置继续探索
            while (right < n - 1 && x[right + 1] - x[j] < d) {
                right++;
            }
            
            // left 是 i 左边第一个不满足 x[i]-x[k] > d 的点的下标
            // 所以 [0, left-1] 都是“遥远的”点，共 left 个
            // right 是 j 右边最后一个满足 x[k]-x[j] < d 的点的下标
            // 所以 [right+1, n-1] 都是“遥远的”点，共 n - 1 - right 个
            // 总共有 left + (n - 1 - right) 个遥远点可以自由选择
            // 贡献就是 2 的这么多次幂
            ans = (ans + two[left + n - 1 - right]) % mod;
        }
    }

    cout << ans << endl;
    return 0;
}

复杂度分析的说 ​

  • 时间复杂度: O(n^2) 的说。我们有两层循环，外层是 i 从 0 到 n-1，内层是 j 从 i+1 到 n-1。里面的两个 while 循环，left 指针在整个外层循环中最多移动 n 次，right 指针也是最多移动 n 次。所以内层 j 循环的均摊复杂度是 O(1)，总复杂度就是 O(n^2) 啦。
  • 空间复杂度: O(n) 的说。我们主要用了一个数组 two 来存储2的幂，大小为 n+1，所以空间复杂度是 O(n)。

知识点与总结喵 ​

这真是一道把人绕得团团转，但想通了就豁然开朗的题目呢！(≧▽≦)

  1. 贡献法思想: 当题目要求对所有子集求和时，直接枚举子集是行不通的。一个强大的武器就是“贡献法”，即切换求和主体。我们不再问“每个子集的结果是多少”，而是问“每个元素/元素对/结构对最终总和的贡献是多少”。

  2. 组合计数与标准表示: 问题的核心是 ∑ Result(S)，也就是对所有点群计数。我们通过定义一个“孤立相遇点对”作为每个点群的“标准表示”，成功地将问题转化为了对这些标准表示进行计数，从而避免了重复和遗漏。

  3. 双指针优化: 在计算每个点对 (i, j) 的贡献时，我们发现寻找“遥远点”的边界具有单调性。当 i 固定，j 增大的时候，left 和 right 指针的移动方向是固定的。这正是使用双指针优化，将 O(log n) 的查找操作优化为均摊 O(1) 的绝佳场景。

  4. 注意细节: 解题时要特别小心不等式的符号（<= vs <），这往往和题目中的“平局向左”规则息息相关。正确地推导出“遥远点”的判断条件是解题的关键。

希望这篇题解能帮助到你哦！如果还有不明白的地方，随时可以再来问我！一起加油，干掉更多难题吧！喵~ (ฅ^•ﻌ•^ฅ)

Released under the MIT License.

Copyright © 2024-present Moe