Day2

Prophesy_One · 2024-11-21 20:57:27 · 个人记录

T1

感觉很像背包但是不知道怎么证的，但是感觉很对。

T2

ARC104D。赛时思路很对啊，就是犯蠢了。

首先考虑枚举每个平均值 x，那么就等价于值域在 [1,x-1] 的数，每个数可以选至多 k 个的和 等于 值域在 [1,n-x] 的数，每个数可以选至多 k 个的和的 方案数。

考虑直接 dp，f_{i,j} 表示值域为 [1,i] 的数，和为 j 的方案数，转移有 f_{i,j}=\sum_{t=0}^k f_{i-1,j-it}，时间是 \text{O}(n^3k^2)，过不去，考虑前缀和优化 dp 转移，时间复杂度 \text{O}(n^3k)。

link

T3

神秘转化。

题目等价于对于所有的 i \neq j，都有 a_i \leq a_j,b_i \leq b_j,c_i \leq c_j 或 a_i \geq a_j,b_i \geq b_j,c_i \geq c_j。

然后比较匪夷所思的一步是考虑把这个看成三维坐标系中的坐标，考虑 dp，令 f_{i,j,k} 表示所有 x \leq i,y \leq j,z \leq k 的 (x,y,z) 使合法的最小代价，每次转移考虑使新的不合法的走到 (i+1,j,k)/(i,j+1,k)/(i,j,k+1)，前缀和预处理出点的个数，\text{O}(1) 转移。

时间复杂度 \text{O}(n^3)。link

T4

P7013/CF309E。

首先读完题套路的开始考虑二分答案：