Codeforces 2155D Batteries 题解 [ 绿 ] [ 图论 ] [ Ad-hoc ]

Batteries：很有趣的一个 Ad-hoc，之前见到过一个类似的构造。如果对上脑电波应该很快能秒掉。

看到这种比较奇怪的交互次数限制，可以想到拆限制的式子，\(\lfloor\dfrac{n^2}{a}\rfloor = \lfloor\dfrac{n}{a}\cdot n\rfloor\)。这提示我们对于每一个电池最多只能操作 \(\bm{\dfrac{n}{a}}\) 次。

然后形式化一下题意，可以转化为一个 \(n\) 点的完全图，图上有 \(a\) 个黑点，一条边是黑边当且仅当 \(u, v\) 都是黑点。你需要在 \(\lfloor\dfrac{n^2}{a}\rfloor\) 次内找出一条黑边。

一眼看上去非常没有头猪，所以可以试试拎出来环、菊花、树、链、二分图之类的特殊图来研究。然后你就能发现，如果从这张图里，随意挑出一个 \(n\) 点的简单环，然后往环上加一些捷径边，就能完成构造。具体而言，令 \(k = 1\)，然后按顺序执行下列操作（连边的意思就是对 \(u, v\) 进行一次询问）：

1. 对于所有的 \(1 \le i \le n\)，连边 \(i\to(i+k - 1)\bmod n + 1\)，直到找到一个黑边。
2. \(k\gets k + 1\)，返回第一步。

说人话就是先搞出一个 \(n\) 个点的有向环，然后每一轮对每个点依次询问走 \(1, 2, 3, 4, \cdots\) 步抵达的点进行询问。

正确性证明是简单的，对于有 \(a\) 个黑点的环，任意两个黑点之间的距离的最小值不会超过 \(\dfrac{n}{a}\)，因此每个黑点都跳 \(\bm{\dfrac{n}{a}}\) 步就一定能找到一条黑边，这和我们上文拆的限制是一样的。

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
int n, res;
void solve()
{cin >> n;int now = 1;while(1){for(int i = 0; i < n; i++){int v = (i + now) % n;cout << i + 1 << " " << v + 1 << endl;cin >> res;if(res == 1) return;}now++;}
}
int main()
{int t;cin >> t;while(t--) solve();return 0;
}