C/C++教程

TC14069 - BearDestroys 题解

本文主要是介绍TC14069 - BearDestroys 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

考虑轮廓线 DP。注意到题意就是要求按照以横坐标为第一关键字、纵坐标为第二关键字进行模拟，而我们按这个顺序 DP 恰好是合适的。

需要记录什么？显然要知道当前位置是否能往右倒、往下倒。根据顺序，后者显然如果下面还有位置的话（并且当前位置没有被覆盖）那么一定可以。而是否能往右倒，还取决于 \((x-1,y+1)\) 是否往下倒。所以记录已决定区域的轮廓是否倒、往哪儿倒？这样有三种状态，是 \(3^m\)，寄。注意到其实我们只关心未决定区域的轮廓是否被占领，这样就 \(2^m\) 了。

这题的 DP 转移要求求所有局面的倒的树的数量之和，非常适合定义一个组合对象（也就是维护低次和的套路）的结构体转移，定义加法、乘法、数乘，写的很爽。

然而可以发现这题最大的难点是 \(n\leq 13,m\leq 30\)……把 \(n,m\) 颠倒过来？sorry，做不到，因为必须按照题意中的顺序模拟，不然就不一定能知道当前位置是否能往右倒。

不过我们考虑轮廓线 DP 的本质：就是转移只与相邻位置有关，所以任意时刻只需要保留已决定区域与未决定区域的交界处的状态。而并没有规定 DP 顺序，只是一般使用从上到下、从左到右的顺序可以使得任意时刻的轮廓线上的位置数量达到了下限——\(\min(n,m)\)。而如今不能翻转棋盘，不妨考虑有没有其它 DP 顺序既使得无后效性（DP 能按照题意正常进行），轮廓线又比较小。

考虑为了满足无后效性需要怎样。如果要知道一个位置是否能往右倒，需要知道 \((x,y)\) 和 \((x,y+1)\) 分别是否被占领，而这只与 \((x,y-1),(x-1,y),(x-1,y+1)\) 这三个格子有关。也就是，这三个格子的决定时间一定要在 \((x,y)\) 前。而如果我们每次都选能决定的最低位置决定，手动演绎一波发现决定区域初期是一个三角形，轮廓线始终是副对角线方向的。而这样轮廓线显然时刻不超过 \(\min(n,m)\)。就可以做了，复杂度 \(\mathrm O(2^nnm)\)。

然而这样直接写实在是太复杂了，要对 mask 的变换进行一大大大大堆分类讨论。我采取的策略是：先预处理每一步决定的位置、轮廓线上元素的集合，转移时就维护一个 bool 数组，在里面修改，然后暴力获得新的 mask。这样写是真的很爽，虽然复杂度大了一点（\(\mathrm O\!\left(2^nnm^2\right)\)），但还是能过。

code 
constexpr int N = 20, M = 35;

int n, m, nm;
int sx[N * M], sy[N * M];
vii sur[N * M];

struct type {
	int a0, a1;
	type(int a0 = 0, int a1 = 0) : a0(a0), a1(a1) {}
	friend type operator*(int f, type g) { return type((ll)f * g.a0 % P, (ll)f * g.a1 % P); }
	friend type operator+(type f, type g) { return type(add(f.a0, g.a0), add(f.a1, g.a1)); }
	friend void operator+=(type &f, type g) { f = f + g; }
	friend type operator*(type f, type g) { return type((ll)f.a0 * g.a0 % P, ((ll)f.a0 * g.a1 + (ll)f.a1 * g.a0) % P); }
} dp[N * M][1 << 14 | 10];
void trans(int s, int msk) {
	static bool a[N][M]; memset(a, 0, sizeof(a));
	auto nxtmsk = [&]() {
		int res = 0, now = 0;
		for(tii t : sur[s + 1]) if(++now, a[X(t)][Y(t)]) res |= 1 << now - 1;
		return res;
	};
	auto trs = [&](int v, type t) { dp[s + 1][nxtmsk()] += v * t * dp[s][msk]; /* 组合对象的乘法有线性性，所以可以不要括号 */ };
	REP(i, 0, SZ(sur[s]) - 1) if(msk >> i & 1) a[X(sur[s][i])][Y(sur[s][i])] = true;
	int x = sx[s + 1], y = sy[s + 1];
	if(a[x][y]) {
		trs(2, type(1, 0));
	} else {
		bool ok[2] = {y < m && !a[x][y + 1], x < n && !a[x + 1][y]};
		if(ok[0] && ok[1]) {
			a[x][y] = a[x][y + 1] = true, trs(1, type(1, 1)), a[x][y] = a[x][y + 1] = false;
			a[x][y] = a[x + 1][y] = true, trs(1, type(1, 1)), a[x][y] = a[x + 1][y] = false;
		} else if(ok[0]) {
			a[x][y] = a[x][y + 1] = true, trs(2, type(1, 1));
		} else if(ok[1]) {
			a[x][y] = a[x + 1][y] = true, trs(2, type(1, 1));
		} else trs(2, type(1, 0));
	}
}

struct BearDestroys {
int sumUp(int W, int H, int MOD) {
	m = W, n = H, P = MOD, nm = n * m;
	static bool alr[N][M];
	REP(i, 1, nm) {
		PER(x, n, 1) REP(y, 1, m) if(!alr[x][y]) {
			bool flg = true;
			if(y > 1) flg &= alr[x][y - 1];
			if(x > 1) flg &= alr[x - 1][y];
			if(x > 1 && y < m) flg &= alr[x - 1][y + 1];
			if(flg) {
				sx[i] = x, sy[i] = y;
				alr[x][y] = true;
				REP(x, 1, n) REP(y, 1, m) if(!alr[x][y]) {
					bool flg = false;
					flg |= x > 1 && alr[x - 1][y];
					flg |= x < n && alr[x + 1][y];
					flg |= y > 1 && alr[x][y - 1];
					flg |= y < m && alr[x][y + 1];
					if(flg) sur[i].pb(x, y);
				}
				goto edlp;
			}
		} edlp:;
	}
	dp[0][0] = type(1, 0);
	REP(s, 0, nm - 1) REP(msk, 0, (1 << SZ(sur[s])) - 1) trans(s, msk);
	int ans = dp[nm][0].a1;
	return ans;
}
};
这篇关于TC14069 - BearDestroys 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航