题目

给定一个 $2n\times 2n$ 的网格图,在其中取 $n^2$ 个点使得两两距离不为 $\sqrt {D_1}$ 和 $\sqrt {D_2}$。

$1\le n\le 300$,$1\le D_1,D_2\le 2\times 10^5$.

分析

考虑只有一个 $a^2+b^2=D$ 的限制的时候,整张图是个二分图:

  • 若 $D$ 为奇数,则显然距离为 $\sqrt D$ 的点横纵坐标之和奇偶性不同($a,b$ 一奇一偶)。
  • 若 $D$ 为偶数,则我们发现 $2\mid x + y$ 和 $2\nmid x + y$ 的点对互相之间没有连边,于是只考虑其中一部分,发现我们可以将其视为一个旋转了 $45$ 度的网格,单位长度是 $\sqrt 2$,于是我们递归地将 $D$ 除掉 $2$,如此进行 $D$ 总会变为奇数。

考虑对 $D_1, D_2$ 建出两张二分图,然后这两张二分图分别进行二分图染色,我们可以根据每个点在两张二分图上分别属于哪部分来将其分为 $4$ 类点(均为独立集),根据鸽巢定理,必然存在一类点的数量超过 $n^2$,然后我们就构造完了。

代码

const int kN = 2e3 + 5, kInf = 0x3f3f3f3f;

int n, D[2], cnt[4], col[2][kN][kN];
std::vector <pii> s[2];

void GetEdge() {
    for(int p = 0; p < 2; ++p) {
        for(int i = 0; i * i <= D[p]; ++i)
            for(int j = 0; j * j <= D[p]; ++j)
                if(i * i + j * j == D[p]) {
                    s[p].push_back(mkp(i, j));
                    s[p].push_back(mkp(i, -j));
                    s[p].push_back(mkp(-i, j));
                    s[p].push_back(mkp(-i, -j));
                }
    }
}
std::queue <pii> que;
bool vis[kN][kN];
void GetColor() {
    for(int p = 0; p < 2; ++p) {
        memset(vis, false, sizeof(vis));
        for(int i = 0; i < n << 1; ++i)
            for(int j = 0; j < n << 1; ++j) if(!vis[i][j]) {
                que.push(mkp(i, j)); vis[i][j] = true;
                while(!que.empty()) {
                    pii u = que.front(); que.pop();
                    for(auto k : s[p]) {
                        int ni = u.fi + k.fi, nj = u.se + k.se;
                        if(ni < 0 || nj < 0 || ni >= n << 1 || nj >= n << 1 || vis[ni][nj]) continue;
                        col[p][ni][nj] = col[p][u.fi][u.se] ^ 1;
                        que.push(mkp(ni, nj));
                        vis[ni][nj] = true;
                    }
                }
            }
    }
}

int main() { 
    int T = 1; //rd(T);
    while(T--) {
        rd(n, D[0], D[1]);
        GetEdge(); GetColor();
        for(int i = 0; i < n << 1; ++i)
            for(int j = 0; j < n << 1; ++j) {
                ++cnt[col[1][i][j] << 1 | col[0][i][j]];
            }
        for(int i = 0; i < 4; ++i) {
            if(cnt[i] >= n * n) {
                int output_cnt = 0;
                for(int j = 0; j < n << 1; ++j)
                    for(int k = 0; k < n << 1; ++k) {
                        if(output_cnt < n * n && (col[1][j][k] << 1 | col[0][j][k]) == i) {
                            printf("%d %d\n", j, k);
                            ++output_cnt;
                        }
                    }
                break;
            }
        }
    } return 0;
}
最后修改:2021 年 02 月 04 日 06 : 03 PM