在 cdqz 的集训结束了，虽然总榜比较好看但感觉只过了一堆平凡题。
怎么一个月就省选了（恼）
150【IOI2016】shortcut（拆绝对值）
考虑确定了架桥架在哪里之后怎么算（经过桥的）直径。实际上就是 \(\max (|pos_u-pos_x|+|pos_v-pos_y|+d_u+d_v)\)。
大力转切比雪夫（大概）然后二分，先排除 \(|pos_u-pos_v|+d_u+d_v\leq X\) 的点，剩下的点限制 \(pos_x-pos_y\) 和 \(pos_x+pos_y\) 的范围，然后双指针就行。
提交记录 #674333 - Universal Online Judge (uoj.ac)
151【IOI2016】messy（交互，分治，构造）
考虑一个构造：传一个 \(s_0=1\)，然后询问 \(n\) 次，就可以知道 \(0\) 的位置。
实际上你也可以传一个集合过去，在 \(n\) 次询问得到这些集合。
问题是每个数只能传一次。所以假设我们上次传过去的集合是 \(S\)，那么传下一个集合 \(T\) 的方式是把 \(x\in T\)，\(\{x\}\oplus S\) 传过去。由于我们知道 \(S'\)，所以枚举 \(x'\) 之后询问 \(\{x'\}\oplus S'\) 很容易得到 \(T'\)。
大力二进制分组，可以得到 \(n\log n\) 次操作的做法。
提交记录 #674659 - Universal Online Judge (uoj.ac)
152【IOI2017】Ancient Books（贪心，析合树）
考虑 \(\text{cir}(p)=1\) 的情况，发现答案是下界 \(X=\sum |i-p_i|\)。
容易构造出 \(2(\text{cir}(p)-1)+X\) 的上界：搜出生成树，每次以 \(1\) 的代价换连通块，然后以 \(1\) 的代价回到原来的位置。
然而换块未必需要 \(1\) 的代价。考虑连通块编号为 \(\{1,2,1\}\) 的三个点，可以从第一个数出发往后走到 \(2\)，把书放到 \(2\)，做完 \(2\) 连通块，再返回原位置。随便构造一下可以发现一个值域连续段（\(p_{[l,r]}\to[l,r]\)）可以取到下界 \(X\)，所以换块次数是值域连续段数量 \(-1\)。
写上去发现只过了 \(s=0\)，发现 \(s=1\)，\(\{0,2,1,4\}\) 会出问题，也就是 \(s\) 需要”跳出来“。然后大概是析合树上跳祖先的过程（？）直接贪心就好了。
不太懂析合树，瞎写了个东西/kk。
提交记录 #674659 - Universal Online Judge (uoj.ac)
153 IOI 2017 Toy Train（博弈，图论）
考虑只有一个充电站，且充电站是自环怎么做。可以 BFS 出所有 Arezon 能保证到充电站的结点。
考虑只有一个充电站怎么做，按上面 BFS 之后，如果 Arezon 控制充电站且存在出边对应结点能到充电站，或者 Borzon 控制且全部出边都能到充电站，那么能到的就是合法的，否则答案为空集。
考虑多个充电站，那么 BFS 多次，如果一个充电站不满足上面条件那么一定不会去这个充电站充电，那么把这个充电站删掉，重复 \(n\) 次可以得到解。
提交记录 #674949 - Universal Online Judge (uoj.ac)
154 IOI 2017 Simurgh（交互）
可以 \(\mathcal{O}(m)\)。具体而言，找到生成树，然后对于一个环，依次删去一条树边并加入非树边，可以得到非树边和树边的大小关系。如果所有边都和非树边相等那么一定都是 \(0\)。据此可以得到所有边的信息。
拓展到正解：如果我们只询问生成树上边的信息，那么我们就可以选择一个无环的边的子集，并询问子集中是否有关键边，然后通过二分技巧找到所有关键边。关键在于把原图拆成尽可能少的生成森林，一个构造是：找到一个点和它相连的所有边，这样可以拆出来 \(\mathcal{O}(n)\) 棵生成树，在所有生成树里面二分边即可。询问次数大约是 \(3n+n\log n\)，不是很懂为啥给 \(8000\) 次询问。
https://uoj.ac/submission/675475
标签：ac,Set,询问,Solution,pos,充电站,Judge,uoj From： https://www.cnblogs.com/yllcm/p/17981183