【Codeforces】CF 2020 D

Connect the Dots

#动态规划 #并查集 #枚举

题目描述

One fine evening, Alice sat down to play the classic game “Connect the Dots”, but with a twist.

To play the game, Alice draws a straight line and marks $n$ points on it, indexed from $1$ to $n$. Initially, there are no arcs between the points, so they are all disjoint. After that, Alice performs $m$ operations of the following type:

• She picks three integers $a_i$, $d_i$ ($1\le d_i\le 10$), and $k_i$.
• She selects points $a_i,a_i+d_i,a_i+2d_i,a_i+3d_i,\dots ,a_i+k_i\cdot d_i$ and connects each pair of these points with arcs.

After performing all $m$ operations, she wants to know the number of connected components${}^{†}$ these points form. Please help her find this number.

${}^{†}$ Two points are said to be in one connected component if there is a path between them via several (possibly zero) arcs and other points.

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^5$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1\le n\le 2\cdot 10^5$, $1\le m\le 2\cdot 10^5$).

The $i$-th of the following $m$ lines contains three integers $a_i$, $d_i$, and $k_i$ ($1\le a_i\le a_i+k_i\cdot d_i\le n$, $1\le d_i\le 10$, $0\le k_i\le n$).

It is guaranteed that both the sum of $n$ and the sum of $m$ over all test cases do not exceed $2\cdot 10^5$.

输出格式

For each test case, output the number of connected components.

样例 #1

样例输入 #1

3
10 2
1 2 4
2 2 4
100 1
19 2 4
100 3
1 2 5
7 2 6
17 2 31

样例输出 #1

2
96
61

解法

解题思路

首先容易发现，如果以$d$的速度经过了点$x$，那么下次再以$d$的速度经过这个点的时候，就可以直接跳到最后了，无需重复操作。

发现$d\le 10$，因此可以直接开$d$个并查集，来维护每个速度$d$跳过的节点，将它们存入一个联通块内。

最后，我们还需要将同一个点的不同速度$d$的联通块再次合并为新的联通块，这里再开一个并查集维护，最终答案就是这个并查集的联通分量了。

代码

const int N = 2e5 + 10;int fa[N][12];
int p[N];
int n, q;void init() {for (int i = 1; i <= n; ++i) {p[i] = i;for (int j = 1; j <= 10; ++j) {fa[i][j] = i;}}
}int find(int x, int y) {return fa[x][y] = fa[x][y] == x ? x : find(fa[x][y], y);
}int find(int x) {return p[x] = p[x] == x ? x : find(p[x]);
}void solve() {std::cin >> n >> q;init();int vis[12] = {};while (q--) {int x, d, k;std::cin >> x >> d >> k;vis[d] = 1;for (int i = 1; i <= k; ++i) {int u = find(x + i * d, d);int px = find(x, d), py = find(u, d);fa[px][d] = py;i = (u - x) / d; }}std::set<int>st;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= 10; ++j) {if (vis[j]) {int px = find(find(i, j)), py = find(i);p[px] = py;}}}for (int i = 1; i <= n; ++i) {st.insert(find(i));}int res = st.size();std::cout << res << "\n";
}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t = 1;std::cin >> t;while (t--) {solve();}
}