胡策部分题解

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的构造是:

img

我们将完全与分界点相离的子树选中(蓝色),并且选中分界点的根,递归构造。

这样考虑蓝色点子树内答案都是 \(1\),然后红色点子树内都是 \(0\),绿色点选上的理由是强制绿色点大于蓝色点,这样不会有交。

此时我们就能区分出前半段后半段。

考虑二分每次只是把一半的集合扣去,同时每次查询的大小严格小于[l,r]的大小,所以 \(\sum\)\(n^2\) 级别的。


R2


R3


R4


R5


R6


R7


R8


T2

叫做妙妙题,实际上也是妙妙题。


一个不太晓得怎么想到的至关重要的转化。

如果我们自私每次猜自己,那么由于不知道 \(A,B\) 的分配关系,很难保证一半的正确性。

为了人民!为了集体!为了联盟!我们必须舍弃小义,奉献集体。

想想呀,某一个颜色的奇偶性一定是确定的,那我让一半的猜这个数是奇数,另一半猜是偶数。

这样就能保证全体至少一半人猜的对的!这就是集体的魅力呀!!!

/qiang/qiang/qiang

现在问题变成了区分两个点。

当然这个题还是尽可能写多一点别的的

  1. type=1 我让奇数的猜奇数,偶数的猜偶数。
  2. 如果 \(n\) 是偶数的话,让每个人和对面的人区分,看他们两个之间的字符串是左串大还是右串大。如果>=2个人相同考虑这样必定形成中心对称结构,直接猜对面的即可。
  3. 如果 \(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!\)


胡策部分题解
https://proton-z.github.io/2022/11/01/A-huce/
作者
Imitators
发布于
2022年11月1日
许可协议