专栏文章

比赛：CF2151 Div.2

cchenwenmo
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minsotg1
此快照首次捕获于
2025/12/02 07:43
3 个月前
此快照最后确认于
2025/12/02 07:43
3 个月前
查看原文

CF2151 Div.2

A. Incremental Subarray

如果有跨段的情况，答案为 11。否则子数组只在一段内，输出 n−am+1n-a_{m}+1。
Code

B. Incremental Path

考虑继承上一个人的位置，如果上一个人的最后一个操作是 BB，那么当前的人就在上一个人的终止位置进行一次 BB 操作，然后再进行这个人的最后一次操作。暴力往后跳即可，跳的次数是 O(n)O(n) 的。
Code

C. Incremental Stay

[ai,ai+1][a_i,a_{i+1}] 被覆盖的次数 xx 一定和 ii 同奇偶，并且 x≤min⁡(k,i,n−i+1)x\le \min(k,i,n-i+1)，于是可以有如下构造来使每一段被覆盖的次数都达到上界：
  • 对于两端的 (1,n),(2,n−1),⋯ ,(k−1,n−(k−1)+1)(1,n),(2,n-1),\cdots,(k-1,n-(k-1)+1) 匹配。
  • 对于中间的 (k,k+1),(k+2,k+3),⋯ ,(n−(k−1)−1,n−(k−1))(k,k+1),(k+2,k+3),\cdots,(n-(k-1)-1,n-(k-1))。
Code

D. Grid Counting

这题限制条件都很紧，从题目的条件一步步缩小计数范围即可。
Code

E. Limited Edition Shop

赛时不知道为什么想那么久贪心。考虑 DP。
设 f(i,j)f(i,j) 表示 Alice 拿完前 ii 个，Bob 拿完前 jj 个，之后 Alice 能获得的最大价值。边界是 f(n,∗)=0f(n,*)=0，答案为 f(0,0)f(0,0)。
考虑 O(n2)O(n^2) 暴力转移：
  • f(i,j)←f(i+1,j)+[j<pai+1]⋅vai+1f(i,j)\gets f(i+1,j) + [j<p_{a_{i+1}}]\cdot v_{a_{i+1}}，其中 pip_i 表示 ii 在 bib_i 中的下标。
  • f(i,j)←f(i,j+1)f(i,j)\gets f(i,j+1)。
第一个转移是前缀加，第二个转移相当于要维护后缀 max⁡\max。
如果前缀加一个正数，后缀 max⁡\max 不变。
如果前缀加一个负数，
  • 假设当前是区间 [1,p)[1,p) 加 vv，当前后缀 max⁡\max 数组为 ff。对于 [1,p)[1,p) 中所有满足 fi+v≤fpf_i+v\le f_p 的位置，相当于要直接赋值为 fpf_p；否则，直接加上 vv 不会影响后缀 max⁡\max 数组。
因此用线段树 区间加 + 区间赋值 维护即可，找位置可以用线段树二分做到 O(log⁡n)O(\log n)，直接写二分 O(log⁡2n)O(\log^2n) 也能过。
Code

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...