Posted in: QuestOJ 比赛题解

Goodbye 2019 Solution

内容纲要

小L与小E树染色

记$d_u$为点$u$的度数,则答案为$max(d_u+1)$,构造显然

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

小L与小E打游戏

考虑 $dp$

令 $f[i][j]$ 为到侍从 $i$ 能否打出伤害值为 $j$ 的伤害

对于一个区间 $l, r$, 枚举每一个 $l \leq k \leq r$

转移方程为 $f[i][x] \rightarrow f[i+1][x + k^2]$

从 $1$ 到 $1000000$ 依次枚举 $x$ 和直接将 $f[i]$ 左移 $j^2$ 为再取或是等效的

因此可以使用 $bitset$ 优化

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

小L与小E选礼物

算法一

想一想不难发现如下的贪心:所有的正数一定会选,且如果两个正数之间有非正数的话一定会把这个非正数选上来。

直接做是$O(nq)$的,期望得分32pts。

算法二

发现答案可以被写成$\sum_{i=1}^{n-1}max(ai,a{i+1},0)$。

每次修改最多影响两个$max$的值,于是可以$O(1)$修改,时间复杂度变为$O(n+q)$,期望得分100pts。

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

小L和小E查字典

看到字符串中只包含 $a$, $b$, $c$三个字母且数据随机就能联想到 $Trie$。

题目要求对于一个字符串 $S$, 最长有多少个编号连续的 $T_i$ 不是他的前缀

考虑能否在 $Trie$ 中直接记录以某个结点为结尾的前缀有多少个编号连续的串不是他的前缀

我们依次将 $T_i$ 插入 $Trie$ 中,并用 $last$ 记录上一个访问此节点的 $T$ 的编号,那么就有 $i - last - 1$ 个编号连续字符串没有经过这个节点,也就意味着不是经过这个节点的串的前缀。

插入的过程中不断以最大值更新答案。最后再用 $n+1$ 为 $last$ 更新一下答案(对应着 $a$ 数组最后一个 $1$ 到末尾的一段)

标题的名字已经暗示了字典树

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

小L与小E编密码

以下复杂度分析均将$n,m$视为相同数。

算法一

暴力枚举所有合法序列,时间复杂度$O(n^n)$,期望得分5pts。

算法二

暴力dp,$f{i,j,k}$表示$1-i$中,当前gcd为$j$,有$k$个位置上和$a$不同的方案数,暴力转移是$O(n^4)$的,可以预处理出$g{i,j}$表示满足$gcd(i,x)=j$的数的个数,由于$j|i$,故转移可以被写成$O(n^3logn)$,原因在下面会提到。期望得分23pts.

算法三

考虑没有$a_i$的限制怎么做(即$k=0$时)。

这其实是一个经典问题,把这种$gcd$恰好为$d$的条件转化掉的话,一般考虑先求$gcd$是$d$的倍数的答案,再由其推出$gcd$恰好是$d$答案。记最后要求的是$f_d$,$d$的倍数的答案是$g_d$,那么可以写出如下的代码:

for (int i=m;i>=1;i--)
{
    f[i]=g[i];
    for (int j=i*2;j<=m;j+=i) f[i]-=f[j];
}

分析一波复杂度:最后的总执行次数应该是$m\sum_{i=1}^m\frac{1}{i}$,根据调和级数,后面那个分数求和其实是$O(logn)$于是总的时间复杂度其实是$O(nlogn)$的。

然后$g_d$的答案其实也很简单:$g_d=\lfloor\frac{m}{d}\rfloor^n$.

该算法的期望得分为15pts,结合算法二可以获得38pts。

算法四

考虑加上了$k$的限制后怎么做。

和算法三一样的,我们依然考虑怎么求$g_d$。

记$a_i$中是$d$的倍数的数的个数有$c_d$个,那么不难写出这样的式子

$$
gd=\sum{i=max(0,k-(n-c_d))}^{k}\dbinom{c_d}{i}(\lfloor\frac{m}{d}\rfloor-1)^i(\lfloor\frac{m}{d}\rfloor)^{n-c_d}
$$

上面的式子大致就是在说:$a_i$中不是$d$的倍数的位置在此时的$b$中肯定不相等;是$d$的倍数的位置中,我们枚举$i$个位置不相等的方案数。

我们发现暴力计算这个式子的时间复杂度看起来是$O(m^{1.5})$的,但是这个东西上界严重不满导致事实上跑的很快,如果你预处理幂的话就更快了。

如果你的实现中带有严格的根号算法(比如根号枚举暴力求$c_d$)或者常数很大,那么就只有80pts。把这些全部优化掉就能获得100pts了。

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

发表回复

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

Back to Top