日记

日记

Tue May 06 2025
9 分钟
2198 字

昨天晚上打 CF 去了,没写日记。

Needle in a Numstack Link to

码力题。码力太强导致赛时没写出来。

Spruce Dispute Link to

考虑如果已经删完点了如何求出最大的答案。我们考虑一个点 uu。设它的子树大小是 sizusiz_u,那么它的贡献就是 sizu×(nsizu)siz_u \times (n - siz_u)。为了最优,我们会让每一条路径都经过重心。因为重心的每个子节点 vv 所对应的子树大小 sizvsiz_v 不会大于 n2\frac{n}{2}。于是顺理成章的把重心当成根,无根树就变成了有根树,总的答案就是每个点到根的距离之和。

但是这道题恶心的很,还要我们构造方案。我们发现构造方案主要是要满足重心的每一颗子树内没有颜色相同点,我们可以把 uu 的颜色设成 timmodn2tim \bmod \frac{n}{2},因为一颗子树的大小不会超过 n2\frac{n}{2}

考虑删点。我们发现删掉一个点的代价是 depu+sizu1dep_u + siz_u - 1,因为自己没贡献了,然后子树内的每个点深度还减了 11。经过一番推导,我们发现最优的点一定是深度最小的叶子节点。删了然后按照上面的方法构造即可。

Lost and Pound Link to

我们设 dpi,jdp_{i,j} 表示还有 ii 轮,还要按 jj 次胜利按钮的获胜概率,初始为 dp0,0=1dp_{0,0} = 1

我们发现,每次按完之后都会重新打乱,也就是说不存在知道获胜按钮的情况。于是我们就可以抛弃顺序,直接转移。设按了 xx 个按钮,每个按钮按了 cic_i 次,因为没有顺序,我们钦定 cc 单增。有转移:

dpi,j=(k=1xdpi1,jci)+(nx)×dpi1,jdp_{i,j} = \left( \sum\limits_{k = 1}^{x}dp_{i - 1,j - c_i} \right) + (n - x) \times dp_{i - 1,j}

分别表示获胜按钮被按到了 cic_i 次或者压根没按到。

我们发现 mm 十分的小啊,可以直接枚举所有的 cc。大概有 50005000 多个。加上枚举状态 30230^2,时间复杂度 O(跑得过)O(\text{跑得过})

Removal of Multiples Link to

发现答案最多不会超过 3×1063 \times 10^6,剩下的就是权值线段树的事了。

记得加上奇技淫巧小剪枝。

Ancestor Relation Link to

写日记的时候才发现昨天做了好多题。

想想怎么判无解。题目里说 ai,j=1a_{i,j} = 1 时,i,ji,j 在一条从上往下的链上。而 11,作为根,肯定和所有的点都在一条链上。如果不是,就说明无解。还有:我们看,如果有 ai=aja_i = a_j,那么就说明 aia_iaja_j 相对别的点的位置相同,可以得到他们在一条链上,也就是说必须有 ai,j=1a_{i,j} = 1,否则就无解。还有,如果有 aiaja_i \subseteq a_j,那么就说明 jjii 的祖先,如果没有 ai,j=1a_{i,j} = 1,同样无解。

剩下的就全是有解的状态了。考虑两个点何时能够交换。发现当且仅当 ai=aja_i = a_j 时能够交换。我们就可以把 nn 个点分成几个集合,aa 相同的在一个集合。每个集合的方案数就是 siz!siz!,乘起来即可。

我们发现所有的操作都可以用 bitset 维护。所以时间复杂度 O(n3ω)O(\frac{n^3}{\omega}),其中 ω\omegabitset 常数。

Apple Tree Traversing Link to

码力依然强大。

我们发现“字典序最大”,而排在前面的又是长度,我们肯定是让长度最大。于是我们先取个直径。取完直径之后就分成了几个子树,递归处理即可,时间复杂度 O(nn)O(n \sqrt{n})

Cycling (Easy Version) Link to

我们设 dpidp_i 表示跳到了 ii 后面还要多少代价才能跳到最前。初始有 dp0=0dp_0 = 0。转移时考虑最后一个区间 [j+1,i][j + 1,i]。我们发现最优策略是把 [j+1,i][j + 1,i] 里的最小值拿过来一直超,代价为 (ipos)+(ij1)+val×(ij)(i - pos) + (i - j - 1) + val \times (i - j),分别表示把最小值掏过来,最小值跟着走,超最小值的总代价。于是我们拥有 O(n2)O(n^2) dp,可以通过简单版。

Cycling (Hard Version) Link to

不会 O(n)O(n) 做法。

我们发现其实我们是可以确定区间的分界点的。比如我们拿一个样例:4 1 3 2。我们首先拿 22 一直超。直到我们发现这里出现了一个 11。我们发现拿 11 一直超比拿 22 一直超更优。于是我们改拿 11 一直超。我们把 dpidp_i 的意义改一下,改成:先拿最后的一直超,直到现在超的比前一个数小,我们改拿前一个数继续超,如此循环往复。用此策略超到最前面的最小代价。显然,这玩意可以 O(n)O(n) 预处理。

不懂策略的看过来
比如 4 1 3 2 5 3,先拿 33 一直超,直到我们看到了 22,就改拿 22 继续超,然后我们又看到了 11,我们又改超 11

那有人要问了:你没考虑把一段区间的最小值掏过来然后拿它一直超的情况啊?确实没考虑,所以我们现在考虑。依然是这个样例:4 1 3 2 5 3。假设我们现在在第 66 个数后面。如果我们想把 22 掏过来超,那么需要花费的代价是 dp4+(64)×2+2×(641)dp_4 + (6 - 4) \times 2 + 2 \times (6 - 4 - 1)。每一项分别表示:已经走到 22 所在的位置还需要的代价,22 往返需要的代价,不停的超过 22 需要的代价。

我们再推几组样例,会发现:如果我想把 aia_i 拿到 jj 的位置然后一直超,所需要的代价是 dpi+(ji)×2+(ji1)×aidp_i + (j - i) \times 2 + (j - i - 1) \times a_i。这玩意可以看做是一个关于 jj 的一次函数。总共 nn 个一次函数。我们把所有的一次函数都塞到一颗李超线段树里,然后每个位置的答案就是在这个位置查最小值。

05-04 T1 Link to 05-04 T1

我居然记得去问?

首先有一个结论:如果上一层有 xx 个非叶子节点,上上层有 yy 个,那么这一层至多有 x+yx + y 个非叶子节点。因为每个点可以选择是当左儿子还是右儿子,分别代表上一层和上上层。

我们肯定是按照 aa 从大到小,深度从小到大填的。设 dpd,i,x,ydp_{d,i,x,y} 表示当前的深度为 dd(这一层的叶子已经确定),一共有 ii 个点被钦定成了叶子,这一层还有 xx 个空位,下一层还有 yy 个空位。转移枚举下一层钦定 tt 个作为叶子:

dpd,i,x,y+(sumi+tsumi)×(d+1)dpd+1,i+t,yt,x+ytdp_{d,i,x,y} + (sum_{i + t} - sum_i) \times (d + 1) \to dp_{d + 1,i + t,y - t,x + y - t}

我们发现 dd 其实是不必要的,状态改成 dpi,x,ydp_{i,x,y}。依然是钦定这一层有 tt 个叶子:

dpi,x,y+(sumnsumi)dpi+t,yt,x+ytdp_{i,x,y} + (sum_n - sum_i) \to dp_{i + t,y - t,x + y - t}。

之所以加的值从 sumi+tsumisum_{i + t} - sum_i 变成了 sumnsumisum_n - sum_i,是因为最开始钦定所有的深度都为 00,转移时使一段后缀的深度 +1+1

我们发现这依然是 O(n4)O(n^4) 的,跑不过。究其原因是转移是 O(n)O(n) 的。考虑简化转移:

  1. 再钦定一个点作为叶子:dpi,x,ydpi+1,x1,y1dp_{i,x,y} \to dp_{i + 1,x - 1,y - 1}
  2. 往下一层:dpi,x,ydpi,y,x+ydp_{i,x,y} \to dp_{i,y,x + y}

于是转移就变成了 O(1)O(1),总复杂度 O(n3)O(n^3)。记得滚动数组优化空间。

关于 dpi,x,ydpi+1,x1,y1dp_{i,x,y} \to dp_{i + 1,x - 1,y - 1}
因为本来就钦定的剩下的都在这一层,所以转移的时候不用加。x,yx,y1-1 的原因是这一层少了一个,xx 自然要 1-1。但是上一层又没变,所以 yy 也减了 11

后日谈 Link to 后日谈

才发现我这两天做了这么多题。

因为每次想要颓废的时候看到草神,就感觉颓废对不起自己,于是再切一道题。

拼命练就的本领绝不会辜负自己。