26.9.5 比赛记录

更新于 2026年9月26日约 2 分钟阅读

成外 & 梦熊 CSP-S 模拟赛 1。

T1

太简单,不讲了。

T2 P17313

一直没看出来,原来这题是 DP(我还把它当成贪心加大模拟)。

可以发现一个键最多只有 55 个字符,由于 1,2,3,4,51,2,3,4,5 的 LCM 是 6060,因此最多按 6060 下特殊按键所有键就会恢复原位。

设 dpi,jdp_{i,j} 为打出前 ii 个字符,按 jj 次特殊按键的花费。

转移过程:

if(src!=dst)cost=abs(dst-src)+q;
else cost=p;
dp[i][j]=min(dp[i][j],dp[i-1][j>=k?j-k:j+60-k]+t*k+cost);

T3

原题做过,不讲了。

T4 P17307

怎么感觉 T4 紫比 T2 绿简单?

就是直接硬做的,用的是贪心。先预处理出 fuf_u,表示 uu 在子树中和最近的白色点的距离。之后一次 dfs 计算答案,把 11 次走 kk 步转化成 kk 次走 11 步,维护一个变量 step\text{step},表示还能走几步就必须着陆。step\text{step} 初始值为 kk,当走到白色节点时恢复为 kk,当走到黑色节点时减一。如果一个节点的子树中有一个白色节点,我们可以考虑在走得到的情况下先走到那个白色节点,把剩余步数重置到 kk,然后再走回 uu 这个节点。当然先走到白色子节点再走回来的方案不一定更优,取剩余 step\text{step} 较大的方案即可。计算出节点 uu 的 step\text{step} 之后,我们可以计算答案,计算答案的方法也很简单,step\text{step} 为 00 就把答案加一并把 step\text{step} 重置为 kk。

Vector Log · 算法竞赛学习笔记

Built with Nuxt UI & Nuxt MDC