XY_cpp edited 1 年，9 月前
由于命题失误和网站故障，本次比赛成绩不计入 EOJ 积分。
By XY_cpp
签到题，枚举$\sum$里面的整个式子的值，设为$x$，进而确定$x$对应的$k$的上下界，能够轻松算出$x$的贡献，复杂度$O(T\sqrt{\frac{n}{114}})$。
By TealCloud
B题出锅了，自首。std是觉得可以枚举26个目标终态，得到delta之后，找连续区间一直减就行，反正delta最多不超过26。所以纯暴力是2626n，如果用查分来写是26*n。但是在赛时，有选手用dp算出了更优解，验证之后发现确实std出错了。出现了我可能多走26步反而更优的情况，出题和验题的时候没有考虑到，所以补救的时候对题面条件进行了约束。对影响到的选手道歉。
By Huawei
注意到一个盒子里相同的数字的卡牌不会超过$5$个，可以枚举这个卡牌的排列，依次去匹配即可。
当然更快的解法可以跑最小费用最大流：
对于每个盒子里的卡牌，向能够和它匹配的判定卡牌连一条流量为1，费用为$s*p$的边；建立源点$S$，向所有的卡牌连一条流量为$1$，费用为$0$的边；建立汇点$T$，所有的判定卡牌向汇点连一条流量为$1$，费用为$0$的边。
By SHU_Fox_516
这里介绍其中一种做法，我们可以对n进行讨论，
初始集合为$[1,2,3,…,n]$,我们可以很容易的把他变成$[2,4,6,8,…,2x]$
其中$2x$是大于等于$n$的第一个偶数，这个最多需要$x+1$步就能实现，使得集合减少了至少$x$个数字。$(1和2x-1,3和2x-3,…,以此类推)$
然后对于新的集合，可以记录其为$2 \times [1,2,3,…,x]$去递归处理。
请注意在$n \le 6$ 时不满足没办法用上述做法实现，故需要特判处理。
总步数上界为$\lceil \frac{n}{2} \rceil + \lceil log_{2}(n) \rceil$。
By SHU_Fox_516
这题原来数据范围想要开到$q \le 1e5$，但是由于出题人比较菜，写不出来。
这里提供一种简单的做法，我们一开始把所以询问的节点和其所有的祖先预处理出来，总共会有$qm$个节点，除去$n=1$的情况需要特判，其他可以得到$m \le 18 $,故总节点数$qm \le 4e4(其实是远远小于)$,此时每次询问可以暴力修改这些点，故理论上界复杂度是$O(q^2m)$。
其实还有一种做法，即每次修改时留下一个标记去处理，对于$全0,全1,翻转,抱持原态$和$被父节点更新,未被父节点更新$几个状态进行处理，去动态的维护这棵树的节点。这样每次修改可以只修改当前节点的所有祖父节点，并且可能删除其所有的儿子节点，每次最多创建$m$个点，最多删除所有被创建的点，此时复杂度为$O(2qmlog_{2}(qm))$
By XY_cpp
设我们现在选出的点集为$S$，显然答案就是如下式子：
$$
\sum_{i=1}^{|S|}\sum_{j=i+1}^{|S|}[\gcd_{x\in path(s_i,s_j)}{x}\le m]
$$
设$f(x)=[x\le m]$，期望找到函数$g$使得$f(x)=\sum_{d|x}g(d)$，那么就能将路径的权值分开考虑（具体见式子）。
为了求这样的$g$，考虑莫比乌斯反演：
$$
\begin{align}
g(x)&=\sum_{d|x}f(d)\mu(\frac{x}{d})\
&=\sum_{d|x}[d\le m]\mu(\frac{x}{d})\
\end{align}
$$
那么原式
$$
\begin{align}
&=\sum_{i=1}^{|S|}\sum_{j=i+1}^{|S|}f(\gcd_{x\in path(s_i,s_j)}{x})\
&=\sum_{i=1}^{|S|}\sum_{j=i+1}^{|S|}\sum_{d>0}g(d)[d|\gcd_{x\in path(s_i,s_j)}{x}]\
&=\sum_{d>0}g(d)\sum_{i=1}^{|S|}\sum_{j=i+1}^{|S|}[d|x,x\in path(s_i,s_j)]\
\end{align}
$$
首先思考简化的问题：
如果只有一次询问， 且选了所有的点，该如何操作？
记$h_S(d)=\sum_{i=1}^{|S|}\sum_{j=i+1}^{|S|}[d|x,x\in path(s_i,s_j) ]$，
那么原式
$$
=\sum_{d>0}g(d)h_S(d)
$$
可以取出所有在树上是$d$的倍数的边按照原来的关系连边，显然这是一个森林，得出每一颗树的大小后就能轻松计算$h_S(d)$。
现在考虑多个询问：
在处理多个询问的时候，可以对于给出的点集建立虚树，虚树上$u,v$两点的边是原树的$u$到$v$上的每条边权的最大公因数。在得到的虚树上跑上述的方法即可。
注意到$g$是和$m$有关的，思考如何求$g$的值。为了保证复杂度，我们一定是先枚举$d$，然后再枚举$d$的倍数去更新$g(x)$的。因此我们考虑离线，将询问按照$m$排序，那么对于上一次询问$m’$，我们只需要用$(m’,m]$之间的$d$去更新$g(x)$就可以了。
对于一次询问：
设边的最大权值为$w$，设点集的大小为$k$
因为$\sum k,n,w$同阶，所以总复杂度为$O(n \sqrt{n})$