当前位置：首页 > news >正文

并查集(非连通性问题)——# P2391 白雪皑皑

news 2026/3/26 22:06:15

P2391 白雪皑皑

题目背景

“柴门闻犬吠，风雪夜归人”，冬天，不期而至。千里冰封，万里雪飘。空中刮起了鸭毛大雪。雪花纷纷，降落人间。美能量星球（pty 在 spore 上的一个殖民地）上的人们被这美景所震撼。但是 pty 却不高兴，他不喜欢白色的世界，他觉得这样太单调了。所以他想对雪花进行染色，让世界变得多彩些。

题目描述

现在有nnn片雪花排成一列。 pty 要对雪花进行mmm次染色操作，第iii次染色操作中，把第((i×p+q) mod n)+1((i\times p+q)\bmod n)+1((i×p+q)modn)+1片雪花和第((i×q+p) mod n)+1((i\times q+p)\bmod n)+1((i×q+p)modn)+1片雪花之间的雪花（包括端点）染成颜色iii。其中p,qp,qp,q是给定的两个正整数。他想知道最后nnn片雪花被染成了什么颜色。没有被染色输出000。

输入格式

输入共四行，每行一个整数，分别为n,m,p,qn,m,p,qn,m,p,q，意义如题中所述。

输出格式

输出共nnn行，每行一个整数，第iii行表示第iii片雪花的颜色。

输入输出样例 #1

输入 #1

4 3 2 4

输出 #1

2 2 3 0

说明/提示

对于20%20\%20%的数据满足：n,m≤1000n,m\leq 1000n,m≤1000。
对于40%40\%40%的数据满足：n≤8000n\leq 8000n≤8000，m≤106m\leq 10^6m≤106。
对于80%80\%80%的数据满足：n≤5×105n\leq 5\times 10^5n≤5×105，m≤107m\leq 10^7m≤107。
对于100%100\%100%的数据满足：1≤n≤1061\leq n\leq 10^61≤n≤106，1≤m≤1071\leq m\leq 10^71≤m≤107。

保证1≤m×p+q,m×q+p≤2×1091\leq m\times p+q,m\times q+p\leq 2\times 10^91≤m×p+q,m×q+p≤2×109。

代码

#include<bits/stdc++.h>usingnamespacestd;constintMAXN=1e6+5;// 常量名更语义化structSnowflake{intcolor;// 雪花最终染色编号（0表示未染色）intnext;// 以当前位置为起点，首个未染色的位置（路径压缩用）}snow[MAXN];// 并查集查找：找到x位置开始的首个未染色位置，路径压缩优化intfind(intx){if(snow[x].next!=x){snow[x].next=find(snow[x].next);// 路径压缩，直接指向最终未染色位置}returnsnow[x].next;}intmain(){ios::sync_with_stdio(false);// 加速cin/cout，应对1e6量级数据cin.tie(nullptr);intn,m,p,q;// n:雪花总数 m:染色操作数 p/q:随机数参数cin>>n>>m>>p>>q;// 初始化：所有雪花未染色，每个位置的首个未染色位置是自身；n+1作为边界哨兵for(inti=1;i<=n+1;++i){snow[i].color=0;snow[i].next=i;}// 逆序处理染色操作：后执行的操作覆盖先执行的，保证每个位置只染最后一次for(intop=m;op>=1;--op){// 计算当前操作的染色区间 [l, r]，保证1<=l<=r<=nintpos1=((1LL*op*p+q)%n)+1;// 1LL防止乘法溢出intpos2=((1LL*op*q+p)%n)+1;intl=min(pos1,pos2);intr=max(pos1,pos2);// 遍历区间内所有未染色位置：通过find直接跳转到未染色位置，避免重复遍历for(intj=find(l);j<=r;j=find(j)){snow[j].color=op;// 标记为当前操作的颜色（逆序保证是最后一次染色）snow[j].next=j+1;// 染完后，该位置的首个未染色位置指向右侧}}// 输出每个雪花的最终颜色for(inti=1;i<=n;++i){cout<<snow[i].color<<'\n';// '\n'比endl快，避免刷新缓冲区}return0;}