1 条题解

  • 0
    @ 2026-11-15 19:27:38

    题目分析

    天(sky)题解

    很明显问题就是问 ss 能否变成 s′s'。读入字符串后枚举 ss 的每一位,依题意模拟即可。

    云(cloud)题解

    两种顺序的不同之处只在于同行的棋子的顺序是反着来的。根据这个可以有不同的做法,我们只讲其中一种:记 pip_i 表示 aia_i 在 bb 中的出现位置,那么 pp 序列的每个极长下降段便标识了同行的棋子,对于一个极长下降段 [l,r][l,r],a[l,r]a[l,r] 和 b[l,r]b[l,r] 应该是反序的关系,判断一下,如果不是反序就没有可行方案。这样我们会分出若干段,如果段数超过了 nn 也没有可行方案,否则相当于先从 nn 行里选出若干行,行内再进行放置,用组合数算一下方案数即可。这里只需要用到递推 C(n,m)=C(n−1,m−1)+C(n−1,m)C(n,m)=C(n-1,m-1)+C(n-1,m)。

    雨(rain)题解

    卷王狂潮的过程其实构成了一棵满二叉树,LTF 只需要与 [2,2],[3,4],[5,8],⋯ ,[2n−1+1,2n][2,2],[3,4],[5,8],\cdots,[2^{n-1}+1,2^n] 中的胜者竞争。有一个自然的贪心策略是在 LTF 参与的这 nn 场竞争中,能不使用金手指就不使用,也就是说每次竞争如果不使用金手指就会被淘汰,那就使用金手指使得 LTF 的幸福指数与对手恰好相等,这样由于 LTF 编号最小,对手一定会被淘汰。假设知道了 [2w−1+1,2w][2^{w-1}+1,2^w] 区间内的胜者的幸福指数,那么模拟这个过程是 O(n)O(n) 的。

    于是考虑每次修改对于胜者的幸福指数的影响,不难发现第 2i−12i-1 和第 2i2i 个人的幸福指数同时加上 xix_i 相当于没加,所以区间修改顶多会在端点处会产生影响。维护一下树形结构,就可以 O(n)O(n) 地处理出端点修改造成的变化。复杂度 O(2n+nm)O(2^n+nm)。

    情(friendship)题解

    题意抽象出来就是:给定一张 nn 个点 mm 条边的无向连通图,qq 次询问 [l,r][l,r] 中有多少整数 ww 满足存在一条从点 11 到点 xx 的长度为 ww 的路径。保证边权只有 1,21,2 两种。

    首先来考虑如果只有边权为 11 的边怎么做,其实就是经典的奇偶最短路,可以参考 [CSP-J2019] 加工零件。对于每个 xx 先求出 11 到 xx 的长度为偶数的最短路 dx,0d_{x,0} 和长度为奇数的最短路 dx,1d_{x,1},那么通过在 11 权边上左右横跳我们就能够构造出所有长度为 dx,0+2kd_{x,0}+2k 和 dx,1+2kd_{x,1}+2k 的路径(kk 为自然数),又因为不可能有路径的长度比这两个值更小,所以这实际上就是所有可能的路径长度。

    注意到这个做法的关键在于抓住一条 11 权边左右横跳,使得所有比 dx,0d_{x,0} 大的偶数都能被得出(奇数同理)。那对于有 22 权边的情况,奇最短路经过的边里肯定有 11 权边,所以不会受到影响;但是偶最短路却有可能仅由 22 权边组成,此时”左右横跳“的调整就只能做到 +4k+4k 而非 +2k+2k,会漏掉一部分偶数。为了应对这种情况,我们只需要额外求出至少经过一条 11 权边的偶最短路,这个也是好做的,类似最短路拓展到奇偶最短路,在跑奇偶最短路时额外记录一维 0/10/1 表示目前有没有走过 11 权边即可。这一部分的复杂度视最短路的实现而定,如果用堆优化 Dijkstra 复杂度为 O(nlog⁡n)O(n\log n)(默认 n,mn,m 同阶)。 回答询问时,奇数部分是一个公差为 22 的等差数列,偶数部分是公差分别为 2,42,4 的两个等差数列求并,可以通过简单的分类讨论以 O(1)O(1)​ 的复杂度完成。

    T5

    做法:若 lowbit(n)\text{lowbit(n)} 小于等于 kk ,则先手胜,否则后手胜。

    证明:若 lowbit(n)\text{lowbit(n)} 小于等于 kk , 则先手取 lowbit(n)\text{lowbit(n)} ,之后后手无论取什么数,先手只需重复后手的取数即可。

    若 lowbit(n)\text{lowbit(n)} 大于 kk , 则先手无论取何数字,取之后的 lowbit(n)\text{lowbit(n)} 一定小于等于 kk ,此时后手必胜。

    • 1

    信息

    ID
    177
    时间
    1000ms
    内存
    512MiB
    难度
    3
    标签
    递交数
    1
    已通过
    1
    上传者