[Codeforces 321D][2018HN省队集训D4T2] Ciel and Flipboard

rvalue 收录于 cnblogs 题解

2019-03-04 约 797 字预计阅读 2 分钟

迁移提示

本文迁移自博客园, 原文链接

[Codeforces 321D][2018HN省队集训D4T2] Ciel and Flipboard

题意

给定一个 $n\times n$ 的矩阵 $A$, ($n$ 为奇数) , 每次可以选 $A$ 的一个 $\frac {n+1}2 \times \frac {n+1} 2$ 的子矩阵并让这个子矩阵中的所有值取反.

进行若干次操作最大化整个矩阵中的元素值之和. 输出这个最大值.

$n\le 33$, $|A_{i,j}|\le 1000$

题解

~~毒瘤wls活该被A~~

hzoi2017_jjm 当场AC, 大强辣!

这题是个结论题.

首先我们看他 $n\le 33$ 必有高论. ~~实际上就是个结论优化暴力.~~

接着我们发现这个 $\frac{n+1}2$ 非常奥妙重重. 设这个值为 $m$. 它刚好卡在比一半稍多的位置, 中间的一行一列经常被翻转. 或者说, 只要 $(i,j)$ 被翻转, $(i,m)$ 和 $(m,j)$ 一定也被翻了. 如果 $(i,j)$ 没被翻但是 $(i,m)$ 被翻了, 那么肯定当前操作的子矩阵就被怼到一边去, 导致 $(i,j\pm m)$ 被翻. 不难发现 $(i,j),(i,m),(i,j+m)$ 三个位置在一次操作中如果有一个被翻, 那么必定有且仅有另一个被翻. 也就是说这三个位置的翻转状态的异或和不变且一直是 $0$.

这个结论显然对于另一维也成立. $(i,j),(m,j),(i+m,j)$ 三个位置的翻转状态的异或和也是 $0$.

这三个位置的翻转状态只要知道两个显然就能计算出第三个. 而这些关系都和 $(i,m)$ 以及 $(m,j)$ 有关. 我们考虑枚举这些用得很多的位置的翻转状态. (注意到我们对于第 $m$ 行/列, 只需要枚举一半就可以推出另一半的状态.) 容易发现第 $m$ 行和第 $m$ 列的状态确定后, 剩余的位置被分为若干形如 ${(i,j),(i+m,j),(i,j+m),(i+m,j+m)}$ 的组合, 组合之间互相不再有影响. 于是我们可以枚举其中一个位置的状态推出其余位置的状态, 然后两种情况取 $\max$ 求和即为答案.

虽然我们只需要枚举一半, 但是总枚举量还是有 $2^n=2^{33}\approx 8\times 10^9$. 再加上还需要 $O(n^2)$ 验证显然非常不靠谱.

我们又惊奇地发现, 枚举行之后, ${(i,j),(i+m,j),(i,j+m),(i+m,j+m)}$ 只和 $(i,m)$ 有关. 于是我们可以分别枚举 $(i,m)$ 的状态计算一遍和再取 $\max$ 最后求和.

总时间复杂度 $O(2^mn^2)$.

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51


#include <bits/stdc++.h>

const int MAXN=50;
const int k[2]={1,-1};

int n;
int a[MAXN][MAXN];
int d[MAXN][MAXN];

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			scanf("%d",a[i]+j);
	int m=(n+1)>>1;
	int ans=INT_MIN;
	for(int s=0;s<(1<<m);s++){
		int sum=0;
		for(int i=0;i<m;i++)
			d[m-1][i]=((s>>i)&1)?1:-1;
		for(int i=m;i<n;i++)
			d[m-1][i]=d[m-1][i-m]*d[m-1][m-1];
		for(int i=0;i<n;i++)
			sum+=d[m-1][i]*a[m-1][i];
		for(int i=0;i<m-1;i++){
			int cur=INT_MIN;
			for(int r=0;r<2;r++){
				d[i][m-1]=k[r];
				d[i+m][m-1]=d[i][m-1]*d[m-1][m-1];
				int now=d[i][m-1]*a[i][m-1]+d[i+m][m-1]*a[i+m][m-1];
				for(int j=0;j<m-1;j++){
					int tmp=INT_MIN;
					for(int r=0;r<2;r++){
						d[i][j]=k[r];
						d[i+m][j]=d[i][j]*d[m-1][j];
						d[i][j+m]=d[i][j]*d[i][m-1];
						d[i+m][j+m]=d[i+m][j]*d[i+m][m-1];
						tmp=std::max(tmp,d[i][j]*a[i][j]+d[i+m][j]*a[i+m][j]+d[i][j+m]*a[i][j+m]+d[i+m][j+m]*a[i+m][j+m]);
					}
					now+=tmp;
				}
				cur=std::max(cur,now);
			}
			sum+=cur;
		}
		ans=std::max(ans,sum);
	}
	printf("%d\n",ans);
	return 0;
}

目录

[Codeforces 321D][2018HN省队集训D4T2] Ciel and Flipboard

[Codeforces 321D][2018HN省队集训D4T2] Ciel and Flipboard

题意

题解

参考代码