文章分类:题解

    文章分类:题解

    • 「CF2145G」Cost of Coloring

      CF2145G

      有一个 n×mn \times m 的网格图。最初,每个格点都没有颜色。

      每次操作,你可以选择任意一行或一列染色。在第一次操作中,你只能选择颜色 11;在第 i(i>1)i(i > 1) 次操作,你可以选择颜色 ci−1c_{i - 1} 或 ci−1+1c_{i - 1} + 1(其中 ci−1c_{i - 1} 表示第 i−1i - 1 次操作选择的颜色)。

      如果满足以下条件,我们称最终的染色结果为优美:

      • 每个单元格都被染色。
      • 1∼k1 \sim k 的每个颜色都被使用(至少有一个单元格被染成该颜色)。

      对于优美的最终染色,我们定义优美值为实现该染色方案最少需要的操作次数。

      对于 i=min⁡(n,m),…,n+m−1i = \min(n, m), \dots, n + m - 1,你需要求出优美值为 ii 的优美染色个数。

      数据范围:2≤n,m≤20002 \leq n, m \leq 2000,1≤k≤n+m−11 \leq k \leq n + m - 1。

      时空限制:33s / 512512MiB。

    • 「2024 ICPC 上海站」F. Fast Bogosort

      QOJ 9042

      给出一个关于 nn 的排列 aa,对排列 aa 使用 Fast Bogosort:

      • 如果数组已经有序,则算法终止。
      • 否则,将数组划分成尽可能多的区间,每个区间 [l,r][l, r] 恰好包含 [l,r][l, r] 中的所有数字。注意区间不能重叠,并且他们的并集为 [1,n][1, n]。
      • 对于每个被划分的区间 [l,r][l, r],如果 l<rl < r,则调用 shuffle(l, r),在区间 [l,r][l, r] 内均匀随机打乱数字。

      现在,请你计算对排列 aa 使用 Fast Bogosort,shuffle 函数的期望调用次数。

      数据范围:1≤n≤1051 \leq n \leq 10^5。

      时空限制:33s / 10241024MiB。

    • 「4th Ucup Stage 1」K. Robot Construction

      QOJ 14436

      给出一个非负整数序列 a1,a2,…,ana_1, a_2, \dots, a_n。初始时,你可以创造一个机器人,高度为 [0,d][0, d] 之间的正整数。每当经过一个检查点 aia_i 时,如果当前的高度 hh 满足 h≥aih \geq a_i,则高度 h←h−aih \gets h - a_i;否则不会发生任何事。

      有 QQ 次询问,每次询问给出两个正整数 l,rl, r (1≤l≤r≤n1 \leq l \leq r \leq n),你需要选择机器人的初始高度,使得依次经过检查点 al,…,ara_l, \dots, a_r 之后机器人剩下的高度最大,你只需要求出该高度即可。

      数据范围:1≤n,Q≤3×1051 \leq n, Q \leq 3 \times 10^5,1≤d≤1091 \leq d \leq 10^9,0≤ai≤1090 \leq a_i \leq 10^9,1≤l≤r≤n1 \leq l \leq r \leq n。

      时空限制:11s / 256256MiB。

    • 「CF2150D」Attraction Theory

      CF2150D

      有 nn 个人,分别位于坐标轴上的 p1,…,pnp_1, \dots, p_n 位置。初始时 pi=ip_i = i。

      你可以在坐标轴上的某个位置 xx (1≤x≤n1 \leq x \leq n) 放置一个景点,接下来所有人都会朝着这个景点靠拢。具体地,对于每个人 ii:

      • 若 pi=xp_i = x,则位置不变。
      • 若 pi<xp_i < x,则向右走一步 pi←pi+1p_i \gets p_i + 1。
      • 若 pi>xp_i > x,则向左走一步 pi←pi−1p_i \gets p_i - 1。

      每个位置 xx 都有一个对应的权值 axa_x,对于某一时刻的站位数组 p1,…,pnp_1, \dots, p_n,得分定义为

      ∑i=1napi\sum_{i = 1}^n a_{p_i}

      你可以进行任意次操作,每次放置景点的位置任选。对于所有可能的站位数组 pp,你需要求出得分总和。答案对 998244353998244353 取模。

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

      时空限制:22s / 256256MiB。

    • 「QOJ 9904」最小生成树

      QOJ 9904

      给出一个包含 nn 个点的完全图,节点编号为 1∼n1 \sim n,其中 i,j(i≠j)i, j(i \neq j) 之间的边权为 ai+ja_{i + j},求这张图的最小生成树。

      数据范围:2≤n≤2×1052 \leq n \leq 2 \times 10^5,1≤ai≤1091 \leq a_i \leq 10^9。

      时空限制:33s / 256256MiB。

    • 「ABC409G」Accumulation of Wealth

      ABC409G

      给出一个正整数 nn 和一个整数 P∈[0,100]P \in [0, 100],记 p=P100p = \frac{P}{100}。

      有一个正整数序列 aa。初始时,aa 的长度为 11,且 a1=1a_1 = 1。

      接下来会对 aa 进行操作 n−1n - 1 次。每次操作,有 pp 的概率执行操作 1,有 1−p1 - p 的概率执行操作 2。记 mm 是不出现在 aa 中的最小正整数。

      • 操作 1:将 mm 添加到序列 aa 的末尾。
      • 操作 2:记 c1,…,cm−1c_1, \dots, c_{m - 1} 分别表示 1,…,m−11, \dots, m - 1 在 aa 中的出现次数。在 1,…,m−11, \dots, m - 1 中按照与 ckc_k 成正比的概率选择一个数 kk(即概率为 ck/∑j=1m−1cjc_k / \sum_{j = 1}^{m - 1} c_j)。然后将 kk 添加到序列 aa 的末尾。

      请你求出 1,…,n1, \dots, n 在操作结束后在 aa 中的期望出现次数。答案对 998244353998244353 取模。

      数据范围:1≤n≤1051 \leq n \leq 10^5,0≤P≤1000 \leq P \leq 100。

      时空限制:22s / 10241024MiB。

    • 「ABC390G」Permutation Concatenation

      ABC390G

      给出一个正整数 nn。

      对于一个长度为 nn 的整数序列 A={a1,a2,…,an}A = \{a_1, a_2, \dots, a_n\},设 f(A)f(A) 表示 a1∼ana_1 \sim a_n 顺次连接构成的十进制数值 a1…an‾\overline{a_1\dots a_n}。例如 f({1,20,34})=12034f(\{ 1, 20, 34 \}) = 12034。

      你需要对于 nn 的所有排列 PP,求出 f(P)f(P) 之和。答案对 998244353998244353 取模。

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

      时空限制:22s / 10241024MiB。

    • 「2024 北京市赛」E. 骰子

      QOJ 8717

      有 nn 枚 m+1m + 1 面的骰子,m+1m + 1 个面上分别写着 0∼m0 \sim m,丢出第 ii 枚骰子使得数字 jj 朝上的概率永远是 pi,jp_{i, j}。

      你打算投 QQ 轮骰子,第 ii 次你会将编号在 [li,ri][l_i, r_i] 中的骰子全部掷出,将每个骰子面朝上的数字相加,设总和是 sum\mathrm{sum},若 sum≤m\mathrm{sum} \leq m,你会获得 bsumb_{\mathrm{sum}} 的开心度,否则你将什么都得不到。

      请你求出每一轮投骰子,得到的开心度的期望是多少。答案对 109+710^9 + 7 取模。

      数据范围:1≤n≤15001 \leq n \leq 1500,1≤m≤2001 \leq m \leq 200,1≤Q≤6×1051 \leq Q \leq 6 \times 10^5。

      时空限制:未知。

    • 「2024 杭电多校 3」1004. 游戏

      HDU 7460

      有 nn 名玩家进行游戏,每个玩家都有一个初始能力值 aia_i。

      游戏会进行 tt 轮,每一轮会等概率随机选择两个不同的人,将他们的能力值分别加 11。

      求游戏结束后,∑1≤i<j≤n[ai=aj]\sum\limits_{1 \leq i < j \leq n} [a_i = a_j] 的期望值。答案对 998244353998244353 取模。

      数据范围:2≤n≤1062 \leq n \leq 10^6,1≤t≤1071 \leq t \leq 10^7,1≤ai≤1061 \leq a_i \leq 10^6。

      时空限制:66s / 512512MiB。

    • 「Luogu P4389」付公主的背包

      Luogu P4389

      有 nn 种物品,其中第 ii 种物品的体积为 viv_i,每一种物品的数量都是无限的。

      给出背包的体积上限 mm,对于 s∈[1,m]s \in [1, m],你都需要求出使用这些物品恰好装满 ss 体积的方案数。两个方案不同当且仅当存在某个物品的选取个数不同。

      数据范围:1≤n,m≤1051 \leq n, m \leq 10^5,1≤vi≤m1 \leq v_i \leq m。

      时空限制:11s / 500500MiB。