Logo EncodeTalker的博客

博客

标签
暂无

ddk的良心模拟赛 题解

2020-02-29 18:32:51 By EncodeTalker

胡萝卜

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

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所述处理掉相同的$a_i$,接下来仿照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

ddk的良心模拟赛 公告

2020-02-26 08:17:26 By EncodeTalker

在网课的间隙,你是否会感到空虚;

在作业的尽头,你是否会滋生焦虑;

你是否还在吐槽着练习题的千篇一律,

抑或是疫情之下无法出门的枯燥无趣?

那么,放下你的鼠标,握起你的妙笔,

“退群杯” “ddk的良心模拟赛”,发挥你卓越的才能!

大家好!我不是EncodeTalker,我是ddk,一位刚学OI大概10天的萌新,喜欢唱跳rap爆零射箭。EncodeTalker是我的一位可爱的圆滚滚的学长(雾)。

有一天,我拿着我刚学OI时遇到的难题去问我的学长,学长沉思了$(10^9+7) s$后,说“这些题实在太简单了,我分分钟切爆,而且我可以把它们加强哦。我来看看你会不会做加强版吧。“看着一道道我不会的题目,我只能来求助各位了。

本次比赛将于2020年2月29日下午2:00开始,将进行4.5h,共有5个题目,其中包含一道交互题,如果您对交互题了解较少,可以参照这个题的“使用交互库”的评测方式。

希望大家能帮助来自乌干达的可怜的ddk,祝大家在切题的时候都能“ちまちませずに、ドーンと行くぜ!”(雾)

注:本次比赛全程提供赛时答疑,如对题目有任何疑问可直接询问我的学长EncodeTalker.

Goodbye 2019 Solution

2019-12-28 23:41:31 By EncodeTalker

小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(a_i,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$个,那么不难写出这样的式子

$$ g_d=\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

Goodbye 2019

2019-12-23 22:16:50 By EncodeTalker

时间过得真快啊,2019年已经接近尾声了。

在2019年里,小E碰到了许多事情,其中最重要的就是认识了小L。他们两个人一起干过了许多愉快的事情(这里请各位看官自己脑补)。

有一天,小E突然意识到一件事情,他们还没有一起出过一场比赛!

于是就有了这场象征着告别2019的历史的比赛了。

本次比赛时长4小时,共有5题,将在2019年12月28日(星期六)13:30开始,难度横跨入门到csp-s中的中等偏难,出题人是 limstashEncodeTalker 。本次比赛不分设Div1和Div2.

赛制采取类OI赛制,每一题的测试数据被分成了若干subtask,只有通过了某一subtask的全部测试数据才能获得这个subtask的所有分数,同时对每个subtask良心的出题人都造了一组样例数据,在提交代码时会作为pretest进行测试。

祝大家玩得开心!GL&HF!

UPD:由于各种原因,本次比赛不提供赛时答疑,出题人将会尽可能保证不出锅qwq。

UPD2:Solution

共 4 篇博客