胡策部分题解
R1
T1
题目大意：将 \(0/1\) 串分成若干段，任意拼接，最后的lis最短长度。
推一波式子：\(\max_{i}(A_i+s_b-(i-A_i))=\max_{i}(2A_i-i)+s_b\)。
也就是看成 \(A_i=0\) 有 \(1\) 的贡献 \(A_i=1\) 有 \(-1\) 的贡献。
我需要拆成若干子区间，一个区间的权值是上面说的和 \(0\) 取 \(max\) 的。
换句话说找到前 \(i/2\)（选 \(i/2\) 个区间会产生 \(i\) 段） 大的区间和。拿线段树带悔贪心就行。
这个线段树需要维护的是 前缀最值，后缀最值，子段最值。（当然是Min和Max都要维护）。
注意我们还需要枚举前缀，后缀选不选。
前缀选后缀选你会发现实际上是，强制选全部，然后删去一个子段。
T2
咕咕咕咕，/kel
T3
题目大意：你需要通过若干次询问找到一棵树。询问的形式为
ask(x,S) 表示询问 \(\sum_{u\in
S}dis(x,u)\)
首先可以 \(n\) 次问出dep，然后在相邻两层连边。
如何连边？
随机化。
大概是说，我随便把前一层随机划分成两个集合。然后看按照 \(\sum dis(i,x)\) 划分成若干等价类。
出题人哥哥说，最劣情况是都连一个点，然后这样每次等价类大小减半。
只能感性理解了/kk
\[ \sum dis(i,x)=\sum dep_i+dep_x-2dep_{lca(i,x)} \]
\(\sum dep_{lca(i,x)}\) 可以交换求和号，变成对于子树siz的树上前缀和。
然后比较经典的想法是在上一层的集合二分。
一个很神奇但是也很reasonable的构造是：
我们将完全与分界点相离的子树选中（蓝色），并且选中分界点的根，递归构造。
这样考虑蓝色点子树内答案都是 \(1\)，然后红色点子树内都是 \(0\)，绿色点选上的理由是强制绿色点大于蓝色点，这样不会有交。
此时我们就能区分出前半段后半段。
考虑二分每次只是把一半的集合扣去，同时每次查询的大小严格小于[l,r]的大小，所以 \(\sum\) 是 \(n^2\) 级别的。
R2
R3
R4
R5
R6
R7
R8
T2
叫做妙妙题，实际上也是妙妙题。
一个不太晓得怎么想到的至关重要的转化。
如果我们自私每次猜自己，那么由于不知道 \(A,B\) 的分配关系，很难保证一半的正确性。
为了人民！为了集体！为了联盟！我们必须舍弃小义，奉献集体。
想想呀，某一个颜色的奇偶性一定是确定的，那我让一半的猜这个数是奇数，另一半猜是偶数。
这样就能保证全体至少一半人猜的对的！这就是集体的魅力呀！！！
/qiang/qiang/qiang
现在问题变成了区分两个点。
当然这个题还是尽可能写多一点别的的
- type=1 我让奇数的猜奇数，偶数的猜偶数。
- 如果 \(n\) 是偶数的话，让每个人和对面的人区分，看他们两个之间的字符串是左串大还是右串大。如果>=2个人相同考虑这样必定形成中心对称结构，直接猜对面的即可。
- 如果 \(n\) 是素数时，考虑 \(\sum_{i\in A} x-i=kx-\sum_{i\in A}i\)，注意此时时统计到自身的，\(kx\) 遍历了整个值域，所以每个人的值=\([0,p-1]\)，这样也可以直接猜奇偶。
正解策略是把这 \(n\) 个点放到单位圆上。然后考虑一条过圆心的线，必定将整个平面（单位元）划分成两个大小类似的区域。
我们现在知道的是除了这个向量外的向量和。如果这个点不落在 \(OP\) 上，那么已经做完了。
特殊决策是如果落在 \(OP\) 上，我们就当作最终点是原点 \(O\)。
这样如果最终点真的是 \(O\) 没关系，如果不是 \(O\) 那最多也就会两个点错误（偶数情况）；一个点错误（奇数情况）是可以接受的。
很神奇的是如果我们只知道个数，(\(|S|\)) 的话，这个问题难的要死。
我们比“只知道个数”仅仅多了一个顺序。但这样就能让我们猜对了。
EXlucas如何卡常
我们都知道 exlucas本质上就是在扩域算 \(n!\)