时过一年来补题解了233,顺便来补一下游记

一年前,参赛莫有一年的我,侥幸过了初赛,之后就是各种颓,算法都没有学几个$233$。

由于记不太清了,所以就口胡一下吧。

day0

跟$wzh$住一间房,早睡失败,精力$--$,八卦$++$

day1

第一题不是积木大赛吗?写个贪心直接水了过去。

第二题是什么神仙题?不管了,先码一个模拟,莫得正确性的贪心,水不过大样例啊,只好作罢,得了$75pts$(数据是真的水)。

第三题直接放弃,开始胡思乱想。

day2

全都不会,我还是太菜了

赛后总结

只有$200+$,果然是半吊子啊233

题解

Day1

$T1$:

就是一个随便都能水过去的模拟题,可以考虑横着连续的一块填,那么就是一个贪心。

$T2$:

排序之后,发现最小那个一定要选,之后正序遍历每一个货币,如果已经被表出,那么证明它没有贡献,因为它本身与它的倍数都能被表出。

$T3$:

以后看到最小的最大,九八不离十就是二分判定答案了。

考虑如何是最优的,由于上行路径每个子节点只能贡献一次,因此要尽量在子树内完成对答案的贡献,对于那些链已经大于$mid$长度的,直接++;

不足$mid$,根据贪心的思想,可以先排序,之后对于每个点进行二分,找到恰好能够到达$mid$的另外一条链,拼在一起,又可以贡献了。之后找一条最长的链上传就好了。最后判断一下是否到达了赛道数。

Day 2

$T1:$

分析题意可以得知

如果是一棵树,如果选择了一个子节点,一定要遍历完这棵子树才能回溯,否则就无法再到达这棵子树了。这个性质相当的重要。

之后对于每一层,排序之后,贪心选择最小的点就好了。

如果是一棵基环树,显然可以得到一个结论,环上始终有一条边是不会被遍历到的,因此可以暴力断边,$n^2(n^2log_n)$碾过去。

如果想用更高级的做法,回想一下刚刚的性质,对于环上的点,最多也只能回溯一次(从另一路径到达)。因此从环的入点出发,如果找到一个环上的位置,上一次(注意是上一次,因为回溯时必要先经过这里,才能去访问其他未访问的子树)还未遍历的子树中的最小的那个节点的编号,小于即将要遍历到的环的点,那么此时要进行回溯,使字典序更小,从另外一条路径到达即将要到达的这个点。

$T2:$

想不到$CCF$居然如此毒瘤地出找规律题

此处的$n$,均小于等于$m$

$n=1$时,就是一个$2^m$。

$n=2$时,就是一个$(1+1)^m$关于$2$次幂的系数矩阵,再带上权乘上$4$,就是答案。

$n=3$时,不好推,尝试打表找规律。

之后就可以发现,$n=3$时,就是$112*3^{m-3}$

$n=4$时,通过打表可以发现

$ans_{n+1,n+1}=ans_{n,n}*8-5*2^{n+1},n\ge 4\\ans_{n,n+1}=ans_{n,n}*3-3*2^{n},n\ge 4\\ans_{n,m+1}=ans_{n,m}*3,n\ge 4,m\ge n+1$

至于详细证明,qtm的详细证明

$T3:$

回想一下写过的树形$DP$,

$\begin{cases}f_{x,0}=\sum f_{y,1}\\f_{x,1}=\sum\min\{f_{y,0},f_{y,1}\}+val_x\end{cases}$

之后就可以很容易联想到一个$nm$的解法,也就是对于每一个询问,将那两个点的状态设一下无穷就好了,好了,你现在有$44pts$的高分。

动态$DP$不会。

因此考虑倍增$DP$乱搞。

对于两个点$(x,y)$,改变的只有$x->lca(x,y),y->lca(x,y),lca(x,y)->root$

因此需要预处理出$x$的子树信息,以及除子树以外的信息(用来快速求得$lca(x,y)->root$)

因此需要来一遍自下而上,再来一遍自顶而下的$DP$

用$g_{x,0},g_{x,1}$,$1$表示$x$这个位置放了,但这个$x$放与不放均不记录贡献,但决策状态可以相应的增加。

对于中间这一部分,可以考虑用倍增来实现乱搞。

具体实现开一个$fs_{x,i,u,v}$表示$x$的第$2^i$代祖先的子树信息减去$x$的子树信息,其中$u$代表$x$选不选,$v$代表$x$的第$2^i$代祖先选不选,与$g$同理。