Codeforces exercises 2025
记录了25/1/4-25/10/3的二十六场 codeforces, \(rating\;1785\rightarrow1868\)
随着 AI 的发展以及表达的沉默, 这就是最后的记录了
我的最后一场 codeforces 比赛在 25/10/19 结束, 最终 rating 1938,
对我足够了
Undone 部分不会补充
Hello 2025 25/1/4
\((1785 \rightarrow 1819,
rk1577)\)
掌握了挣扎的能力, 跳过 D 把 E1 开出来了, 这就说明我还是有希望的？
D 数据结构
给你一个长度为 \(N\) 的序列 \(a\), 有 \(q\) 次修改, 每次令 \(a_p = x\) , 问最初以及每次修改后, 对于 $ 1 l r N$, \(max(a_l, a_{l+1}, ..., a_r) - min(a_l, a_{l+1}, ..., a_r) - (r-l)\) 的最大值
\(N, q \leq 2e5;\; a_i, x \leq 10^9\)
思路:
明显最大值和最小值要分别为选定序列的两端, 否则序列长度可以进一步缩小,
看到这个 \(r-l\)
的形式我们自然想到构造偏移量将其抵消,
为此我们要讨论最大值在左端以及最大值在右端的两种情况, 最大值在左端时,
\(a_p +=p\) , 最大值在右端时, \(a_p -= p\) , 我们的线段树要维护五个值,
分别是两种最大值, 两种最小值以及最终答案。
我们可以写个 info 结构体来弄这个东西, 更新答案时在
左树答案、右树答案、右树右最大-左树右最小、左树左最大-右数左最小 中取
max
主要代码:
1 | struct info |
其中 mx1, mn1 为最大值在右边的情况, mx2, mn2 为最大值在左边的情况, 构建 info 和重载加号的好处是让我们能够直接套最简单线段树的模板解决问题
E2 图论
给你一个有 \(n\) 个节点, \(m\) 条边的有边权的无向图, \(q\) 次询问, 每次询问 \((a,b,k)\): 在所有 \(a\) 到 \(b\) 的路径中, 最小的第 \(k\) 大边权为多少？保证 \(a\) 到 \(b\) 的路径至少有 \(k\) 条边, 图无重边、自环
\(n \leq 400, n-1 \leq m \leq \frac{n \cdot (n-1)}{2}, q \leq 3e5, e_c \leq 10^9\)
思路:
在 E1 中, 有 \(m \leq 400\) ,
所以我们可以在对边权离散化后, 对每条边跑一遍 dijkstra, 处理 \(d_{u,c,v}\), 表示从点 \(u\) 出发到点 \(v\) 经历的最少边权 \(> c\) 的条数, 然后在询问中遍历每条边
\((u,v,c)\), 看 \(d_{u,c,a}+d_{v,c,b} < k\)
是否成立符合要求, 总复杂度为 \(O(m(n+m)\;log\;m + qm)\), 即使可以用 floyd
和二分询问 \(d_{a,c,b}\) , 也显然会寄在
E2
我们希望最终的复杂度不含 \(m\) ,
这启发我们从端点来考虑, 假设一开始所有边权都为 1 , 我们设 \(d_{u,k,v}\) 为从 \(u\) 到 \(v\), 令最小原边权的 \(k\) 条边边权置 0
时的最短路长度。我们将所有边按原边权从小到大排序, 因为 \(n \leq 400\) 我们可以先 floyd 处理 \(d_{u,0,v}\) , 然后逐步将边权置 0 , 设置 0
边为 \((u,v)\), 为第 \(p\) 小边, 对于 \(\forall i,j\) 有:
\[d_{i,p,j} =
min(d_{i,p-1,j},\;d_{i,p-1,v}+d_{u,p-1,j},\;
d_{i,p-1,u}+d_{v,p-1,j})\]
我们可以再存一下此时边权 ( \(val[p]\)
), 就不用离散化了, 在询问时二分获得答案, 此时的复杂度是 \(O(n^2m + q\;log\;m)\) 的, 代码
瓶颈在与边权置 0 的部分, 我们不禁思索, 真的所有边置零都有用,
需要我们更新答案吗？随着我们置零边权, 有一些节点间的距离会变为 0,
这件事情正好会发生 \(n-1\) 次,
并且每次置 0 都可能发生一次, 若没有发生, 则说明 \((u,v)\) 间距离已经为 0 了,
我们便跳过这样的情况, 可以很方便地拿并查集维护这个东西
代码: link
Codeforces Round 997 25/1/18
\((1819 \rightarrow 1819,
rk1097)\)
这 cf 怎么出的跟 abc 一样？这给我整哪来了？
D 思维
给你一个数组, 问它有多少个子数组的上中位数等于下中位数 (即排序后 \(a_{\lfloor \frac{n+1}{2} \rfloor} = a_{\lceil \frac{n+1}{2} \rceil}\) )
\(n \leq 10^5, 1 \leq a_i \leq \color{red}10\)
思路:
看到 \(a_i\)
范围如此之小很自然想到枚举中位数 \(x\)
, 若 \(a_i \leq x\) 赋值 \(b_i =-1\), 否则赋值 \(b_i = 1\), 这样若区间内 \(\sum\limits_{i=l}^{r}b_i =0\)
则说明这个子数组不合法, 接下来处理重复统计的问题, 比如若 \(a_1 = 1, a_2 = 10\), 则这个数组会被重复统计
9 次, 所以我们还要强制要求子数组中出现 \(x\), 为了满足这个性质, 我们可以只在 \(a_i = x\) 时将前缀和更新到 \(i\),
这样可以保证每次我们找相同的前缀和时对应的数组都包含 \(x\), 具体可以看代码理解
代码: link
E 卡特兰数
预先给你 \(M\) 条不相交或包含的线段集合 \((l_i, r_i)\) , 问有多少种继续填补不相交或包含的线段的方法, 使总的线段数目最多？
\(N, M \leq 2 \times 10^5, 1 \leq l_i \leq r_i \leq N\)
思路:
即求在一定限制条件下二叉树的种类数, 一个结论是 \(n\) 个节点构成的二叉树种类数为 \(C(n)\) , 其中 \(C(i) = \frac{(2n)!}{n!(n+1)!}\)
代表卡特兰数的第 \(i\) 项,
每个限制相当于把原来的 \(C(n)\)
划分为了 \(C(i), C(n-i+1)\) 两部分,
所以我们要将线段按包含关系排序 (\(l_i\)
作为第一关键字从小到大, \(r_i\)
作为第二关键字从大到小), 然后开栈处理每个线段的真实贡献,
最后把这些卡特兰数全乘起来即可
代码: link
Codeforces Round 999 25/1/20
\((1819 \rightarrow 1770, rk2620)\) D 要反着做, 哈哈, 考场上否了这个想法, 第二天突然意识到正着做是不唯一的
E 贪心
给你长度为 \(N\) 的 \(a_i\) 数组和长度为 \(M\) 的 \(b_i\) 数组, 你可以进行最多 \(k\) 次操作, 选择 \(i,j\) 将 \(a_i \;\&=\; b_j\), 求 \(min\; \sum a_i\)
\(N \leq 10^5, M \leq 10, k \leq N \times M, 0 \leq a_i,b_i < 2^{30}\)
思路:
预处理出 \(a\) 中每个数处理 \([1,M]\) 次能得出的最低结果,
将所有差值存起来贪心取前 \(k\) 个,
复杂度 \(O(N \times 2^M)\) ,
我以为这不能过来着, 可能是 __builtin_popcount 快吧......
代码: link
Codeforces Round 1000 25/1/22
\((1770 \rightarrow 1800, rk948)\) D 成为了我对于反悔贪心思想在考场上的第一次成功应用, 但是 C 因为考虑情况少了卡了 1h 实在太蠢了
E 思维/树
给你一颗 \(N\) 个节点的树, 根节点为 \(1\), 定义一个节点对 \((u,v)\) 为好对代表 \(u,v\) 不在一条链上, 定义 \(f(u,v)\) 为:
- 若 \((u,v)\) 为好对, \(f(u,v)\) 为数值 \(x\) 的取值种类数, 使得 \(dis(u,lca(u,v)),\;dis(v,lca(u,v)),\;x\) 能构成一个非退化的三角形
- 若 \((u,v)\) 不为好对, \(f(u,v)=0\)
求 \(\sum\limits_{i=1}^{n-1}{\sum\limits_{j=i+1}^{n}{f(i,j)}}\) , 数据范围 \(N \leq 3 \times 10^5\)
思路:
一个条件的化简是, 当 \((u,v)\)
为好对时, \(f(u,v)=2 \times
min(dis(u,lca(u,v)),dis(v,lca(u,v)))-1\)
一般来讲, 我们要么钦定 lca 找下面的 \(u,v\), 要么钦定一个最小值,
一开始我有一个极抽象的 \(O(n\;log^3n)\)
做法, 设 \(u\) 点到根的距离为 \(dep(u)\), 我们钦定最小值, 即为在 \(T-T_u-link(1,u)\) 上找所有 \(v\), 满足 \(dep(v) \geq dep(u)\), 我们套一个树剖,
暴力跳链统计出来除了 \(T_u\) 的部分,
在上面再套一个树状数组套线段树便可以解决问题
当然时限 \(2s\) , 这样寄定了,
看一眼题解, 发现要再拆一下贡献, 我们再改一下式子, 有:
\[
f(u,v) = 2\times min(dep(u),dep(v)) - 2\times dep(lca(u,v)) - 1
\] 可以分为两部分贡献, 这两部分贡献是互相独立的
对于 \(min(dep(u),dep(v))\), 假定取一个
\(dep(u)\),
对每个深度的节点数做一个后缀和, 用对应的后缀和再减掉 \(siz_u\) 就是 \(v\) 的个数, 注意到若 \(dep(u)=dep(v)\) 会算两边, 记得减掉
对于 \(2 \times dep(lca(u,v)) + 1\), 设
\(lca(u,v) = w\), 我们要求的是一个
\(\sum\limits_{fa(x)=w}siz(x)\times[siz(w)-1-siz(x)]\)
的东西, 也很好求, 总的复杂度是 \(O(N)\)
的
代码: link
F1 卡特兰数
已知一个匹配括号序列的长度为 \(2N\), 每次告诉你匹配的两个括号位置 \(l_i, r_i\), 然后询问合法的括号序列种数(取模)
\(N \leq 5000,\;1 \leq l_i < r_i \leq 2N,\;p=998244353\)
思路: 经过了 997E
的洗礼后我上来就是一个卡特兰数的猜, 每次的 \(l_i, r_i\) 把整个串分成内部和外部,
两部分之间不能相互匹配, 设第 \(i\)
项卡特兰数为 \(C(i)\), 一开始是 \(C(N)\), 插了之后就变成了 \(C(\dfrac{r_i-l_i-1}{2}) \times
C(\dfrac{2N-(r_i-l_i+1)}{2})\), 你就这么一直做下去就行了
代码: link
Codeforces Round 1001 25/1/26
\((1800 \rightarrow 1843,
rk1356)\)
挣扎能力的确上升了, 跳过 D 把 E1 用简单的 lca 弄出来了
D 思维
给你一棵 \(N\) 个节点的树, 每个节点有权值 \(w_i\) 在 \([l_i,r_i]\) 之间, 每次你可以选择两个点 \(u, v\), 以 \(u\) 为根将 \(v\) 子树内节点的权值全体 \(+1\), 最终要求树上所有节点的权值一样, 问这个最终权值的最小值
\(1 \leq N \leq 2 \times 10^5, 0 \leq l_i, r_i \leq 10^9\)
思路:
先不考虑 \([l_i,r_i]\) 的限制,
为了让所有权值一样, 树自顶向下应该是逐渐递减的, 假设以 1 为根, 当 \(w_u > w_{fa(u)}\) 时, 应该以 \(u\) 为根将 \(fa(u)\) 子树处理 \(w_u - w_{fa(u)}\) 次, 最终答案为 \(w_1 + \sum max(w_u-w_{fa(u)},0)\)
现在考虑限制, 假设已经处理好一个节点 \(u\) 的所有子树节点权值, 我们要尽可能让
\(w_u\) 满足逐级递减的性质,
有一个下界即为 \(max_{v\in
son(u)}{w_v}\) , 越接近越好, 并且要优先保证不能过小,
因为子节点可能有很多个, 而父节点只有一个, 所以 \(w_u = min(r_u,max(l_u,max_{v\in
son(u)}{w_v}))\), 处理完所有的 \(w\) 就可以算出答案了
代码: link
E2 思维/树/数据结构
给你一颗 \(N\) 个节点的树, 以 \(1\) 为根, 每个节点有权值 \(w_i\), Alice 和 Bob 玩游戏, Alice 先手, 选择一个节点 \(i\) 并移除其子树, Bob 接下来便要选择未被移除的节点 \(j\) 满足 \(w_j>w_i\) 并同样移除其子树, 最后不能操作的人获胜, 请找出能让 Alice 获胜的所有节点
\(N \leq 4 \times 10^5, 1 \leq w_i \leq N\)
思路:
E1 只要求找出任意获胜节点即可,
显然上来选最大权值的节点会直接寄, 所以我们上来选一个次大值节点,
这样对手就会寄,
但是如果所有次大值节点的子树都包含了所有的最大值节点还是会寄,
这时候我们尝试选择次次大节点, 这样反复向上选, 没有答案就是无解
这个东西可以很方便的用 lca 维护, 我们把节点按权值倒序排序,
假设我们要选的节点为 \(u\), 当 \(lca(u,\underset{e_{v_i}>e_u}{lca\{v_i\}}) \neq
u\) 时说明 Alice 可以选 \(u\)
来获胜, 注意到我们一找到这个 \(u\)
就要跳出, 因为后面节点就不满足这个性质了, 代码
现在想想 E2 怎么做, 假设你找到了 \(u\), 而对手找到了比 \(u\) 权值大且先手必胜的点 \(v\), 则会寄之
因此我们要保证, 在删除 \(u\) 后, 所有比
\(u\) 权值大的点 \(v\), 要么 \(v\) 在 \(u\) 的子树内, 要么所有权值比 \(v\) 大的且不在 \(v\) 子树内的点 \(w\) 都在 \(u\) 的子树内
因为所有点 \(w\) 都在 \(u\) 的子树内, 和 E1 一样, 对于某一个 \(v\), 记所有 \(w\) 的 lca 为 \(A\); 对于某一个 \(u\), 记所有 \(v\) 的 lca 为 \(B\); 若 \(u\) 为答案, 则 \(u\) 对于每个 \(v\) 为 \(A\) 的祖先或为 \(v\) 的祖先, 且有 E1 的大前提: \(B\) 为 \(u\) 的祖先
问题转化为怎么求出这个 \(A\),
我们可以在 dfs 序上考虑这个问题, 用一个 set 维护所有权值比 \(v\) 大的外部点的 dfs 序, 所有 \(w\) 的 lca 可以转化成不在 \(v\) 子树内的最小 dfs 序点和最大 dfs 序点的
lca, 把这个 lca 和 \(v\)
用树上差分的方式挂在树状数组上即可维护每个 \(v\)
每次循环是这样的, 先更新答案, 再更新维护 \(v\), 再插入 set 和维护 \(B\), 看代码可能会更方便理解......
代码: link
Codeforces Round 1002 25/2/2
\((1843 \rightarrow 1915, rk357)\) 在掌握了挣扎能力后上紫显得比较自然了, 因为总有一场能震荡上去, 现在的问题是尽可能不要掉下来
E1 队列
给你大小为 \(N \times M\) 的两个二维数组 \(a, b\), 每次操作你可以选择 \(a\) 的一行, 在最前面插入一个数, 将这行的最后一个数字删除并插入下一行, 依次进行, 最后删掉最后一行的最后一个数, 问让 \(a\) 变成 \(b\) 的最小操作次数
\(1 \leq N \times M \leq 3 \times 10^5\)
思路:
假设前面的行已经处理好了, 若想减少次数, 当前行的前缀必须是 \(b\) 中的一个后缀, 我们可以开个 queue
先处理前面扔下来的部分, 然后尝试匹配当前行, 找到一个最长的匹配 \(b\) 的后缀的某种前缀
代码: link
Codeforces Round 1004 25/2/11
\((1915 \rightarrow 1825,
rk1047)\)
喜报: 掉下来了, div1 一题不会, 有观察, 但都不够完整
A 是道挺有趣的交互
B 思维
我们称一个序列为好序列当且仅当对于 \(\forall i, 1\leq i \leq n-1, {\rm min}(a_1,a_2,...,a_i) \geq {\rm mex}(a_{i+1},a_{i+2},...,a_n)\), 给你一个序列, 找出其子序列中最长的好序列长度
\(1 \leq N \leq 2 \times 10^5, 1 \leq a_i \leq 10^9\)
思路:
假设一个序列没有 0, 肯定是好序列; 假设有两个 0, 一定存在 \(i\) 在两 0 之间, 此时 \(0 \geq 1\) 不成立, 肯定不是好序列
所以我们就看能不能再插一个 0 进来, 我们先考虑简化的仅有 0, 1
的情况不难注意到 [1, 1, 0] 会寄, [1, 0, 1] 会寄, [0, 1, 1] 没问题,
所以我们要尽可能往 0 的右边插数字, 所以我们要选取最左边的 0 并尝试插入,
计算 0 右边的 \(\rm mex\) , 看 0
左边的数是否能全部插入
代码: link
Codeforces Round 1015 25/4/5
\((1825 \rightarrow 1847,
rk1303)\)
忙了两个月回来, 也不知道忙啥了, 反正就是忙去了, 做了 HDU 的题和历年 XCPC
的题, 回来发现 codeforces 简直是和排列与 mex 杠上了经常出这类题
水平竟然还能保持一点, 可喜可贺
E 计数
给你一个 0 到 N-1 的排列, 不确定项用 -1 代替, 问你所有可能排列的所有子序列的 \({\rm mex}\) 之和为多少?
$1 N , p = 1e9+7 $
思路:
\(n^3\) 算法比较显然,
对于每个子序列维护所有的 \({\rm mex}\)
值的个数, 将对应的个数乘以对应的 \({\rm
mex}\) 再求和即可
与其计算 \(\sum_{\rm mex}\rm num_{mex} \times
mex\), 我们可以计算 \(\rm \sum_{mex}
num_{\geq mex}\), 把乘 \({\rm
mex}\) 消去
假设我们要计算 \({\rm mex} = m\)
的子序列数量, 那么每个 0 到 m-1 中的确定项必须出现在子序列中,
我们设这个子序列有 \(c_1\) 个 -1, 0 到
m-1 中的不确定项个数为 \(c_2\),
序列总的不确定项个数为 \(t\),
那么序列在 \({\rm mex} = m\)
的贡献为
\[
\displaystyle\binom{c_1}{c_2} \cdot c_2! \cdot (t-c_2)!
\] 所以我们主要关心 \(m\) 和
\(c_1\), 设 \(f_{x,y}\) 表示所有满足 \(m=x,c_1=y\) 的子序列数量,
我们枚举每个子序列\((O(N^2))\), 处理到
\(f_{x,y}\) 上, 再对 \(f_{x,y}\) 做一个第一维前缀和\((O(N^2))\), 就可以计算最终答案,
这里需要找到最大的 \(m\) 作为 \(x\)
代码: link
O3-mini-high 已经能独立解决这道难题, 从 22 年到 25 年, exercise 博客存在的意义越来越小, 既然 O3-mini-high 目前还没有广泛铺开, 我也就暂时继续写下去
Codeforces Round 1022 25/5/1
\((1847 \rightarrow 1870,
rk590)\)
手速场, 有趣的 D 和愚蠢的我, 竟然还能靠 ABC 上点小分
D 交互/二分
交互问题, 给你两个数字 \(k, n\), 要确定是否存在唯一的数组 \(A, B\), 满足:
- \(|A|+|B| = n\)
- \(|A| \geq k\) 且 \(|B| \geq k\)
- 数组仅由 \(1 \sim k\) 的数字组成
- 在数组 \(A, B\) 中的 \(k\) 个连续数字都不同
现在存在数组 \(C = AB\), 可以最多询问 250 次 \(C\) 中某个下标的数字, 要求最后确定 \(A, B\) 的长度或说明 \(A, B\) 不唯一
\(1 \leq k \leq 50, 2k \leq n \leq 10^6\)
思路:
根据题意, 数组左起右起分别是两个周期为 \(k\) 的循环节, 求出唯一的分界点
先记录首尾循环节, 然后枚举中间部分看是否能成为分界点
接下来可以二分所有能成为分界点的位置是属于 A 还是属于 B,
当且仅当二分后下标 l+1 = r 时有唯一解
代码: link
Codeforces Round 1026 25/5/24
\((1870 \rightarrow 1807,
rk2813)\)
不会写 D 的拓扑导致的, 那很幽默了
E 思维/欧拉路径
给你 \(n\) 个元素对 \((a_i, b_i)\), 请构造一个排列, 使得任意相邻的两个元素对恰有 \(a\) 或 \(b\) 相同, 并且没有连续三个元素对的 \(a\) 或 \(b\) 都相同
\(n \leq 2 \times 10^5, a_i, b_i \leq 10^9\)
思路:
每个不同的 \(a_i, b_i\) 看作一个点,
将元素对 \((a_i, b_i)\) 对应的两点连边,
题目转化为找到一条欧拉路径经过所有边,
然后你套一下无向图欧拉的板子就行
代码: link
无向图欧拉的确太久没写, 简单提一下, 统计节点度数,
合法时要么两奇度数点要么没有奇度数点
用 vector<pair<int,int>> 存图,
.second 放边 id, 访问后标记, 重复访问时跳过
用 cur[x] 做一个类似网络流的当前弧优化, 不重复找出边,
单个节点每找到一条出边都要在 dfs 后加入答案栈中,
这和平时做找点的欧拉路径在单点全部 dfs 完后将点加入答案栈中不同
Codeforces Round 1028 25/5/31
\((1807 \rightarrow 1836,
rk659)\)
手速场, 40 mins 后开始坐牢时光, 三题从 1400 perf 到 1900 perf 都有
D 思维
对于长度为 \(n\) 的序列 \(a_1, a_2, \dots, a_n\), 按顺序进行 \(q\) 次操作, 每次给出三个 \([1,n]\) 之间的整数 \(x_i, y_i, z_i\), 令 \(a_{z_i} = min(a_{x_i}, a_{y_i})\), 令最终数组为 \(b_1, b_2, \dots, b_n\)
现在给你数组 \(b_1, b_2, \dots, b_n\) 以及 \(q\) 次操作 \((x_1, y_1, z_1), \dots, (x_q, y_q, z_q)\), 请给出一种合法的序列 \(a_1, a_2, \dots, a_n\) 或说明这样的序列不存在
\(1 \leq n, q \leq 3 \times 10^5, 0 \leq a_i \leq 10^9, 1 \leq b_i \leq 10^9\)
思路:
肯定要反着做, 考场上尝试对每个数维护一个可行域区间,
但是想不明白区间合并和如何判无解, 大败特败
我们注意不到, 对于一个操作 \((x_i,
y_i, z_i)\), 实际上 \(z_i\)
决定了 \(x_i, y_i\) 的最小值,
这是个隐式 DAG, 因为数组的最小值不可能被更新更小, 于是我们维护最小值,
设置 \(b_{x_i} = \max(b_{x_i}, b_{z_i}),
b_{y_i} = \max(b_{y_i}, b_{z_i})\),
最后再正着做一遍看看能不能得到初始的 \(b_i\), 否则无解
于是你交上去, 发现 WA ON 3 了, 因为还要考虑 \(b_{z_i}\) 的情况, 当 \(x_i,y_i,z_i\) 两两不等时, 此时 \(b_{z_i}\) 最小值可以取到 \(0\), 若 \(z_i\) 与 \(x_i,
y_i\) 中的一个相等, 则不用考虑
代码: link
Codeforces Round 1033 25/6/21
\((1836 \rightarrow 1790,
rk2014)\)
AI 场, 印度人统治榜单, 不过我也打的很烂就是了……
D 组合
给定 \(k\), Alice 给 Bob 两个数 \(n, m\), Bob 去构造一个 \(n \times m\), 每个数在 \([1,k]\) 之间的矩阵,
再给定 \(a, b\), 为了保证 Alice 能够在矩阵中取出来一个 \(a \times b\) 大小, 每个数都相等的子矩阵, 字典序最小的 \(n, m\) 是多少?
\(1 \leq a,b,k \leq 10^5\), \(n, m\) 对 \(p = 10^9+7\) 取模
思路:
根据题意, 可以先考虑最小的 \(n\),
因为必须存在一个数字出现 \(a\) 次, 故
\(n = k(a-1)+1\)
现在考虑 \(m\), 考虑一行,
可能的行情况有 \(k \times C_n^a\) 种,
必须存在一种出现 \(b\) 次, 故 \(m = (k \times C_n^a)(b-1) +1\)
在场上一直以为可能的行情况有 \(k \times C_n^a
\times \dfrac{(n-a)!}{(a-1)^{k-1}}\) 种, 然后寄了
代码: link
E
\(N\) 条车道, 每条有 \(a_i\) 辆车, 每秒所有车主的怒气值 +1, 同时每条车道过一辆车, 你可以让车主将车改道, 同时车主的怒气会增加 \(k\), 问最小的总怒气值是多少？
\(1 \leq N \leq 2\times 10^5, 1 \leq k,a_i \leq 10^6\)
思路:
每次移动的最优解一定是把最长队伍的最后一辆车移到最短队伍中,
能想到要进行某种二分
假设二分移动次数 mid 次, 然后可以继续二分移动后有 \(\max\{a_i\} \leq \text{num}\)
Edu Round 180 25/6/23
\((1790 \rightarrow 1769,
rk1619)\)
乱打场, A 不看题 WA 了三发后就开始摆烂了, 哈哈
E DP
给一棵树染色, 有绿、蓝、黄三种颜色, 一种染色是好的当且仅当
- 根是绿色的
- 任意蓝色节点与任意绿色节点 中 任选两点的路径不经过黄色节点
- 任意黄色节点与任意绿色节点 中 任选两点的路径不经过蓝色节点
现在给你一个数字 \(m\), 问你最少的树节点数 \(n\), 使得存在一颗有 \(n\) 个节点的树恰好有 \(m\) 种好染色方案
\(1 \leq t \leq 10^5, 1 \leq m \leq 5 \times 10^5, 4s \;1024\text{ MB}\)
思路:
题上来就读错了 20mins, 例如对于链的染色 G-B-G 是不合法的,
因为两个绿色节点的路径经过了蓝色节点
容易想到是某种树形 DP, 可以注意到绿色节点不会施加任何限制,
而以蓝色或黄色节点为根的子树必须也是相同颜色的
假设 \(v_i\) 为 \(u\) 的子节点, 以 \(v_i\) 为绿根的染色方案有 \(cnt_{v_i}\) 种, 故有, \[
cnt_u = \prod_{v_i \in son(u)} (cnt_{v_i} + 2)
\] 这里的 \(+2\)
是子树全部为蓝或黄的情况
故设 \(dp_m\) 代表恰好有 \(m\) 种好染色方案所需的最少节点数, 有 $dp_m
= {}{ dp_{m/x} + dp_{x-2} } $,
在这题中, 因为给了 4s, \(O(M \sqrt M)\)
也行, 但是你可以枚举所有的 \(x\)
能作为哪些 \(M\) 的因子来做到 \(O(M \log M )\) 的调和级数复杂度
代码: M
M
Codeforces Round 1035 25/7/5
\((1769 \rightarrow 1781,
rk1277)\)
CN round, 手速场, 因为 DP/计数 这种东西不太做的来
D DP/计数
称一个序列 \(\{ a \}\) 合法当且仅当 \(\forall 1 \leq i \leq n, 0 \leq a_i \leq i\)
定义长度为 \(n\) 的数组 \(a\) 权重为 \(f(a)\):
- 初始在 \([1, n]\) 数轴的每个正整数位置上放置一个 token
- 进行 \(n\) 次操作, 在第 \(i\) 操作中, 如果 \(a_i \neq 0\), 则取走一个 \([a_i, i]\) 之间的 token, 否则什么也不做
- \(f(a)\) 代表移除 token 的方法数, 两种方法只要在一次操作中不同即视为不同
给定 \(n, m\), 对于一共 \((n+1)!\) 个长度为 \(n\) 的合法序列 \(\{ a \}\), 输出 $( f(a) ) {} $
\(1 \leq n \leq 5000, 10^8 \leq m \leq 1.01 \cdot 10^9, \sum n^2 \leq 2.5 \cdot 10^7\)
思路:
场上努力在往 \(O(n^2)\) dp
的思路去想了, 可是数字 0 的存在太狗屎了, 最后大败而归
看了题解, 题目可以转化为统计每个数被谁拿走, 对于 token \(i\), 只能被 \(\{a_i, a_{i+1}, \dots, a_n\}\) 拿走
故记 \(f_{i,j}\) 表示位置 \(i \sim n\) 中有 \(j\) 个 token 已经被移走的方案数,
有转移:
\[
f_{i,j} = f_{i+1,j} + f_{i+1,j-1} \times (n-i-j+2) \times i
\] 这里的 \(f_{i+1,j}\) 代表
\(a_i=0\) (不移除 token), \(f_{i+1,j-1}\) 代表移除 token, 有 \((n-i+1)-(j-1)\) 种 token 可以被移除, 对应的
\(a_i\) 有 \(1, 2, 3, \dots, i\) 共 \(i\) 种选择
答案即为 \(\left(
\displaystyle\sum\limits_{i=0}^N{f_{1,i}} \right) {\rm
mod\;m}\)
代码: link
Codeforces Round 1036 25/7/6
\((1781 \rightarrow 1810,
rk1254)\)
被 E 诈骗了, 感觉又回到以前那种不敢对题目深想的状态
E 思维
给你一个长度为 \(n\) 的数组 \(a\), 你要最多做 17 次操作, 每次操作为:
- 选择一个长度为 \(n\) 的数组 \(b\), \(\forall i \in [1,n], 0 \leq b_i \leq a_i\)
- 存在下标 $ 1 i < n$, 满足 \(b_1 + b_2 + \dots + b_i = b_{i+1} + \dots + b_n\)
- 然后从 \(a\) 中对应减掉 \(b\)
如果存在满足的操作, 请输出具体操作, 否则输出 \(-1\)
\(2 \leq n \leq 5 \cdot 10^4, 1 \leq a_i \leq 10^{12}\)
思路:
其实最多两次操作就可以了, 设 \(s = \sum
a_i\), 将能前缀和取到 \(s/2\)
的下标记为 \(i\), 即有 \[
\sum\limits_{j=1}^{i-1}a_j + a_i \geq
\sum\limits_{j=i+1}^n{a_j},\;\;\;\; \sum\limits_{j=1}^{i-1}a_j \leq a_i
+ \sum\limits_{j=i+1}^n{a_j}
\] 设前面为 \(s_1\), 后面为
\(s_2\), 中间的 \(a_i\) 拆成两部分,
在两次操作中分别划分进前面和后面, 有 \[
a_{i,1} = \dfrac{s_2-s_1+a_i}{2}, a_{i,2} = \dfrac{s_1-s_2+a_i}{2}
\] 接下来做一下可行性验证, 仅在 \(a_{i,1} > s_2\) 或 \(a_{i,2} > s_1\) 时无解,
然后构造解就简单了, 例如一次 \(a_{i,1},
a_{i,1}\) 和一次 \(s-a_{i,1},
s-a_{i,1}\)
代码: link
F1 DP/计数
初始给你空数组 \(a\), 可进行以下操作任意次:
选择整数 \(s \geq 1\) 然后将数组 \([1, 2, 3, \dots, s]\) 的一种循环移位(eg. \([r, r+1, \dots, s, 1, 2, \dots, r-1]\))添加到 \(a\) 的后面
\(a\) 的最终长度需要为 \(n\), 并且有 \(m\) 条限制 \(i\;x\) 规定 \(a_i \neq x\)
输出合法 \(a\) 数组的数目
\(1 \leq n \leq 100, 0 \leq m \leq \min(5000,n^2), p=998244353\)
思路:
看到 \(n\) 这么小, 可以往 \(O(n^3)\) 或 \(O(n^4)\) 上面想, 起手可以设一个 \(f_i\) 表示只考虑前 \(i\) 个数的方案数, 从所有的 \(f_j, j<i\) 转移而来, 暴力枚举 \(r, s\), 复杂度 \(O(n^4)\)
一个反例是, 对于 [1 2 3 4 1 2], 可能从 [1, 2] 转移过来, 也可能从 [1 2 3
4] 转移过来, 这里的重复是因为接上来的短段 [1, 2] 的 \(r=1\), 所以要减掉短段的贡献, 故加一维, 设
\(f_{i,s}\) 为只考虑前 \(i\) 个数且最后一段长为 \(s\) 的方案数, 再设一个辅助的 \(g_{i,s}\) 表示只考虑前 \(i\) 个数且最后一段长为 \(s\) 且最后一段 \(r=1\) 的方案数
代码: link,
这个贡献的减除是找前面的 \(k>s\) 的
\(g_{j,k}\) 段, 个人觉得挺巧妙
Codeforces Round 1038 25/7/19
\((1810 \rightarrow 1799,
rk2388)\)
题好, 我蠢
D 图论/DP
一个简单无向图, \(n\) 个点, \(m\) 条边, 初始在 \(1\) 号点, 时间为 \(0\) s,
每秒钟你可以等待或者走向当前点(设为 \(u\) 点)的第 \(t\;\text{mod}\; deg(u)+1\) 条出边, 问到达 \(n\) 号点的最短时间以及最短时间下的最少等待时间, 保证能够到达
\(2 \leq n \leq 5000, n-1 \leq m \leq \frac{n(n-1)}{2}\)
思路:
先猜一手总时间是 \(Cn\) 级别的,
最短路径外的点最多连接三个最短路径内的点, 否则路径更短, 于是答案最多为
\(3n\)
然后开始 dp, 设 \(f_{i,t}\) 表示 \(t\) 时刻走到 \(i\) 的最小等待时间, 等到更新出来 \(f_{n,t}\) 就是答案了
代码: link,
压缩了维度 \(t\)
Edu Round 181 25/7/22
\((1799 \rightarrow 1725,
rk3830)\)
最近状态又下滑的很抽象, HDU 多校也打得一坨狗屎, 看来别的地方的下滑有
“前滑带动后滑” 的趋势, 目前(25/7/26) 正在尝试调整, stay tuned
D DP
数轴上一共 \(1\) 到 \(m\), \(m\) 个整数点, 给 \(n\) 条线段, 每条线段有 \(\dfrac{p}{q}\) 的概率被选中, 覆盖整数点区间 \([l,r]\), 问每个整数点恰好被覆盖一次的概率是多少?
\(1 \leq n,m \leq 2 \times 10^5, p=998244353\)
思路:
明显 dp, \(f_i\) 表示 \([1,i]\) 恰好各点被覆盖一次的概率,
对线段按左端点排序后逐条线段转移 \(f_{r_i} =
f_{r_i} + \dfrac{p_i}{q_i} f_{l_{i}-1}\),
这里的问题是没有考虑不选某条线段的概率, 场上就卡死在这了
于是可以先假设全不选, 初始概率为 \(f_0 =
\prod\left(1-\dfrac{p_i}{q_i}\right)\), 转移改为 \(f_{r_i} = f_{r_i} + \left(
\dfrac{\frac{p_i}{q_i}}{1-\frac{p_i}{q_i}} \right) f_{l_{i}-1} = f_{r_i}
+ \left( \dfrac{p_i}{q_i-p_i} \right) f_{l_{i}-1}\) 即可, 此时
\(f_i\) 表示选 \([1,i]\) 且不选 \([i+1,n]\) 的概率
代码: link
E DP
我们构造互补总和集 \(Q\) 为:
- 选择一个有 \(m\) 个正整数的数组 \(a\)
- 计算 \(s = \sum a_i\)
- 对于任意 \(a_i\), 将 \(s-a_i\) 加入集合中, 即 \(Q = \{ s-a_i | 1 \leq i \leq m\}\), 其中 \(Q\) 不是可重集
请计算正好有 \(n\) 个元素, 每个元素在 \([1,x]\) 间的互补共和集的数量
\(1 \leq n, x \leq 2 \cdot 10^5, p=998244353\)
思路:
若正好有 \(n\) 个元素, \(a\) 中就有 \(n\) 种不同的数, 从小到大排序, 即有 \(\sum a_i \leq x + a_1\),
直觉上来讲, 因为 \(x \leq 2 \cdot
10^5\), 所以 \(n\)
的有解合法取值很小, 因为 632*633/2 = 200028, 所以 \(n\) 最大为 631
一个重要的想法/观察是不计数 \(Q\),
而是计数 \(a\), 先考虑 \(a\) 中最小值, 如果不是 \(1\), 相当于 \(s =
s+n\), 互补后的每个元素都加上了 \(n-1\), 但如果我们在 \(a\) 末尾加上一个数字 \(1\), 相当于互补后的每个元素都加 1,
可以覆盖前一种情况
于是问题转化为对长度为 \(n\)
的元素两两不同的正整数序列 \(a\) 计数,
满足 \(\min\{a_i\} = 1\) 且 \(\sum a_i \leq x+1\)
为了 dp 方便, 将每个 \(a_i\) 减一,
转化为 \(n-1\) 个数的和不超过 \(x-n+1\)
定义 \(f_{i,j}\) 为前 \(i\) 个数和为 \(j\) 的方案数, 有 \(f_{i,j} = f_{i-1,j-i} + f_{i,j-i}\),
即给所有数 +1 并新增 1 和给所有数 +1 两种情况
初始化 \(f_{0,0}=1\), 答案为 \(\displaystyle\sum\limits_{s=n-1}^{x-n+1}
((x-n+2)-s) f_{n-1,s}\), 这里 \(f\) 项前面的系数代表在 \(a\) 后面加额外 1 的方案数
对于 \(n=1\) 的情况下, \(m=1\) 不合法, 需要特判一下
代码: link
Codeforces Round 1039 25/7/27
\((1725 \rightarrow 1671, rk3460)\)
Codeforces Round 1041 25/8/7
\((1671 \rightarrow 1747, rk1160)\)
Codeforces Round 1044 25/8/24
\((1747 \rightarrow 1750, rk1556)\) 不会 DP, 阿巴
D DP
\(n\) 个鸡骑士垒在一起, 从下到上血量分别为 \(h_1, h_2, \dots, h_n\), 史蒂夫每次可以对一个鸡骑士造成一点伤害, 鸡骑士死后, 其上方的鸡骑士会落下形成新的一垒, 同时上方的最下面的鸡骑士会受到下方鸡骑士数量的掉落伤害, 问杀死所有鸡骑士需要的最少攻击次数?
\(n \leq 2 \times 10^5, 1 \leq h_i \leq 10^9\)
思路:
尽可能最大化掉落伤害, 所以倒着砍, 但是 DP 正着做,
因为一个怪物的掉落仅与前一个怪物有关系
设 \(f_i\) 为打掉第 \(i\) 个且消灭 \(i
\sim n\) 个的最少攻击次数, 现在考虑第 \(i-1\) 个的死亡与第 \(i\) 个的情况的关系, 第 \(i\) 个可能仅受到一点掉落伤害,
或者在直接杀死第 \(i-1\) 个时, 第 \(i\) 个受到 \(i-1\) 点掉落伤害
代码: link
Codeforces Round 1045 25/8/26
\((1750 \rightarrow 1806,
rk693)\)
事实上打的很蠢, 这几场都是 ABC 战神, D 从没出来过, 大家都出不来就上分,
都出来就掉分
D 思维
一颗 \(n\) 个节点的树, 每次操作选择连续的 \(a, b, c\) 三个点, 将连向 \(b\) 的除 \(a, c\) 部分的其他邻居全部断边并接到 \(c\) 上, 请输出对于 "将树变成一条链的最少操作数对应的任意操作序列" 的第一次操作
\(n \leq 2 \times 10^5\)
思路:
设树直径为 \(d\), 最少操作数是 \(n-1-d\), 下面感性证明: 每次操作最多 +1
直径, 所以最少操作数下界就是 \(n-1-d\),
具体操作上, 每次选直径上的点 \(a, b\),
和直径外的点 \(c\), 即可保证 \(b-c\) 边被加入直径, 如此迭代即可
代码: link
E 交互
\(n\) 个盒子, 每个盒子有弹力为 1 或 2, 摆在数轴 \(1-n\) 上
你可以最多进行 \(\lceil \dfrac{3n}{2} \rceil\) 次操作, 每次要么换相邻的盒子, 要么在一个盒子上方扔下一个球, 球会根据弹力往右弹相应的距离直到落地, 交互器会返回在盒子上总共弹了几次
输出每个位置原来盒子的弹力
\(n \leq 1000\)
思路:
从后往前确定, 首先注意到球扔在第 N-1 个盒子上会直接揭示它的弹力为 1 或
2, \(\lceil \dfrac{3n}{2} \rceil\)
的限制提醒我们可以用三次确定两个盒子的弹力
在任意时刻, 假设我们不知道前面两个盒子的弹力, 知道后面所有盒子的弹力,
我们仅考虑两个未知的和最前面两个已知弹力的, 可以处理出来两个辅助量 \(a, b\),
代表分别从第一个/第二个已知弹力的盒子上方扔球,
到落地所需的弹跳次数
接下来根据假设两个未知盒子的弹力为 1 1 / 1 2 / 2 1 / 2 2 来讨论,
很简单能手玩出来这个东西:
考虑不同的弹力与不同的交互器返回结果, 再将两个盒子 swap
一次后的返回结果, 每种情况有四个返回值特征, 最终得到,
当 \(a=b+1\) 时, 扔在后面的未知盒子上,
swap 未知盒子, 扔在后面的未知盒子上即可
当 \(a \neq b+1\) 时,
扔在前面的未知盒子上, swap 未知盒子, 扔在前面的未知盒子上即可
具体实现见代码, 这里其实非常简单
最后还要控制一下奇偶性,
因为倒着做的时候最前面剩下一个单独的未知盒子没法处理,
所以初始讨论处理最后的两个或三个盒子, 还是利用第 N-1 个盒子, 略
代码: link
体感难度 D >> E, 场上应该看眼榜然后跳着写的……
Codeforces Round 1046 25/8/29
\((1806 \rightarrow 1802,
rk994)\)
D 出来了, 但是这场手速慢了……
E 图论
无向图 \(n\) 个点, \(m\) 条边, 每个节点一个权值 \(a_i\), 一些节点需要你来赋值, 其 \(a_i = -1\), 赋值范围为 \([0,V-1]\) 之间的整数
图上路径权值定义为路径经过的所有节点权值的异或, 若想使得对于所有的 \(1 \leq p < q \leq n\), \(p\) 到 \(q\) 的简单路径的权值都相同, 问有多少种合法的赋值方案?
\(n \leq 200000, 1 \leq V \leq 10^9, -1 \leq a_i \leq V-1\)
思路:
赛后 2.5h 自己解决, 很自然从环开始考虑
假设环长为 \(n\), 对于相邻的 \(a, b\), a 到 b 有两条路径, 故环上连续 n-2
个数异或起来为 0
故间隔 n-1 个的两值相同, 故间隔 n-(n-1) = 1 个的两值相同
故环上所有值相同, 对于连通块也是所有值相同
tarjan 做边双后剩下一颗树, 随便填
但如果联通块内有奇数长度的值为非 0 的环就坏事了,
故联通块合法当且仅当:
- 全为 -1, 向答案贡献 *V
- 全为 0, 向答案贡献 *1
- 最多存在一个不为 0 的值, 且不出现 0, 且联通块不存在奇环, 向答案贡献 *1
联通块内判奇环对连通块内黑白染色即可
代码: link
Codeforces Round 1048 25/9/8
UNRATED
题其实是好题, 如果能把我这场估计的 +40 补回来就更好了
E2 思维
总结一下题意, 你有两个背包, 体积分别为 \(x\) 和 \(n-x\), 现在有一些物品, 每个物品都有重量 \(v_i\), \(\sum v_i \leq n\), 问最多能装多少个物品？
\(n \leq 2 \times 10^5, 6s, 1024 {\rm MB}\)
思路:
E1 的 n = 5000, 直接 \(n^2\) dp 之,
虽然 E2 可以 bitset 后 \(n^2/w\)
艹过去, 但这不是出题人本意……
这里因为有 \(\sum v_i \leq n\),
设物品数为 \(m\), 可以知道答案肯定是
\(m\) 或 \(m-1\), 我们想想还有没有更好的性质
有一个 \(\sqrt n\) 的 trick,
可以知道最多只有 \(\sqrt n\) 个重量
\(\geq \sqrt n\) 的物品, 对于重量 \(< \sqrt n\) 的物品, 假设它们各有 \(c_i\) 个, 我们可以将 \(c_i\) 二进制分解, 这样总的物品数的量级就是
\(O(\sqrt n)\) 的, 可以在 \(n \sqrt n\) 解决这个问题
这个做法还可以和 bitset 结合达到 \(O(\dfrac{n
\sqrt n}{w})\) 的复杂度
代码: link
Codeforces Round 1051 25/9/17
\((1802 \rightarrow 1845,
rk741)\)
把上场失去的 +40 补回来了, A B C D1 D2 思路一帆风顺,
可惜代码能力差了一点, 在寝室只能打到零点, D2 没写完……
E 思维
给你一个括号字符串 \(s\), 每次你可以将连续的两个同种括号(即
((或))) 将其反转(即))或((), 问能否将 \(s\) 变为合法的字符串？
\(|s| \leq 2 \times 10^5\)
思路:
最典的 trick 又忘了, 将偶数位置括号翻转, 于是操作变为
() -> )( 或 )( -> ()
相当于我们可以交换任意相邻的括号
在任何合法括号字符串中, 奇/偶 数位置的开括号与 偶/奇 数位置的闭括号匹配,
基于此可以推理出在翻转后合法时 (, )
的数量都应该是偶数个
于是可以先构造翻转后的字符串类似 ())))))((( 然后再翻回来,
有 (()()())()()
代码: link
奇偶分类思想做过题但是没想起来, 构造翻转后的字符串这招太聪明了
Global Round 29 25/9/20
\((1845 \rightarrow 1873,
rk1320)\)
C > D ≈ B, 抽象场
E 思维
给你一个非负整数数组 \(a\), 长度为 \(n\), \(Q\) 次独立询问, 每次询问你最多可以执行 \(b_i\) 次将一个数字 \(+1\) 的操作, 问每次询问对应的 \(\max{\rm \{popcount}(\displaystyle\odot_{i=1}^n a_i)\}\)
\(n, q \leq 10^5, a_i, b_i \leq 10^9\)
思路:
设初始值 \(s = {\rm
popcount}(\displaystyle\odot_{i=1}^n a_i)\),
如果能处理出来使得答案 $+1, +2, , +32 $ 的最少的 \(b_i\), 问的时候直接 \(O(32)\) 查表就行了
Codeforces Round 1051 25/10/3
\((1873 \rightarrow 1868,
rk1641)\)
猜猜场, 题有点无聊
E 交互/思维
一个长度为 \(n^2 + 1\) 的排列, 你需要求出它长度为 \(n+1\) 的单调序列(上升或下降)
你可以进行 \(n\) 次询问, 每次询问其任意个下标 \(i_1, i_2, \dots, i_k\), 让我们把对应的排列 \(p_{i_1}, p_{i_2}, \dots, p_{i_k}\) 想象成建设在对应下标的大楼的高度, 交互器会返回你从左往右看能看到的大楼的下标, 即满足 \(p_{i_k} = \max(\{p_{i_1}, p_{i_2}, \dots, p_{i_k}\})\) 的 \(i_k\)
\(n \leq 100\)
思路:
思路就在题目的提示中, 为什么要在 \(n^2+1\) 个中求 \(n+1\) 长度的单调序列？这就是 Erdős–Szekeres定理,
可以用鸽巢原理证明
我们先问全集, 第 \(i\)
次询问把问出来的都打上标签 \(i\),
然后扔掉问下一次
若某次收到的回答长度 \(\geq n+1\),
那就是答案(上升链)输出即可
否则, 肯定会剩下最少一个没有被打上标签, 我们将没打过标签的打上 \(n+1\) 标签, 很容易注意到标签间存在偏序关系,
我们肯定能剩下一条下降链, 由标签为 1 2 3, ..., n+1 的数构成,
你要倒序去找这条链, 因为每个标签的决定其实来自于它前面的标签,
而不是后面的标签
代码: link
Codeforces exercises 2025