AT_agc025_d [AGC025D] Choosing Points

闲话

好久没写题解了，来写一篇。

题解

题面

这个题图大小为 \(4n^2\)，但是他要我们给出一个大小为 \(n^2\) 的点集，使得点集中任意两个点距离不为 \(\sqrt{D1}\) 和 \(\sqrt{D2}\)，注意到给出点集大小恰好为图大小的 \(\frac{1}{4}\)，这启示我们把图上的点分成四类，其中每一类中任意两个点的距离都不为 \(\sqrt{D1}\) 或 \(\sqrt{D2}\)，这样子就是我们有四个候选点集 \(S_1,S_2,S_3,S_4\)，满足：

\[|S_1|+|S_2|+|S_3|+|S_4|=4n^2 \]

根据鸽巢原理，我们有 \(\max(|S_1|,|S_2|,|S_3|,|S_4|) \ge n^2\)，于是我们这么做一定能找出一个满足条件的大小为 \(n^2\) 的点集。

但是还是不好找这个点集，我们先考虑限制只有 \(D1\) 没有 \(D2\) 的情况（下称 \(D\) 为 \(D1\)），我们发现对于一个距离为 \(D\) 的点对不会被我们同时选出，他们互相有限制关系，这启示我们在他们两个点间建边，这样我们问题转化成在一张无向图上找到几个点集，每个点集内部不存在边。

这里并不知道到底是几个点集，让我们猜一下：题目要求总的划分为 \(4\) 个点集，然后限制分别有 \(D1\) 和 \(D2\)，假设对于每一个限制都分成 \(k\) 类点，那么总的点就有 \(k^2\) 类（一个点在第一种限制的划分下可能在 \(k\) 个不同的类，在第二种划分下可能又在 \(k\) 个不同的类），那么就是 \(k^2=4\) 解得 \(k=2\)。

那么我们就有了一个猜想：对于一个限制 \(D\)，可以把图上的点分成两类点，那么我们之前建出来的图应该是一个二分图，我们考虑证明这个东西。

这个限制 \(D\) 如果想要连边要求：

\[(x_1-x_2)^2+(y_1-y_2)^2=D \]

因为要建成二分图，我们尝试分类讨论 \(D\) 的奇偶性，看能不能通过点的奇偶性来分类：

• \(D \equiv 1 \pmod 2\)：

  这种情况说明 \(x_1-x_2\) 和 \(y_1-y_2\) 奇偶性不同，即：

  \[x_1-x_2+y_1-y_2 \equiv 1 \pmod 2 \]

  因为模 \(2\) 所以可以把减法换成加法（\(-1 \equiv 1 \pmod 2\)）：

  \[x_1+y_1+x_2+y_2 \equiv 1 \pmod 2 \]

  那么我们可以得到 \(x_1+y_1\) 和 \(x_2+y_2\) 不同奇偶性，那么我们就对 \(x+y\) 的奇偶性分类。

这样我们讨论完了 \(D\) 为奇数的情况，但是 \(D\) 为偶数的情况下我们得到的是 \(x_1+y_1\) 和 \(x_2+y_2\) 相同奇偶性，无法套用 \(D\) 为奇数的情况，我们考虑按 \(D\) 模 \(4\) 的情况分类：

• \(D \equiv 2 \pmod 4\)：

  注意到一个数的平方模 \(4\) 一定等于 \(0\) 或 \(1\)（偶数余 \(0\)，奇数余 \(1\)），如果 \(D \equiv 2 \pmod 4\) 说明 \(x_1-x_2\) 和 \(y_1-y_2\) 都为奇数，如果我们对每个点的坐标 \((x,y)\) 模 \(2\) 会得到四类点：\((0,0),(0,1),(1,0),(1,1)\)，这种情况下连的边为 \((0,0),(1,1)\) 和 \((0,1),(1,0)\)，于是我们直接令 \((0,0)\) 和 \((0,1)\) 为左部点，\((1,0)\) 和 \((1,1)\) 为右部点即可。

• \(D \equiv 0 \pmod 4\)：

  这种情况非常难分类，你如果还按上面的方式把点分成 \((0,0),(0,1),(1,0),(1,1)\) 这样会出现同类点向自己内部连边，无法说明这是一个二分图。

  但是因为他模 \(4\) 为 \(0\)，我们可以直接将 \(D\) 不断除以 \(4\) 把这种情况归到之前的情况，具体来讲，设 \(D=4^pd\)（\(4\nmid d\)），那么我们对之前那一个式子除以 \(4^p\)，有：

  \[\begin{aligned} \frac{(x_1-x_2)^2+(y_1-y_2)^2}{4^p}&=\frac{D}{4^p}\\ (\frac{x_1-x_2}{2^p})^2+(\frac{y_1-y_2}{2^p})^2&=d \end{aligned} \]

  然后你观察这个式子，发现一定有 \(2^p \mid x_1-x_2,y_1-y_2\)（如果没有的话平方后加起来一定不是一个整数，不可能等于 \(d\)），那么我们就可以按点 \((x,y)\) 两个坐标模 \(2^p\) 的余数分类，不难发现不同类之间是独立的，只有在同一类的点会产生连边，那我们就分开讨论每一类，由于 \(\frac{a-b}{c}=\lceil\frac{a}{c}\rceil-\lceil\frac{b}{c}\rceil\)（\(c \mid a-b\)），点坐标可以看作 \((\lceil\frac{x}{2^p}\rceil,\lceil\frac{y}{2^p}\rceil)\)，限制从 \(D\) 变为 \(d\)，由于不存在 \(d \equiv 0 \pmod 4\)，可以归为之前几类。

那么这样我们对于一个 \(D\)，可以把图上的点分成两类，那么对于两个 \(D1\) 和 \(D2\) 就是四类，可以挑出一个大小 \(\ge n^2\) 的点集。

#include<bits/stdc++.h>
using namespace std;const int N=605;int n,bl[N][N],s[4];void Put(int d,int tmp){int p=0;while((d&3)==0){d>>=2;p++;}for(int i=0;i<n;i++)for(int j=0;j<n;j++){int k1=i%(1<<p),k2=j%(1<<p),x=(i-k1)/(1<<p),y=(j-k2)/(1<<p);if(d&1){if((x+y)&1)bl[i][j]|=tmp;else bl[i][j]|=0;}else{if(x&1)bl[i][j]|=tmp;else bl[i][j]|=0;}}return;
}int main(){scanf("%d",&n);n*=2;int d1,d2;scanf("%d%d",&d1,&d2);Put(d1,1),Put(d2,2);for(int i=0;i<n;i++)for(int j=0;j<n;j++)s[bl[i][j]]++;int goal=0;for(int i=0;i<4;i++)if(s[i]>=n*n/4){goal=i;break;}int cnt=n*n/4;for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(bl[i][j]==goal){cnt--;printf("%d %d\n",i,j);if(cnt==0)return 0;}return 0;
}
/*
2026.8.3
18:57-19:07
*/