24.10.17

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

A

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

B

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

0：6

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）数据了。

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