胡策部分题解
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!\)