浙江农林大学蓝桥杯程序设计竞赛校选拔赛 E-谁是天选之人

众所周知下棋是一个运气游戏，不过好像也是有规律可循的。

Graceful smiling cookies给它的n个棋子标序号，他决定以这些序号决定谁是天选。

最开始每个棋子标号都是0.

它要进行m次标序号。

  第i次标序号，它会将第（i X a+b）%n +1个棋子和第(i X b + a)%n +1个棋子之间的棋子都标上序号i。我会告诉你a和b的值，你可以告诉我最后每个棋子的颜色吗？

输入描述:

一行四个整数 1=<n<=1e6 ,  1=<m<=1e7 ,  a  ,  b

保证：1<=m*a+b, m*b+a<=int最大值

输出描述:

n行，每行表示第i个棋子的标号

示例1

输入

复制

3 2 1 3

输出

复制

0
2
2

解题思路： 

 并查集，后面找到的区间肯定会把前面的给覆盖掉，所以我们倒着循环，遇到已经改变过的部分不改变。用数组记录当前区段最右边改变的点，从这个部位开始变化。

#include<bits/stdc++.h>
using namespace std; 
const int MAXN = 1e6 + 5;
int fa[MAXN], A[MAXN];
int get(int x)
{
    if (fa[x] == x) return x;
    return fa[x] = get(fa[x]);
}
 
int main(void) 
{
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    for (int i = 1; i <= n + 1; ++i) 
    {
        fa[i] = i;
    }
    for (int i = m; i > 0; --i) 
    {
        int l = (i * a + b) % n + 1;
        int r = (i * b + a) % n + 1;
        if (l > r) swap(l, r);
        int x = get(l);
        while (x <= r) 
       {
            fa[x] = x + 1;
            A[x] = i;
            x = get(x);
        }
    }
    for (int i = 0; i < n; ++i) 
    {
        printf("%d\n", A[i + 1]);
    }
 
    return 0;
}