首页 > 代码库 > NOIp模拟赛 旅游
NOIp模拟赛 旅游
很神奇的一道题，金策大爷给的题解：
什么叫神犇什么叫蒟蒻？
IOI冠军的一句基本相同让我思考了一下午。
看完了题解我就想都没想开始用遍历二分图搞，但是搞到了65分后就总是会WA掉7组。
然后仔细的看了看std，位运算上对几处做了常数上的优化，读起来异常麻烦，到最后看懂他在干什么了。但是总是不理解。
下午浪费了两节英语课思考原理，总之想明白了。
我简单说一下我的想法。
首先考虑如果一条路径的所有边权的gcd为$d$,那么不管正着走反着走或者绕上几圈，其总路径和一定为$kd$,$k$为任意正整数。
这一点学过gcd应该都很好想到。那么很显然的一件事就是如果一张图中两个相通的点，从一个点到另一个点的总路径和也一定为$kd$，$d$为这个连通分量里所有边权的gcd。同样的，如果需要把答案mod$K$,只需要$d=gcd(K,d)$即可，最后的答案一定是$d$或者0。这点转化是这道题的第一步。但不是最重要的一步。
这时候就把问题转化为了从$node_i$到$node_j$是否存在一条路径，使得其总长为$cK$,$c$为任意正整数。如果存在，显然答案为0，如果不存在，那么答案就是$d$。同时，需要提前用并查集判断连通性。
首先，考虑$K$为奇数的情况，在这种情况下，只要两点联通，答案一定为0，因为如果K为奇数，而假设从$node_i$到$node_j$的最短路径为$h$,那么一定存在一个数$b$使得$bh=cK$,如果想到了这点。就能拿到20分的部分分。
然后我们是否应该考虑$K$为偶数的情况？
并不，相对来说有更通用的情况。回到前面，我们已经得出了如果把总路径$modK$,那么一定存在一种方案使得从$node_i$到$node_j$的长度为$d$,这时候如果$K$为$d$的奇数倍，那么显然答案为0。
再思考，既然$d$为这个连通分量里所有边权的gcd，这也就意味着所有边的边权都是$d$的整数倍，也就是说所有边都可以拆成任意整数个边权为$d$的边。而如果存在一个数使得$hd==cK$,那么答案就是0。
那么是否可以把每个点拆为$node_i$和$node_{i+N}$，其中的两个点集之间相连的边的长度是奇数个$d$,而任意一个点集里的点之间的边都是偶数个$d$,这个显然可以用并查集维护。
这时候如果$node_i$和$node_j$位于一个点集，显然其是存在为0的答案。
但是除此之外，还存在特殊的情况。如果从一个点到另一个点既存在奇数个$d$的路径，也存在偶数个$d$的路径。怎么处理？
这时候只需要把这个联通块标记即可，这个连通块的任意两点之间到达的答案均为0。
1 //NOIp 0924 pod 2 //by Cydiater 3 //2016.9.24 4 #include <iostream> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cstdio> 8 #include <queue> 9 #include <map> 10 #include <ctime> 11 #include <cmath> 12 #include <iomanip> 13 #include <algorithm> 14 #include <string> 15 using namespace std; 16 #define ll long long 17 #define up(i,j,n) for(int i=j;i<=n;i++) 18 #define down(i,j,n) for(int i=j;i>=n;i--) 19 #define FILE "pod" 20 const int MAXN=1e6+5; 21 const int oo=0x3f3f3f3f; 22 inline int read(){ 23 char ch=getchar();int x=0,f=1; 24 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 25 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 26 return x*f; 27 } 28 int N,M,Q,LINK[MAXN],len=0,f[MAXN],f2[MAXN],tol[MAXN]; 29 struct edge{ 30 int x,y,next,v; 31 }e[MAXN<<1]; 32 bool OK[MAXN]; 33 namespace solution{ 34 inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;e[len].x=x;} 35 int gcd(int a,int b){return b==0?a:gcd(b,a%b);} 36 int getf(int k){ 37 if(f[k]==k) return k; 38 f[k]=getf(f[k]); 39 return f[k]; 40 } 41 int getf2(int k){ 42 if(f2[k]==k) return k; 43 f2[k]=getf2(f2[k]); 44 return f2[k]; 45 } 46 void merge(int x,int y,int v){ 47 x=getf(x);y=getf(y); 48 if(tol[x]!=0)v=gcd(v,tol[x]); 49 if(tol[y]!=0)v=gcd(v,tol[y]); 50 tol[x]=v;f[y]=x; 51 } 52 int merge2(int x,int y,int v){ 53 if(v==1){ 54 if(getf2(x)==getf2(y)) return 0; 55 f2[getf2(x)]=getf2(y+N); 56 f2[getf2(y)]=getf2(x+N); 57 }else{ 58 if(getf2(x)==getf2(y+N)) return 0; 59 f2[getf2(x)]=getf2(y); 60 f2[getf2(x+N)]=getf2(y+N); 61 } 62 return 1; 63 } 64 void init(){ 65 N=read();M=read();Q=read(); 66 memset(tol,0,sizeof(tol)); 67 up(i,1,N){ 68 f[i]=i;f2[i]=i; 69 f2[i+N]=i+N; 70 } 71 up(i,1,M){ 72 int x=read(),y=read(),v=read(); 73 insert(x,y,v);insert(y,x,v); 74 merge(x,y,v); 75 } 76 up(i,1,M<<1){ 77 int x=e[i].x,y=e[i].y,v=e[i].v; 78 int d=tol[getf(e[i].x)]; 79 int flag=merge2(x,y,(v/d)%2); 80 if(!flag)OK[getf(x)]=1; 81 i+=1; 82 } 83 } 84 void slove(){ 85 while(Q--){ 86 int x=read(),y=read(),K=read(); 87 if(getf(x)!=getf(y)) puts("NIE");//unconnect 88 else{ 89 int d=gcd(K,tol[getf(x)]); 90 if((K/d)&1) puts("0"); 91 else{ 92 if(OK[getf(x)]) puts("0"); 93 else{ 94 if(getf2(x)==getf2(y)) puts("0");//same color 95 else printf("%d\n",d); 96 } 97 } 98 } 99 }100 }101 }102 int main(){103 freopen(FILE".in","r",stdin);104 freopen(FILE".out","w",stdout);105 using namespace solution;106 init();107 slove();108 return 0;109 }
NOIp模拟赛 旅游