文章分类:题解

    文章分类:题解

    • 「CF1313D」Happy New Year

      CF1313D

      有 mm 个孩子,编号为 1∼m1 \sim m。

      圣诞老人会 nn 种魔法,第 ii 种魔法可以给所有编号在区间 [Li,Ri][L_i, R_i] 内的孩子各发一个糖果。每种魔法最多使用一次,并且已知如果所有魔法都使用,每个孩子至多收到 kk 个糖果。

      你可以控制这 nn 种魔法的使用情况,请你求出最多有多少个孩子收到奇数个糖果。

      数据范围:1≤n≤1051 \leq n \leq 10^5,1≤m≤1091 \leq m \leq 10^9,1≤k≤81 \leq k \leq 8。

      时空限制:22s / 500500MiB。

    • 「CF875F」Royal Questions

      CF875F

      有 nn 个王子与 mm 个公主。每个公主有喜欢的两个王子,编号分别为 ai,bia_i, b_i,但一个王子只能娶一个公主,一个公主也只能嫁给一个王子。每个公主有一个嫁妆价值 wiw_i。

      求国王能够得到的嫁妆最大值(允许有王子或公主无伴侣)。

      数据范围:2≤n≤2×1052 \leq n \leq 2 \times 10^5,1≤m≤2×1051 \leq m \leq 2 \times 10^5。

      时空限制:1.51.5s / 500500MiB。

    • 「CF1559D2」Mocha and Diana (Hard Version)

      CF1559D2

      给出两个森林,节点数均为 nn,节点编号均为 1∼n1 \sim n。

      你可以进行加边操作。每次操作,你需要选择两个不同的正整数 x,yx, y,然后在两个森林中都加上 (x,y)(x, y)。你需要保证两个森林在加边后仍然是森林。

      求最多可以加几条边。并给出加边方案。

      数据范围:1≤n≤1051 \leq n \leq 10^5,0≤m1,m2<n0 \leq m_1, m_2 < n。

      时空限制:22s / 250250MiB。

    • 「CF2077C」Binary Subsequence Value Sum

      CF2077C

      对于一个二进制字符串 vv,定义其分数为

      max⁡0≤i≤∣v∣{F(v,1,i)×F(v,i+1,∣v∣)}\max_{0 \leq i \leq |v|} \{ F(v, 1, i) \times F(v, i + 1, |v|) \}

      其中 F(v,l,r)=r−l+1−2×zero(v,l,r)F(v, l, r) = r - l + 1 - 2 \times \mathrm{zero}(v, l, r),这里 zero(v,l,r)\mathrm{zero}(v, l, r) 表示子串 v[l:r]v[l : r] 中 0 的数量。

      给出一个长度为 nn 的二进制字符串 ss。

      有 QQ 次操作,每次操作都会给出一个 ii (1≤i≤n1 \leq i \leq n),你需要将 sis_i 取反。每次操作结束后,你都需要求出 ss 的所有非空子序列的得分之和。答案对 998244353998244353 取模。

      数据范围:1≤n≤2×1051 \leq n \leq 2 \times 10^5,1≤q≤2×1051 \leq q \leq 2 \times 10^5。

      时空限制:33s / 256256MiB。

    • 「CF1209E2」Rotate Columns (hard version)

      CF1209E2

      给出一个 n×mn \times m 的矩阵 aa。

      你可以进行若干次操作。每次操作,你可以选择任意一列,并循环移位该列中的元素。

      设 rir_i 表示第 ii 行的最大值,求 ∑i=1nri\sum_{i = 1}^n r_i 的最大值。

      数据范围:1≤n≤121 \leq n \leq 12,1≤m≤20001 \leq m \leq 2000,1≤ai,j≤1051 \leq a_{i, j} \leq 10^5。

      时空限制:33s / 512512MiB。

    • 「CF1253F」Cheap Robot

      CF1253F

      给出一个包含 nn 个点 mm 条边的简单无向连通带权图。节点编号为 1∼n1 \sim n,其中恰好有 kk 个充电中心,编号为 1∼k1 \sim k。

      有一个电池容量为 cc 的机器人在图中移动,任意时刻电量 xx 必须为区间 [0,c][0, c] 中的整数。经过一条长度为 ww 的边需要消耗 ww 的电量,每当到达一个充电中心时,其电池将会充满。

      有 QQ 次询问,每次询问给出 a,ba, b,你需要求出机器人从 aa 到 bb 至少需要的电池容量 cc 是多少。

      数据范围:2≤k≤n≤1052 \leq k \leq n \leq 10^5,1≤m,Q≤3×1051 \leq m, Q \leq 3 \times 10^5,1≤w≤1091 \leq w \leq 10^9,1≤a,b≤k1 \leq a, b \leq k,a≠ba \neq b。

      时空限制:33s / 512512MiB。

    • 「FJOI 2018」领导集团问题

      Luogu P4577

      给出一棵大小为 nn 的树,第 ii 个节点的权值为 wiw_i。

      你需要选出一个最大的节点集合,使得节点集合中不同的两个点 i,ji, j,若 ii 为 jj 的祖先节点,必须满足 wi≤wjw_i \leq w_j。

      数据范围:1≤n≤2×1051 \leq n \leq 2 \times 10^5,1≤wi≤1091 \leq w_i \leq 10^9。

      时空限制:10001000ms / 250250MiB。

    • CSP2022-S 题解

    • FJOI2022 题解

      先开个档,有空再填。

    • 「CTSC 2010」珠宝商

      Luogu P4218

      给出一棵包含 nn 个节点的树,每个节点上都有一个字符。除此之外,还会给出一个长度为 mm 的文本串。

      求树上所有路径,经过的所有字符按顺序连接形成的字符串,在文本串中的出现次数之和。

      数据范围:1≤n,m≤5×1041 \leq n, m \leq 5 \times 10^4,给出的字符均为小写字母。

      时空限制:88s / 500500MiB。