「AGC025D」 Choosing Points

神仙构造题。

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

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

考虑分情况讨论：

\(D \equiv 3 \pmod 4\)

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

\(D \equiv 1 \pmod 2\)

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

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

\(D \equiv 0 \pmod 2\)

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

\(D \equiv 2 \pmod 4\)

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

\(D \equiv 0 \pmod 4\)

根据小学二年级得到数学知识显然没有 \(x^2\equiv 2\pmod 4\)，所以一定有\((x_1-x_2)^2+(y_1-y_2)^2\equiv 0 \pmod 4\iff x_1\equiv x_2\pmod 2 \and y_1\equiv y_2\pmod 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<<'\n',++num;

			if(num==siz*siz) return 0;

		}

	return 0;

}

巴特西

「AGC025D」 Choosing Points

「AGC025D」 Choosing Points

最新文章

热门文章