构造刷题记录

[AGC001D] Arrays and Palindrome

首先观察发现奇数的个数看起来很重要，然后手玩一会发现最多只能有两个奇数，然后再分讨构造就可以了。

[AT_hitachi2020_c] ThREE

观察到 \(3\mid a\times b\) 要求 \(a,b\) 中至少一个 3 的倍数。

发现如果两个点的距离为 3 的话他们的深度的奇偶性一定不同，所以可以以此建立二分图，如果某一部的大小小于 3 的倍数的数量就给这边全放 3 的倍数。否则就将模 3 余 1 或 2 的两类数分两边放再把 3 的倍数随便放。

[AT_hitachi2020_e] Odd Sum Rectangles

首先考虑 \(n=m\) 的情况，通过对小规模矩阵的打表我们大致可以发现答案的构造大概可以分治构造。

考虑把当前的 \(2^k-1\times2^k-1\) 的矩阵切成 4 个 \(2^{k-1}-1\times2^{k-1}-1\) 的矩阵和正中间的一个十字结构，考虑在正中间放一个 1 然后递归处理，发现这玩意结构优美得符合条件。

然后对于 \(n\neq m\) 的情况就用若干个这样的方形拼起来。

[ABC111D] Robot Arms

首先考虑有解的判定：显然你不管怎么操作，最后的奇偶性是变不了的，所以如果存在两对终点 \((x,y)\) 和 \((a,b)\)，使得 \(x+y\not\equiv a+b \pmod2\) 就无解。

然后考虑 40 步的限制，看起来就很二进制。

所以我们直接用 \(2^38\) 到 \(2^0\)，每次朝走了过后曼哈顿距离更小的方向走。