Round 862

Round 862(div 2)

Codeforces Round 862 (Div. 2)

$A$

如果 $n$ 为偶数，那么如果 $a_i$ 异或和为 $0$，则 $x$ 为任意数都可以。否则偶数个 $x$ 异或和为 $0$ ，无解。

如果 $n$ 为奇数，那么设 $k$ 表示 $a_i$ 异或和，所以 $x=k$ 就可以满足条件

$B$

容易发现，把整个字符串里面的最小的移动到最前面的一定是最优的。如果有多个，则取最在末尾的。所以扫一遍就可以得出答案。

$C$

神秘题。

考虑对于每个方程 $a_i x^2 + b_i x + c_i$，可得一个 $k_jx=a_i x^2 + b_i x + c_i$

所以可得方程 $a_i x^2 +(b_i-k_j)x+c_i$，$\Delta = (b_i-k_j)^2-4a_ic_i < 0$

可以二分判断有没有$k_i$可以满足条件，时间复杂度 $\Theta(n\log n)$

$D$

脑车题

容易发现，定义 $L$ 表示树的直径。当 $k>L$ 时，显然每个点都是独立的。当 $k=L$ 时，直径的端点构成一个连通块。

所以考虑记录 $d_i$ 表示 $i$ 到直径的最大距离。用类似双指针的思想，对 $d_i$ 排序。考虑统计独立的点的个数。因为 $d_l$ 单调递增，所以对于距离 $k$，$k-1$ 以及以前的贡献任然会对 $k$ 做贡献。再算上直径一个连通块，设当前独立的点的个数为 $ans$，答案即为 $\min( ans+1,n)$

$E$

我是采购