本文共 1337 字，大约阅读时间需要 4 分钟。
挺有意思的一道题，能考出并查集思想也是不错的
由于后面会覆盖前面，因此我们可以倒序处理颜色
令nxt[i]表示i后第一个未被染色的点，这样每个点只被染一次，那么处理每个询问时，我们暴力跳nxt处理,O(nm)
考虑在跳nxt时，有一些部分是染上色的，可以被一步跳过的，这个步骤就很像并查集中的路径压缩
因此改暴力跳为并查集式的递归，O(n+m)
#include #include #include #include #include #include #include using namespace std;#define O(x) cout << #x << " " << x << endl;#define O_(x) cout << #x << " " << x << " ";#define B cout << "breakpoint" << endl;#define clr(a) memset(a,0,sizeof(a));#define pii pair #define mp make_pairtypedef double db;typedef long long ll;inline int read(){ int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (ans *= 10) += ch - '0'; ch = getchar(); } return ans * op;}const int maxn = 1e6 + 5;int nxt[maxn],n,m,p,q;int l,r;int co;int col[maxn];int find(int x) { while(col[x]) x = nxt[x]; if(x < l) return x; col[x] = co; return x == l ? nxt[x] = l - 1 : nxt[x] = find(x - 1); }int main(){ n = read(),m = read(),p = read(),q = read(); for(int i = m;i >= 1;i--) { co = i; l = (i * p + q) % n + 1,r = (i * q + p) % n + 1; if(l > r) swap(l,r); //O(l) ;O(r); find(r); } for(int i = 1;i <= n;i++) printf("%d\n",col[i]);}
转载于:https://www.cnblogs.com/LM-LBG/p/10945087.html