AGC025D Choosing Points

题意：给定 , 要求构造一个在 的网格中选出 个点的方案, 使得任意两点间的距离不为 或 。

，时限 。

---

记某两个点的坐标差值为 ，则两点的距离为 。

若 ，由于平方不改变奇偶性，则 的奇偶性与 相同。

所以，当 为奇数时，互斥关系为二分图（棋盘染色）。

当 为偶数时， 要么全为奇数，要么全为偶数。也就是说，棋盘染色中的同色点之间才有边，异色点之间没有边。

将棋盘染色中的黑点（ 为奇数的点）单独取出，考虑内部的边。不难发现可以将原图转化为 的子问题。

如此反复，直到 为奇数。于是我们证明了，无论 为何值，互斥关系都是二分图。

（当然，用代码验证这个结论也是不难的）

---

递归地划分坐标，最后构造二分图，复杂度为 。推式子可以做到 ，不表。

本题中有两个 ，则问题转化为：有两张标号对应的，有 个点的二分图，要求选出 个点，使得这些点在两张图上都是独立集。

这个问题是很简单的。对于一个二分图，取出所有左部点或所有右部点，则形成独立集。

我们将两张图都黑白染色，则每个点的染色情况有 种。选出一组染色情况相同的点，显然是独立集。

选择点数最多的一组，即可保证点数 。