首页 > 代码库 > DS x
DS x
数据结构课后题整理....只会一个是什么鬼....
染色问题：
线段树? 功能太强大了! 我们并不需要那么多的功能
运用并查集！！！
将相同的并为一段
BZOJ 2375(讲真我没找到这个题在哪里...)
(其实是因为我没有权限号啦~)
题目大概是这样的:
小t非常喜爱画画,但是他还是一个初学者.他最近费尽千辛万苦才拜到已仙逝的达.芬奇为师(神仙?妖怪?谢谢).
达.芬奇果然是画鸡蛋长大的,让小t一入门就拿着一张白纸条疯狂地涂色.
假设纸条被划分成了n个区域,用1~n的整数从左到右顺序编号,达芬奇总共下达了m条指令.
第I条指令是让小t把编号为(I*p+q)mod n+1与(I*q+p)mod n+1(p,q为常整数)之间的区域(连续的一段区域)涂成第I种颜色.
你可以假设达芬奇家中颜料的颜色数足够多(达芬奇是画鸡蛋长大的).
输入格式
文件仅一行，为四个整数n,m,p,q。
输出格式
文件共n行，第i行代表最后第i个格子的颜色。白色编号为0
输入样例
4 3 2 4(假样例....)
输出样例
2
2
3
0
数据范围
20%数据满足：1≤n≤1000，1≤m≤10000
40%数据满足：1≤n≤10000，1≤m≤100000
100%数据满足：1≤n≤1000000，1≤m≤10000000;1≤m*p+q，m*q+p≤231-1
/*思路+小技巧*/
因为一开始染好的色，如果后来也将其染色，那么他以前染过的颜色便会被覆盖，所以我们大可以不必从前往后进行染色可以考虑从后往前进行，
但是这样做所扫过的还是每个区间的长度，所以还需要进行优化!
那么怎么优化呢?
首先考虑bool数组，记录下来是否被染过色，如果染过就跳过，但是这样做还是全部都扫过一遍，在复杂度上是没有什么本质上的变化的
所以划掉
接下来我们需要考虑的是并查集的性质，以及考虑其父亲结点，……
正确的思路是这样的:
一开始先将父结点设置为自己(并查集~)
将被染色的结点的父亲结点都手动设置为该染色区间的最后一个的父结点，然后将接下来再次染色的循环从要被染色的结点的父亲结点开始。
因为没有染过色的结点的父亲结点一定是自己，但是染过色的的父亲结点却不是自己,是已经染色的区间的最后,会直接蹦到没有被染色的地方!
所以可以将for循环染色的开始设置为这个结点的父亲结点，限制条件是当前长度小于被染色区间的最右边(及当前被染色区间最后一个结点)，下一个变成的是当前的结点的父亲的下一个结点的父结点，以此循环...
所以遇到这种题我们需要考虑的就是:尽量不重复刷,(因为只需要知道最后颜色状态).
代码如下(其他的就是并查集的操作):
for (int a=m;a>=1;a--) //逆序{ for (int b=getf(l[a]);b<=r[a];b=getf(b+1)) //如上面的解释 { if (!color[b]) //如果没有被染色 { color[b]=1;//标记 ans[b]=a;//记录答案 f[getf(b)]=getf(r[a]);//进行合并 } }}
完整代码:(已经经过检验^_^请放心食用)
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <string> 6 7 using namespace std; 8 9 const int M = 1000002;10 int n,m,p,q;11 int f[M];12 bool color[M];13 int ans[M];14 15 inline int read()16 {17 int x=0,f=1;18 char ch=getchar();19 20 while(ch<‘0‘||ch>‘9‘)21 {22 if(ch==‘-‘)f=-1;23 ch=getchar();24 }25 26 while(ch>=‘0‘&&ch<=‘9‘)27 {28 x=10*x+ch-‘0‘;29 ch=getchar();30 }31 32 return x*f;33 }34 35 inline int getf(int x)36 {37 return f[x] == x ? x : f[x] = getf(f[x]);38 }39 40 int main()41 {42 n=read();43 m=read();44 p=read();45 q=read();46 for(int i=1;i<=n+1;i++) f[i]=i; //因为有可能会蹦到n+1位置 47 for(int i=m;i>=1;i--)48 {49 int l=(i*p+q)%n+1,r=(i*q+p)%n+1; //题目的变态要求... 50 if(l>r) swap(l,r); //可能会出现"左端点">"右端点"的情况 51 for(int j=getf(l);j<=r;j=getf(j+1))52 {53 if(!color[j]) //如果没有被染色54 {55 color[j]=1; //进行染色56 f[getf(j)]=getf(r); //将当前被染色的父结点手动设置到最后一个的父结点 57 // f[getf(j)]=getf(j+1); //在网上是有人这样写的,那样比较快一些!但是我没有理解... 58 ans[j]=i; //记录答案 59 }60 // if(getf(1) == n+1) break; //注意当所有位置全部染色后及时退出61 }62 }63 64 for(int i=1;i<=n;i++) printf("%d\n",ans[i]);65 66 return 0;67 }
End.
DS x