欢迎大家访问我的算法提高课补全计划!算法提高课补全计划。里面包括提高课里的题目以及我补充的例题。欢迎点赞收藏。
题目描述
现在有 $n$ 片雪花排成一列。 pty 要对雪花进行 $m$ 次染色操作,第 $i$ 次染色操作中,把第 $((i\times p+q)\bmod n)+1$ 片雪花和第 $((i\times q+p)\bmod n)+1$ 片雪花之间的雪花(包括端点)染成颜色 $i$。其中 $p,q$ 是给定的两个正整数。他想知道最后 $n$ 片雪花被染成了什么颜色。没有被染色输出 $0$。
对于 $100\%$ 的数据满足:$1\leq n\leq 10^6$,$1\leq m\leq 10^7$。
解法:并查集。
这是一道倒序染色结合并查集的题目。由于后面染上的颜色会覆盖前面染上的颜色,所以可以倒序考虑,先染后面的颜色,再染前面的颜色。后面染上的颜色一定不会被前面的覆盖。
设 $fa_i$ 表示 $i$ 及后面第一个还没有被染上色的点。
每次只需要暴力地,从 $l$ 开始,不停的找没有染过色的点并且染色,一直找到 $r$ 为止。
这样看起来很暴力,但是时间复杂度却是正确的。
这里可以感性理解一下:每个点最多只会被访问一次并且染一次,所以复杂度是 $O(n)$ 的。
具体实现细节可以看代码。
#include <iostream>
#include <cstring>
#include <cstdio>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
using namespace std;
const int N = 1000010;
int n, m, p, q;
int fa[N], c[N];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int main() {
scanf("%d%d%d%d", &n, &m, &p, &q);
rep(i, 1, n + 1) fa[i] = i;
for (int i = m; i >= 1; i -- ) {
int l = (1ll * i * p % n + q) % n + 1;
int r = (1ll * i * q % n + p) % n + 1;
if (l > r) swap(l, r); int it = find(l);
while (it <= r) {
c[it] = i; fa[it] = it + 1;
it = find(it + 1);
}
} rep(i, 1, n) printf("%d\n", c[i]);
}