CF2196C2题解

传送门：https://www.luogu.com.cn/problem/CF2196C2
弱化版题解：https://www.cnblogs.com/Jefferyz/p/19660552

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

因为询问不能超过 \(n+m\) 次，我们绝不可能在 \(n\) 或 \(m\) 上乘上任何东西，弱化版的二分完全不能考虑。沿用弱化版优化成 \(O(4n\log n)\) 的思想：处理出一个点引出的路径条数，当当前询问到某个遇到过的节点，因为字典序的优先级，该路径所引出的路径条数已经被计算完成，直接加上跳过这个点即可。然而我们不能二分出某个点的位置。我们尝试从头开始遍历，当在当前路径末尾加入新边时，我们在图加入最后一条边而不是像弱化版一样加入第一条边。在加入后如果发现当前加入的节点已经向外延申过，直接加上由新节点引出的路径数避免重复加边。在这种情况，一次询问可能清空路径加入一个新的点，或是加入一条新边，询问次数严格为 \(n+m\)。当然还需要判断什么时候终止，当读入 \(0\) 时，说明当前的 \(k\) 已经超过路径总数，遍历结束。我们还需要多出一次询问这样就是 \(n+m+1\) 次了。注意到第一次询问必定是一个无意义的 \(1\) 节点，我们直接从第二条路径开始询问就行了。询问次数 \(n-1+m+1=n+m\)，恰好符合限制。

#include <bits/stdc++.h>using namespace std;int a[32], sum[32];void ask(int k) {cout << "? " << k << endl;memset(a, 0, sizeof a);cin >> a[0];for (int i = 1; i <= a[0]; ++i) cin >> a[i];for (int i = 1; i < a[0]; ++i) sum[a[i]] += sum[a[a[0]]] + 1;
}void solve() {memset(sum, 0, sizeof sum);vector<pair<int, int> > ans;int n;cin >> n;for (int k = 2; ; ++k) {ask(k);if (!a[0]) break;if (a[2]) ans.push_back(make_pair(a[a[0] - 1], a[a[0]]));k += sum[a[a[0]]];}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;
}