在比赛开始30分钟内依次A了10，7，3，一个小时左右A了11，然后就再也没有写出任何一道题。。。
其实比赛过程中心态有很大的问题，我一直在5上面钻牛角尖，耗费了太多时间。
基本上比赛后半程三个人都在看2，5两道题，其他题目几乎没看。
到最后基本没有做下去的欲望了，可能是因为是女队压力比较小吧（不，是因为我比较菜）。。
以及网络赛的排行榜真的很迷。。第2题min25筛一堆人过。。然而队里三个人甚至都没有听说过这玩意。。
（226大佬7题，ORZ）
1002 Graph Theory Class
题意：在一个有n个点的图中，图中点1~n编号。对于i,j之间的一条边，它的权重为lcm(i+1,j+1)，求这个图的最小生成树大小。
思路：很明显对于(j+1)为质数的情况，j应该与1连接，权重为2*(j+1)；
对于(j+1)不是质数的情况，j可以与任意一个满足i+1==factor(j+1)的i连接，factor(j+1)指j+1的因子，权重为j+1。
于是最小生成树的大小为(3~n+1以内所有质数)*2+(3~n+1以内所有非合数)，即(3~n+1所有数之和)+(3~n+1以内所有质数之和)
前者可以用等差数列求和计算，(n+4)*(n-1)/2；由于n<=1010，后者可以使用min25筛计算。
min25筛，可以在O(n3/4/logn)的时间内求积性函数f(x)的前缀和。
（积性函数，指对于所有互质的整数a和b有性质f(ab)=f(a)f(b)的函数）
（代码待补充
1003 Express Mail Taking
题意：有n个保险柜，编号为1~n，每两个相邻编号的保险柜之间的距离为1，第k个保险柜用来打开其他保险柜（每次只能同时打开一个保险柜）。从1出发，需要从m个保险柜中取东西后再从1离开。问距离最短的路线长度。
思路：一开始理解错了题意，以为只要到达第k保险柜后其他保险柜就打开了，就WA了一次。
对于m个要取东西的柜子，除了最后一个柜子有可能不需要返回k柜，对于其他柜子，都必须在该柜子与k柜之间走一个来回。
于是找到m个柜子中最小的一个x，若x比k小，则将该点删去（在回1点的路上就可到达，对距离无贡献）
接着对剩下的每个柜子i，贡献2*abs(i-k)的答案。
再加上出发和结束的2*(k-1)，就是答案。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int maxn=2000005; int a[maxn]; int main() { int i,T,n,m,k,mi; ll ans; scanf("%d",&T); while (T--) { scanf("%d%d%d",&n,&m,&k); ans=2ll*(k-1); mi=k; for (i=1;i<=m;i++) { scanf("%d",&a[i]); ans+=2ll*abs(a[i]-k); if (a[i]<mi) mi=a[i]; } if (mi!=k) ans-=2ll*abs(mi-k); printf("%lld ",ans); } return 0; }
1005 Lunch
题意：有n个数，两人轮流进行操作，每次操作能将其中一个数x变为k*(x/k)，此处的k必须是x的因子且k!=x。当场上的数均为1时游戏结束，当前操作方输。问先手可不可以获胜。
思路：（看了半天别人的题解还是有点晕乎乎的）
观察发现，对于一个数，分成偶数个会增加偶数个操作，于是这样不会使得最后的胜负情况发生改变。
分成奇数个则刚好相反，会改变最后的胜负情况。
把数x分解，x就变成了一堆质因子的乘积。
（）
因为每次操作要让这个数x变成自己的因数，所以每次必须取走x的至少一个质因子，
那么就可以将这个数的所有质因子（考虑重复，因为假如你有2个质因子3，那么是可以分开取，所以重复的而要考虑）当作一堆石子的个数。
而其中的2它比较特殊，因为它是偶数，不会使最后的胜负情况发生改变。
于是不管分几次取2，都相当于直接把2全取走。但是又必须要取走2，所以就把所有的因数2当作一个石子一起取走。
（以上来自队友的分析）
然后就变成了nim博弈，即有n堆石子，两人轮流进行操作，每次可从任意一堆石子里取走任意多枚石子，不能不取，问先手必胜还是必败。
对于答案，求每一堆的石子数的异或和，若为0则必败，否则必胜。
（然后不知道为什么T了很久，好像也不是读入优化的问题啊。。。
补充：对于nim答案的分析：对于一堆石子，只要石子数不为0，直接拿走所有石子就赢了，所以必胜。
对于两堆石子，如果异或和为0则必败。此时两堆石子数相同，对方只要按照先手方对一堆石子的操作，对另一堆石子上进行同样的操作，就能够胜利。
如果异或和不为0则必胜。先手方可以先将一堆石子变为和另一堆石子一样，然后就变成了刚才所说的局面，异或和为0。
......
对于很多堆石子，如果异或和为0必败；否则改变其中最大的那堆的大小，一定能使剩下的局面的异或和为0。
（局面异或和为0的具体操作：对手对一堆进行操作，其他堆中一定有某一堆，可以使先手对它做出相同的操作。）
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int cnt,vis[32005],prime[5005]; int div(int x) { int re=0; while (!(x&1)) { x>>=1; re=1; } for (int i=2;i<=cnt && 1ll*prime[i]*prime[i]<=x;i++) { while (x%prime[i]==0) { x=x/prime[i]; re++; } } if (x!=1) re++; return re; } void pri(int n) { cnt=0; memset(vis,0,sizeof(vis)); for (int i=2;i<n;i++) { if (!vis[i]) prime[++cnt]=i; for (int j=1;j<=cnt && 1ll*i*prime[j]<n;j++) { vis[i*prime[j]]=1; if (i%prime[j]==0) break; } } } int main() { int T,n,ans,x; pri(32000); scanf("%d",&T); while (T--) { scanf("%d",&n); ans=0; for (int i=0;i<n;i++) { scanf("%d",&x); ans^=div(x); } if (ans) printf("W "); else printf("L "); } return 0; }
1006 Robotic Class
题意：给一个有n点的图，点i有k[i]条出边，若通过i的一条出边j，就会使当前的权值x变为c[i][j]*x+b[i][j]，并走到下一点d[i][j]。对于有多条出边的点i，每次会选择一条满足a[i][j]≥x并且编号j最小的路径j。现在从任一点s出发，初始权值为x0，走到n点停止，最后到达n点的权值为Cs(x0)，问对于每一个s，Cs(x)是否均为连续。
思路：看完了别人的代码，感觉这题没做出来有点亏。。
因为f(x)连续，所以若在i点的权值为a[i][j]-与a[i][j]+，那么两者到达n点得到的权值应当相同。
所以对于每一个点i的a[i][j]，模拟以初始权值x0=a[i][j]-与a[i][j]+从i出发直到n的路径，检查最后得到的Ci(a[i][j]-)与Ci(a[i][j]+)是否相等。
具体见代码。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int maxn=505; const int maxm=2005; int n,k[maxn],a[maxn][maxm],b[maxn][maxm],c[maxn][maxm],d[maxn][maxm]; ll dfs(int t,ll x,int mark) { if (t==n) return x; int pos=lower_bound(a[t],a[t]+k[t],x)-a[t]; if (pos<k[t] && x==a[t][pos] && mark>0) pos++; int now=0; if (c[t][pos]>0) now=1; else if (c[t][pos]<0) now=-1; return dfs(d[t][pos],1ll*c[t][pos]*x+b[t][pos],now*mark); } int main() { int t,T,i,j,flag; ll l,r; scanf("%d",&T); for (t=1;t<=T;t++) { scanf("%d",&n); for (i=1;i<n;i++) { scanf("%d",&k[i]); for (j=0;j<k[i];j++) scanf("%d%d%d%d",&c[i][j],&b[i][j],&d[i][j],&a[i][j]); scanf("%d%d%d",&c[i][j],&b[i][j],&d[i][j]); } flag=1; for (i=1;i<n;i++) { for (j=0;j<k[i];j++) { l=dfs(i,a[i][j],-1); r=dfs(i,a[i][j],1); if (l!=r) { flag=0; break; } } if (!flag) break; } printf("Case #%d: ",t); if (flag) printf("YES "); else printf("NO "); } return 0; }
1007 CCPC Training Class
题意：花里胡哨的题面。
思路：是一题题面比较长的签到题。。
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; int t,a[30],mx,pos,cs,l; char s[100010]; int main() { scanf("%d",&t); while (t--) { scanf("%s",s+1); l=strlen(s+1); mx=0; memset(a,0,sizeof(a)); for (int i=1;i<=l;i++) a[s[i]-'a']++; for (int i=0;i<26;i++) mx=max(mx,a[i]); printf("Case #%d: %d ",++cs,mx); } return 0; }
1010 Reports
题意：就是每次输入一个长度为n的01串，若存在相邻两位一样就输出NO，否则输出YES。
思路：这么短的题目显然是签到题啦，照题意做就行了。
#include<cstdio> using namespace std; int t,y,x,op,n; int main() { scanf("%d",&t); while (t--) { scanf("%d",&n); scanf("%d",&y); op=1; for (int i=1;i<n;i++) { scanf("%d",&x); if (x==y) op=0; y=x; } if (!op) puts("NO"); else puts("YES"); } return 0; }
1011 3x3 Convolution
题意：给出n*n矩阵A和3*3矩阵K（n>=3）， 定义n*n矩阵C(A,K)，它的每一项Cx,y满足
定义Cm(A,K)=C(Cm−1(A,K),K) and C1(A,K)=C(A,K)，求limt→∞Ct(A,K)。
思路：观察样例，发现样例中答案只有两种，原矩阵和零矩阵。
经过一番胡乱分析，推测当输入的K矩阵只有左上角有不为0的数，其他位置都是0时，输出原矩阵；其他情况输出零矩阵，
然后跟队友说了猜想，队友就A了，A得我一头雾水，果然像学长说的一样，大胆猜想，不用证明(bushi)。
以及这题的输出格式真的。。。我写的时候PE了一片，（然而我的队友一发就过了。。
补充：C1,1=A1,1*K1,1+A1,2*K1,2+......+A3,2*K3,2+A3,3*K3,3
......
Cn,n-1=An,n-1*K1,1+An,n*K1,2
Cn,n=An,n*K1,1
然后进行分类讨论
1、如果K1,1==0，Cn,n就为0；接下来的C2中的Cn,n-1也会变成0，以此类推，最后矩阵Ct会变成零矩阵。
2、如果K1,1!=0，K其他位都为0，那么矩阵中的所有项相当于乘上了K1,1的t次方，各项之间的比值不变，于是答案是原矩阵。
3、如果K1,1!=0，K其他位中存在不为0的项，因为K1,1<1，Cn,n会不断变小，直至无限趋近于0
推理可得，Ct中的Cn,n-1=An,n-1*Kt1,1+t*An,n*Kt-11,1*K1,2，
由于K所有项之和为1，K1,1与K1,2都小于1，分析可得当t→∞时，Ct中的该项趋近于0；
同理，其他项在Ct中也都趋近于0，于是最后得到的Ct是零矩阵。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int maxn=52; int a[maxn][maxn]; int main() { int i,j,T,n,flag,x; scanf("%d",&T); while (T--) { scanf("%d",&n); for (i=1;i<=n;i++) for (j=1;j<=n;j++) scanf("%d",&a[i][j]); flag=0; for (i=1;i<=3;i++) for (j=1;j<=3;j++) { scanf("%d",&x); if (x) { if (i==1 && j==1) flag=1; else flag=0; } } if (flag) { for (i=1;i<=n;i++) for (j=1;j<=n;j++) { printf("%d",a[i][j]); if (j==n) printf(" "); else printf(" "); } } else { for (i=1;i<=n;i++) for (j=1;j<=n;j++) { printf("0"); if (j==n) printf(" "); else printf(" "); } } } return 0; }
#include<cstdio> #define N 55 using namespace std; int t,n,a[N][N],b[N][N],sum; int main() { scanf("%d",&t); while (t--) { scanf("%d",&n); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) scanf("%d",&a[i][j]); sum=0; for (int i=1;i<=3;i++) for (int j=1;j<=3;j++) scanf("%d",&b[i][j]),sum+=b[i][j]; if (b[1][1]==sum) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) printf("%d%c",a[i][j]," "[j==n]); else for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) printf("0%c"," "[j==n]); } return 0; }