Codeforces 321D Ciel and Flipboard（结论题+枚举）

题目链接 Ciel and Flipboard

题意给出一个$n*n$的正方形，每个格子里有一个数，每次可以将一个大小为$x*x$的子正方形翻转

翻转的意义为该区域里的数都变成原来的相反数。

求经过若干次操作之后整个正方形的所有数之和。

这题关键就是要知道这个结论。

假设$st[i][j]$为$a[i][j]$的翻转情况（$st[i][j] = 0$ 不翻转 $st[i][j] = 1$ 翻转）

那么一定有 $st[i][j]$ xor $st[i][x]$ xor $st[i][j + x]$ = $0$

这是行的情况

那么对于列的情况也有

$st[i][j]$ xor $st[x][j]$ xor $st[i + x][j]$ = $0$

每一个式子中，我们求出了两项，就可以知道另外一项。

考虑枚举$st[x][1]$, $st[x][2]$, $st[x][3]$, ..., $st[x][x]$

这样一共有$2^{17}$种枚举方案

根据上面的结论，枚举了这$x$个元素之后，这一行的剩下全部元素都知道了

也就是说我们花了$2^{x}$的复杂度，得到了中间这一行的所有情况。

接着我们要对剩下的一些未知情况进行枚举。

首先我们枚举$st[1][x]$（$0$ or $1$）

这样的话我们得到了$st[x + 1][x]$的值

在知道这两个值的情况下，我们再枚举$st[1][1]$的值（$0$ or $1$）

于是根据所有之前得到的值，我们可以得到$st[1][1], st[1][x + 1], st[x + 1][1], st[x + 1][x + 1]$

我们根据这些枚举得到的值算出$a[1][1] + a[1][x + 1] + a[x + 1][1] + a[x + 1][x + 1]$在$st[1][1]$等于$0$或$1$的时候哪个更大

处理完$st[1][1]$这边之后我们处理$st[1][2]$（同枚举$st[1][1]$的方法），直到处理到$st[1][x - 1]$。

然后我们枚举$st[2][x]$（$0$ or $1$）

......

直到枚举到$st[x - 1][x]$（$0$ or $1$）

这样就把所有的情况都覆盖了。

时间复杂度$O(2^{x}x^{2})$

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

const int N = 53;

const int mul[2] = {1, -1};

int a[N][N];

int n, x;

int st[N][N];

int ans;

int main(){

	scanf("%d", &n);

	rep(i, 0, n - 1) rep(j, 0, n - 1) scanf("%d", &a[i][j]);

	x = (n + 1) / 2;

	ans = -(1 << 30);

	rep(s, 0, (1 << x) - 1){

		int sum = 0;

		rep(i, 0, x - 1) st[x - 1][i] = (s >> i) & 1;

		rep(i, x, n - 1) st[x - 1][i] = st[x - 1][i - x] ^ st[x - 1][x - 1];

		rep(i, 0, n - 1) sum += mul[st[x - 1][i]] * a[x - 1][i];

		rep(i, 0, x - 2){

			int cnt = -(1 << 30);

			rep(op, 0, 1){

				st[i][x - 1] = op;

				st[i + x][x - 1] = op ^ st[x - 1][x - 1];

				int now = a[i][x - 1] * mul[op] + a[i + x][x - 1] * mul[st[i + x][x - 1]];

				rep(j, 0, x - 2){

					int et = -(1 << 30);

					rep(ct, 0, 1){

						st[i][j] = ct;

						st[i][j + x] = ct ^ st[i][x - 1];

						st[i + x][j] = ct ^ st[x - 1][j];

						st[i + x][j + x] = st[i + x][x - 1] ^ st[i + x][j];

						et = max(et, a[i][j] * mul[st[i][j]] + a[i][j + x] * mul[st[i][j + x]] + a[i + x][j] * mul[st[i + x][j]] + a[i + x][j + x] * mul[st[i + x][j + x]]);

					}

					now += et;

				}

				cnt = max(cnt, now);

			}

			sum += cnt;

		}

		ans = max(ans, sum);

	}

	printf("%d\n", ans);

	return 0;

}

巴特西

Codeforces 321D Ciel and Flipboard（结论题+枚举）

最新文章

热门文章