IT评测·应用市场-qidao123.com技术社区

标题: 「IOI2017」西默夫 / Simurgh [打印本页]

作者: 三尺非寒 时间: 2022-8-9 14:46
标题: 「IOI2017」西默夫 / Simurgh
称御道状态是 \(1\)，其余为 \(0\)。\(a_p\) 表示 \(p\) 这条边是不是御道。
如果允许我们问一个森林的话，问题会简单很多：
我们可以直接枚举一端 \(i\)，每次二分出最小的 \(r\) 使得一端在 \(i\)，一端在 \([i + 1, r]\) 的所有边存在 \(1\) 边的，这样就找到了一条 \((i, r)\) 的御道，然后往后二分就行了。这样次数就可以做到 \(n + n \log n\)。
如果我们已经知道任意一棵生成树的 \(01\) 状态，那么我们就可以使用上述的森林再拼一些这棵树上的边形成的树，询问回来再减掉已知的，就行了。
考虑寻找一棵生成树的状态。
如果是完全图，我们考虑一个长度为 \(n\) 的大环，每次挖掉一条边问一下，把所有答案加起来除 \(n - 1\) 就得到了大环上有多少 \(1\) 边，再和每个询问减一下就得到了每条边的状态。
如果不是完全图，并没有那么好的性质，如果是割边，那一定是 \(1\) 边，否则至少有一个经过这条边的环。
假设环的大小为 \(len\)。

假设我们知道环上任意一条边的状态 \(a_p\)，我们可以推出环上未知边的状态 \(a_q\)，使用挖掉两条边的两次询问相减即可。
如果环上信息都未知，事实上也有 \(len\) 次询问获得所有状态的方法，设除了环以外的地方和是 \(t\)，每次获得的是 \(t + \sum a - a_i\) 这种形式。求和后是 \(sum = len \times t + \sum a \times (len - 1)\)。考虑在 \(\pmod {len}\) 意义下，每多一个御道就相当于 \(-1\)，最多减 \(len\) 次，如果 \(sum \bmod len\) 并非零很好推出 \(\sum a, t\)，否则因为是生成树，不可能环上都是 \(1\)，肯定环上都是 \(0\)。

考虑找一棵 dfs 树，每次找一条非树边，把他在树上覆盖的边信息都问出来。问出每条边最多均摊 \(2\)，因此这部分不超过 \(2n\)，总询问次数 \(3n + n \log n\)。
code

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)