0%



把之前写的部分题的题解发一下,有些补的题没立马写估计是咕咕了。

A

银川原题加强版,给 $n$ 个串 $(n\leq 10^5)$,字符集是 $66$ ,长度不超过 $100$,求对所以的前 $i$ 个串,需要的最少前缀数量,能够满足覆盖到前 $i$ 串的某个前缀,但不能覆盖到后 $n-i$ 个串的任何前缀。保证所有串本身不互为前缀,即一定有答案。 空间 $32MB$。

银川大概是 $256MB$ 还是 $512MB$ 来着,赛场上虽然磕磕绊绊但终于是过了。

但这个内存非常小是怎么做呢?

首先必须领悟,这题把字典树建出来就做完了,不妨假设所有结点刚开始都是白的未染色,加入一个前缀就把一条链染色,只要一个结点的子树全部染了色,那么这个结点子树就只需要 $1$ 的答案,即只需要在加入串时把要选的前缀尽可能上移即可。


存在一种时间换空间的字典树建立方法,普通的字典树,遍历所有的字符能开即开,复杂度是字符数的。但对于这题来说,显然有浪费,很多结点信息我们并不需要,比如不同于其他串的前缀后面的一堆字符,是无效信息。

考虑将串分治建立这棵字典树,在分治过程中。按照当前处理到所有串的第 $len$ 个字符的字典树进行字典序的排序,对于第 $len$ 个字符一样的可以一起递归处理。如果区间的串有一堆一样的前缀也可以一起进行 $len$ 的加。分治到单串显然可以直接结束。

这样复杂度虽然带了排序的 $log$,但分治建树的效率实际上非常的高,这题只需要父亲信息,所以只需开一个 $fa$ 数组即可。


更牛逼的做法甚至可以字典序排序后,对串递归不建树,直接对答案的影响贡献进行差分。

G

$n$ 个人,每人都会等概率的选择一个除了自己以外的人,然后同时开一枪,这一枪的命中率是 $p$ ,求恰好 $k=0,1,\dots,n$ 个人存活下来的概率。

感觉挺神仙的概率题,一般这种恰好的问题,都是转化成至少至多然后容斥的,然后这题还有从集合的角度来看比较好做。

来写一写人能看懂的题解。

理解后感觉非常的妙而简单!


首先设

$f(S)$ 表示只有 $S$ 集合的人恰好都被击中死掉的概率。

$g(S)$ 表示只有 $S$ 子集的人被击中的概率。大概就是个至多的概念。

那么有 $f(S)= \sum _{T \subseteq S}(-1)^{|{S}|-|{T}}g(T)$ 。

考虑 $g(S)$ 的求法,击中落在子集内。

对于这个集合的人,分成两类 $S$ 所包含的和不包含的。每个人的选择都是独立的,选择要么不中,要么中只能击中这个集合的人,于是有下列式子

由于这个问题中,同样大小的集合 $S$ , $g(S)$ 的概率显然一样( $f(S)$ 同理),那么 $f(S)$ 可以继续写成

$g$ 可以直接求出,$f$ 显然是个卷积可求的东西。

最后只需考虑 $f$ 是集合,记得搞上所有大小一样的情况即可求出答案的反面。

J

$n$ 个点凸包,凸包外有 $n$ 个光源,坐标 $(x_i,y_i)$ ,求最少的光源数量能够覆盖凸包的所有边界。

凸包切线+最小环覆盖 $O(nlog_2n)$

已经加入豪华午餐!

1005

>

1012

给一个小写字母串,求所有字符在所有区间出现次数平方的和。

即求 $\sum _{c=97}^{122} \sum _{i=1}^n \sum _{j=i}^n cnt(i,j,c)^2 $

感觉这个问题我已经精通了,然后教了好多人这个怎么做,虽然不知道有没有教会。

考虑不带平方,一次怎么做。

显然可以递推或者说区间转前缀来求得答案。


考虑平方的答案,贡献从 $c^2$ 到 $(c+1)^2$ 发生了什么,答案会多 $2*c+1$,这个 $c$ 就是每种情况的一次项的答案,于是你要对所有情况统计,于是维护 $f_i=\sum c$,而常数也要对所有情况都加上,于是需要 $+i$​​,设 $g_i$​ 为以 $i$ 结尾所有情况下的平方的答案。

那么有若当前字符是, $g_i=g_{i-1}+2*f_{i-1}+i$ 。

不是,则 $g_i=g_{i-1}$。

比赛里枚举字符 $O(26n)$ 就过了。

赛后有优化思路,因为当不是当前你这个字符的时候,其实 $f_i$,$g_i$ 只在该字符出现时发生变化,于是可以一段一段一起算。

$O(n)$ 可过。

A

厕所战神的故事,读题。

逆元签到题

E

判定是否是闰年且是素数

动动脑子发现输出 No 即可。

F

$n \times m $ 的有障碍的网格图,有三种类型的机器人, $type1$ 只能向下, $type2$ 只能向右, $type3$ 可以右下, $q$​ 次询问是否某一种类型的机器人是否能从一个网格图中坐标到另一个坐标。

($1\leq n,m\leq 500$, $q\leq 5*10^5$ )

对于第一和第二类的机器人,我们显然可以直接判定,只要判他们之间是否有障碍即可,前缀和或者暴力都可以搞定。

对于第三类询问,对于每个机器人,判定他能否从一个地方到另一个地方,显然有一个 $dp$ 可行路的方法,但会遍历整个区域。于是我们发现似乎有很多重叠的问题,对于每个问题分别做,显然非常的浪费,不如一起搞。

考虑分治询问,按行或者按列分治,不跨越中间这一行的询问扔到各自的子区间,当前解决所有跨越中间这一行的询问。

可以对上下半区分别维护

$bitsetdpl[N][N]$​ 表示上半区的某个点是否能到中间这一行的某一列。

$bitsetdpr[N][N]$ 表示下半区的某个点是否能通过中间这一行的某一列到达。

转移显然,最后对于一个询问,只需要判定是否能从起点到中间这一行某一列,再到终点。显然就是集合求交的操作。

复杂度 $O(qlog_2n+\frac{nlog_2n*m^2}{64})$​ 。

J

博弈。

给定一棵树,第一个人在 $s$ ,第二个人在 $t$​ ,两个人都想尽可能多的移动,如果朝一个点移动,必须删去所有原来所在位置点的连边。询问最终第一个移动次数 - 第二个人移动次数会是多少。

首先考虑 $s$ 到 $t$ 的一条链,如果一个人决定脱离这条链,一定是往深度最大的点走取,那么他再也不可能回到这条链了,还有一种选择是继续在这条链上走。

于是我们可以预处理第一个人和第二个人在这条链走到哪里答案会是多少,一定是链上步数加上额外能取得最大深度。

由于两个人都要使得自己最大,于是可以对抗搜索。


两个人都会选择最优解来走,一种选择是当前脱离链,那么可以取得当前的答案,另一个人就能在剩下的链中取得他能得到的最大值。

若不脱离,则递归向前一步,这样对抗搜索最优答案。

终止条件是两人位置相交,不合法。


只要线段树或者 $st$ 表来 $RMQ$ 即可。

B

给序列 $a$​ 和 01序列$b$​ ,三种操作

  1. 单点修改 $a_{t1}=t2$
  2. 给 $b$ 的 $[t1,t2]$ 区间加上 $1$
  3. 询问一个区间 $[l,r]$,对于 $a$ 序列,找这样一个下标的集合,先把 $l$ 加入,然后每次在序列中,找下标集合中最大的元素的右边的且在区间内的大于等于该下标元素的第一个数,把他加入集合,如果找不到就结束这个过程。输出这个得到的下标递增集合在 $b$ 序列中的有多少相邻数满足 $b_{p_{i}} \neq b_{p_{i+1}} \mod 2$​​​​​​ 。

线段树经典 $log \space update$ 问题?

意思就是说除了普通的线段树区间操作,所要维护的信息还需要进一步递归的继续获得。


前置题目 P4198楼房重建

发现这两题非常的类似,都有对一个序列递增的要求,这题唯一的不同就是还需要维护一个对应下标的 b 序列切换的答案。

设一个区间中满足题目要求的答案是 $ans$​, 我们可以在线段树上用递归来求。

考虑一个区间 $[l,r]$​ 的答案,他的左区间是 $[l,mid]$​​,那么左区间的所有答案一定必须成为当前区间的答案,只需要考虑右区间在受限于左区间的最后一个取的东西,也就是最大值来继续取。

对于右区间,显然的剪枝是若这个区间最大值已经更小了,就不可能有扩展的答案了。

然后继续分治递归。

  1. 若右区间的左区间的最大值能继续延申,那么递归左区间,同时这个左区间的最大值一定能被取得,可以利用已有信息直接算出把右区间的右区间的贡献。

  2. 若右区间的左区间不能延,只需要递归右区间即可。

  3. 在叶子结点,按照题目条件判断即可。

然后就做完了。

对于修改,只需正常的线段树修改操作。

对于询问,因为每次都是重新取,可以先取个左界,再把线段树上剩余结点拿出来求一遍。

线段树上一次修改询问最多 $log$ 个结点,信息从下合并上来最多递归 $log$ 层。

复杂度 $O(nlog_2n^2)$​。​

E

$n$ 堆石子,两人玩类似 $nim$ 的博弈,每次取的数可以是 $mu[x]=1$ 的数或者是给定的至多 $5$ 种数。每堆石子的范围是介于 $[l_i,r_i]$的数,需要输出所有的 $\prod r_i-l_i+1$​ 种方案中,有多少种方案先手必胜。

$n<=10^6$, $1 \leq l_i \leq r_i \leq 10^5$​。

首先,可以考虑打表打一下 $sg$ 。

发现 $sg$​ 没什么规律,且值域不大。因为取的数 $mu[x]=1$​ 其实也没什么规律,出题人说最多值域到 $230$ 。

如果能打表出到这个类似的数字,考虑优化转移求 sg 的过程。这个可以用bitset简单的做到。

设 $trans[i][j]$ 表示 $j$ 是否存在 $sg$ 值为 $i$ 的出边,这样枚举 $j$ 就能方便的求得他的 $sg$ ,且更新对应$trans[sg[j]]$ 数组 ,所有的别的数都可以通过取 $j$ 来得到 $sg[j]$ 。

1
2
3
4
5
trans[0]=pick;
for(int i=1;i<=100000;++i) {
while(trans[sg[i]][i]) ++sg[i];
trans[sg[i]]|=pick<<i;
}

这样复杂度是 $O(\frac{n^2}{64})$​的。


剩下的部分,就相当于要求所有异或和不为 $0$ 的方案,这个按照套路可以用 $fwt$ 来求,但两个序列的异或情况好求, $n$​ 个序列无法一一做变换最后再乘起来。

考虑所做的数都是一些连续的数,可以用前缀和来求,考虑直接求出 $fwt$ 异或变换后数组的前缀和,这样对于每个 $[l_i,r_i]$​ 直接乘起来就是对的,因为是 $fwt$ 异或变换后的数组了。

然后这里还需要知道 $fwt$​ 异或变换在干嘛,不然也不能做

其中 $C_1$​ 表示 $i\&j$​ 奇偶性为 $0$​ , $C_2$​ 表示 $i\&j$​ 奇偶性为 $1$​​​​,如果当前下标与变换后下标 $i$​ 与运算是偶数个 $1$​ 则加,否则减。

于是就可以在 $O(100000*256)$​ 算出 $sg$​ 值变换后的前缀和,最后只需要 $fwt$ 乘起来即可。

复杂度 $O(\frac{n^2}{64}+(n+100000)*256)$​

F

>
>
>

J

$n$​个点, $m$​ 条边的有向图,求 $floyd$​​ 算法 和 三重循环最后枚举中间点的算法最短路 $dis$​ 数组有多少对依然正确。

K

给一个序列 $a$​​ ,每次可以任选一个区间进行区间 $\mod k$​​ 意义下的 $+1$ 或者 $-1$,每次询问一个区间,最少需要多少次将所有数都变成 $0$。

1004

给一个长为 $n$ 的串 $S$ ,定义 $k$ 匹配是长度一样的串容许有 $k$ 位不一样,定义 $t$ 分割是以 $t$​ 位置分割成 $S[1,t-1]$ 和 $S[t,n]$,需要求对于所有 $t$ 分割有多少个非空子串满足 $k$ 匹配。

1009

给一个序列 $a$ ,每个数的值域在 $0 \leq a_i \leq 10^6$ 。对于所有区间,求存在一个数比所有别的数都要多的区间数。

区间严格众数数量原题。P4062 [Code+#1]Yazid 的新生舞会

目前只会到一个 $nlog_2n$ 的观察性质树状数组二阶差分的三阶前缀和做法。

考虑对每个数 $w$ 分别维护每个数作为区间众数出现的区间数对答案的贡献。

那么对于一个区间 $[l+1,r]$​​​ ,记 $S_i$​​​ 表示前 $i$​​ 个数 $w$​​​ 出现次数。

他能成为答案则 $S_r - S_l > \frac{r - l}{2}$​​​​​ 。

化简得 $2S_r - r > 2S_{l} - l$​​

设 $P_i=2S_i-i$ ,那么对于一个 $P_i$ 只需统计前面有多少个比他小的数,就是这个点作为右区间的答案。

这样的话,就有一个 $nwlog_2n$​​ 的树状数组的暴力…


但观察一些性质,对于一个 $w$​ 的相邻两个位置, $P_i$​ 的值是逐渐需要 $-1$​ 的。

而总共的间隙,总段数是 $O(n)$ 的。

如果我们能一次处理出来一段的答案,并算好贡献,那么复杂度就是对的。

考虑如何维护序列,询问需要的操作是树状数组里内容的前缀和,具体来说,不妨设 $G_i=ask(P_i)$ ,那么询问显然是连续的一段,所以得到答案需要维护原序列的更高一维的前缀和。

但由于自己段里 $P_i$​ 递减,不需要考虑影响,只要考虑前面段的影响即可。于是可以先询问,后加贡献。

而影响贡献的操作,是区间加上递减的数,这个可以用二阶差分转化为单点修改。这样的话,询问就是需要做三阶的前缀和,就能得到准确的答案。


第一次写三阶前缀和,大概就是

交换和号,就能推出

$n$ 阶前缀和可以用 $n$ 个数组来维护。

单点修改的时候,同时维护 $d_k$ , $d_kk$ ,$d_kk^2$ 的变化。

询问点 $x$ 的前缀和时,乘上各个对应的系数。

那么这道题就做完了。


据说还有线性的做法…

C

$n$ 个点的无向完全图,每次删除一个三元环,使得边数 $\leq n$ ,输出方案。

构造,不会。

论文题还是什么?

输出所有满足 $i+j+k \mod n = 0$ ,且 $1 \leq i < j < k \leq n$​ 的三元组即可。

D

你是一个赌怪!每次有 $\frac{a_i}{\sum_{j=0}^{n-1}a_j}$​​ 的概率取到一个数,赌怪是贪心的,当你取的数 $y$​ 和你当前的数 $x$​ 满足 $x\oplus y > x$​ 则取,否则不动​,求最终达到全集 $n-1$ 的所需要的期望次数。

($n\leq 2^{16}$ 且必定是2的次幂)

定义 $E(x)$ 表示当前状态是 $x$ ,到终态还需要的期望次数。

显然有转移

不妨记 $\sum _{y \oplus x>x}p_y =S_x$​,这个东西可以贪心按位求出来。

那么有

对 $x$ 有贡献的部分拆成它本身和更加大的,于是可以在 cdq分治 过程过先处理大的出来,然后考虑大的对小的贡献,就有了一个分治 $fwt$ 的做法。

考虑分治$fwt$ 过程,对于分开来的两部分,他们的很多高位一定一样的,那么区间长度,受影响的值域只有 $2^{len}$ ,于是保证长度的逐渐增长,复杂度才能达到 $O(nlog_2nlog_2n)$ 。

H

有一个小兔子会按 $d$ 的步长在平面内跳,但平面内有一些矩形内会有捕兽夹,求一个起始坐标 $(x_0+0.5,y_0+0.5)$​ 使得小兔子能自由的跳跃。不存在输出 $-1$ 。

经典思路,小兔子跳去适配矩形不太好,考虑让矩形跳。矩形按 $d$ 跳跃最终都到达到 $(0,0)$ 到 $(d,d)$ 之内的,且最多会拆成 $4$​​ 个矩形。

坐标是位于中心的,不妨把矩形右区间 $-1$​ 转化为闭区间。

我们要求一个合法的点,就是求一个未被占据的点,这个可以按一维扫描线,一维线段树来维护寻找未被覆盖的一点。

1003

一个01串 $s$ 可以被重写成 $kp+p’$,其中 $p’$ 是 $s$ 的一个可以为空的前缀,给定 $n$ ,求所有长度为 $n$ 的 $01$ 串的重写后最大的 $k$​ 的和。

1004

给每个字符一个权值 $c_i$​​ ,定义串的价值是他所有字符的权值和,求一个串所有的本质不同子串第 $k$​​​​ 小的权值是多少?不存在输出 $-1$ 。

($1 \leq c_\alpha\leq 100,1\leq n \leq 10^5,1 \leq k\leq \frac{n(n+1)}{2}$​​​)

子串是后缀的前缀。

后缀数组的 $height$ 可以去重解决本质不同子串的问题,并找到相应的位置。

找第 $k$ 经典套路,二分答案,只需 $check$​ 比这个值小的出现次数即可。

因为一个后缀的前缀权值是递增的,可以二分找右端点数这个后缀的本质不同的子串有几个小于 $check$ 的值。

复杂度 $O(nlog_2wlog_2n)$

双指针处理一下正常顺序下,每个点开始的右端点,考虑先得到不管本质不同的子串有几个的答案,在按 $sa_i$​​ 顺序遍历减去重复的子串符合条件的个数即可。

复杂度 $O(nlog_2w)$

1005

$n$​ 个数的序列, $m$​ 次询问在 $[l,r]$​ 区间等概率选子区间 $[x,y]$​ ,即 $(1 \leq l \leq x \leq y \leq r \leq n)$​​ 求子区间 $\frac{max+min}{2}$​ 的期望。

$(1 \leq n,m \leq 2 \times 10^5)$

关键在询问,不然单调栈算每个数贡献直接做完了。

具体来说,对于一个询问,只需要求每个数作为最大值出现的次数和最小值出现的次数就能得到分子。

多次询问怎么解决,发现是有原题的。

不妨先只考虑怎么数,一个区间子区间内每个数作为最小值出现次数的和。


对于一个区间,已知他的最小值所在位置是 $p$,那么这个点对答案的贡献是 $a_p(r-p+1)(p-l+1)$ ,我们考虑根据这个最小值,把答案切成两个子区间 $[l,p-1]$ ,$[p+1,r]$ 在求这两个子区间内的答案。

先只考虑对右区间求解


考虑设这样一个函数

$f_{l,r}$表示说所有恰好以 $r$ 为右端点,左端点是 $l,l+1…,r$ 的区间的答案。

转移显然是从上一个比 $a_r$ 小的地方转移过来,中间的一系列左端点到 $r$ 都是以 $a_r$ 为最小值的,记 $pre_i$ 表示上一个比 $a_i$​ 小的位置

发现这个第一维 $l$​​ 似乎根本没必要,只要能一直找到前缀更小的位置的转移点就可以直接做。

就可以写成

那么一定存在一个位置点 $x$​ , $pre_x=p$​ ,这个 $p$​ 就是我们前面求的最小值的位置,那么所有恰好以 $r$​ 为右端点,左端点是 $p+1…r$​ 的区间的答案就是 $f_r-f_p$​​​。

是不是很对啊,​​​这么做对的前提是 $p$ 一定是 $r$​​ 的转移点才对。

那么考虑对右边的区间 $[p+1,r]$

对于 $r$​ 来说,所有恰好以 $r$​ 为右端点,左端点是 $p+1…,r$​ 的区间的答案是 $f_r-f_p$​​ 。

对于 $r-1$​​​​ 来说,所有恰好以 $r-1$​​​​ 为右端点,左端点是 $p+1…,r-1$​​​​ 的区间的答案是 $f_{r-1}-f_p$​​​​ 。

对于 $p+1$​​​​​​​ 来说,所有恰好以 $p+1$​​​​​​​ 为右端点,左端点是 $p+1…p+1$​​​​​​​ 的区间的答案是 $f_{p+1}-f_p$​​​​​​ ​。

显然可以前缀和优化,记 $g_i=\sum_{j=1}^{i}f_i$​ 。

那么所有右边区间 $[p+1,r]$​​​ 的答案为 $g_r-g_p-f_p*(r-p)$​​ 。


左边区间也可以类似处理,要维护一个后缀的类似的数组,因为此时 $p$ 在右侧。

这题这样对最大值和最小值分别搞一次,就做完了。

1003

公式有点烂,$mathjax$​​ 渲染出来的和 我本地的 typora​ 出来不一样,不想修了啊 。T_T

似乎修好了, \ast 写成 * 的问题。

字符集为 $|S|= \lbrace 0,1…9,\ast \rbrace$​​​​​​​​​ ,其中 $\ast$​​ 为通配符,求两个串 $s_1$​​,$s_2$​​ 长分别为 $n$​​ ,$m$​​($n\geq m$​​) 的字符串匹配情况,具体来说是第一个串的一个长度为 $m$​​ 的子串和第二串的整串去匹配,容许有 $k$​​ 个字符不一样,对所有 $k \in [0,m]$​​​​​​​​ 输出能匹配的方案个数。

卷积求带通配符的串匹配情况,还好比赛里做出来了。

题目主要特点是字符集小,且允许 $k$​​ 个地方不一样,那我们必须得到每个位置结尾前缀的子串有几个字符一样或者不一样,这样就对所有 $k$​ 输出答案了。

无法通过构造函数来推出这一点,因为字符的差值固定,不太好做。

于是只能枚举字符来做。

$Solution_1$:

考虑一种字符 $c$​​

对第一个串构造 $A[i]=(s1[i]==c)$​​

对第二个串构造 $B[i]=(s2[i]==c \lor s2[i]==*)$​​​

此处 $s2$​ 当然已经按照套路翻转过了。

这样就得到了 $s_1$​ 所有位置这个字符和 $s_2$ 匹配情况,这样做字符集次,最后只需要加上 $s_1$每个位置前缀长 $m$ 的 $*$​​​​​ 即可,不难发现这样能得出所有结尾位置匹配上的情况了。$O(10nlog_2n)$​

$Solution_2$​:

题解的做法,枚举完字符,第二串中的通配符也不管,这样每个位置最后答案需要额外

$+$​ (第二串中 $\ast$​ ) $+$​ (第一串中一段的 $\ast$ )$-$​ (共用也就是匹配上的 $\ast$​ )

不难发现这样也是正确的,简单容斥了一下,多算的去掉。

$O(11nlog_2n)$​

md,比赛里想了好久才想到一种正确的做法,脑子好慢啊

1004

给定 $n$​​​ 条直线, $Alice$​​​ 选 $k$​​​ 条出来, $Bob$​​ 会画一条直线,前者想让后者画的直线于她选的交点尽可能多,后者想让尽可能少,对所有 $k \in [1,n]$​​ 输出交点数。

分析:

首先, $n$ 条不平行直线,Bob只能得到 $n-1$ 的答案,只能画一条和某一条直线平行的线来做到。

这样,我们可以推得一点就是若存在共线的直线, $Bob$​​​​ 一定是画一条与最多平行直线平行的一条。

而反过来 $Alice$ 一定想让最大平行数尽可能少,于是缓慢递增,统计一个每种次数出现的后缀和就能做到。

1009

$n*n$​​ 网格图,从 $(1,1)$​ 走到 $(n,n)$​,只能走右或下,经过某点能获得 $a_{i,j}$​的钻石,并使得钻石价值提升 $b_{i,j}$​​​ ,到终点最后会统一售卖出去,求能获得的最大价值,保证数据随机。 $(n \leq 100)$

数据随机又是乱搞题,但还是必须基于一定策略。

设 $f[i][j][k]$ 表示达到 $(i,j)$ 且身上有 $k$ 个钻石能获得的最大单价。

到达一个点,对于已经有 $a$​​​​, $b$​​​​ 个钻石的状态,若 $(a<b) \land f[i][j][a]<=f[i][j][b]$​​ ,那么前者不可能成为答案,比你多且比你有钱怎么能成为答案呢。

故只需维护一个对钻石数量的单价下降序列即可,类似单调栈。

数据随机是保证在 $n=100$​ ,这样的状态数峰值在 千级别。

复杂度 $O(n^2*state)$​

1010

$n$ 个点 $m$ 条边的无向图,每条边有两种费用 $d_i$, $c_i$,$d_i\leq c_i$,求恰好使用 $k$​ 次便宜边的最小生成树。$(n\leq1000,m\leq200000,1\leq d_i \leq c_i \leq 1000)$

题面如果这么被读出来了,就是恰好使用 $k$ 条白边的最小生成树,是个显然的 $wqs$ 二分问题。

直接做边数依然过大,那显然最后使用的边只会是在原来纯用黑边或白边的最小生成树中。这样边数也是 $O(n)$ 级别了。

由于值域很小,且要对所有 $k$ 输出答案,故可以不二分,对所有 $-1000$ 到 $1000$ 的附加权参数预处理出最终 $MST$ 权值 和 用的白边的次数。

询问直接找即可。

复杂度 $O(mlog_2m+nc)$​​​ 。

当然直接对每个 $k$ 二分做应该也是可以的。

B

$[1,n]$​ 的数,每个数以 $p_i$​​ 概率生成。

重复下列操作

  1. 产生一个随机数。

  2. if 随机数大于等于之前所有数,$goto \space 1$, else $goto \space 3$

  3. 如果产生了 $x$​ 个数,获得 $x^2$​ 的分数,停下。

求期望分数。

$Solution$​​​​:常用套路,因为要求平方。

而 $E((X+1)^2)=E(X)^2+2*E(X)+1$​​​ ,其递增不线性,故要分别维护一次项和平方项的期望。

设 $f_i$ 表示当前取得的最大数是 $i$​​ ,还能进行的操作轮数的期望。

设 $g_i$​ 表示当前取得的最大数是 $i$​​ ,还能进行的操作轮数的期望的平方。

转移就是枚举所有的后继,相应的概率乘上能带来的收益即可。

整理一下可以分离一下 $f_i$​ , $g_i$ 系数可以得到

这样就可以倒推得到所有的 $f$​ ,$g$​​ 。

注意求出的是还能进行的操作轮数的期望,那么实际答案还需加上取到这个数的一次,故对每个 $i$​ 的答案是 $g_i+2*f_i+1$​​,乘上对应的概率就可以得到答案。

发现 $O(n)$ 维护后缀和即可做完。

E

题意: $n$ 个结点的树,每个点权介于一定范围 $[l_i,r_i]$ ,边权是点权的异或值,给定边权,求有多少种可能的点权序列。

分析:

发现已知一个点的值 $a$​ ,比如说 $w_1=a$,那么你可以唯一确定得到所有 $w_ i$​ 的值。

于是题目就变成了,求 $n$ 个等式限制下 $a$ 的取值个数。

$l_i \leq w_i \oplus a \leq r_i$​​

这 $n$ 个等式下的所有区间交长度就是我们的答案,即满足所有限制条件的 $a$ 。

考虑将所有值域放在线段树上,求 $a$ 的合法取值的区间个数。

这个可以类似之前几天题目来做,在动态开点的线段树上依次判断区间。

比如对于一个式子 $w_i \oplus a \leq r_i$​​​,最多能确定线段树上递归 $30$​​​ 次,并能判断一些不合法的 $a$​ 的取值区间,线段树和字典树差不多。

最后递归求线段树上依然合法的区间即可。

G

给 $n$ ,$k$ ,$D$​​​,求所有满足

  1. $\forall i \in[1,n],a_i \geq 0$
  2. $\sum _{i=1}^n a_i=D$

的 $a_i$​序列的$\frac{D!} {\prod_{i=1}^n (a_i+k)!} $​​。

$(n,k \leq 50,D\leq 10^8)$

考虑构造

$f(x)=\frac{1}{k!}x^0+\frac{1}{(k+1)!}x^1+\frac{1}{(k+2)!}x^2+…$

显然题目就是要求 $(f(x))^n$ 的$x^D$ 次项系数,再乘上 $fac(D)$ 即可。

$D$ 值域较大,但只需要一个,可以分段打表。

发现 $f(x)*x^k = e^x - (1+\frac{1}{1!}x^1+ … \frac{1}{(k-1)!} x^{k-1} )$。

设 $g(x)=1+\frac{1}{1!}x^1+ … \frac{1}{(k-1)!} x^{k-1}$

$(f(x))^n= (\frac{e^x-g(x)}{x^k})^n$

显然只需求分子的 $D+k*n$ 项系数。

$(e^x-g(x))^n=\sum _{i=0}^n (-1)^i C_n^i (e^x)^{n-i}* g(x)^i$

对每个 $i$ ,枚举 $g(x)$ 的 $x$ ,容易算得对应的系数。

复杂度大概每次乘一个 $k$ 次多项式,最高指数到 $k*n$ 。

估摸着复杂度上界在 $O(n^2k+n^2k*log_2(kn))$ 。

1001

签到

1002

有向树上路径加上从 $1$ 开始逐渐递增 $1$ 的平方数,即每个点分别加上$1^2,2^2,3^2…$,询问单点值。

这种题首先可以考虑序列做法,然后把序列搬到树上路径只需树剖就可以解决。

对于一个序列区间加上平方数,既然是区间操作,肯定用线段树。

常见的询问平方和,一般是用 $pushup$ 来做到,一般是维护 $\sum x^2$,$\sum x$​,在考虑其他修改操作的影响,来继续维护这些值,就能做到。

而这里是区间加平方数的操作,是对于修改有递增的情况,这个可以用 $pushdown$​来维护。

考虑给区间 $[l,r]$​​ 加递增的平方值 $v^2,(v+1)^2…$​​,先考虑只给区间的左端点加上一个确切的平方值 $v^2$​​,那么考虑这个区间的其他点该加上啥?

应该是 $(v+len)^2$​ , $len$ 表示里左端点的距离。

展开后发现只需维护 $v^2$​,$2*v$​, $1$​,在乘上对应的 $len$​ 部分即可,这个可以在线段树中的 $pushdown$​​​​ 里将所有点的递增影响都搞定。

有向的话,依然让区间递增是 $1$​ ,考虑一个初值给一个负数即可。

不难发现这样做的正确性,虽然我也是第一次见。

搬到树上,只需维护一下当前要处理加上的 $[l,r]$​​​的平方值,按树剖划分的重链进行序列操作来搞即可。

1003

$n$​ 个点 $m$​ 条边的无向图,两人一人在 $x$​ 点,一个人在 $y$​ 点,都想到 $z$​​​​ 点,每一轮中两人先后移动,在某轮结束后,如果一人到了但另一人没到就谁赢,都没到或者都到不了算平局。合法 $move$​​ 是不动或者走邻边,除了起点和终点以外不能同时存在超过两个人。

分析:

$n<=1000$ 允许 $n^2$ 做法。

$Case_1$:首先,谁离 $z$ 近谁一定赢,另一个人因为距离最远,无法破坏更近的人先到。

$Case_2$​:距离一样的时候,因为最短路可能有多条,点会重,有不能共点的性质,比较麻烦,考虑一个显然的 $dp[x][y][0/1]$​ 表示第一个人在 $x$​ ,第二个人在 $y$​ ,轮到谁移动,两个人都想先到,所以转移一定枚举到 $z$​​​ 最短路上的边进行转移。只需记忆化搜索一下即可。

证明:如果你不走到 $z$ 的最短路,那么另一人走了,转为$Case_1$​你就莓樂。

因为目的是最快到 $z$ , $bfs$ 预处理从 $z$​​ 出发所有走最短路的边即可。

每个状态,每个转移只会遍历到一次,故复杂度$O(n^2+m)$​。

1004

一个序列 $c_i$ $(1 \leq c_i \leq n)$,每次询问一个区间 $[l,r]$ 有多少不同的 $c_i$ 满足 $c_i\bigoplus a \leq b$ 。

发现是前面几天两个题的结合。

询问 $c_i\bigoplus a \leq b$ ,属于是经典题,很容易可以在字典树上维护信息贪心做到。

询问区间不同数个数,杭电1也有题,又属于是经典题了,这个可以用莫队离线做。

两者结合在一起,很显然,我们有一个维护字典树的莫队离线做法。维护数出现的次数在字典树上修改,查询在对应的一棵区间的字典树上找答案即可。这样复杂度上界是 $O(n \sqrt n log_2n+qlog_2n)$的。因为莫队的修改,可能会让数在字典树上频繁插删。(只要你不像我傻逼一样写,在字典树上维护 $cnt$ ,$2s$ 是能卡过的)

实际上,在字典树上找数,其实对应的是一个连续的区间,我们可以对值域分块。这样修改很简单,不需要搞字典树,只需要维护块的变换即可。而查询类似在字典树上,按位走,查询连续的一块区间,虽然看起来一次询问是 $O(\sqrt n)$的,对一个询问 $log$ 位次,但实际上询问的区间长度是 $2^k$ 不断缩小的。似乎可以除掉一个 $log$ 。单次总共询问的区间长度是 $n$ 级别的,故是个 $\sqrt n$ ?

最终复杂度是 $O(n\sqrt n + q \sqrt n)$ 的。

1005

签到

1006

1007

每个点有 $a_i,b_i$​,维护下列操作

  1. 区间给 $a_i$或 $b_i$ 加 $x$
  2. 区间 a 变 $3a+2b$, b变 $3a-2b$
  3. 区间交换 $a,b$
  4. 求 $\sum_l^r a_i \cdot b_i$

有个显然的线段树维护 $6$​ 阶矩阵,我冲了,但我 T 了。

维护5阶似乎比赛可过,正确做法是只需维护变换的两阶,剩下的可以算出来?

没学(

1008

简单dp一下即可。

1010

给一个序列 $b_x = ax \mod p$ $ (1 <= x <= p-1)$。求这个序列逆序对的奇偶性。

8会,题解抽象,经 jly 讲解懂了一点。

显然 $b$​ 序列 是一个长度为 $p-1$​ 的排列。

设一个排列 $\pi$,第 $i$ 项是 $\pi_i$ ,设逆序对数为 $n$, 设他的奇偶性 $sgn(\pi)=(-1)^n$​

意思就是说你可以枚举排列的值,和排列的下标情况,如果他是逆序的,就会贡献一个 $-1$ ,否则是 $1$ ,这就是逆序对的所有情况,一个逆序对会贡献一个 $-1$​。

化简式子可以直接得到答案。

1009

1011

给长为 $n$​ 的数组 $A$​ , $B$​ ,定义 $C_k=max{A_iB_j},(i\&j\geq k)$​,求 $\sum _{i=0}^{n-1}C_i$​

假设你要求一个二进制状态 $k$ 的答案。

那么对于 $k$ 的超集 $i$ ,超集就是所有的 $ k\&i=k $ 的 $i$,他的超集状态 $\&$ 起来一定能够超过他。对于一个 $k$ ,我们类似 $sosdp$, 可以维护出他的超集 $max$ 和 $min$ ,那么这些一定可以成为当前的答案。

但还有一些不是他的超集的状态,但能 通过 $\&$ 出来比他大的数,那么可以对更大的 $k$ ,做一样的事情,于是记录答案的后缀 $max$ 即可。

1012

签到

我居然因为 $s.size()$ 返回的是无符号数,减到负数会烂导致wa了一发。