「AGC025D」 Choosing Points 「AGC025D」 Choosing Points

神仙构造题。

首先你会尝试暴力做，先随便选一个点，然后把当前能选得全选上，然后你发现这样样例都过不了。

然后我们可以这样考虑：你把距离为 (sqrt{D}) 的点连起来，会得到一个二分图。

考虑分情况讨论：

(D equiv 3 pmod 4)

根据小学二年级的数学知识可知这种情况不存在。

(D equiv 1 pmod 2)
此时有 ((x_1-x_2)^2+(y_1-y_2)^2equiv|x_1-x_2|+|y_1-y_2|equiv (x_1-x_2)+(y_1-y_2)equiv 1pmod 2)

显然可以按照 ((x+y)) 的奇偶性进行分组。

(D equiv 0 pmod 2)

现在好像处理不了了，我们可能需要继续分组。

(D equiv 2 pmod 4)

根据小学二年级得到数学知识显然没有 (x^2equiv 2pmod 4)，所以一定有 ((x_1-x_2)^2equiv 1 and (y_1-y_2)^2equiv 1)。按照 (x) 的奇偶性分组后，有边相连的显然不在同一组。

(D equiv 0 pmod 4)

根据小学二年级得到数学知识显然没有 (x^2equiv 2pmod 4)，所以一定有((x_1-x_2)^2+(y_1-y_2)^2equiv 0 pmod 4iff x_1equiv x_2pmod 2 and y_1equiv y_2pmod 2)
然后把有边相连的点看成一组，我们只需要证明每组都是二分图。这个东西只需要将所有的坐标都除以二向下取整，就转化成了范围更小的子问题。

然后你现在有两个 (D)，每个 (D) 会把图划分成两部分，也就是说，我们会将原图分成至多四个部分，找最大的那个部分输出即可。

/*---Author:HenryHuang---*/
/*---Never Settle---*/
#include<bits/stdc++.h>
using namespace std;
int siz,d1,d2;
int vis[1010][1010];
void solve(int x){
	int tim=0;
	while(x%4==0) x/=4,++tim;
	if(x&1){
		for(int i=0;i<siz*2;++i)
			for(int j=0;j<siz*2;++j)
				if(((i>>tim)+(j>>tim))&1) vis[i][j]=1;
	}
	else{
		for(int i=0;i<siz*2;++i)
			for(int j=0;j<siz*2;++j)
				if(((i>>tim))&1) vis[i][j]=1;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>siz>>d1>>d2;solve(d1),solve(d2);
	int num=0; 
	for(int i=0;i<siz*2;++i)
		for(int j=0;j<siz*2;++j){
			if(!vis[i][j]) cout<<i<<' '<<j<<'
',++num;
			if(num==siz*siz) return 0; 
		}
			
	return 0;
}

「AGC025D」 Choosing Points 「AGC025D」 Choosing Points

相关推荐