[CF321D] Ciel and Flipboard

前言

智商题杀我。

题目

洛谷

CF

讲解

(n) 为奇数，操作区间长度 (m=frac{n+1}{2})，显然需要挖掘性质。

假如我们一次操作只会翻转一行，假设翻转第 (i) 行的某个长度为 (m) 的区间，不难发现 (a_{i,m}) 一定会被翻转，如果这一次 (a_{i,j}(j<m)) 被翻转，那么 (a_{i,j+m}) 一定没有被翻转，vice versa。

更进一步地，一行中如果翻转了偶数次，那么 (a_{i,j}(j<m)) 与 (a_{i,j+m}) 同号，奇数次则异号。

注意不是对称！某 ( m Rain) 姓同学因为这个和搬题人“精心”构造的大样例 ( m color{red}WA) 了。

当然列也有相同的性质，只不过中间那个点变成了 (a_{m,i}) 。

那么翻转一个 (m imes m) 的矩阵意味着什么呢？意味着你可以在满足上述规则的基础上任意变换！因为它们是线性不相关的！

所以只需要枚举一个轴的正负号，另外一个轴贪心求解即可。

时间复杂度 (O(2^mm^2))。

代码

短代码完全不能说明题目难度.jpg

//12252024832524
#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std;

typedef long long LL;
const int MAXN = 35;
const LL INF = 1ll << 60;
int n,m;
LL a[MAXN][MAXN],ans = -INF;

LL Read()
{
	LL x = 0,f = 1; char c = getchar();
	while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
	while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
	return x * f;
}
TT void Put1(T x)
{
	if(x > 9) Put1(x/10);
	putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
	if(x < 0) putchar('-'),x = -x;
	Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}

int f[MAXN];
void solve()
{
	LL ret = a[m][m]*f[m];
	for(int i = 1;i < m;++ i) ret += f[i] * a[m][i] + f[i] * f[m] * a[m][i+m];//中间那一行 
	for(int i = 1;i < m;++ i)
	{
		LL MAX = -INF;
		for(int sg = -1;sg <= 1;sg += 2)
		{
			LL cur = a[i][m]*sg+a[i+m][m]*sg*f[m];
			for(int j = 1;j < m;++ j) 
				cur += Abs(a[i][j]+a[i+m][j]*f[j]+a[i][j+m]*sg+a[i+m][j+m]*f[j]*f[m]*sg);
			MAX = Max(MAX,cur);
		}
		ret += MAX; 
	}
	ans = Max(ans,ret); 
}
void dfs(int x)
{
	if(x == m+1) {solve();return;}
	f[x] = 1; dfs(x+1); 
	f[x] = -1; dfs(x+1); 
}

int main()
{
//	freopen("taozi.in","r",stdin);
//	freopen("taozi.out","w",stdout);
	n = Read(); m = (n+1) >> 1;
	for(int i = 1;i <= n;++ i)
		for(int j = 1;j <= n;++ j)
			a[i][j] = Read();
	if(n == 1){Put(Abs(a[1][1]),'
');return 0;}
	dfs(1);
	Put(ans,'
');
	return 0;
}