problem
小明有一个隐藏的排列 \(p\),小红想要猜出来。
现在允许小红提问,每次提问的形式是 \(a_i\) 和 \(b_i\),然后小明会告诉小红谁大谁小。
小红是个老实的人,她的询问顺序已经提前被小明套出来了,即小明知道小红心里对 \(n * (n-1) / 2\) 种可能询问的预期猜测顺序。
而且他也知道小红虽然老实,但不是笨蛋,如果某一次询问可以通过前面的结果推导出来,她就会跳过这个询问。
给定 \(n* (n-1) / 2\) 个按顺序的提问,问有多少种排列 \(p\),可以使得小红老老实实做出所有提问。
solution
第一步是强制定向:使 \(a_i<b_i\)。
然后是一个引理:只需要考虑三个元素的 “链”。(这个是最难的地方)
- 如果有一条很长的链 \(a\to b\to c\to\cdots\to z\),然后询问了 \(a\to z\)。
- 你拎出前三个点 \(x,y,z\),假如询问 \((x,y)\) 的时间戳是 \(v_{x,y}\)。
- 那么如果 \(v_{x,z}>max\{v_{x,y},v_{y,z}\}\),则 \(x,y,z\) 不合法。否则可以删掉 \(y\)。
于是我们很开心的取三个下标 \(1\leq i<j<k\leq n\),然后大力的分讨。
- 结论一:一共只有 \((i,j),(j,k),(i,k)\) 有用。记按时间顺序的询问依次为 \(x,y,z\)。
- 结论二:按时间的前两个询问的顺序没啥用。
- 当 \(z=(i,j)\) 是最后一个询问时,它生效的条件是 \(p_j<p_k,p_i<p_k\) 或 \(p_j>p_k,p_i>p_k\),简称 \(x,y\) 同向。
- 当 \(z=(j,k)\) 是最后一个询问时,对称,\(x,y\) 同向。
- 当 \(z=(i,k)\) 是最后一个询问时,它生效的条件是 \(p_i<p_j>p_k\) 或者反过来,简称 \(x,y\) 异向。
这意味着我们枚举三个点之后,会有一些形如 “我无条件地钦定某两个询问的回答要相同或者不同” 的东西,我们先不管环的问题,我们用种类并查集,拆点连一下,然后发现如果有环,就相当于是 \(p_i<p_j\) 推出了 \(p_i>p_j\)。
最终的答案,每个连通块都有唯一的另一个与它对称,且只能二选一,所以 \(2^{\text{全局连通块个数}/2}\)。
标签:Guessing,顺序,题解,询问,小红,Long,Possible,提问 From: https://www.cnblogs.com/caijianhong/p/solution-AGC059C.html