## 建筑升级
#序列dp
首先看到 $1\le n,m\le 1000$ 就很不能让人不想到 $\mathcal O(nm)$ 的 dp。dp 状态中，第一位表示长度为 $i$ 的建筑前缀是必须的，那么第二维是什么呢？由于最终获得的额外分数和所有建筑的最小级别有关系，因此第二维就存前缀中所有建筑中最低的级别。
设 $dp_{i,j}$ 表示在前 $i$ 个建筑中，等级最小为 $j$，最多能得多少分。那么对于新的一个建筑，假设我们选择让这个建筑升级到 $k$ 级，那么有以下两种情况：
- 如果 $k\ge j$，那么最低等级 $j$ 不会改变；
- 如果 $k<j$，那么最低等级 $j$ 会变成 $k$。
因此假设当前转移到 $dp_{i,j}$，那么有两种方式，一种是从最小值比当前大的状态，但是当前选择的等级就是 $j$ 的转移；另一种是最小值和当前一样，那么当前的等级就可以是任意比之前最小值大的而等级。
```cpp
#include <iostream>
using namespace std;
using LL = long long;
const LL kMaxN = 1005;
LL a[kMaxN][kMaxN], dp[kMaxN][kMaxN], d[kMaxN], t, n, m, ans;
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n >> m;
for (LL i = 1; i <= n; i++) {
for (LL j = 1; j <= m; j++) {
cin >> a[i][j];
a[i][j] += a[i][j - 1];
}
}
for (LL i = 0; i <= m; i++) {
cin >> d[i];
if (i >= 1) {
d[i] += d[i - 1];
}
}
fill(dp[0], dp[0] + m, -1e18);
dp[0][m] = 0;
for (LL i = 1; i <= n; i++) {
for (LL j = m, pre = -1e18, mx = a[i][j]; j >= 0; j--) {
mx = max(mx, a[i][j]);
dp[i][j] = max(dp[i - 1][j] + mx, pre + a[i][j]); // 最低等级不变或降低最低等级
pre = max(pre, dp[i - 1][j]);
}
}
ans = -1e18;
for (LL i = 0; i <= m; i++) {
ans = max(ans, dp[n][i] + d[i]);
}
cout << ans << '\n';
}
return 0;
}
```
## 快速蜗蜗变换
#状压dp #枚举 #集合 #位运算
最开始我想到的是 01 trie，但是后面发现不能考虑到所有的情况。
最后还是写了个子集枚举，即对于每个 $i$ 枚举 $i$ 的二进制的子集，然后把 $a_i$ 和 $b_i$ 存入所有 $i$ 的子集的值中间，并且分别取最大、最小值，然后倒序枚举 $i$，把之前的最大、最小 $a,b$ 值取出来以四种情况中取最大值，然后再做一个后缀 $\max$，累加即可。
正确性证明：如果 $k\subset i$ 且 $k\subset j$，那么必然有 $k\subset (i\cap j)$，因为 $k$ 有的每一个 $1$ 都在 $i$ 和 $j$ 里面出现过，此时 $k\le i\operatorname{\&}j$，然后我们再做一个后缀和就可以覆盖所有的 $i\operatorname{\&}j\ge k$ 的情况。
时间复杂度高达 $\mathcal O\left(\sum\limits_{i=1}^n 2^{\text{popcount}(i)}\right)$，当 $n=2\times 10^5$ 时大约是 $2\times 10^8$ 左右，但是可以直接卡过。其实正解和这个区别不大，这个是枚举出所有的子集，正解是每次从已有的 $1$ 中间掏去一个。
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
using LL = long long;
const LL kMaxN = 2e5 + 5, kMod = 998244353;
LL a[kMaxN], b[kMaxN], mxa[kMaxN], mxb[kMaxN], mna[kMaxN], mnb[kMaxN], t, n, ans, mx;
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n;
for (LL i = 0; i < n; i++) {
cin >> a[i];
}
for (LL i = 0; i < n; i++) {
cin >> b[i];
mna[i] = mnb[i] = 1e18;
mxa[i] = mxb[i] = -1e18;
}
for (LL i = 0; i < n; i++) {
for (LL x = i; x; x = (x - 1) & i) {
mxa[x] = max(mxa[x], a[i]);
mna[x] = min(mna[x], a[i]);
mxb[x] = max(mxb[x], b[i]);
mnb[x] = min(mnb[x], b[i]);
}
mxa[0] = max(mxa[0], a[i]);
mna[0] = min(mna[0], a[i]);
mxb[0] = max(mxb[0], b[i]);
mnb[0] = min(mnb[0], b[i]);
}
ans = 0;
mx = -1e18;
for (LL i = n - 1; i >= 0; i--) {
mx = max(mx, max(
max(mna[i] * mnb[i], mna[i] * mxb[i]),
max(mxa[i] * mnb[i], mxa[i] * mxb[i])));
ans = ((ans + mx) % kMod + kMod) % kMod;
}
cout << ans << '\n';
}
return 0;
}
```
## 互不相同
#贪心
我使用的是暴力。
对于子任务 3，可以采用迭代加深搜索，由于答案大概在 $\cfrac{n}{2}$ 左右，因此最多也就迭代 $4$ 次，单次瞎选一个区间，然后加一个特别大且特殊的值（我是 $4\times 10^9\times 2^x$，$x$ 是当前深度，二进制保证不会重复），如果满足条件就可以退出了。这个搜索可以帮助我们找出子任务 1、2 的规律。
对于子任务 1，全部 $a_i$ 都是 $1$，使用我们的搜索不难得到
$
\begin{cases}
1&\text{if}~n=1\\
\left\lceil{\cfrac{n}{2}}\right\rceil&\text{if}~n>1
\end{cases}
$
对于子任务 2，我的式子猜错了，导致 wa 最后一个子测试点。
## 运货
#平衡树
我的思路是错的。
我最开始想的是二分，二分出一个答案进行 $\mathcal O(n)$ 判断，时间复杂度 $\mathcal O(n^2\log_2 V)$，但是答案根本没有单调性（如 `6 3 2`， 如果承重为 $5$ 可以带 $2$ 个，但是当承重为 $6$ 时只能带 $1$ 个），于是趋势。
## 总结
分数 $100+100+23+0=223$。
下次写题目的时候不能看着好像可以二分就写二分，应该仔细判断单调性。然后更改做题侧重点，应该把重点放在第二题和第三题上而非第四题。