CF2196C1题解

传送门：https://www.luogu.com.cn/problem/CF2196C1
强化版：

题意简述：给你一个图的节点数，你可以询问字典序第 \(k\) 条路径是怎么样的，求出具体的每条边。

很显然路径第一条边就是一对边。我们只需要遍历所有路径然后选第一条边就行了。然而所有路径的上界是 \(O(n^4)\) 的，我们不能暴力枚举。因为按字典序排列，前两个节点相同的路径一定是连续的，我们往后二分找到前两个节点不同的第一条路径就找到了一个新边。对于每一条边向后二分。最坏询问复杂度 \(O(4m\log n)\)，最大为 \(16m\)，远小于 \(32(n+m)\)，可以通过。这里也可以只对于第一个点进行二分，我们通过二分找到某一个点引出的路径数量，保证当且仅当一个点第一次被引出时才会进行二分，否则直接加上由上一个节点计算出的该点引出的边数量。复杂度 \(O(4n\log n)\)。

\(O(4m\log n)\) 代码：

#include <bits/stdc++.h>const int N = 226;using namespace std;int a[16];void ask(int k) {cout << "? " << k << endl;memset(a, 0, sizeof a);int cnt;cin >> cnt;for (int i = 1; i <= cnt; ++i) cin >> a[i];
}void solve() {vector<pair<int, int> > ans;int n, m = 0;cin >> n;int now = 1, V = n * n * n * n;while (now <= V) {ask(now);if (a[2]) ++m, ans.push_back(make_pair(a[1], a[2]));int v1 = a[1], v2 = a[2];int l = now, r = V;while (r >= l) {int mid = (l + r) >> 1;ask(mid);if (a[1] == v1 && a[2] == v2) l = mid + 1;else r = mid - 1;}now = r + 1;}cout << "! " << ans.size() << endl;for (auto k: ans) cout << k.first << ' ' << k.second << endl;
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T;cin >> T;while (T--) solve();return 0;
}

\(O(4n\log n)\) 代码：

#include <bits/stdc++.h>using namespace std;int a[16], pos[32];void ask(int k) {cout << "? " << k << endl;a[1] = 0;int cnt;cin >> cnt;for (int i = 1; i <= cnt; ++i) cin >> a[i];
}void solve() {vector<pair<int, int> > ans;int n;cin >> n;int now = 1, V = n * n * n * n + 1;while (now <= V) {ask(now);int v1 = a[1];pos[v1] = now;if (!v1) pos[n + 1] = now;int l = now, r = V;while (r >= l) {int mid = (l + r) >> 1;ask(mid);if (a[1] == v1) l = mid + 1;else r = mid - 1;}now = r + 1;}for (int i = 1; i <= n; ++i) {int p = pos[i] + 1;while (p != pos[i + 1]) {ask(p);ans.push_back(make_pair(i, a[2]));p += pos[a[2] + 1] - pos[a[2]];}}cout << "! " << ans.size() << endl;for (auto k: ans) cout << k.first << ' ' << k.second << endl;
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T;cin >> T;while (T--) solve();return 0;
}