CF1254C Point Ordering
Codeforces Luogu 分析 首先用 $A_1,A_2$ 两个点将凸包分为两部分。我们容易用 $n-2$ 次询问二求出其它的 $n-2$ 个点在左侧还是右侧。 接着用 $n-2$ 次询问一，求出其他每个点与 $A_1,A_2$ 构成的三角形的面积。这时我们实际上已经得知了每个点到直线 $A_1A_2$ 的距离。 我们把两侧的点分开处理。对于某一侧的点（假设已按逆时针排列），显然它们...
Codeforces Luogu 分析 首先用 $A_1,A_2$ 两个点将凸包分为两部分。我们容易用 $n-2$ 次询问二求出其它的 $n-2$ 个点在左侧还是右侧。 接着用 $n-2$ 次询问一，求出其他每个点与 $A_1,A_2$ 构成的三角形的面积。这时我们实际上已经得知了每个点到直线 $A_1A_2$ 的距离。 我们把两侧的点分开处理。对于某一侧的点（假设已按逆时针排列），显然它们...
UOJ 分析 我们先假装原图是个二分图。 我们可以先想办法求出原图的一棵生成树，那么对其黑白染色即可求出答案。 一个暴力的做法是尝试删掉所有边，如果删掉某条边后连通性发生改变则这条边在生成树上，保留这条边，否则删掉这条边。这样子询问次数是 $\frac{n(n-1)}{2}$。 事实上我们可以每次二分下一条树边的位置：如果删掉 $[L,mid]$ 中的边后图仍连通则下一条树边在 $(mid,...
Codeforces 分析 为了方便，下面把为 $y$ 的数称为特殊数。 首先我们可以通过一次询问得到某个集合内的特殊数的个数的奇偶性。 如果询问的集合大小是偶数，且特殊数的个数为偶数，那么返回值为 $0$ 。 如果询问的集合大小是偶数，且特殊数的个数为奇数，那么返回值为 $y$ 。 如果询问的集合大小是奇数，且特殊数的个数为偶数，那么返回值为 $x$ 。 如果询问的集合大小是奇数，且特...