GDOI 2018

直面现实

Posted by Ghastlcon on May 2, 2018
CC 采用 $\text{CC BY-NC-SA 4.0}$ 许可,转载请注明:“转自 GDOI 2018

$\text{GDOI 2018}$

其实开始时是想认真写的。

但是最后莫名其妙就变成了回忆录。

明明是我跟左谭励提大样例的问题的啊

大样例可能反而会使得我这种无智商选手进队更加困难?感觉纪中二中的貌似都因为大样例而没有 $\text{FST}$ 。

$\text{Day 0}$

体育中考补考,破碎。

在车上祈祷着能够得到什么。


三人睡双人床海星。

拿走 $\text{Excalibur}$ 的机器试图摸鱼,结果发现左方向键是坏的。

这玩个锤子啊……

找 $\text{KsCla}$ 要了机器,居然还附送机械键盘 $2333$(真好啊)。

开始摸鱼,然而手感糟飞。

决死按不出来怪我咯

大约 $9:30$ 的时候被其他人强行拉出去吃东西,然而什么都没有找到,于是相当于散步我自己回去了。

大约 $00:10$ 睡了,$\text{KsCla}$ 睡不着辣 $\text{qwq}$ 。

$\text{Day 1}$

起床比较早于是成功不排队搞到早餐。

进场,诡异的密码($\texttt{tiandihe_naiganyujunjue!66}$),看题。

$\text{P1}$ 奇怪的题目,直接做貌似是 $\text{O}(N\sqrt N)$ 的,只能拿 $80\%$ 。

手推 $1\, \texttt{h}$ 柿子并不知道如何优化。

然后忽然发现这是个调和级数是 $\text{O}(N\log N)$ 的……

成功丢掉 $1\, \texttt{h}$ 。这个题就应该让选手写复杂度证明……那些不会证复杂度还过了的真的让人超级不爽……

$\text{P2}$ 应该是贪心动态规划。

我能做出来的!(送命的开始)

手推 $2\, \texttt{h}$ 然后发现啥都不会……

这样子下去真的要滚粗了……先去把 $\text{P3,P4}$ 的暴力打了。

继续玩 $\text{P2}$ 。

最终快结束的时候也没有想出来。然后随便搞了下 $\text{P3}$ ——这就是个树套树裸题……

为什么你会认为这是 $\text{P3}$ 就是不可做题啊!

扔掉 $90\%$ 。

最终 $100+30+10+0=140$ 。无话可说,已经猜到进不了 $\text{Day 3}$ 。


发现 $\text{KsCla}$ 有 $300$ 辣。

国际象棋真好玩


继续摸鱼。

又玩了整晚的 $07$,然后发现连 $\text{N}$ 都过不去 $\text{qwq}$ 。

默默切成 $10$ 开始玩。

$\text{Day 2}$

今天早餐主办方似乎改成了围桌子?

喝水看题。密码真嘲讽($\texttt{easy?gdkoi2019_jian!}$),原题比赛真好玩。

$\text{P1}$ 的边权怎么求?

我会线性筛我肯定能做出来!(送命的开始$\times 2$)

推柿子 $2\, \texttt{h}$ 之后心态炸了……

看 $\text{P2}$,发现是个简单的动态规划,多项式暴力展开即可。

$\text{P3}$ 是 $\text{CDQ}$ 分治无误,然而并不会维护信息。

$\text{P4}$ 应该不可做。

回去搞 $\text{P2}$,然而细节成堆,再加上本来就不擅长动态规划,最终也没有调出来。

$0+15+10+0=25$ 。$\text{P1}$ 奇怪地挂掉了,但是并不想去复评。


$\text{KsCla}$ 不小心丢掉了 $\text{P2}$ 的 $70\%$ ……

但是还是好强啊,愉快地谈笑风生。

然后我就忘了我推出过 $NK^2$ 的做法!


进不了 $\text{Day 3}$ 了……

想说的话放到 $\text{Memory}$ 里写。

各作换着玩之后去看 $\text{aspe}$ 搓炉石 $2333$ 。

$\text{Day 3}$

去听严紫熙讲网络流。

题目简单超有意思。


跟着 $\text{KsCla}$ 到处转。

最终的榜也很快出来了,非常可惜呢。


最后的晚上。

闲着无聊去推了下 $14$,被正邪那几张符恶心到了……

$\text{Day 4}$

本来以为要胸牌滚粗的结果居然有块废铁?很神秘。

于是大家又散了,重头来过。

$\text{Memory}$

在 $\text{GDOI 2017}$ 的末尾,我写下了“明年,我们 $\text{GDOI 2018}$ 见。”。

很快就到了自认为的 $\text{GDOI 2018}$,但是最终却仍然以失望收场——居然只有废铁。

就在刚刚过去的这年里,我进步了吗?我在为自己的目的而努力吗?

虽然事实上是如此的。

知识点的确多了很多,但是不知道为什么到了考场上就用不出来了。

非常可惜呢……石门 $8$ 年断了,更加替他们感到可惜。

$\text{Solution}$

$\text{P1}$

由于最终的块数 $x$ 是整数,并且每块的和相等,因此有 $\sum a\equiv 0\pmod x$ 。

枚举 $\sum a$ 的约数 $x$,判断能否分成 $x$ 块。其实就是判断 $a$ 的前缀和里是否存在 $\frac{\sum a}{x},\frac{2\sum a}{x},..,\frac{x\sum a}{x}$ 。

因为 $\forall i\in [0,n),a_i>0$,因此前缀和里不会出现相等的。把前缀和里的每个数都标记为出现过,然后每次判断时暴力看这 $x$ 个数是否都在前缀和里出现过即可。单次判断的时间复杂度为 $\text{O}\left (\frac{\sum A}{X}\right )$ 。

看起来复杂度是 $\text{O}(N\sqrt N)$,但是这是个调和级数,因此时间复杂度为 $\text{O}(N\log N)$ 。

$\text{P2}$

直接做会发现很困难。

由于是区间加减,考虑差分。

先在原数组的末尾加 $1$ 个 $0$ 再差分,得到长度为 $n+1$ 的 $b$ 数组。由于加入了 $0$,因此 $\sum b=0$ 。

操作变成了对某个数 $+1$,再对另外的某个数 $-1$ 。

明显,在某个数上又加又减是不优的。并且在某个数(意思是真正的操作区间从这个数开始)加$/$减次数 $\geq m$ 是不必需的(这个数已经开始循环了,如果把次数 $\geq m$ 的,真正的操作区间向后移 $1$ 位,得到的方案不会比现在差)。

又因为 $\forall i\in [0,n),a_i\in [0,m)$,所以差分后的数组的每个数在 $(-m,m)$ 内。

每个数上的操作次数均 $<m$,因此每个数最终会变成 $0/m/-m$ 。

贪心即可。

$\text{P3}$

摘苹果的操作可以无视:直接认为苹果会掉出 $1$ 号点即可。

考虑没有修改操作应该如何解决。当在时间 $t$ 询问点 $x$ 的答案时,实际上就是在问在 $x$ 的子树中,$deep_y\geq deep_x+t-1$ 的所有点 $y$ 的权值和。

子树询问,只需要把树的 $\text{DFS}$ 序建出来即可转化为区间询问。

给定 $n$ 个 $2$ 元组 $(x_i,y_i)$,每次给 $3$ 个数 $l,r,k$,求

树套树模板题。


如果有修改操作呢?在时刻 $t$ 对 $x$ 的权值增加 $v$,实际上相当于对 $x$ 加了 $1$ 个权值为 $v$ 的子结点 $y$,但是 $deep_y=deep_x+t$ 。

离线,先预处理出每个结点的 $deep$ 值与及整颗树在加完点后的 $\text{DFS}$ 序,但是这些加进来的点的权值暂时先为 $0$ 。

把所有询问和修改混合,按照时间从小到大排序。询问正常回答,修改的话找到对应的点把 $v$ 值改掉即可。

时间复杂度 $\text{O}(N\log^2 N)$ 。

$\text{P4}$

不可做题。

也许等我学了 $\text{NTT}$ 之后会回来补这题。

$\text{P5}$

如果已经计算出了边权,直接 $2$ 分跑 $\text{Heap}+\text{Dijkstra}$ 即可。

下面集中考虑如何计算边权。

……

$\text{M}\ddot{\text{o}}\text{bius}$ 反演模板题

时间复杂度

$\text{P6}$

先考虑 $k=1$ 时应该如何做。

$f[i]$ 表示在以 $i$ 为根的子树内的答案。

$\text{P7}$