CCPC2020网络赛 赛后总结

（未完待续） T2 Graph Theory Class --- [题目链接](http://acm.hdu.edu.cn/showproblem.php?pid=6889) 题意：给你$n$，规定$(i,j)$边的权值是$lcm(i+1,j+1)$，求最小生成树。$n<=10^{10}$，50组数据。 Solution： ~~其实可以打表找规律~~ 这样考虑，一个点去找唯一的一个父亲，让这个父亲边的权尽量小，这类似$Prim$，一定是正确的。从最大的$n+1$考虑，如果$n+1$是合数，那么我一定能让$n+1$去连它的一个更小的约数，这样边权就是$n+1$，不会比这更小。如果$n+1$是质数，那么让他连啥都得是乘积，所以就连最小的2，即$2*(n+1)$。 所以$ans=\sum_{i=3}^{n+1}i+\sum_{i=3}^{n+1}i*[i\in Prime]$，即求质数和，直接上$Min\_25$板子……~~orz shadowice1984现推min25筛~~ ~~其实你是不是忘了还有个东西叫分段打表~~ T4 Chess Class -- [题目链接](http://acm.hdu.edu.cn/showproblem.php?pid=6891) 题意：给你一个有向图，每个点一定有出边，有一个点权，A和B在图上进行博弈，A能够控制一个点集$S$，B控制剩下的点。每局博弈的时候，往某个起点上放个棋子，然后A、B依次操作，他们会把自己控制的所有点都仅保留一条出边，定义$Val$为这棋子能移到的最大点权，A希望$Val$最大，B希望$Val$最小，对每个起点求最终的$Val$。点是100万级别的。 Solution： 这题类似[CF1407E](https://www.luogu.com.cn/blog/ywycasm/xie-ti-bao-gao-bfs-gou-zao-cf1407e-egor-in-the-republic)的倒着BFS让前面的点尽量到不了后面的思路。 先考虑$S$为所有点，即仅有A进行操作的情况（毕竟这题我们最终要从A的角度考虑问题），首先点权最大的点，答案一定是他自身，我们显然要贪心地让别的点都能到达它，那么就从他出发反向BFS把能到达他的那些点强制到达他（出边就是BFS树的父亲边），这样依次从大到小贪心从每个点出发BFS即可。 现在出现了一些“坏点”，那不就是尽量使坏点到达不了当前BFS树么？当我搜索到一个坏点时，我把这条边能删就删，删不了那无可奈何只能把坏点加入BFS树，由于我们是从大到小依次考虑所有答案这肯定是正确的。 md比赛时看这题懵逼了，基本上就是被那奇怪的题目描述劝退，后来比赛结束后我仔细思考了一下把AB拆开考虑就发现就会了…… T5 Lunch --- [题目链接](http://acm.hdu.edu.cn/showproblem.php?pid=6892) 题意：有$n$个数，A和B在搞博弈，每次一个人选一个数，如果这个数是1那这人就输了，否则，选出$d|n(d\not=1)$，将$n$分为$d$个$\frac{n}{d}$，求先手是否必胜。$n<=10,x_i<=10^9$，2万组数据。 Solution: ~~比赛完之后听副校长讲话听的昏昏欲睡的时候才突然想到的……~~ 这种东西当然要考虑$SG$函数啊…… 考虑$SG$函数的定义，即所有后继局面的$mex$，多个独立的游戏的$SG$可以xor起来。 对于一个单个的数，我们发现它的SG显然只和它包含的质因子2，以及其它质因子的个数（其它的质因子本质上都是一样的，但它们都是**奇数**）。 考虑边界情况：$SG(1,1,1...1)=0,SG(P)=1$ 对于一个奇的$P^k$，它的后继局面就是枚举一个约数$d$（肯定就是奇数），得到剩下的$d$个相同的数，把它们异或起来肯定还是$SG(\frac nd)$，那么$SG(P^k)=mex\{0,SG(P^1),SG(P^2)...SG(P^{k-1})\}$，归纳可得$SG(P^k)=k$，这个和Nim游戏本质上是一样的。 对于偶数呢？也可以归纳证明。 $SG(2^k)=mex\{0\}=1$（因为随便枚举一个约数都是偶数，剩下偶数个相同的SG异或起来都是0），$SG(2^k*P)=mex\{0,SG(2^k)\}=2$，归纳可得$SG(2^kP^h)=h+1$。 那么质因数分解即可。 T11 3×3 Convolution -- [题目链接](http://acm.hdu.edu.cn/showproblem.php?pid=6898) 题意：给你$n$阶方阵$C$以及3阶方阵$K$，其中$K$为非负实数矩阵，和为1，定义矩阵变换$F(C,K)$为，$C_{i,j}$变成它右下方3×3的部分（若超出则不取）与$K$对应位相乘求和。对$C$做无限次变换，求“极限矩阵”。 Solution： ~~其实这也可以打表找规律~~ 其实样例就已经提示我们了，若$K_{1,1}=1$，那么$C$永远是不变的，否则，$K_{1,1}<1$，考虑$C_{n,n}$，每次就是让它本身乘上$K_{1,1}$，一定会变小，一定会收敛到0，递归地考虑它左上的元素也会像这样的收敛到0。所以就这两种情况。 然后关于此题的非常悲惨的故事是由于我们第一次打acm然后我以前极少用hdu做题并不知道hdu关于输出文末空行以及行末空格的严格规定，这题比赛的时候PE了11次……心态爆炸……不仅没A还罚时罚到了垫底……血亏.jpg T12 Xor --- [题目链接](http://acm.hdu.edu.cn/showproblem.php?pid=6899) 题意：求有多少对$(x,y)$，满足$x\in[0,A],y\in[0,B],|x-y|<=K,x\space xor\space y<=W$，数字都是$10^9$级别。 Solution： 感觉这题不难啊，为啥那么多人没过掉这题啊 异或显然可以按位进行数位DP，而差值其实也可以进行数位DP。 我发现一种非常简单的方法是从低位到高位dp，令$dp[i][0/1][0/1][0/1][0/1][0/1]$为，已经构造出了$x$和$y$的低$i$位（强制使最后$x>=y$），$x$和$y$分别是否在低$i$位已经$<=A$或$B$的低$i$位（这样的话，我在枚举一个更高的位的时候，仍然可以得出低$i+1$位的大小关系，貌似基本上所有数位DP都可以这样），$x-y$是否要借位（既然是从低到高的减法，就必须考虑借位），结果是否$<=K$（低位的已经算好了的结果显然和借位没关系），异或是否$<=W$。