Day1
T1
题意：给定 \(n,b\),求 \(2\le k \le b\) 进制下 \(n\) 的各数位上的值之和最小值。
多组询问，\(T\le 10000,n\le 10^9\)。考虑先暴力计算 \(2-1000\) 的进制下最小值，不难发现2进制下答案最大 \(\log_2 n\)，于是在更大的进制下 \(n\) 只有最多三位甚至两位，形如 \(ak^2+bk+c=n,ak+b=n\)，这个你可以在已经有的答案下枚举数位然后解两个方程得到。
T2
题意：给定一棵树，有 \(m\) 条线段以一定覆盖，一个点可以不断走到和其有同一条线段共同覆盖的其他点，求期望在几个位置赋值可以走到所有点。
先考虑链，发现显然。于是直接上树，设 \(f_i\) 表示 \(i\) 子树内全部赋值的期望代价，那么每次转移只需要看 \(i\) 和其儿子 \(v\) 的连边有多大概率被覆盖即容易转移。
线段覆盖可以树上差分。注意概率是0的要特判。
T3
题意：给定有根树，每个点有一个限制 \(f_i\) 表示其子树内必须有正好 \(x\) 种颜色。全局有 \(m\) 种可用。保证 \(f_1=m\)。有一些 \(f_i=-1\)，表示没有限制。
考虑把 \(f_i=-1\) 干掉。显然一个 -1 可以把他所有儿子挂到他父亲上然后把这个点看成 \(f_i=1\)。设 \(dp_u\) 是染色方案。
然后容斥，考虑 \(g_i\) 表示使用最多 \(i\) 种颜色的答案，那么就有
\[g_i = \binom{m}{i} \sum_{son} \binom{i}{f_{son}} \]则
\[dp_u =\sum_{i=max{f_{son}}}^{f_u} (-1)^{f_u-i}g_i \]发现是 \(O(nm)\) 的。
但是不同的 \(f_{son}\) 最多只有 \(\sqrt{n}\) 个，可以合并起来快速幂。毛估估一下复杂度大概 \(O(n^{1.5})\)
T4
你直接把每个位置的 \(r\) 所能覆盖的 \([i-r_i,i-1]\),\([i+1,i+r_i]\) 看成线段覆盖到线段树上，每个节点维护堆存这个东西也方便求最大值，然后每个节点维护原 \(a_i\) 的最大值和线段的最大值，然后每次询问合并即可。堆的性质使之可以懒惰删除，即删除只需要等更新节点的时候发现删掉的就一直pop。注意随时更新答案和堆以免出锅。
problems
Day2
T1
题意：给定长度 \(n\) 的序列，有一种类似双闭二分的查找，目标随机，要求你求出某种策略，使期望查找次数尽可能少，输出期望。当然，有一个阈值 \(m\)，当你的询问次数大于 \(m\) 的时候你会不计算他进期望。换言之，你需要求出最小的查询次数不大于 \(m\) 的查询次数平均数。
注意到你用纯二分去做，答案是 \(\log_2 n\) 级别的。
考虑这个类二分就是二叉树的中序遍历，于是题意变成了构造二叉树。
然后你二分一个答案 \(x\)，对于不大于 \(x\) 的深度，你贪心能塞多少塞多少，塞成满二叉树，然后对于大于 \(x\) 的深度，你塞成一条链，显然这样最优。你判断下这样所有深度不大于 \(m\) 的平均数是否满足答案即可。
T2
转化题意：给定树，边有权，用所有点构造一个权值最大的环，环的权值就是相邻点树上带权距离之和。
不难发现对于一条边，他最多会被两侧子树大小较小的大小*2次经过，经过构造证明容易看出对于每一条边都是这样的。
T3
题意：给定序列 \(a_i\)，其中 \(a_0=a_{n+1}=0\)，\(q\)次询问可以进行 \(x\) 次操作使得某个位置减一，任意时刻不可以小于0，求最小的 \(\sum_{i=0}^n{|a_i-a_{i+1}|}\)。
先离线询问排序。
考虑相同颜色缩成一段，不妨称其为有序三元组 \((l,r,x)\) 表示 \([l,r]\) 这段极长相等连续段长度是 \(x\)，那么显然对于这段，其可以用 \(x\) 的代价使答案减二，知道其和 \(l-1|r+1\) 权值相同。
同时不难发现这玩意只关心左右端点的信息，于是维护一个堆和链表即可。
T4
有两种操作，各 \(n,m\) 个，一个是花费 \(b_i\) 将 \(a_i\) 减一，另一个是花费 \(w_i\) 将 \(a_{x_i}\) 减一，\(a_{l_i,r_i}\) 加一。
首先转化，设 \(f_i\) 是只把 \(i\) 位置减一的最小代价，初始 \(f_i=b_i\)。
容易看出这玩意和最短路像啊，很像啊，于是用 dij 的思维每次取出当前最小的 \(f\) 去更新答案。
发现唯一的小问题在于如何求出某一个 \(f_i\) 固定后会新使得哪些区间覆盖的位置的 \(f\) 全固定了，这个可以经典线段覆盖，将一个操作区间拆成 \(\log\) 段区间放到线段树上，记一下这个区间的个数，然后每次线段树上一段区间全部都固定了就把覆盖的区间的计数器减一，如果减到0了就用这个去更新答案。
更新答案可以树状数组。
最小表示法(?)
分析复杂度：有 \(n\le12\) 的一张无向图，有 \(k\le 10^9\) 种颜色，求出所有本质不同的状态数。
考虑一个点的本质颜色不超过 \(\max{col}+1\)，即前面出现过的最大颜色加一。这样搜一下发现是 \(4\times 10^6\) 级别的。
标签：10.1,le,题意,覆盖,线段,减一,答案,qbxt2022 From： https://www.cnblogs.com/infinities/p/16749033.html