共42道题,当前是第13

初赛真题

(电电鼠与方阵)有一个 $n * n(2 \leq n \leq 5000)$ 的方阵,其中每个方格有一个电力值。小Y 可以在这个方阵中得到电力,方法就是在一些方格放上电电鼠来吸收电力,这样就可以获得这些方格上的电力。

不过放的电电鼠须要遵循两个规则:

1. 一个方格最多只能放一只电电鼠;
2. 所有 $2 * 2$ 的子矩阵(共有 $(n - 1) * (n - 1)$ 个)必须恰好包含两只电电鼠。   

小Y用了一个程序求出了能获得的最大总电力。试补全程序。

#include<bits/stdc++.h>
using namespace std;    

const int N = 5100 ;
int a___(1)___ ;  

int main() {
	int n, ans1 = 0, ans2 = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) scanf("%d", & a[i][j]);
	for (int i = 1; i <= n; i++) {
		int odd = 0, even = 0;
		for (int j = 1; j <= n; j++) {
			int x = ___(2)___;
			if (j & 1) odd += x;
			else even += x;
		}
		ans1 + = max(odd, even);
	}
	for (int i = 1; i <= n; i++) {
		int odd = 0, even = 0;
		for (int j = 1; j <= n; j++) {
			int x = ___(3)___;
			if (___(4)___) even += x;
			else odd += x;
		}
		ans2 += max(odd, even);
	}
	printf("%d\n", ___(5)___);
	return 0;
}

1. C。
2. A。
3. B。
4. C。
5. D。

观察规律,我们可以发现,在任何一种方案中,都会呈现出重复前两行或者重复前两列的规律。也就是说,我们可以通过枚举这两种不同的情况来找出所有的方案。观察规律可以发现,在列复制的情况下,每一行要么是奇数编号的点全部被选择,要么是偶数编号的点全部被选择。所以在代码中,我们可以枚举所有的行并将其奇数点的和与偶数点的和统计起来,并贪心地选择最大的一种策略,这就是代码中 $ans1$ 的计算原理。 $ans2$ 的计算无非就是在计算行复制的情况,与上面的过程是类似的。

Question

1. (1) 处应填( )

2. (2) 处应填( )

3. (3) 处应填( )

4. (4) 处应填( )

5. (5) 处应填( )

陈伦制作 版权所无 粤ICP备16127491号-1