挂分 100pts。
T1：数组不清空导致的。
题意：\(n\) 个物品，第 \(i\) 个物品花费 \(2^{a_i}\)，价值 \(b_i\)。问获得 \(k\) 的价值最少花多少钱。\(n\le 10^5\)。
二分，求 \(x\) 块能买到多少价值。按花费从小到大枚举 \(i=0\sim 30\)，维护一个 "当前物品集合" \(q\)，初始只存储 \(a=0\) 的物品。
若 \(x\) 二进制第 \(i\) 位是 \(1\)，从 \(q\) 中取最大价值的物品买了。
然后把 \(q\) 中剩下物品按价值从大到小排序，最大和第二大、第三大和第四大、…… 两两配对，价值相加，作为花费 \(i+1\) 的物品保存。同时若多出一个物品单独了，也将它单独视作一个 \(a=i+1\) 的物品放在 \(q\) 里。
T2：
题意：给定 \(n\times n(n\le 1000)\) 的 01 方格。判断每个格子，是否存在两个 \(1\)，到它的曼哈顿距离相等。
观察：两个格子的曼哈顿距离取值为 \(1\sim 2(n-1)\)，所以若 \(1\) 个数 \(\ge 2n-1\)，由抽屉原理知每个格子都能找到两个 \(1\) 的距离相等。
因此只剩下 \(2000\) 个 \(1\) 了，采用枚举每一对 \(1\) 然后打标记的方式。
若两个 \(1\) 曼哈顿距离是奇数，跳过。否则开始大分讨。
-
同行，则中间那一列都可以。
-
同列，则中间那一行都可以。
-
同对角线，则考虑它们构成的正方形的另外一条对角线。这条对角线也是可以的。另外，这条对角线的端点对应的子矩阵也是可以的（例如这条对角线是左上-右下，那么以它左上端点为右下端点的子矩阵也是可以的）。
-
啥也不是。找到它们构成的矩形的中心 \(mid\)，从 \(mid\) 画一条与两个 \(1\) 不同方向的 \(45\)° 对角线，这条对角线是可以的。如果这条对角线触碰到矩形上下边界，则从对角线端点向上/下是可以的；否则，从对角线端点向左/右是可以的。
维护二维前缀和，和两个对角线的前缀和。
T3：
题意：给定 01 串 \(s,t\)，问有多少个 \(w\)，使得 \(w\) 包含 \(s\) 是子序列，且以某种方式删去 \(s\) 后，预留的是 \(t\)。\(|s|,|t|\le 50\)。答案取模。数据随机生成。
怎么分类，使得不重不漏，是难点。
\(dp[i][S]\) 表示 \(w\) 填了前 \(i\) 个字符。若 \(S\) 的第 \(j\) 位是 \(1\)，表示可以把这 \(i\) 个字符分配，使得匹配好 \(s[1\sim j]\) 和 \(t[1\sim i-j]\)。这是一个不重不漏的分类。
\(S\) 转移到 \(S'\)。考虑填 \(0\) 还是 \(1\)，再根据 \(s,t\) 下一位是否对上了，就能求 \(S'\)。实际上甚至可以位运算优化这个到 \(O(1)\)。
但是状态定义是 \(O(100\cdot 2^{50})\) 的。怎么办？
数据随机提示我们：有效状态非常少。经过代码，非 \(0\) 状态个数下一般不超过 \(2^{20}\)，还要再少得多。因此直接用队列来转移状态即可。
T4：
题意：给定 \(n,m,p,q,r\)。三个变量 \(x,y,z\) 初始为 \(0\)。每次操作可以选一个变量 \(\pm 1\)，也可以三个变量一起 \(\pm 1\)。问有多少种长度 \(n\) 的操作序列，使得最终 \(m|x-p,m|y-q,m|z-r\)。\(n,m\le 10^6\)。取模。
标签：10,le,题意,17,2024,端点,对角线,物品 From： https://www.cnblogs.com/FLY-lai/p/18474329