24.10.17

KinNa-Sky / 2024-10-22 / 原文

签到，爽！为啥我把这个放考试三个题上面？

A

签到！每天所有数 $\le t_i$ 的取完，剩下的减 $t_i$，没有脑子只剩平衡树了。

$\alpha$ or this

B

签到！必须 01 交错？将 $2|(i + j)$ 的格子取反就是求最大全零矩阵和最大全一矩阵。悬线法。

0：6

$\beta$

C

签到？

$m \le 10$，状压，但是 $2 \times 3$ 的物品需要压两行，根据状压 DP 经典经验之状态数复杂的合法状态必不很多（假的），用 map 只记录合法状态的 dp 值。

转移好麻烦，可以先搜一遍所有转移要求的状态哪里不能为 $1$，然后发现由于物品是个矩形所以新状态对应位置也是 $1$。

最后输出了一下发现在 $m = 10$ 时合法转移只有 $274$ 种。

// 搜索
void dfs(int x, int sta, int cnt) {
	if (x >= m) {
		trss[sta] = cnt;
		return ;
	}
	dfs(x + 1, sta, cnt);
	int two = 15; // 1111
	if (x + 1 < m)
		dfs(x + 2, sta | (two << (x * 2)), cnt + 1);
	int three = 21; // 010101
	if (x + 2 < m)
		dfs(x + 3, sta | (three << (x * 2)), cnt + 1);
}

// 转移
Base = 0;
rep(i, 1, m) Base = Base << 2 | 1;
rep(i, 1, k) {
	int x, y; cin >> x >> y; --y;
	no[x] |= 1 << (y * 2);
}
int st = (Base << 1) | no[1];
f[1].clear(); f[1][st] = 0;
rep(i, 2, n) {
	int op = i & 1; f[op].clear();
	for (auto [sta, v] : f[!op])
		for (auto [trs, val] : trss)
			if ((sta & trs) == 0 && (trs & no[i]) == 0) {
				int nxt = (((sta | trs) & Base) << 1) | trs | no[i];
				int &nv = f[op][nxt]; if (v + val > nv) nv = v + val;
			}
}

好像复杂度寄了来着，不会算，反正过 Heoi（衡二 OI）数据了。

啊？过原题数据了？陈年老题强度是这样的。

P5504

划分区间时，两端点颜色相同，选的颜色一定是端点颜色，不然缩小区间肯定不劣，缩小的部分划成新区间。

所以转移柿子很好写：

\[\begin{aligned} f_i &= f_j + s_i(cnt_i - (cnt_j - 1))^2\ \ \ (s_{j + 1} = s_i)\\ f_i - s_icnt_i^2 &= -2s_i(cnt_j - 1)cnt_i + f_j + s_i(cnt_j - 1)^2 \end{aligned} \]

我都写成这样了当然是每个颜色一棵李超树啦。

~~只会李超树了~~。