首页 > 其他分享 >题解 AGC059C【Guessing Permutation for as Long as Possible】

题解 AGC059C【Guessing Permutation for as Long as Possible】

时间:2022-12-17 21:44:06浏览次数:54  
标签:Guessing 顺序 题解 询问 小红 Long Possible 提问

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

相关文章

  • 题解 SS221112B【Y】
    problem\(2n\)个有顺序的整数,每个数在\([0,m]\)内随机独立均匀生成,求前一半的和大于后一半的和的方案数。\(T,n,m\leq2000\)。solution0总方案数是明晰的:\(S=(m+1)......
  • 洛谷P3224 [HNOI2012]永无乡 题解 splay tree 启发式合并
    题目链接:https://www.luogu.com.cn/problem/P3224主要知识点是:树上启发式合并,即每次合并将小的树里面的每个点合并大大的树里面,时间复杂度\(O(n\log^2n)\)。同时需要......
  • java跨域问题解决
    问题描述:在使用前后端分离的情况下,前端访问后端时会出现跨域问题解决方式:1.设置跨域1)、单个控制器方法CORS注解在单个方法中加入注解@CrossOrigin。2)、整个控制器......
  • 题解 SP10264 METEORS - Meteors
    整体二分经典题,所以我们用分块解决Solution和整体二分类似,我们把\(k\)次操作分成\(\sqrtk\)块,每一块一起考虑。对于区间加,可以转化为差分,那么在每个块一起作差分后......
  • CodeForces-300#B 题解
    题意给定\(n\)个数,保证\(n\mid3\),要将这\(n\)个数分配到\(\dfrac{n}{3}\)个三元组,有\(m\)个要求\(a,b\),每个要求表示\(a,b\)要在同一个三元组里,求最后的分......
  • P3874 砍树 题解
    前置树形dp,二分。题意本质上是一个树上背包,需要选不少于\(k\)个物品,每个物品有一个重量\(w\)和价值\(v\),求性价比最大值。分析既然是性价比,显然是分数规划。先......
  • CF992E Nastya and King-Shamans 题解
    传送门分析由于满足\(a_i\ge0\),所以\(s_i\)单调不减。当我们找到一个\(i\)时,不管\(i\)是否满足,下一个可能的一定大于等于\(a_i+s_{i-1}\)。而且\(a_i+s_{i-1}......
  • P8810 [蓝桥杯 2022 国 C] 数组个数 题解
    思路比较简单的一道题。用的五维dp,看到二维和三维的dp直接膜了orz。正文开始。分析不难看出dp。因为\(b_i\)的值只与\(a_{i-1},a_i,a_{i+1}\)有关,所以我们定......
  • CF939F Cutlet 题解
    题意简述有一个正反面都为\(0\)的卡片,每过\(1\)分朝下那一面的数值就会增加\(1\),你可以在几个区间的时间内翻转卡片,求经过\(2n\)秒后能否让这个卡片的正反面的数都......
  • YACS 11 月甲题解
    https://iai.sh.cn/contest这把还是简单的,难度对标普及组。所有题解均口胡。T1观察&性质你扫左端点,然后维护以当前左端点最长的合法子段,显然右端点单不降,因为当你......