CodeForces - 201A (Clear Symmetry)做题笔记

发表于 | 更新于 | | 阅读次数：

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接： https://cn.vjudge.net/problem/CodeForces-201A

这题是找规律题，但又有点奇怪，一开始尝试按照题目要求那样枚举x找n变化的规律，但是找不到。。后来才知道这题是枚举n找x的变化规律，可以证明除了x=3的情况，只要方阵的sharpness>=x，对应的n就一定满足条件（证明见下），因而只要找到能使矩阵的最大sharpness>=x的最小的n就行了。

在纸上画图，能得出来n为奇数的情况优于n为偶数的情况（n为奇数时n对应矩阵的最大sharpness大于n-1对应矩阵的最大sharpness），所以只考虑n为奇数的情况，此时容易根据图推出最大sharpness的公式为(n//2)^2 * ((n//2)+1)^2

下面证明找sharpness>=x的最小n的正确性（x=3除外）：
证明：除了x=3的情况，逐组去掉所有的四个一组的1，有可能把sharpness控制在abs(sharpness-x)<4的范围（如果不能，那么去掉所有四个一组的1），继续逐组去掉两个一组的1，一定能把sharpness控制在abs(sharpness-x)<2的范围，此时如果sharpness!=1，那么去掉矩阵中心的1就行了）

最后贴上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
#include <cstring>
using namespace std;
int main() {
	int x,tmp;
	scanf("%d",&x);
	if (x==3) {
		printf("5");
		return 0;
	}
	for (int i=1;;i+=2) {
		tmp=i>>1;
		if (tmp*tmp+(tmp+1)*(tmp+1)>=x) {
			printf("%d",i);
			return 0;
		}
	}
}