「CF#662」A Chess Coloring(div.2)

题意

Link

给你一个$n\times n$的图,对其用2种颜色染色,要求:1.相邻的格子颜色必须相反 2.从最外圈开始染色

问需要最少多少次染色

题解

打比赛的时候推样例推出来公式了……

先说结论:$ans=n/2+1$

手推一下可以发现最外圈最少都要2次(因为要染完了才能下一圈

而里面的$n-3$圈则只用一次,因为如果上一圈用了黑色

染下一圈的时候用黑色,这样就不用换色,减少次数

每一层之间的差距方格数差距为2,那么我们就可以算出一共有$n/2$层

(在除去最后一层的情况下,也就是只有一个方格)

而只有第一次要多一次,其他都是一次,所以答案为$n/2+1$

这里的圈是指n*n矩阵的最外围的一圈,然后依次推进去的圈

Code

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
#include <bits/stdc++.h>
using namespace std;

#define RE register

inline void fread(long long &x){
x=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
x*=f;
}



int main(){
long long T;
fread(T);
for(RE int i=1;i<=T;i++){
long long qwq;
fread(qwq);
printf("%lld\n",qwq/2+1);
}
return 0;
}
0%