「Log」2023.10.9 小记

发布时间 2023-10-10 07:50:34作者: Eon_Sky

序幕

寒气犹如来自北方的信使,凌厉而确切。
天空消退了往日的蔚蓝,宛若一块泛着淡淡铅灰色的丝绒布匹,安静地铺在无边无际的宇宙。
阳光也丧失了曾经的热烈,变得暗淡且寡味。

总结:太冷,下小雨,不想起床。

\(\text{6:40}\):准时到校,补博客,准备写题。

\(\text{7:00}\):写圆方树题。

\(\text{7:50}\):小改后切掉。

\(\color{blueviolet}{CF1763F\ Edge\ Queries}\)

路径上经过的点双中边数总和即答案,特殊地,割边的贡献要去除,简单维护一下树上前缀和即可。

间幕 \(1\)

Zpair 买了个可以躺下的电脑椅,高级的。

吃个早饭,摸鱼到 \(\text{9:00}\)

继续补 POI。

\(\color{blueviolet}{P3577\ [POI2014]\ TUR-Tourism}\)

转 DFS 树后深度不超过 \(10\),直接状压 DP(三进制)。

间幕 \(2\)

上午效率极低,开摆一会后午休。

发现一家性价比极高的烤肉饭店。

吃饭的时候一直在看 JoJo,吃了好久才开始接着写题。

\(\color{blueviolet}{P3546\ [POI2012]\ PRE-Prefixuffix}\)

给出的字符串形如 \(ABCBA\),我们,目的是使 \(AB\) 最长。考虑枚举 \(A\) 的结尾处,维护 Border,不难发现其转移方式,哈希判断相等即可。

\(\color{blueviolet}{P3530\ [POI2012]\ FES-Festival}\)

一个强联通分量答案固定,多个之间互不影响,考虑一个强连通分量贡献即 \(\min\{dis(i,j) + 1\}\)\(i,j\) 都为其中的点),Floyd 求解即可。

\(\color{blueviolet}{P3533\ [POI2012]\ RAN-Rendezvous}\)

分讨点对情况,倍增维护一下随便做了。

\(\color{black}{P3543\ [POI2012]\ WYR-Leveling Ground}\)

先转换为差分,套一个 exgcd,求出特解之后调和即可。

尾声

好困。
睡。