D. Connect the Dots 详细题解

题目回顾

在直线上有 $n$ 个点（编号 $1\sim n$），初始时每个点独立为一个连通分量。 进行 $m$ 次操作：每次给出 $a_i, d_i, k_i$（$1\le d_i\le 10$），选中点：

将这些点两两连通。 求最终的连通分量数量。

一、核心突破口

题目给出关键限制：$\boldsymbol{d_i \le 10}$，这是解题的核心。 直接暴力合并等差数列的点会超时，但利用 $d$ 很小的特点，我们可以用并查集（DSU）+ 状态递推高效合并。

二、关键定义（数组含义）

定义常数：

• $N=2\times10^5+2$（点的最大数量）
• $C=11$（因为 $d\le10$）

数组说明：

1. par[], sz[]：并查集标准数组，父节点和集合大小
2. start_cnt[i][d]：以 $i$ 为起点、步长为 $d$ 的操作数量
3. end_cnt[i][d]：以 $i$ 为终点、步长为 $d$ 的操作数量
4. dp[i][d]：记录点 $i$ 被步长为 $d$ 的活动区间覆盖的层数
5. ind[i][d]：点 $i$ 在步长为 $d$ 的连续区间内，代表的连通分量根节点

三、核心算法思想

1. 操作转化

每次操作不需要暴力合并，只需要：

• 起点 $a$：start_cnt[a][d]++
• 终点 $a+k\cdot d$：end_cnt[end][d]++

2. 递推合并（核心逻辑）

遍历每个点 $i$，遍历每个步长 $d=1\sim10$：

1. 当前层数：$dp[i][d] = start_cnt[i][d] - end_cnt[i][d]$
2. 若前一个步长点 $i-d$ 存在，且 $dp[i-d][d]>0$：
   • 说明 $i$ 和 $i-d$ 在同一个等差数列区间内
   • 直接合并 $ind[i-d][d]$ 和 $i$
   • 继承 $ind[i-d][d]$ 作为当前代表元
   • 层数累加：$dp[i][d] += dp[i-d][d]$

3. 为什么正确？

只要 $dp[i-d][d]>0$，说明 $i-d$ 正处于一个步长为 $d$ 的连续合并区间中，那么 $i$ 也属于这个区间，必须和区间内的点连通。 利用 $d\le 10$，总复杂度仅 $O(n\times10)$，完美通过题目限制。

四、标程代码逐行解析

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 2e5+2;
const ll C = 10 + 1;  // d <= 10，所以开 1~10

// 并查集
vector<ll> par(N), sz(N, 0);
// dp：覆盖层数  ind：连通代表元
// start_cnt/end_cnt：起点终点计数
vector<vector<ll>> dp(N, vector<ll> (C, 0)), ind(N, vector<ll> (C, 0));
vector<vector<ll>> start_cnt(N, vector<ll> (C, 0)), end_cnt(N, vector<ll> (C,0));

// 并查集找根
ll find_par(ll a) {
    if (par[a] == a) return a;
    return par[a] = find_par(par[a]);
}

// 并查集合并
void unite(ll a, ll b){
    a = find_par(a), b = find_par(b);
    if (a == b) return;
    if (sz[b] > sz[a]) swap(a, b);
    sz[a] += sz[b];
    par[b] = a;
}

// 每组测试用例重置数组
void reset(ll n) {
    for (ll i = 1; i <= n; i++) {
        par[i] = i;
        sz[i] = 1;
        for (ll j = 1; j < C; j++) {
            dp[i][j] = start_cnt[i][j] = end_cnt[i][j] = 0;
            ind[i][j] = i;
        }
    }
}

void solve() {
    ll n, m, a, d, k;
    cin >> n >> m;
    reset(n);
    
    // 只记录起点和终点，不暴力合并
    for (ll i = 0; i < m; i++) {
        cin >> a >> d >> k;
        start_cnt[a][d]++;
        end_cnt[a + k * d][d]++;
    }

    // 核心递推：遍历每个点，每个步长 d
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j < C; j++) {
            // 当前覆盖层数 = 起点数 - 终点数
            dp[i][j] = start_cnt[i][j] - end_cnt[i][j];
            
            // 如果前一个步长点存在
            if (i-j < 1) continue;
            
            // 前一个点在有效区间内 → 合并
            if (dp[i-j][j]) {
                unite(ind[i-j][j], i);
                ind[i][j] = ind[i-j][j];  // 继承代表元
                dp[i][j] += dp[i-j][j];   // 继承层数
            }
        }
    }

    // 统计连通分量数量（根节点数量）
    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        if (find_par(i) == i) ans++;
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); // 加速输入输出
    ll t;
    cin >> t;
    while (t--) solve();
}

五、算法流程总结

1. 输入操作：只记录每个步长 $d$ 的起点和终点。
2. 递推遍历：
   • 对每个点 $i$ 和步长 $d$，计算当前覆盖层数。
   • 若 $i-d$ 处于覆盖状态，直接合并 $i$ 与 $i-d$ 的代表元。
3. 统计答案：遍历所有点，统计根节点数量。

六、复杂度分析

• 时间复杂度：$\boldsymbol{O(t \cdot (n+m) \cdot 10)}$
• 空间复杂度：$\boldsymbol{O(n \cdot 10)}$
• 完全满足 $n,m\le 2\times10^5$ 的限制

七、样例验证（第一个样例）

输入：

10 2
1 2 4 → 点 1,3,5,7,9
2 2 4 → 点 2,4,6,8,10

递推后：

• 所有奇数点连通
• 所有偶数点连通 最终连通分量 = $2$，与样例输出一致。

总结

1. 核心利用：$d_i\le 10$，采用递推避免暴力合并。
2. 关键思路：用 dp 记录区间覆盖，用 ind 记录连通代表元。
3. 高效合并：仅遍历 $n\times10$ 次，并用并查集维护连通性。
4. 标准答案：代码与标程完全一致，可直接AC。