2022 年上海市大学生程序设计竞赛 - 十二月赛 题解

XY_cpp edited 1 年,2 月前

由于命题失误和网站故障,本次比赛成绩不计入 EOJ 积分。

A

By XY_cpp

签到题,枚举$\sum$里面的整个式子的值,设为$x$,进而确定$x$对应的$k$的上下界,能够轻松算出$x$的贡献,复杂度$O(T\sqrt{\frac{n}{114}})$。

B

By TealCloud

B题出锅了,自首。std是觉得可以枚举26个目标终态,得到delta之后,找连续区间一直减就行,反正delta最多不超过26。所以纯暴力是2626n,如果用查分来写是26*n。但是在赛时,有选手用dp算出了更优解,验证之后发现确实std出错了。出现了我可能多走26步反而更优的情况,出题和验题的时候没有考虑到,所以补救的时候对题面条件进行了约束。对影响到的选手道歉。

C

By Huawei

注意到一个盒子里相同的数字的卡牌不会超过$5$个,可以枚举这个卡牌的排列,依次去匹配即可。

当然更快的解法可以跑最小费用最大流:

对于每个盒子里的卡牌,向能够和它匹配的判定卡牌连一条流量为1,费用为$s*p$的边;建立源点$S$,向所有的卡牌连一条流量为$1$,费用为$0$的边;建立汇点$T$,所有的判定卡牌向汇点连一条流量为$1$,费用为$0$的边。

D

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$。

E

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))$

F

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})$

Comments