题目概述

有 $n\times n$ 的网格，每次可以选择一个 $m\times m(m={n+1\over 2})$ 的子网格将数字进行取反，求最大数字和。

解题报告

根本不可做的结论题……感性理解手玩一下会发现，在一行中，$j,m,j+m​$ 这三个网格不可能出现奇数个被反转，即记录 $s_{i,j}​$ 表示 $(i,j)​$ 的反转状态（ $0​$ 没反转，$1​$ 反转了），则 $s_{i,j}\ xor\ s_{i,m}\ xor\ s_{i,j+m}=0​$ 。列同理。

观察上面的结论，会发现除了第 $m$ 行和第 $m$ 列之外，$(i,j),(i+m,j),(i,j+m),(i+m,j+m)$ 是相关的，与其他独立，这样的话我们可以考虑枚举 $m$ 行前 $m$ 个和 $m$ 列前 $m$ 个的反转状态，然后对于每个格子 $(i,j)$ 枚举 $0/1$ 两个状态，取最优值累加。

继续观察……发现只需要枚举第 $m$ 行前 $m$ 个，这样第 $m$ 列的前 $m$ 个也会变得互相独立，可以枚举 $0/1$ 取最优值。

但是怎么证明这样构造出来的反转状态一定存在？由于 $>m$ 的部分都是推出来的，所以我们只需要保证前 $m\times m$ 的网格内可以被构造出来即可，可以通过按顺序（从上往下，从左往右）构造。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=33;

int n,m,a[maxn+5][maxn+5],s[maxn+5][maxn+5],ans;

#define val(x,y) (s[x][y]?-a[x][y]:a[x][y])
inline int Update(int x,int y,int f){
    s[x][y]=f;s[x+m][y]=s[x][y]^s[m][y];s[x][y+m]=s[x][y]^s[x][m];s[x+m][y+m]=s[x+m][y]^s[x+m][m];
    return val(x,y)+val(x+m,y)+val(x,y+m)+val(x+m,y+m);
}
inline int Solve(int i,int f,int sum=0){
    s[i][m]=f;s[i+m][m]=s[i][m]^s[m][m];sum=val(i,m)+val(i+m,m);
    for (int j=1;j<m;j++) sum+=max(Update(i,j,0),Update(i,j,1));return sum;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);m=n+1>>1;
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) scanf("%d",&a[i][j]),ans+=a[i][j];
    for (int S=0,sum=0;S<(1<<m);ans=max(ans,sum),sum=0,S++){
        for (int i=1;i<=m;i++) s[m][i]=S>>i-1&1;for (int i=1;i<m;i++) s[m][i+m]=s[m][i]^s[m][m];
        for (int i=1;i<=n;i++) sum+=val(m,i);for (int i=1;i<m;i++) sum+=max(Solve(i,0),Solve(i,1));
    }printf("%d\n",ans);return 0;
}