[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