[luogu P2391] 白雪皑皑

[luogu P2391] 白雪皑皑

题目背景

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

题目描述

现在有 N 片雪花排成一列。 Pty 要对雪花进行 M 次染色操作,第 i次染色操作中,把第(i*p+q)%N+1 片雪花和第(i*q+p)%N+1 片雪花之间的雪花(包括端点)染成颜色 i。其中 p,q 是给定的两个正整数。他想知道最后 N 片雪花被染成了什么颜色。

输入输出格式

输入格式:

包含 4 行:

N M p q 意义如题中所述。

输出格式:

包含 N 行:

第 i 行表示第 i 片雪花被染成的颜色 c

输入输出样例

输入样例#1: 复制
4
3
2
4
输出样例#1: 复制
2
2
3
0

说明

20%的数据满足:1<=n,m<=1000

40%的数据满足:1<=n<=8000,1<=m<=1000000

80%的数据满足:1<=n<=500000,1<=m<=10000000

100%的数据满足:1<=n<=1000000,1<=m<=10000000

保证 1<=M*p+q,M*q+p<=2*10^9

脑子都不好使了。。。并查集都用不来了。

对于这一题,我们可以把原问题转为做m次修改。

每一次修改,在一个区间内,把没有修改过的位置染上色(即修改)。

然后,最后输出每一个位置分别是哪一种颜色(即哪次修改,也可能为0,表示没有修改)。

妙用并查集,有点链表的味道,用fa[i]表示1~i里面,离i最近的没有被修改过的位置。

然后,对于一次修改,把当前位置修改好了就修改fa[i],一直到修改好为止(或是修改到0)。

由于每个位置最多被修改1次,所以复杂度是O(n)的。最多乘上一个并查集常数。

有个地方还需要探讨一下——就是路径压缩的问题。

对于这题,路径压缩之后有没有影响?

不存在的。我们可以吧点于点的关系看做是树,森林。

那么,事实上,只有根节点才没有被修改过,其他点都是已经修改过的,所以无论关系怎么变化,都不会有影响。

当然,运用并查集就是为了增快查询速度,而且路径压缩是关键。

注意,在更新fa[i]时,直接取i-1或fa[i-1]或get(i-1)就好,因为i这个位置被访问到当且仅当它第一次被更新到。

那么这样,根据定义,fa[i]就是get(i-1)了。

code:

 #pragma GCC optimize(2)
 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 typedef long long LL;
 namespace fastIO {
     inline int read() {
         ,f=; char ch=getchar();
         ') {
             if (ch=='-') f=-f;
             ch=getchar();
         }
         ') {
             x=(x<<)+(x<<)+ch-';
             ch=getchar();
         }
         return x*f;
     }
     ];
     inline void write(int x) {
         ) {
             putchar(');
             return;
         }
         ) {
             x=-x;
             putchar('-');
         }
         ; x; x/=) w[++cnt]=x%;
         );
     }
     inline void newline() {
         putchar('\n');
     }
 }
 namespace OJ{
     void Online_Judge() {
         #ifndef ONLINE_JUDGE
             freopen("in.txt","r",stdin);
             freopen("out.txt","w",stdout);
         #endif
     }
 }
 ;
 int n,m,p,q,fa[N],cov[N];
 inline int get(int x) {
     return fa[x]==x?x:fa[x]=get(fa[x]);
 }
 int main() {
     OJ::Online_Judge();
     using namespace fastIO;
     n=read(),m=read(),p=read(),q=read();
     ; i<=n; ++i) {
         cov[i]=;
         fa[i]=i;
     }
     int l,r;
     for (int i=m; i; --i) {
         l=(i*p+q)%n+,r=(i*q+p)%n+;
         if (l>r) std::swap(l,r);
         for (r=get(r); l<=r; r=get(r)) {
             cov[r]=i;
             fa[r]=r-;
         }
     }
     ; i<=n; ++i) {
         write(cov[i]);
         newline();
     }
     ;
 }
上一篇:基于php-fpm的配置详解[转载]


下一篇:Azure系列2.1.13 —— CloudBlockBlob