remake 前的训练记录

2024.7.9

cf1989

赛时通过 abcd，补了e。

E

对于原数组的一段元素相同的区间，会对应到 b 数组形如 \([1, 2, \cdots , x-1, x, x, x-1, \cdots , 2, 1]\) 或者 \([1, 2, \cdots , x-1, x, x-1, \cdots , 2, 1]\) 的区间。

所以只需要求长度为 \(n\) 的序列能被切成至少 \(k\) 段的方案数。

但是对于通过分段在原数组和 b 数组建立的映射并不是一一对应，因为对于 b 数组中长度为 \(2\) 的区间，若其不在原数组的头尾，那么在原数组中其可以分为两段，也可以当成一段，但对应的是同一个 b 数组。

所以设 \(f(i,j)\) 表示前 \(i\) 个数分为至少 \(j\) 段，且除了头尾没有长度为 \(2\) 的段落的方案数。记个前缀和转移就行。

2024.7.11

cf1976

爆了，赛时通过 abd。

C

去掉一个人后对答案有影响的只有第一个不符合“能力优先”选法的人，于是扫一遍讨论一下算出答案变化就行了。

E

对于 \(l_i\) 和 \(r_i\)，\(l_i\) 一定要在 \(r_i\) 的左边，于是先倒序合并，把原序列一部分拼出来。

对于未在 \(l_i\) 与 \(r_i\) 中出现过的数，可以插到已经固定的数的空隙中。但对于未出现数 \(x\)，要插入到 \(l_i\) 与 \(r_i\) 中间，要满足 \(x < \max \{l_i, r_i \}\)，因为如果大于最大值，那么就无法通过分割构成给出的 l 和 r 序列。

所以从大到小扫一遍统计答案，注意新插入一个数之后空隙会增加 1 个。