本来是打算所有半夜进行的CF都不参加的，但看到这次比赛22：35就开始，还是没有忍住orz……晚上总是不够清醒，做题思维不如白天活跃，低级错误常常出现。出的比较早的C因为一个书写错误有点小bug，在比赛快结束时被hack，还好一下子就发现改正了过来，b题很水，却刚开始没想到合适的做法，也卡了比较久。D题因为刚学到DP，还很不熟练，比赛前没能写完。整体来说这一场实在是表现的菜的一塌糊涂。不过因为现在rating低，还在神奇的上分，算是一点慰藉了。
A
简要题意：
输入一个整数n，输出1378的n次方的个位数。
思路分析：
只要看8的n次方个位数是多少。显然是有循环节的，写几项发现循环节为4，所以只需要看n模4余几，注意n=0时要特殊判断一下，任何非0数的0次方都是1.
参考代码：
1 #include<stdio.h> 2 #include<bits/stdc++.h> 3 #include <iostream> 4 using namespace std; 5 typedef long long ll; 6 int main() 7 { 8 int n; 9 scanf("%d",&n); 10 if(n==0) 11 { 12 printf("1 "); 13 } 14 else if(n%4==1) 15 { 16 printf("8 "); 17 } 18 else if(n%4==2) 19 { 20 printf("4 "); 21 } 22 else if(n%4==3) 23 { 24 printf("2 "); 25 } 26 else if(n%4==0) 27 { 28 printf("6 "); 29 } 30 return 0; 31 }
B
简要题意：
给若干数，要求判断这些这些数有多少对异或值为给定的另一个数。（每一对顺序固定，按给定时的顺序）
思路分析：
注意到x^y=z则x^z=y。利用此，建立数组记录每个数出现的次数，因为每一对顺序固定，对于一个数x，只需看出现在x之前的（x^“目标数”）出现了多少次，就多形成了多少对。注意异或值可能会比给出的数的范围大，所以把数组大小开大一点。
参考代码：
1 #include<stdio.h> 2 #include<bits/stdc++.h> 3 #include <iostream> 4 using namespace std; 5 typedef long long ll; 6 const int INF=1e6+5; 7 ll an=0; 8 int ci[INF],n,mu,i,tem; 9 int main() 10 { 11 memset(ci,0,sizeof(ci)); 12 scanf("%d%d",&n,&mu); 13 for(i=0;i<n;i++) 14 { 15 scanf("%d",&tem); 16 an+=ci[tem^mu]; 17 ci[tem]++; 18 } 19 printf("%I64d ",an); 20 return 0; 21 }
C
简要题意：
一个有向图，每一个点有且只有一条出的线。求最小的n，使任意从一点走2n步之后就回到本身。
思路分析：
显然，有向图中的每一点入度都需要恰为1，否则必然有入度为0的点，那么不管n取多少，从这点都走不回这一点。而当满足每一点入度都恰为1时就一定可以找到符合要求的n。只需要求所有形成的环的“长度”（如果长度为偶数2x，n取x即可走2x步就回到本身，所以用于计算的“长度”取值为x）的最小公倍数即可。
参考代码：
1 #include<stdio.h> 2 #include<bits/stdc++.h> 3 #include <iostream> 4 using namespace std; 5 typedef long long ll; 6 int gcd(int x,int y) 7 { 8 while(x%y!=0&&y%x!=0) 9 { 10 if(y>x) 11 y=y%x; 12 else 13 x=x%y; 14 } 15 if(x%y==0) 16 { 17 return y; 18 } 19 else 20 { 21 return x; 22 } 23 } 24 int main() 25 { 26 int n,a[105],i,an=0,len=0,j,b[105],cnt=0; 27 bool vi[105]; 28 memset(vi,false,sizeof(vi)); 29 scanf("%d",&n); 30 for(i=1;i<=n;i++) 31 { 32 scanf("%d",&a[i]); 33 vi[a[i]]=true; 34 } 35 for(i=1;i<=n;i++) 36 { 37 if(!vi[i]) 38 { 39 printf("-1 "); 40 return 0; 41 } 42 } 43 memset(vi,false,sizeof(vi)); 44 for(i=1;i<=n;i++) 45 { 46 len=0; 47 if(!vi[i]) 48 { 49 j=a[i]; 50 len=1; 51 while(j!=i) 52 { 53 54 vi[j]=true; 55 len++; 56 j=a[j]; 57 } 58 b[cnt++]=len; 59 } 60 } 61 if(b[0]%2!=0) 62 an=b[0]; 63 else 64 an=b[0]/2; 65 for(i=1;i<cnt;i++) 66 { 67 if(b[i]%2!=0) 68 an*=(b[i]/gcd(an,b[i])); 69 else 70 an*=((b[i]/2)/gcd(an,b[i]/2)); 71 } 72 printf("%d ",an); 73 return 0; 74 }
D
简要题意：
有若干人，，每个人有一个体重值和颜值，且若干人组成一组，这一组必须全取或取小于等于1个人。要找到一种总体重小于等于W，而颜值之和最大的选人办法。
思路分析：
0、1背包，不同的是题目中的限制。只需要先根据题意把同一组的标记出来，这一组的每个人，和这一组的整体作为第i个可选物品进行0、1背包即可。
参考代码：
1 #include<stdio.h> 2 #include<bits/stdc++.h> 3 #include <iostream> 4 using namespace std; 5 typedef long long ll; 6 #define num 1010 7 vector <int> group[num]; 8 int pre[num],w[num],b[num],ww[num],bb[num],dp[num][num],cnt,fpre[num],org; 9 int n,m,W,i,l,r,an=0; 10 int trimax(int x,int y,int z) 11 { 12 if(x>=y&&x>=z) 13 return x; 14 if(y>=x&&y>=z) 15 return y; 16 if(z>=x&&z>=y) 17 return z; 18 } 19 int trace (int s) 20 { 21 if(pre[s]==s) 22 return s; 23 else 24 return trace(pre[s]); 25 } 26 27 int main() 28 { 29 scanf("%d%d%d",&n,&m,&W); 30 for(i=1;i<=n;i++) 31 { 32 scanf("%d",&w[i]); 33 } 34 for(i=1;i<=n;i++) 35 { 36 scanf("%d",&b[i]); 37 } 38 for(i=1;i<=n;i++) 39 { 40 pre[i]=i; 41 } 42 for(i=1;i<=m;i++) 43 { 44 scanf("%d%d",&l,&r); 45 if(trace(l)!=trace(r)) 46 pre[trace(l)]=trace(r); 47 } 48 cnt=1; 49 for(i=1;i<=n;i++) 50 { 51 int st=-1; 52 int org=trace(i); 53 int j; 54 for(j=1;j<cnt;j++) 55 { 56 if(fpre[j]==org) 57 { 58 st=j; 59 break; 60 } 61 } 62 if(st==-1) 63 { 64 ww[cnt]+=w[i]; 65 bb[cnt]+=b[i]; 66 group[cnt].push_back(i); 67 fpre[cnt++]=org; 68 } 69 else 70 { 71 ww[st]+=w[i]; 72 bb[st]+=b[i]; 73 group[st].push_back(i); 74 } 75 } 76 for(i=1;i<cnt;i++) 77 { 78 for(int k=W;k>=0;k--) 79 { 80 if(k>=ww[i]) 81 dp[i][k]=trimax(dp[i][k],dp[i-1][k],dp[i-1][k-ww[i]]+bb[i]); 82 else 83 dp[i][k]=max(dp[i][k],dp[i-1][k]); 84 } 85 for(int j=0;j<group[i].size();j++) 86 { 87 for(int k=W;k>=0;k--) 88 { 89 if(k>=w[group[i][j]]) 90 dp[i][k]=trimax(dp[i][k],dp[i-1][k],dp[i-1][k-w[group[i][j]]]+b[group[i][j]]); 91 else 92 dp[i][k]=max(dp[i][k],dp[i-1][k]); 93 } 94 } 95 } 96 for(i=0;i<=W;i++) 97 if(dp[cnt-1][i]>an) 98 an=dp[cnt-1][i]; 99 printf("%d ",an); 100 return 0; 101 }
E
简要题意：
n对情侣坐在一个圆桌上（情侣都是一男一女的，没有别的情况），给他们发两种食物，要求：
1、一对情侣食物不同
2、任意连续3个人，必须2种食物都出现
思路分析：
大家初看可能觉得是二分图匹配，但其实并不是，只是一个普通的图随便整一下。
下面是对必定有解的证明。
2n个点的无向图 将12 34 …… 2n-12n 连线 再将一组的两点连线 这样组成的图只存在偶回路（若不然 存在2*k+1个点组成奇回路 将这2*k+1条边 编上号 为1——2*k+1 因为相邻的两边必定一个是 按之前的编号相邻点连线 另一个是 情侣点连线 从1出发 如果1是前者 那么2是后者…… 2*k+1是前者 矛盾 如果1是后者 同理矛盾 ）故此图为二部图 可分为两个点集 U、V 将U中点赋为1 V中点赋为2 这样图中任意一条线两个端点颜色不同 任意连续3个点必存在一条连线 而连线两端点值不同 即证明了必定有解。
1 #include<stdio.h> 2 #include<bits/stdc++.h> 3 #include <iostream> 4 using namespace std; 5 typedef long long ll; 6 const int N=200010; 7 vector <int> a[N]; 8 int b[N],g[N]; 9 int an[N]; 10 bool vi[N]; 11 void dfs(int x,int t) 12 { 13 vi[x]=true;an[x]=t; 14 for(int i:a[x]) 15 { 16 if(!vi[i]) 17 dfs(i,(t^1));} 18 } 19 int main() 20 { 21 memset(vi,false,sizeof(vi)); 22 int n,i; 23 scanf("%d",&n); 24 for(i=1;i<=n;i++) 25 { 26 scanf("%d%d",&b[i],&g[i]); 27 a[b[i]].push_back(g[i]); 28 a[g[i]].push_back(b[i]); 29 } 30 for(i=1;i<=n;i++) 31 { 32 a[2*i-1].push_back(2*i); 33 a[2*i].push_back(2*i-1); 34 } 35 for(i=1;i<=2*n;i++) 36 if(!vi[i]) 37 dfs(i,0); 38 for(i=1;i<=n;i++) 39 printf("%d %d ",an[b[i]]+1,an[g[i]]+1); 40 return 0; 41 }