题意
? 给定 \(n, D_1,D_2\), 要求构造一个在 \(2n\times 2n\) 的网格中选出 \(n^2\) 个点的方案, 使得任意两点间的距离不为 \(\sqrt {D_1}\) 或 \(\sqrt {D_2}\)。
? 数据范围：\(n \le 300,D \le 2\times 10 ^5\)
题解
? 很妙的一道题，完全没有想到里面竟然藏了一个二分图。
? 先考虑只有一个D的情况。
? 假定我们把 \(2n\times 2n\)? 的点中距离为 \(D\) 的点连边，形成了一个图，我们要证明它是二分图。
? 假定 \(D=4^k\times p\)?，\(D=A^2+B^2\)?，那么 \(A\) 和 \(B\) 可以表示成 \(2^k\times a,2^k\times b\) 的形式，现在讨论 \(p\mod 4\) 的情形。
- \(p\mod 4 = 1\)?，那么\(a\mod 2=1 , b\mod 2 = 0\)?，按照网格点 \((x,y)\) 中 \(x+y\) 的奇偶性黑白染色。
- \(p\mod 4 = 2\)?，那么\(a\mod 2= 1 , b\mod 2 = 1\)，按照网格点 \((x,y)\) 中 \(x\) 的奇偶性黑白染色。??
- \(p\mod 4 = 3\)，那么 \(a,b\) 不存在，没有边必然是二分图。?
? 所以，对于一个D，肯定是二分图。
? 现在我们有两个二分图，我们分别对两个图按如上方案黑白染色，对于某个点都有一个颜色对 \((a,b)\) 来表示其在两张二分图中被染上的颜色。显然 \((a,b)\) 只有 \(4\) 种方案，那么 \(4\times n^2\) 个点分成四个集合，一定存在一个集合的点数 \(\ge n^2\) ，把那个集合中的 \(n^2\) 个点输出即可。
代码
#include <bits/stdc++.h>
using namespace std ;
#define ll long long
#define rep(i,l,r) for(ll i=(l);i<=(r);++i)
#define per(i,r,l) for(ll i=(r);i>=(l);--i)
#define wif while
#define d1 sdfikjo
#define d2 dsfgkjh
const ll inf = INT_MAX , df = 1305 ;
ll i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,cnt[2][2],col[2][df][df],d1,d2;
void solve(ll d,ll id) {
ll k = 0 ;
wif( d % 4 == 0 ) d /= 4 , k ++ ;
k = 1ll << k ;
if( d % 4 == 3 ) return ;
if( d % 4 == 1 ) {
rep(i,0,n-1) rep(j,0,n-1) col[id][i][j] = ( ( i / k + j / k ) & 1 ) ;
}
else {
rep(i,0,n-1) rep(j,0,n-1) col[id][i][j] = ( ( i / k ) & 1 ) ;
}
return ; }
int main() {
cin >> n >> d1 >> d2 ; n <<= 1 ;
solve( d1 , 0 ) , solve( d2 , 1 ) ;
rep(i,0,n-1) rep(j,0,n-1) {
cnt[col[0][i][j]][col[1][i][j]] ++ ; }
ll x = 0 , y = 1 ;
rep(i,0,1) rep(j,0,1) {
if( cnt[i][j] >= n * n / 4 ) { x = i , y = j ; break ; }
}
ll num = 0 ;
rep(i,0,n-1) rep(j,0,n-1) {
if( col[0][i][j] == x && col[1][i][j] == y ) {
++ num ;
printf( "%lld %lld\n" , i , j ) ;
if( num == n * n / 4 ) return 0 ;
}
}
}