游记鸽了

Day1

F

转化后的题意：要做物品大小为 \(10^9\)，价值为 \(1\sim 4\) 的背包。\(10^5\) 个物品。

赛时的想法：设 \(f_i\) 为得到价值为 \(i\) 的最小代价，转移是个背包。

以前见过一个结论，\(1,2,3,4\) 的背包 \(f_{r},f_{r+12},f_{r+24}..\) 是个凸壳，证明的话，因为大小为 \(24\) 的一组一定能被分为 \(12+12\)。

于是闵科夫斯基和的时候，把数组拆成 \(12\) 份，做 \(12\times 12\) 次闵科夫斯基和。估计是有更简单的做法。

J

题意：将一个 RBW 的序列染色成只有 RB，每次操作可以删掉一段 \(r\) 个 R 和 \(b\) 个 B，求最多能操作多少次。\(10^5\) 长度。

可以猜个结论，一段连续的有 \(kr\) 个 R 和 \(kb\) 个 B 的一定能被消掉。

考虑 DP，枚举 \(j\)，\([j,i]\) 能被删的条件是：

• \(j-i+1=k\times l\)
• \(sumr_i-sumr_{j-1}\le (j-i+1)\frac{b}{b+r},sumb_i-sumb_{j-1}\le \frac{r}{b+r}\)

第二个限制可以二维偏序处理。

Day2

啥都没听懂。

Day3

E

求有多少个矩阵，使得每条从 \((1,1)\) 到 \((n,m)\) 的路径权值和 \(\le k\)。\(1\le n,m,k\le 100\)。

对于一个矩阵可以求出一个 DP 数组，满足 \(f_{i,j}\ge f_{i-1,j},f_{i,j}\ge f_{i,j-1}\)。发现 DP 数组的计数是 LGV 的经典问题！