1 条题解

  • 0
    @ 2026-11-15 21:09:43

    A

    使用桶进行储存,然后从最大的分数从小历遍,当现在是第三个有值的,这就是第三,然后输出分数和人数就可以了。

    B

    使用 dfs 和 bfs 搜出来所有可以走到的格子即可,然后按题意计算价值。

    C

    40pts

    一共只有 33 个点,手动讨论两个人的选择情况,时间复杂度为 O(1)O(1)。

    80pts

    考虑 f[S][T]f[S][T] 表示 Alice 目前把 SS 集合染成了黑色,Bob 目前把 TT 集合染成了白色两人采取最优策略的最终答案。

    如果为 Alice 的回合,一定选所有后继状态中的最大值,如果为 Bob 的回合,一定选后继状态的最小值,每个点只有黑色/白色或还未被染色,时间复杂度不超过 O(3n)O(3^n)。

    100pts

    如果一条边最终不是黑边也不是白边,我们看成两人分别得到了这条边边权的一半。

    所以把每个点的点权看作所有邻边的边权之和的一半,按照点权两人从大到小依次取即为最优策略。

    D

    考虑求出使得 A,BA, B 不同的第一个位置 pp,有如下限制:

    • 需要修改的位置数量不能超过 kk。

    • 没有考虑到的位置数量不能小于还需要修改的位置。

    具体地,对于每一位 ii,求出 ss 表示在第 ii 位之前有多少 A≠BA \ne B 的位置。ii 合法的必要条件是 Bi≠0B_i \ne 0,先判掉。由于上述限制要求修改位置数量既不能太小,也不能太大,所以需要考虑当前位置是否修改:

    • 若 Ai<BiA_i < B_i,说明可以不修改。此时若 s≤ks \le k 且 n−i≥k−sn - i \ge k - s,则 ii 合法。

    • 若 Bi>1B_i > 1 或 Ai>0A_i > 0,说明可以强制修改(因为当 Ai=0,Bi=1A_i = 0, B_i = 1 时不能修改)。此时若 s+1≤ks + 1 \le k 且 n−i≥k−s−1n - i \ge k - s - 1,则 ii 合法。

    若找不到合法的 pp 则无解。

    输出答案的过程中时刻维护变量 kk,表示还需要修改的位置数:

    • 若当前位 i<pi < p,输出 BiB_i。

    • 若当前位 i=pi = p,若 n−i+1=kn - i + 1 = k 且 Ai+1=BiA_i + 1 = B_i,输出 Bi−2B_i - 2,否则输出 Bi−1B_i - 1,前者因为这一位必须修改(否则将导致剩余位数小于要修改位数,不合法)。

    • 若当前位 i>pi > p,若 n−i+1=kn - i + 1 = k 且 Ai=9A_i = 9输出 8 ,否则输出 9 。

    • 若输出的数字与 AiA_i 不同,则令 kk 自减 11。

    • 若 k=0k = 0,则输出 AiA_i。

    时间复杂度线性。

    E

    10pts

    暴力枚举所有可能的情况,进行判定。

    30pts

    可能满足要求的 kk 至多 1010 种,枚举哪些 kk 满足条件作容斥,把相同的数放在一起,答案为 m不同的数m^{不同的数},把所有可能的情况的答案加在一起即可。

    100pts

    我们考虑对于一个 kk 而言,满足要求的字符串有 mn−km^{n-k},但是答案会算重。

    因此我们考虑对于一个 k0k_0,计算 k0k_0 是所有满足要求的 kk 中最小的一个时的方案数。

    这意味着不存在 k<k0k<k_0,使得 S[1:k]=S[n−k+1:n]S[1:k]=S[n-k+1:n]。

    又由于 k=k0k=k_0 成立,因此 S[1:k0]=S[n−k0+1,k0]S[1:k_0]=S[n-k_0+1,k_0]。

    对比两个式子,可以得到 S[1:k]=S[k−k0+1:k0]S[1:k]=S[k-k_0+1:k_0]。

    即如果 k0k_0 是所有满足要求的 kk 中最少的一个,等价于 S[1:k0]S[1:k_0] 是一个不好的字符串,但在这里 2k≤k02k \leq k_0,而原问题中 2k<k02k<k_0,有细微差异。

    记 f[x]f[x] 为长度为 xx 的字符串中好的个数(2k<n2k<n),g[x]g[x] 为好的个数(2k≤n2k \leq n),那么有

    f[n]=∑2i<ng[i]×mn−2if[n]=\sum_{2i <n} g[i] \times m^{n-2i} g[n]=mn−∑2i≤ng[i]×mn−2ig[n]=m^n -\sum_{2i \leq n} g[i] \times m^{n-2i}

    上述表达式可以利用前缀和进行优化,时间复杂度为 O(n)O(n)。

    $$g[n]=m^n -(\sum_{2i \leq n} g[i] \times m^{-2i}) \times m^n$$
    • 1

    信息

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