T1：
一场比赛一共有\(n\)位选手和\(m\)道题目，其中你是第\(1\)位选手。你现在知道了每位选手通过了哪些题目。
你可以调整题目的顺序，然后给题目赋予一个分值，使得第\(i\)道题目的分值是\(2^i\)。
你想知道能否通过调整题目的顺序，使得你的成绩恰好是第二高的。
保证不存在两个选手的通过的题目集合是一样的。
多组数据。
\(T\le 200,n,m\le 400\)
若有至少两个超集，不行。
若有恰好一个超集，可以。
否则枚举哪个比 \(1\) 大，假设是 \(i\)。然后枚举 \(i\) 中一个是 \(1\)，且 \(1\) 中不是 \(1\) 的位，若除了 \(1,i\) 以外的数这一位都是 \(0\)，可行。
如果找不到，不可行。
直接做是 \(O(T\cdot n^2m)\) 的，用 bitset 优化可以除以 \(w\)。
T2：
给定 \(n\times m\) 的平面和 \(k\) 个点。求一条路径，从 \(x=0\) 的某个点去 \(x=m\) 的某个点，最大化与上下边界、点的距离的最小值。
\(k\le 7000\)。
显然是二分，然后能到的点之间连边，如果有一个连通块卡住了上下界就无解。否则就有解。
但是问题在于可能的边太多了。
法一：充分发扬人类智慧，按 \(x,y,x+y\) 排序后各取 \(50\) 个点连边。
法二：Prim 算法。
T3：
一共有\(n\)个仓库，第\(i\)个仓库里面一共有\(f_i\)个箱子，第\(i\)个仓库和第\(i+1\)个仓库的墙的高度是\(h_i\)。同时，你可以随身带任意多个箱子。
现在假设你在\(i\)仓库，你身上带着\(x\)个箱子，当前仓库里面\(y\)个箱子，你可以做这些操作。
- 拿起一个箱子，也就是使\(x\)加一，\(y\)减一，其中\(y\)要大于\(0\)。
- 放下一个箱子，也就是使\(y\)加一，\(x\)减一，其中\(x\)要大于\(0\)。
- 移动到相邻的仓库，需要满足当前仓库里面的箱子个数不小于与相邻仓库的墙的高度。比如从\(i\)移动到\(i+1\)，那么要求\(y\geq h_i\)。
你可以执行上述操作任意多次。
现在你想知道，如果一开始在\(i=1\sim n\)仓库，你想要访问遍所有的仓库，那么一开始需要至少随身带多少个箱子。
\(n\le 5000\)。
又是区间 DP，一样不会做。
数据范围明显 \(O(n^2)\) 的 DP。
\(dp[l][r][0/1]\)：已经访问了 \([l,r]\) 的区间，最终位于 \(l/r\)，要访问其他仓库，当前至少有多少个箱子在手。
注意这个定义：我们不考虑 \(l\sim r\) 内借了几个箱子、不考虑从仓库里拿了几个箱子，我们只定义为 "现在手上要有几个箱子"。
初值 \(dp[1][n][0]=dp[1][n][1]=0\)，因为没有其他需要访问的仓库了。
答案是 \(\max(0,dp[i][i][0]-a_i)\)。
转移：考虑下一步去哪里。
-
去 \(l-1\)，至少有 \(h[l-1]\) 个箱子才能过去，过去之后手上要有 \(dp[l-1][r][0]\) 个箱子，同时在 \(l-1\) 处获取了 \(f[l-1]\) 个箱子，因此需要的箱子个数为 \(h[l-1]+\max(0,dp[l-1][r][0]-f[l-1])\)。
-
去 \(r+1\)，需要从 \(l\) 跨越 \([l,r]\) 去 \(r+1\)。考虑在这个过程中我们要欠多少箱子，发现就是 \(\max h[l\sim r]\)。一个重要的观察是：当访问完 \(l\sim r\) 且位于 \(l\) 时，\(l\sim r-1\) 的墙右侧都放了 \(h[l\sim r-1]\) 个箱子。 而翻越 \(h[r]\) 后还要 \(dp[l][r+1][1]\) 个箱子在手，同时在 \(r+1\) 处获取了 \(f[r+1]\) 个箱子，因此需要箱子个数为 \(\max h[l\sim r]+\max(0,dp[l][r+1][1]-a[r+1])\)。
上面两种取 \(\min\) 就是 \(dp[l][r][0]\)。\(dp[l][r][1]\) 的转移同理。
T4：
原题为 apc001 XOR Tree。
给一颗带边权（\(w<16\)）的树，每次操作可将一条路径的边权异或任意值。问最少几次使所有边权为 \(0\)。\(n\le 10^5\)。
trick：边权化点权。定义点权 \(a_u\) 为 \(u\) 所有邻边的异或。则边权为 \(0\) 等价于点权为 \(0\)。（若点权为 \(0\)，不停删叶子可证明）
同时
于是一次操作变成把两个点异或任意值。
贪心，两个相同权值的点必然一次消掉。然后最多剩下 \(1\sim 15\) 个不同的权值需要处理。
状压，\(dp[S]\) 表示 \(S\) 中数，至少几次异或后全部变成 \(0\)。
若 \(S\) 中数整体异或非 \(0\)，显然无解。
否则，\(|S|-1\) 次操作显然可行；同时可以枚举一个子集 \(S'\)，\(dp[S]\leftarrow dp[S']+|S-S'|-1\)。
复杂度 \(O(3^w+n)\)。
标签：10,题目,箱子,仓库,max,30,2024,sim,dp From： https://www.cnblogs.com/FLY-lai/p/18518318