GYM106191E-Leaf
GYM106191E-Leaf题目大意：
有一张隐藏的， \(n\) 个节点的有向图。你的目标是在 \(n\) 次查询内，找到这张图的任一叶子节点，或没有则输出 \(-1\) 。
你的查询操作：
输出两个点集：\(S\) 和 \(T\) ，它们是集合 \(\{1,2,3, \ldots \ldots, n\}\) 的子集。集合 \(S\) 和 \(T\) 可以有交集。
系统将会返回，从 \(S\) 出发，到 \(T\) 结束的边的数量。
\(Hint\)
特殊的，当 \(S==T\) 时，系统返回的值即为，集合中的点构成的子图的边数。
题解
要找到一个叶子节点，即找到一个点，出度+入度为 \(0\)。可以发现，单独把一个节点，和剩余节点作为两个集合，一次查询只能得到入度或出度的信息。我们无法在 \(O(n)\) 时间内维护出每个点。
根据 \(Hint\) ，我们可以先查询所有点的集合，得到全图的边数 \(tot\) 。
再依次查询除去第 \(i\) 个点的集合。可以发现用全图边数减去每次查询的结果，得到的就是第 \(i\) 个点的度。度为 \(1\) 即说明该点为叶子节点。
但是这样查询，一共使用了 \(n+1\) 次查询，比题目要求多了一次。一张图中的边数是固定的，所以最后第 \(n\) 个点的度，可以通过 总度数 \(tot*2\) 减去其余每个点的度数得到。这样我们就只使用了 \(n\) 次查询操作，就得到了所有点的度。
#include#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define umap unordered_map//#define endl '\n'using namespace std;using i128 = __int128;const int mod =1e9+7;template void read(T&x){ x=0;int f = 1; char c=getchar(); for(;!isdigit(c);c=getchar())if(c=='-')f=-1; for(;isdigit(c);c=getchar())x=(x yyds。多谢分享 鼓励转贴优秀软件安全工具和文档！ 感谢分享
页:
[1]