CCPC2020网络赛 赛后总结

ywy_c_asm · 2020-09-20 22:26:15 · 个人记录

（未完待续）

T2 Graph Theory Class

题目链接

题意：给你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

题目链接

题意：给你一个有向图，每个点一定有出边，有一个点权，A和B在图上进行博弈，A能够控制一个点集S，B控制剩下的点。每局博弈的时候，往某个起点上放个棋子，然后A、B依次操作，他们会把自己控制的所有点都仅保留一条出边，定义Val为这棋子能移到的最大点权，A希望Val最大，B希望Val最小，对每个起点求最终的Val。点是100万级别的。

Solution：

这题类似CF1407E的倒着BFS让前面的点尽量到不了后面的思路。

先考虑S为所有点，即仅有A进行操作的情况（毕竟这题我们最终要从A的角度考虑问题），首先点权最大的点，答案一定是他自身，我们显然要贪心地让别的点都能到达它，那么就从他出发反向BFS把能到达他的那些点强制到达他（出边就是BFS树的父亲边），这样依次从大到小贪心从每个点出发BFS即可。

现在出现了一些“坏点”，那不就是尽量使坏点到达不了当前BFS树么？当我搜索到一个坏点时，我把这条边能删就删，删不了那无可奈何只能把坏点加入BFS树，由于我们是从大到小依次考虑所有答案这肯定是正确的。

md比赛时看这题懵逼了，基本上就是被那奇怪的题目描述劝退，后来比赛结束后我仔细思考了一下把AB拆开考虑就发现就会了……

T5 Lunch

题目链接

题意：有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游戏本质上是一样的。

对于偶数呢？也可以归纳证明。