26.9.5 比赛记录
更新于 2026年9月26日约 2 分钟阅读
成外 & 梦熊 CSP-S 模拟赛 1。
T1
太简单,不讲了。
T2 P17313
一直没看出来,原来这题是 DP(我还把它当成贪心加大模拟)。
可以发现一个键最多只有 个字符,由于 的 LCM 是 ,因此最多按 下特殊按键所有键就会恢复原位。
设 为打出前 个字符,按 次特殊按键的花费。
转移过程:
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 绿简单?
就是直接硬做的,用的是贪心。先预处理出 ,表示 在子树中和最近的白色点的距离。之后一次 dfs 计算答案,把 次走 步转化成 次走 步,维护一个变量 ,表示还能走几步就必须着陆。 初始值为 ,当走到白色节点时恢复为 ,当走到黑色节点时减一。如果一个节点的子树中有一个白色节点,我们可以考虑在走得到的情况下先走到那个白色节点,把剩余步数重置到 ,然后再走回 这个节点。当然先走到白色子节点再走回来的方案不一定更优,取剩余 较大的方案即可。计算出节点 的 之后,我们可以计算答案,计算答案的方法也很简单, 为 就把答案加一并把 重置为 。