menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[思维]BZOJ5401【s】题解
apps BZOJ
local_offer 查看标签
comment 0 条评论

题目概述

有 $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;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up