题解归档 - cf321D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf321D
• 本地来源：problems/cf321D/idea.md
• 题目链接：https://codeforces.com/contest/321/problem/D
• 原始标题：CF321D — Ciel and Flipboard

思路

CF321D — Ciel and Flipboard

题意

$n\times n$ 棋盘（$n$ 奇数），可反复选一个 $x\times x$ 子矩阵，将其中所有数乘 $-1$。求操作后全盘元素和的最大值。

关键观察（GF(2) 翻转态）

记 $f_{i,j}\in\{0,1\}$ 表示格子 $(i,j)$ 最终是否被翻转（乘 $-1$）。一次 $x\times x$ 翻转等价于在 GF(2) 上加一个掩码。

对任意 $x$、$j\le x$，操作后三元组 $\{f_{i,j}, f_{i,x}, f_{i,j+x}\}$ 中恰有 0 或 2 个 1；列方向同理。于是对所有合法终态有约束：

$$f_{i,j}\oplus f_{m,j}\oplus f_{i+m,j}=0,\quad f_{j,i}\oplus f_{m,i}\oplus f_{j+m,i}=0$$

其中 $m=\lfloor n/2\rfloor+1$ 为中间行/列（1-indexed）。

合法翻转态空间大小为 $2^{m^2}$，但只需枚举中间列 $f_{1,m},\ldots,f_{m,m}$ 共 $2^m$ 种，其余由约束递推，再对每一列对 $(i, i+m)$ 贪心选是否翻转。

算法

1. $m=n/2+1$，枚举 mask ∈ [0, 2^m)，令 $b_i=f_{i,m}$（中间列翻转标记）。
2. 递推行：$b_i=b_m\oplus b_{i-m}$（$i>m$）。
3. 中间列贡献：$\sum_i b_i?-a_{i,m}:a_{i,m}$。
4. 对每个 $i=1..m-1$，尝试 $j\in\{0,1\}$ 作为列 $i$ 的翻转选择，对 $k=1..m-1$ 用约束算出四格符号因子，取绝对值累加；中间行两格用 $j$ 与 $b_m$ 决定符号，取两种 $j$ 的最大值。
5. 取所有 mask 的最大 res。

复杂度 $O(2^m\cdot m^2)$，$n\le 33$ 时 $m\le 17$ 可过。

易错点

• 网传「逐层环带统计负数奇偶、减 $2\min$」对 CF 数据不成立（如 $3\times3$ 反例可得 21 而非 19）。
• 四格合并时第一格 $(k,i)$ 系数恒为 $+1$，其余三格由 $b_k,j,b_{m+k}$ 决定符号，再取 $|z|$。

结论

采用官方题解：枚举中间列 + 列贪心。样例 9、18 及随机小数据与 BFS 暴力（$n\le3$）一致。

代码

来源：problems/cf321D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 05:00:09
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=40;
const ll inf=1e9;
ll a[maxn][maxn],b[maxn];
int main(){
    ll n,m,i,j,k,mask,ans,res,tmp,mz,fl1,fl2,fl3,zc,pd,z;
    cin>>n;
    m=n/2+1;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    ans=-inf;
    for(mask=0;mask<(1<<m);mask++){
        for(j=1;j<=m;j++){
            b[j]=(mask>>(j-1))&1;
        }
        res=0;
        for(i=m+1;i<=n;i++){
            b[i]=b[m]^b[i-m];
        }
        for(i=1;i<=n;i++){
            if(b[i])res-=a[i][m];
            else res+=a[i][m];
        }
        for(i=1;i<m;i++){
            mz=-inf;
            for(j=0;j<2;j++){
                tmp=0;
                for(k=1;k<m;k++){
                    fl1=b[k]?-1:1;
                    fl2=j?-1:1;
                    fl3=(j^b[m+k])?-1:1;
                    z=a[k][i]+a[k][i+m]*fl1+a[k+m][i]*fl2+a[k+m][i+m]*fl3;
                    if(z<0)z=-z;
                    tmp+=z;
                }
                fl1=j?-1:1;
                fl2=(j^b[m])?-1:1;
                mz=max(mz,tmp+fl1*a[m][i]+fl2*a[m][i+m]);
            }
            res+=mz;
        }
        ans=max(ans,res);
    }
    cout<<ans<<endl;
    return 0;
}