题目链接 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
", ans);
return 0;
}