Posted in: QuestOJ 比赛题解

ddk的良心模拟赛 题解

内容纲要

胡萝卜

不难发现无论发了多少根胡萝卜,所有兔子的期望体重之比都是恒定的,所以可以直接计算。

std:https://questoj.cn/submission/866

乘积的和

算法1

把这个矩阵先填出来再计算。

时间复杂度$O(nm)$,期望得分$30\rm{pts}$.

算法2

考虑如何由第$i$行的答案去推第$i+1$行的答案,发现只有两个数发生了修改,暴力做修改即可。

时间复杂度$O(m+n\log n)$或者$O(m+n)$,期望得分$70\rm{pts}$.

算法3

把最后的答案直接写出来:
$$ \begin{aligned} \rm{Answer}=&\sum{i=1}^n\frac{(m+i)!}{i!}\ =&m!\sum{i=1}^n \dbinom{m+i}{i}\ =&m!(\sum_{i=0}^n \dbinom{m+i}{i}-1)\ =&m!(\dbinom{n+m+1}{n+1}-1) \end{aligned} $$

这个组合数是可以在$O(m)$的时间内做出来的,故总时间复杂度是$O(m)$的,期望得分$100\rm{pts}$.

std:https://questoj.cn/submission/865

写规划

算法1

暴力枚举全排列/写一个状压dp,期望得分$10\rm{pts}$或$20\rm{pts}$.

算法2

考虑$k=n$的部分分。本质上$p$就是$1$到$n$的排列。

首先要发现一个性质:对于树上的三个点$u,v,w$, 有$\mathrm{dis}(u,v)\leq \mathrm{dis}(u,w)+\mathrm{dis}(v,w)$.

那么对于所求就有$\mathrm{Answer}\leq 2\sum_{i=1}^n\mathrm{dis}(i,u)$, 其中$u$是树上某个点。

注意到在树上使$\sum_{i=1}^n\mathrm{dis}(i,u)$最小的$u$就是树的重心,接下来如果我们能证明在$u$取重心的时候原不等式可以取等,那么我们就找到了$\mathrm{Answer}$的一个最大值。

证明的话考虑直接构造,我们以重心为根,只要保证相邻的$p_i$不在同一棵子树即可,然后我们又知道以重心为根的子树的$\mathrm{size}\leq\lfloor \frac{n}{2}\rfloor$,于是这样的排列一定是存在的。

总时间复杂度是$O(n)$的,能通过第$5$个$\rm{subtask}$.

算法3

直接计算原式的值显然不成立,我们考虑计算每条边经过的次数。

记$f_{u,i}$为以$u$为根的子树已经选取了$i$个点时的答案最大值,那么对于一条边$(u,v)$就要去考虑如何合并$dp$值,类似于算法2,我们可以让点在子树内外反复横跳来达到最大值,更具体的,这条边的最大经过次数就是$2w\times \min(j,k-j)$)(其中$j$为在子树$v$中选取的点数),时间复杂度是$O(n^3)$,期望得分$80\rm{pts}$.

并不存在的算法4

什么你居然不知道树形背包的复杂度是$O(n^2)$的?好的你现在知道了。

什么你问我为什么不出到$1\leq n\leq 5000$?你以为我会告诉你原本就是$5000$然后出题人发现long long运算的常数巨大才换成$2000$的么。

std:https://questoj.cn/submission/862

后记

验题的时候,好哥哥limstash一眼秒了这个题。于是出题人就想把这个题出成二合一,不过后来考虑到这场比赛主打的是小清新风格就作罢了(好吧事实是出题人直到比赛前两天才编出了$k=n$的部分分做法,不过相比于套路的tree dp我更喜欢这个更有思维难度的做法,但是发现后两个题都是思维题于是就放了这个套路题上去,求轻喷qwq.)

取石子游戏

(以下题解默认大家都已了解SG函数的相关知识,如有不了解的请自行百度,当然这个题需要的只是相当基础的知识了)

算法1

根据SG函数的那一套理论,我们需要知道每一堆石子的SG值,再将它们异或起来就完事了。

继续根据SG函数的那一套理论,大小为$a$的石子的SG值就是$a\%(x+1)$,这个由归纳法不难证得。

于是就有了一个$O(n^2)$的暴力枚举的做法了,期望得分$25\rm{pts}$.

算法2

根据异或的那一套理论,我们发现对于一些有着相同数目的石子的堆而言,假设有$p$堆,那么这$p$堆等价于$p\%2$堆同样数目的石子。

这样的话对于$a_i$均相同的数据,我们在枚举$x$的同时最多只需要计算$1$堆的SG值了,结合算法1期望得分为$32\rm{pts}$.

算法3

考虑一下这个题的本质:对每个$1\leq x\leq n$的正整数$x$,求$\oplus_{i=1}^na_i\%(x+1)$,其中$\oplus$为异或运算。

考虑如何加速这个计算过程,枚举$x$显然是无法避免的,但是之后枚举每一个位置显然很呆,考虑如何优化掉这部分。

记$y=x+1$,注意到对于$a_i\in[ky,(k+1)y)$中的$a_i$,它$\%y$的值就是$a_i-ky$,这启示我们可以将在这一个区间的数一起做,这样的话时间复杂度就是调和级数了,也就是$O(n\log n)$.

光枚举值域显然是不够的,我们还需要快速得到我们所枚举的每一个区间的数的异或值。如何快速得到不带修改的区间相关的信息呢?也许有什么高超的数据结构,但是这里简单的倍增就行了。

先按照算法2所述处理掉相同的$ai$,接下来仿照st表,我们记$f{p,i}$表示那些值在区间$[i,i+2^p-1]$中的数的异或和。计算$f_{p,i}$的话,首先$p-1$位上的贡献只取决于$[i,i+2^p-1]$的后半个区间上是否有数,剩下的位的贡献显然可以从两个子区间上继承。

那么对于一个询问$[l,r]$,我们直接倍增的跳左端点,同时记录下那些有用的高位的值即可,具体实现请参照std.总时间复杂度为$O(n\log^2 n)$

std:https://questoj.cn/submission/857

红黑图

算法0

直接提交sample_tree.cpp,期望得分$0\rm{pts}$.

算法1

利用$O(n^2)$个询问得到所有边的颜色,再使用一些方法找一棵符合条件的生成树即可,期望得分$25\rm{pts}$.

算法2

边不相交这个条件用文字阐述十分麻烦,注意到正如题面所述,这个条件等价于将所有点按顺序排列在圆周上,再按照树连边,要求所有的边互不相交。

注意到这个圆周就是一个天然的符合条件的结构,于是我们先把圆周问一遍,如果只有至多一条边不同色那么就已经找到了一组合法解。

当无法找到一组合法解的时候,肯定存在一个点$u$,满足与它相关的两条边$(u,v_1),(u,v_2)$是两条颜色不一样的边。考虑一个环向内坍缩的过程,即我们在环上删去边$(u,v_1),(u,v_2)$,再加上边$(v_1,v_2)$。我们得到的新图一定还是个环,假设在这个环上有一棵合法的生成树,接下来只要考虑如何利用这棵树来构造答案,也就是如何把$u$连向这棵生成树。这其实十分easy,考虑一下我们删去的两条边,它们一定不和当前的生成树相交,我们只要找到与生成树同色的那条边就可以了。

如果新环上仍然没有我们所需要的生成树,我们可以按照上述过程递归下去,不难发现我们的访问边均是互不相交的。

询问次数的话,一开始需要$n$次询问,最坏情况下我们会坍缩到一个只有$3$个点的环,每坍缩一次就需要询问$1$次,所以最多的询问次数为$2n-3$,可以通过此题。

std:https://questoj.cn/submission/869

发表评论

电子邮件地址不会被公开。 必填项已用*标注