【题解】2020牛客暑期多校训练营第七场
Fake News
做法0：特判1和24
做法1：打表找规律。
做法1.1：小的范围直接分解，大的范围直接当不行。
做法2：n(n+1)(2n+1)/6，三个乘数分别先两两除下gcd，然后分别判定sqrt是否等于自己就好。
Mask Allocation
不妨设（n<m）由于要求字典序最大，所以考虑装口罩最多的盒子，显然不能超过n，不然人数在m的时候这盒子分不出去了。那继续考虑字典序最大，医院数量为n时候需要给每个医院安排m个口罩，我们至多给每个医院安排floor(m/n)个装了n个口罩的盒子，那这里就安排了floor(m/n)*n个盒子，此时每个医院还要额外再拿m%n个口罩才能达到要求。这时候我们考虑医院数量为m的情况，此时需要给每个医院分配n个口罩，那显然已经有floor(m/n)*n个医院满足条件了，还有m%n个医院还啥都没拿到。这样，我们就把问题转化成了n’= m % n，m’= n的子问题，不断循环即可。这不就是gcd嘛kora！
Dividing
先讨论n 是k 倍数的情况, 不妨设n=xk, 那么, x 和k 中总有一个数字不超过10^6, 枚举x 和k 中较小的一个即可, 另一个的个数可以直接通过计算获取
对于n=xk+1 的情况也是同样的
对于n=1 的情况, 直接统计即可
Pointer Analysis
直接暴力求解即可, 本题难点可能只在于处理读入. 这里给出一个简单的暴力框架, 令pt(x) 为指针x 可能指向的对象集合
Let worklist be a set
For every allocation statement A = x:
insert x into pt(A)
If pt(A) has been changed, add A into worklist
While worklist is not empty:
While worklist is not empty:
select one element X from worklist
delete X from worklist
For every assignment statement like Y = X:
merge pt(X) into pt(Y)
If pt(Y) has been changed, add Y into worklist
For every store statement Y.f = X:
For every object o in pt(Y):
merge pt(X) into pt(o.f)
For every load statement Y = X.f:
For every object o in pt(X):
merge pt(o.f) into pt(Y)
If pt(Y) has been changed, add Y into worklist
A National Pandemic
2操作是卖萌的，单独记录一个delta就能解决了。对于1操作，我们考虑一次修改对y来说会增加w-dis(x,y)。W-dis(x,y)=w-(dep(x)+dep(y)-2*dep(lca))=w-dep(x)-dep(y)+2*dep(lca)，所以，对于每次1操作，我们将其到根上所有点的cnt+=2，询问的时候那部分就是求它到根的权值和。所以，树上路径加，路径查询，写个qtree改一下输出就好了。那其实很多人上了点分，复杂度变成一个log，怎么更优就见仁见智了。
Social Distancing
0.Codeforces 460E (Round #262) 原题你最大
1.Dp，f[i,j,k]表示选i个点，横坐标总和为j，纵坐标总和为k时各点间距离平方和最大值
2.模拟退火，激情乱搞
TLE怎么办？观察性质呗~Dp也是类似。整理可得转移方程f[i+1,j+x,k+y]=max{f[i,j,k]+i*(x^2+y^2)-j*x-k*y+(f[i,j,k]+j^2+k^2) div I}，答案为答案为max{f[n,j,k]|-r*n<=j<=r*n,-r*n<=k<=r*n}，由于对于选定的横坐标x选取的点离圆心尽量远更优，可知此时纵坐标y的绝对值为sqrt(r^2-x^2)向下取整，进行DP时只需考虑{(x，y)|abs(y)=sqrt(r^2-x^2)),-r<=x<=r}的点即可。但是还是要打表~
Topo Counting
首先我们需要知道, 如果一个DAG 是由两个完全不相关的子图组合而成的, 不妨设这两个子图的大小分别是S_1和S_2, 对应拓扑序列个数为P_1和P_2, 那么这个DAG 的拓扑序列个数为((S_1+S_2)¦S_1 ) P_1 P_2， 以下是DRG(4) 的形态, 不妨称上面横着的组为架子(V^1), 下面的是肉片(V^2,V^3, …,V^n). 拓扑序列实际上就是一个不断删除入度为0 的节点的过程的删除序列. 我们可以发现每个肉片只受制于架子上的两个节点, 当对应的两个节点被删除之后, 肉片就会与整个DRG 分离. 由于肉片作为一个子图的拓扑序列是非常容易计算的, 所以本题做法的核心就是只维护架子以及连在架子上的肉片的形态. 我们可以发现, 在删除节点的过程中, 架子和与架子相连的肉片的整体形态, 只有大致三种情况:
对于h(n), 接下来只有两种删除方法, 分别会变成f(n – 2, n) 以及g(n – 1, n)，对于f(i, j), 接下来也只有两种删除方法, 分别会变成f(i – 1, j) 以及(f(i, j – 1) 和h(j – 1) 中的其中一种+一个分离出去的完整肉片)，对于g(i, j), 同样只有两种情况, 分别变成g(i, j – 1) 以及(h(i) + 分离出去的一个肉片)，所有这些形态都只有n^2 种情况, 计算都是常数级, 直接把每个形态的数量都计算出来即可.
Valueable Forests
一个森林内部节点的度数平方和等于2 * (长度为2 的路径数+长度为3 的路径数)， n个点的带标号树个数为n^(n-2)，我们可以通过一个n^2 的做法得到n 个点的带标号森林个数，我们分别统计长度为2 的路径的贡献, 相当于从n 个点里面挑出2 个点, 设这两个点所在树大小为j, 那么就需要从剩下n – 2 个点里面挑出j – 2 个点, 然后挑出的这j 个点构成一棵树, 剩下的n-j 个点构成森林. j 个点构成的树需要以那两个点为根(相当于把这两个点看成一个整体), 用prufer 序列的处理可以知道方案数是2j^(j-3)，长度为3 的路径同理, j 个点以特定3 个点为根的方案数是3j^(j-4)
Tokens on the Tree
NeoMole Synthesis
