[AtCoder Grand Contest 025 Problem D]Choosing Points

題目大意：

給你\(n,d_1,d_2\)，讓你找\(n^2\)個點，使得任意兩點的距離不為\(\sqrt{d_1}\)和\(\sqrt{d_2}\)，橫、縱坐标均在\(0\sim 2n-1\)之間。

解題思路：

對\(d\)進行分析\(令d=a^2+b^2\)。

若\(d\mod 2=1\)，則\(a,b\)一奇一偶，對點國際象棋染色（即相鄰兩個染不同顔色）。

若\(d\mod 4=2\)，則\(a,b\)均為奇數，則一行黑，一行白染色。

若\(d\mod 4=0\)，則将四個點當成一個點，對\(\frac{d}{4}\)如上讨論即可。

兩次染色，把剩餘的白點輸出\(n^2\)個即可。

C++ Code：

#include<bits/stdc++.h>
int n,d1,d2,color[606][606],N;
void paint(int d){
	int b=0;
	while(!(d&3))d>>=2,++b;
	if(d&1){
		for(int i=0;i<N;++i)
		for(int j=0;j<N;++j)
		if(((i>>b)+(j>>b))&1)color[i][j]=1;
	}else{
		for(int i=0;i<N;++i)
		for(int j=0;j<N;++j)
		if((i>>b)&1)color[i][j]=1;
	}
}
int main(){
	scanf("%d%d%d",&n,&d1,&d2);
	N=n<<1;
	paint(d1),paint(d2);
	int NN=n*n;
	for(int i=0;i<N;++i)
	for(int j=0;j<N;++j)
	if(!color[i][j]){
		printf("%d %d\n",i,j);
		if(!--NN)return 0;
	}
}
           

轉載于:https://www.cnblogs.com/Mrsrz/p/9270111.html