problem A
首先，设 \(n\) 个数中有 \(i\) 个正数， \(n-i\) 个负数，因为 \(0\) 不会使答案更优所以不考虑。可得：
\[\frac{i\times (i-1)}{2}\le k \le \frac{i\times (i-1)}{2}+i\times (n-i)
\]
\[i\times (i-1)\le 2k \le i\times (i-1)+2i\times (n-i)
\]
\[i\times (i-1)\le 2k \le i^2-i+2in-2i^2
\]
\[i\times (i-1)\le 2k \le -i^2+2in-i
\]
\[i\times (i-1)\le 2k \le i\times (2n-i-1)
\]
可以利用二分求出取值范围吧……
先考虑答案为
\[ans=\frac{i\times (i-1)}{2}+\frac{(n-i)\times (n-i-1)}{2}
\]
\[ans=\frac{i^2-i}{2}+\frac{(n-i)^2-(n-i)}{2}
\]
\[ans=\frac{i^2-i+n^2-2ni+i^2-n+i}{2}
\]
\[ans=i^2-ni+\frac{n^2-n}{2}
\]
然后求二次函数最值。
problem B
可以考虑使用 \(bitset\) 来存储数字，比较的时候就枚举公共前后缀的长度，然后将前一个数向左移动相应位后异或一下在向右移动一定距离在数一下 \(1\) 的个数就可以判断是否匹配了，复杂度基本为常数。
然后没想法了。
problem C
先猜一波结论，答案肯定是在所有数乘上在子区间中出现字数的序列中的中位数，大一个权值线段树先骗骗分。
打完骚操作发现不行。
然后决定暴力和随机化骗分，对于 \(50pts\) ，使用主席树获得所有情况。对于剩下的部分，随机选取若干个区间来获取中位数，最后再把这些区间的中位数求一个中位数。
只能骗分暴力了……
XJOI contest 1668
原文：https://www.cnblogs.com/Point-King/p/13695511.html
