【AtCoder Grand Contest 025 D】Choosing Points | Mrsrz's blog

构造。

题目大意：

给定 $2n\times 2n$ 的二维平面，给出整数 $D_1,D_2$，要求找到 $n^2$ 个整点，使得它们两两的欧几里得距离都不为 $\sqrt{D_1}$ 或 $\sqrt{D_2}$。

题解：

考虑只有一个限制 $D$ 的情况。这时我们有一张二分图，即可以通过对二维平面黑白染色，使得同色点之间的距离均不为 $\sqrt D$。

考虑 $D\bmod 4$ 的值。

若 $D\bmod 4=1$，则说明横、纵坐标一奇一偶，此时按照棋盘染色即可。

若 $D\bmod 4=2$，则说明横、纵坐标均为奇数，此时按照行（或列）标号，每行（或列）染成同一种颜色即可。

若 $D\bmod 4=0$，则我们把 $2\times 2$ 的区域染成同一种颜色，然后相当于考虑 $\frac D 4$ 的子问题。

我们取同色点即可满足条件。

考虑有两个限制的情况。也就是说我们要求两种不同染色都一样的点。由于一共有 $4n^2$ 种点，有 $4$ 种不同染色情况，由抽屉原理可知一定有解。

染色可以 $O(n^2)$ 完成。

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;
    }
}