是瑶瑶呀

2020-08-05 14:14 已编辑北方工业大学运营

关注

【题解】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:

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 分离. 由于肉片作为一个子图的拓扑序列是非常容易计算的, 所以本题做法的核心就是只维护架子以及连在架子上的肉片的形态. 我们可以发现, 在删除节点的过程中, 架子和与架子相连的肉片的整体形态, 只有大致三种情况:

第一种是在一个完整的DRG(n) 中只删除了第一个节点, 不妨设该类形态为h(n)

第二种是在一个完整的DRG(n) 中删除了第一行中两个以上的连续节点, 这类形态有第一行中剩余节点数i 和第二行的节点数j 控制, 不妨设置为f(i, j)

第三种是在一个完整的DRG(n) 中删除了第一行和第二行的第一个节点, 然后连续删除了第一块肉片的左半边部分, 这类形态由架子上第一行的剩余节点数i 以及第一块肉片左半边剩余节点数j 控制, 设置为g(i, j)

对于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

以S中的任意节点为根，将S视为有根树。对于st∈E(T_i)，令记号s;t表示将边st断开后，顶点t所在的子树。令f[u][s;t](u∈S)表示当u子树中包含子树s;t，u与t对应，且u子树中除与s;t对应的部分外，已经分割成了与{T_i }中同构的若干连通子图的最小总代价。令g[u](u∈S)表示将子树u分割成与{T_i }中同构的若干连通子图的最小总代价。

考虑按照dfs逆序进行树形dp：

接下来考虑如何计算f[u][w;v]。对于v的每个相邻节点a（除w外），都要有一个u的子节点b使用状态f[b][v;a]与之匹配；且u的任一子节点最多只能与v的一个相邻节点匹配。更新g[u]的方法类似。只是在考虑a的相邻节点时，无需将w除外。假设v除w外的相邻节点为a_1,a_2,⋯, a_n，u的子节点为b_1,b_2,⋯,b_m，则我们有以下整数规划：

将约束3改写为c_j=g[b_j ]+∑_(i=1)^n▒〖x_ij (f[b_j ][v;a_i ]-g[b_j ])〗，则该整数线性规划可转化为带权二部图的最小权完美匹配：二部图的左部有n个点，右部有m个点，第i个左部点与第j个右部点之间的边权为f[b_j ][v;a_i ]-g[b_j ]，该二部图的最小权左完美匹配加上∑_(j=1)^m▒〖g[b_j]〗即为答案。可使用Kuhn-Munkres算法在O(n^2 m)时间内求出答案。总的时间复杂度为O(∑_(u∈S)▒∑_(v∈T_i)▒〖deg⁡(u) 〖deg⁡(v)〗^3 〗)=O(NM^3)，最坏情况下仍会超时。注意到，对于v的相邻节点为a_1,a_2,⋯, a_n，u的子节点为b_1,b_2,⋯,b_m时的情况，我们实际上要求{a_1,a_2,⋯,a_n}与{b_1,b_2,⋯,b_m}之间的最小权完美匹配，以及{a_1,a_2,⋯,a_n}去掉任一节点后与{b_1,b_2,⋯,b_m}之间的最小权完美匹配。我们可以一次性求出全部的最小权完美匹配（而不是调用n+1次Kuhn-Munkres算法），首先，我们调用一次Kuhn-Munkres算法求出{a_1,a_2,⋯,a_n}与{b_1,b_2,⋯,b_m}之间的最小权完美匹配。要求出去除a_i后的最小权完美匹配，根据网络流理论，只需在上述最小权完美匹配的基础上，找到一条从a_i出发并到达任意右部已匹配节点的权值和最小的交错路*，并沿着交错路退流即可。注意在计算交错路的权值和时，已匹配边的权值需要取负。可使用Floyd-Warshall算法找出所有最短路，并可在总共O(n^2 m)的时间内求出所有最小权完美匹配。这样，整个算法的复杂度即为O(NM^2 )。

解法2：注意到，当T_i中存在大度点时，其所连接的子树大多数是同构的。最坏情况下，也只有O(M/log⁡M )个非同构子树。因此我们可以合并所有同构子树，这样最坏情况总复杂度为O((NM^3)/log⁡M )。由于常数很小，也可以通过本题。