CF3000 乱做

发布时间 2023-06-12 19:18:51作者: mikefeng

CF1832F

进行一个平凡的转化,求人和电网的交的最大值。

因为电网的长度都相等,所以事实上是要求人和电网的中点离得尽量进,也就是说将人按照中点排序,每个电网的作用范围是一段区间。

\(f_{i,j}\)\(i\) 个电网控制前 \(j\) 个人,发现 \(f_{i,j}=\max\limits_{k=1}^j f_{i-1,k-1}+g_{k,j}\),其中 \(g_{k,j}\)\([k,j]\) 的人与一个电网的交的最大值。

先考虑怎么算 \(g_{i,j}\),首先本质有用的电网左端点只有 \(l_i,r_i-m\),发现右边少一个人电网只可能向左,左边少一个人电网只可能向右,决策点有单调性,\(h_{i,j-1}\le h_{i,j}\le h_{i+1,j}\),加上前缀和优化为 \(O(n^2)\),注意因为有多个相等的位置,所以 \(h_{i,i}\) 可能大于 \(h_{i+1,i+1}\),边界需要特判一下。

再算 \(f_{i,j}\),发现这个形式也非常像有单调性的样子,不可能把大量的电网挤在一起,所以 \(h_{i,j-1} \le h_{i,j}\le h_{i+1,j}\),时间复杂度 \(O(n^2)\)

CF1838F

先考虑这么一种情况:

>>>>v
v<<<<
>>>>v
v<<<<

如果答案是 \(-1\),那么可以二分找到不合法的位置,如果答案不是 \((5,1)\),那么可以确定唯一位置。

否则进行第二轮测试:

>>>>^
^<<<<
>>>>^
^<<<<

如果答案是 \(-1\),仍然二分找到不合法位置,否则答案一定是 \((4,1,v)\)