1 条题解
-
0
题目分析
天(sky)题解
很明显问题就是问 能否变成 。读入字符串后枚举 的每一位,依题意模拟即可。
云(cloud)题解
两种顺序的不同之处只在于同行的棋子的顺序是反着来的。根据这个可以有不同的做法,我们只讲其中一种:记 表示 在 中的出现位置,那么 序列的每个极长下降段便标识了同行的棋子,对于一个极长下降段 , 和 应该是反序的关系,判断一下,如果不是反序就没有可行方案。这样我们会分出若干段,如果段数超过了 也没有可行方案,否则相当于先从 行里选出若干行,行内再进行放置,用组合数算一下方案数即可。这里只需要用到递推 。
雨(rain)题解
卷王狂潮的过程其实构成了一棵满二叉树,LTF 只需要与 中的胜者竞争。有一个自然的贪心策略是在 LTF 参与的这 场竞争中,能不使用金手指就不使用,也就是说每次竞争如果不使用金手指就会被淘汰,那就使用金手指使得 LTF 的幸福指数与对手恰好相等,这样由于 LTF 编号最小,对手一定会被淘汰。假设知道了 区间内的胜者的幸福指数,那么模拟这个过程是 的。
于是考虑每次修改对于胜者的幸福指数的影响,不难发现第 和第 个人的幸福指数同时加上 相当于没加,所以区间修改顶多会在端点处会产生影响。维护一下树形结构,就可以 地处理出端点修改造成的变化。复杂度 。
情(friendship)题解
题意抽象出来就是:给定一张 个点 条边的无向连通图, 次询问 中有多少整数 满足存在一条从点 到点 的长度为 的路径。保证边权只有 两种。
首先来考虑如果只有边权为 的边怎么做,其实就是经典的奇偶最短路,可以参考 [CSP-J2019] 加工零件。对于每个 先求出 到 的长度为偶数的最短路 和长度为奇数的最短路 ,那么通过在 权边上左右横跳我们就能够构造出所有长度为 和 的路径( 为自然数),又因为不可能有路径的长度比这两个值更小,所以这实际上就是所有可能的路径长度。
注意到这个做法的关键在于抓住一条 权边左右横跳,使得所有比 大的偶数都能被得出(奇数同理)。那对于有 权边的情况,奇最短路经过的边里肯定有 权边,所以不会受到影响;但是偶最短路却有可能仅由 权边组成,此时”左右横跳“的调整就只能做到 而非 ,会漏掉一部分偶数。为了应对这种情况,我们只需要额外求出至少经过一条 权边的偶最短路,这个也是好做的,类似最短路拓展到奇偶最短路,在跑奇偶最短路时额外记录一维 表示目前有没有走过 权边即可。这一部分的复杂度视最短路的实现而定,如果用堆优化 Dijkstra 复杂度为 (默认 同阶)。 回答询问时,奇数部分是一个公差为 的等差数列,偶数部分是公差分别为 的两个等差数列求并,可以通过简单的分类讨论以 的复杂度完成。
T5
做法:若 小于等于 ,则先手胜,否则后手胜。
证明:若 小于等于 , 则先手取 ,之后后手无论取什么数,先手只需重复后手的取数即可。
若 大于 , 则先手无论取何数字,取之后的 一定小于等于 ,此时后手必胜。
- 1
信息
- ID
- 177
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者