主要思路
虽然是个套路题，但是为了完全体会 min-max 反演的魅力之处，我决定写篇博客来强化一下。
这道题乍一看不是很能做，因为摆放状态很多。然而，计算机科学这种东西解决不了问题的时候不讲究正解，只讲究近似。所以，我们可以枚举一个旋转角 \(\theta\) 来决定最终摆放的形态。枚举之后就可以直接二分费用并建边做二分图。
竖的横的上下分开填。
// CF1103A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 200;
int n, ux, uy, dx, dy;
char str[MAX_N];
int main()
{
scanf("%s", str + 1), n = strlen(str + 1);
ux = 1, uy = 1, dx = 0, dy = 1;
for (int i = 1; i <= n; i++)
if (str[i] == '0')
printf("%d %d\n", ux, uy), uy = uy % 4 + 1;
else
printf("%d %d\n", (dx >> 1) + 3, dy), dx = (dx + 1) % 4, dy = (dy + 1) % 4 + 1;
return 0;
}
一共有 60 次询问机会，我们可以分两个 30 次：第一个 30 次用来询问最高位前的一位，第二个 30 位用来补全我们对 \(a – 1\) 的猜测。
这题还挺好的。最后异或出来的路径是有链和环组成的。我们可以把链和环分开来求，因为从链上某点到环上某点之间的距离可以计算两次，所以不造成影响。所以我们可以把链做一个多项式，环做一个多项式，在做一遍 FWT_XOR 就完美了。
前天晚上打得一场，没想到神仙特别多，把我这个卡在 D 题的小 sb 直接区分出来了，害。