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 个。
标签:训练,对于,记录,2024.7,cdots,数组,remake,序列 From: https://www.cnblogs.com/Lonely-233/p/18296938