2021/4/16

T1:一个圆上有 $3n$ 个点,$n$ 种颜色的点各有恰好三个。
定义一种合法的画圆弧的方案满足:

  • $n$ 条圆弧的两个端点颜色相同,且不过第三个同色点。
  • $n$ 条圆弧互不相交。

求方案数对 $998244353$ 取模。

$n\leq 2*10^5$。

枚举第一种颜色圆弧的连法,剩下的就是序列上的问题,$O(n)$ dp即可。


T2:求有多少个正整数 $x$ 满足:

$\sum_{i=0}^{n-1}c_i^{}x^{a_i}\mod \sum_{i=0}^{m-1}x_i=0$。

$|c_i|=1,0\leq a_i\leq10^9,n\leq10^5$。

对于 $x=1$ 特判。

其他情况考虑同时乘 $(x-1)$,则 $f(x)·(x-1)\mod (x^m-1)=0$。

考虑怎么 check 一个 x 是否合法。

我们把 $f(x)·(x-1)$ 看作一个 $m$ 位的 $x$ 进制数给它进位,如果最后得到的数每一位都是 $x-1,1-x,0$ 那么显然可行。

而 $x$ 只需要在 $[2,\max\{|a_i|+1\}]$ 里面选择即可,级别是 $O(n)$ 的。

check 的话每次进位会让 $|\sum a_i|$ 减少 $x-1$ ,直到 $0$ 。初始值是 $O(n)$ 级别的,所以总进位次数就是 $O(n\log n)$。

2021/4/17

T1: $n$ 种砖块,长度分别为 $1$ ~ $n$,长度为 $i$ 的砖块有 $a_i$ 块。

两人进行游戏,每次执行下面两个操作之一:

  • 选择一种长度的砖块,如果数量<长度,那就消除一块,否则消除的块数等同于砖块的长度。
  • 选择一块长度为 $l$ 的砖,把它拆成两块长度分别为 $l_1,l_2$ 的砖,满足 $l_1+l_2=l$,并且 $l_1$ 和 $l_2$ 至少要有一个是奇数。

不能操作者输。求先手是否必胜。

当只有奇数位置上有砖块的时候,胜负与奇数位置上的砖块的长度和的奇偶性有关。

当一个人选择去消除奇数位置上的砖块时,总和的奇偶性改变了,另一个人只要也选择消除砖块就可以让奇偶性翻转回来。

否则如果选择去拆砖块,另一个人只需要把拆出来的偶数砖块消除掉也能让奇偶性不变。

最后显然没砖块时后手必胜,即长度和是偶数时后手必胜。

加入偶数位置上的砖块之后,我们发现拆砖块只能把它拆成两个奇数长度的砖块,对奇数位置的胜负没有影响。所以这个操作等价于消除一个偶数长度砖块。

于是奇偶分开考虑。由于一个偶数位置上的操作不会影响到其它偶数位置的游戏,所以把每个偶数位置上的游戏独立出来看。

设这个位置上的长度是 x,数量是 n。

  • 若 $n\mod (x+1)\equiv0\pmod 2$,则 $SG$ 值为 $0$。
  • 若 $n\mod (x+1)\equiv1\pmod 2$,则 $SG$ 值为 $1$。
  • 若 $n\equiv x\pmod{x+1}$,则 $SG$ 值为 $2$。

对 $x+1$ 取模的原因是,无论对方选择消除 $1$ 个还是 $x$ 个,我都能转换到消除 $x+1$ 个时的状态。

于是把每个偶数位置上的游戏和奇数位置上的游戏的 $SG$ 值异或起来就可以了。

T3:求 $\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n \varphi(ij)\mu(ik)\sigma^0(jk)$,$\sigma^0$ 是约数个数。$n\leq 5*10^4$。

$\varphi(ij)=\frac{\varphi(i)\varphi(j)(i,j)}{\varphi((i,j))}$

$\mu(ik)=\mu(i)\mu(k)[(i,k)=1]$

$d(jk)=\sum_{x|j}\sum_{y|k}[(x,y)=1]$

推一波柿子之后得到

$(i,j)$ 表示 $\gcd(i,j)$,$[i,j]$ 表示 $\text{lcm}(i,j)$。

$$ ans=\sum_x\sum_d\sum_wF(x)\mu(d)\mu(w)A([x,d])B_2(x,w)C_2(d,w) $$

其中:

$$ \begin{aligned} F(x)=\sum_{p|x}\frac{p}{\varphi(p)}\mu(\frac{x}{p})\\A(x)=\sum_{x|i}\mu(i)\varphi(i)\\B(x)=\sum_{x|i}\varphi(i)\\C(x)=\sum_{x|i}\mu(i)\\ B_2(x,w)=\sum_{w|y}B([x,y])\\ C_2(d,w)=\sum_{w|z}C([z,d]) \end{aligned} $$

$F,A,B,C$ 暴力预处理,$B_2,C_2$ 和枚举 $x,d,w$ 的部分在图上跑。

在一张图上把 $\text{lcm}(i,j)\leq n$ 的 $(i,j)$ 连一条有向边,方向是从度数小的指向度数大的(这样会比反过来快)。

这样的边并不会太多,只有 $3.5e5$ 的级别。

然后就可以暴力算 $B_2,C_2$ 并挂在边上,然后跑三元环计数的时候统计答案。

时间复杂度 $\mathcal O(m\sqrt m)$ ,$m$ 是边数,时间复杂度分析见 SDOI2018旧试题。

CODE

2021/4/19

T1:对于一个 $01$ 串 $S$,定义它的合法压缩如下:

  • $S$ 是 $S$ 的合法压缩。
  • $S$ 合法压缩的合法压缩是 $S$ 的合法压缩。
  • 若 $A,B$ 是 $S,T$ 的合法压缩,则 $A+B$ 是 $S+T$ 的合法压缩。
  • $(A\times k)$ 是 $A+A+...+A(A\times k,k≥2)$ 的合法压缩。

求 $S$ 的所有子集的合法压缩数的总和。

先不考虑子集,考虑区间 dp。

f[l][r] 为区间 $\rm[l,r]$ 压缩的方案数,g[l][r] 表示区间 $\rm[l,r]$ 压缩成一个整体(只有单个字符或形如 $(A)\times k$)的方案数。

$f_{l,r}=\sum_{k=l}^{r-1}g_{l,k}f_{k+1,r}$

$g_{l,r}=\sum_d[d\text{是[l,r]的循环节}]f_{l,l+d-1}$

于是把状态改为一个串,用map来存,就过了。

时间复杂度上界有点大,但是跑不满。

T2:求 $\sum_{i|n}\sum_{d_1|i}\sum_{d_2|d_1}\mu(d_1)\mu(d_2)f_{d_2}$。

$n=\prod_{i=1}^w p_i^{a_i}$,$w\leq17,x,y,a_i,p_i\leq 10^9,p_i\in P$。

其中 $f_0=f_1=1$

$f_i=xf_{i-1}+yf_{i-2}(i≥2)$

由于 $\mu$ 的特殊,设 $G(S)=\prod_{p_i\in S}a_i$。

然后交换一波枚举顺序就可以把柿子改写成$\sum_{S\in n}G(S)f_S$,$S$ 是枚举的质因子集合。

具体步骤:(以下的集合指的是枚举的质因子集合),现在的 $n=\prod_{i=1}^w p_i$

$$ \begin{aligned} ans&=\sum_{S\in n}G(S)\sum_{S_1\in S}(-1)^{|S_1|}\sum_{S_2\in S_1}(-1)^{|S_2|}f_{S_2}\\ &=\sum_{S\in n}G(S)\sum_{S_2\in S}(-1)^{|S_2|}f_{S_2}\sum_{S_1\in S}[S_2\in S_1](-1)^{|S_1|}\\ &\text{枚举$S_3=S_1-S_2$}\\ &=\sum_{S\in n}G(S)\sum_{S_2\in S}f_{S_2}\sum_{S_3\in S-S_2}(-1)^{|S_3|}\\ &=\sum_{S\in n}G(S)\sum_{S_2\in S}f_{S_2}[S_2=S]\\ &=\sum_{S\in n}G(S)f_S \end{aligned} $$

然后 dfs 一波就能过了。时间复杂度 $O(2^w*w*\log p*2^3)$。

CODE

T3:给出一个长度为 $n$ 的字符串 $S$,字符集为 $\text{{A,C,G,T}}$,满足 $A,G$ 只能接 $A,C$;$C,T$ 只能接 $G,T$。

求所有长度为 $n$,每个字符的数量恰好与 $S$ 相同的满足要求的字符串中,$S$ 的排名。

考虑把四个字符分别看做 $00,01,10,11$,字典序不会发生改变,并且恰好满足题意。

于是就枚举前面若干位和 $S$ 相同,钦定一个位置比 $S$ 小,后面的按规则计数即可。

计数的过程考虑算出有多少以及多少 $0,1$,然后组合计数即可。

2021/4/20

T1:初始一棵只包含一个节点 $0$ 的树 $T_0$,之后 $m$ 棵树由一个五元组 $(x,y,u,v,w)$ 生成,表示把 $T_x$ 中的 $u$ 节点和 $T_y$ 中的 $v$ 节点用一条权为 $w$ 的边连起来,$T_y$ 中的点编号要加上 $sz_{T_x}$。

求每次生成新树的 $\sum_{i=0}^{sz-1}\sum_{j=i+1}^{sz-1}dis(i,j)$。

$m\leq300,sz\leq2*10^{18}$,保证数据合法。

考虑 $ans_i=ans_x+ans_y+sz_x*sz_y*w+sz_x*f(y,v)+sz_x*f(x,u)$,其中 $f(x,u)=\sum_{i=0}^{sz_x}dis(x,u,i)$,$dis(i,j,k)$ 表示 $i$ 树中 $j,k$ 的距离。

记忆化+分类讨论即可。

T3:给定一个长度为 $n$ 的序列,求字典序前 $k$ 小的子序列。

$n,k\leq10^5$。

考虑先选小的,再选后面最小的...如果选完了就回来选次小的,这个是个搜索的过程,再配合主席树查询后缀第 $k$ 小即可。

2021/4/21

T1:两个人在一张 $n$ 个点 $n$ 条边的带权无向图 $F$ 上玩游戏。每个点的度数最大为 $2$。两人轮流选择一条 $F$ 中的边加入图 $G$,要求图 $G$ 中不能有环,直到不能选择边加入为止。

先手希望图 $G$ 中的边权和最小,后手反之。

求在最优策略下,最终图 $G$ 的权值。

$n\leq10^5$。

发现显然可以去掉自环之后对于每个环来考虑,因为每个环之间是独立的。

并且由于度数的限制,每个点最多在一个环上,不在环上的边肯定会被加入 $G$。

把设环的长度为 $s$,环上边权排序后的序列是 $a$。

先看奇数长度的环,无论先后手,两人一定是把边权排序后从两端开始选,最后留下 $a_{\frac{s}{2}}$。并且由于只选了偶数条边,所以先后手不会发生改变。

然后是偶数长度的环,我们发现这里谁先开谁占优(是选择 $a_{\frac{n}{2}}$ 还是 $a_{\frac{n}{2}+1}$),并且会交换先后手,于是我们就按这两个的差值排序,先手优先选,这样贪心正确性没有问题,因为没有其它干扰项了。

T2: $n$ 个点的树,在上面任选 $m$ 个标记点,让到所有标记点的距离都 $\leq d$ 的点的个数最大化,输出这个最大值。

$m,d\leq n\leq10^6$。

tmd卡点分的常,看了半天std才整出来神仙线性做法。

首先考虑所有标记点肯定在一个连通块中,于是考虑枚举这个连通块的直径中点 $u$,再枚举这个连通块的直径的一半 $r$。为了让这个半径是整数,我们把 $(fa_i\rightarrow i)$ 拆成 $(fa_i\rightarrow i+n-1),(i+n-1\rightarrow i)$ 就可以保证这个直径是偶数,半径是整数。

对于枚举出的一对 $(u,r)$,当 $\sum_{i=1}^n[dis(i,u)\leq r]$ 大于等于 $m$ 的时候,有答案等于 $\sum_{i=1}^n[dis(i,u)\leq d-r]$。

暴力枚举显然会 $\rm TLE$,因为有查询一个点 $[0,k]$ 级儿子个数的操作,所以我们考虑用长剖来优化这个过程。由于不可能枚举 $u$ 再分别长剖,所以我们还需要一个优秀的换根 $dp$ 或者是什么换根操作。

在 $dfn$ 上做一些操作。这里的 $dfn$ 优先走重儿子。

考虑只以 $1$ 为根,处理出 $f_{dfn_u+d}$ 表示 $u$ 点以 $1$ 为根的 $[0,d]$ 级儿子的个数。这里的儿子需要满足编号不超过 $n$,即不是加边时加入的虚点。这个显然可以 $dfs$+前缀和 来完成。

由于要换根,我们再维护一个 $g_{head+d}$ 表示子树外和自己距离在 $[1,d]$ 之间的点数。$head$ 是一个初值为 $2n-1$ 的变量,每向下走一层就会 $-1$。

下面说的所有更改操作在回溯时都要还原。

考虑走向轻儿子。会更新 $g_{head}=1$ 开始的一个前缀和 $f_{dfn_u+1}$ 的一个前缀。暴力做即可。

走向重儿子的时候,我们先暴力修改一个向后的前缀,但是由于可能修改的向前的前缀长度很长,我们记录两个全局的标记 $tg$ 和 $tg0$,走轻儿子的时候清空 $tg0$ 即可,但是回溯的时候也要还原。

$tg$ 顺便记录一路上的有效点个数。

2021/4/23

T1:求从 $(0,0)$ 开始的蛇形矩阵 $a$ 的 $\sum_{i=x_1}^{x_2}\sum_{i=y_1}^{y_2}a_{i,j}$,$a$ 长这个样子。

有色的部分是询问区间。

大力推一波柿子。先让坐标从 $(1,1)$ 开始,下面的除法都是向下取整,等差数列求和直接写出来了。

$f_k(n)=\sum_{i=1}^n i^k$,$k$ 最多只会用到 $3$。

$f(x)=\sum_{i=1}^x\sum_{j=1}^x a_{i,j}$,这个东西发现只有恰好 $2x-1$ 的平方那一段只有连续 $x$ 个数,例如 $x=3$ 时的 $23,24,25$。这个是令 $a=2x-1$,$(2*a*a-a/2)*(a/2+1)/2$。

剩下的就是一个 $\sum_{b=0,a=2b+1}^{x-2} \frac{(2a^2+1)(a+1)}{2}$ 的东西,这玩意大力展开就是 $f_1(x-1)+8f_3(x-2)+16f_2(x-2)+10f_1(x-2)+2*(x-1)$。

考虑 $get(x,y)=\sum_{i=1}^x\sum_{j=1}^y a_{i,j}$。发现就是上面那样一个正方形加上一个分别等差的矩形。这个大力展开就好。

然后就容斥一下就做完了。

对 $2^{63}$ 取模可以直接用 $ull$ 看做对 $2^{64}$ 取模,最后输出的时候把最高位压掉就可以了。

code


2021/4/24

约定:用 $(i,j)$ 表示 $\gcd(i,j)$,用 $[i,j]$ 表示 $\text{lcm}(i,j)$,$[P]$ 在事件 $P$ 为真时等于 $1$,否则等于 $0$。

51nod1584 加权约数和

求 $\sum_{i=1}^n\sum_{j=1}^n max(i,j)*\sigma(ij)$,$T$ 组数据。

$T\leq 50000,n\leq 10^6$。

首先令 $A=\sum_{i=1}^n\sum_{j=1}^i i*\sigma(ij),B=\sum_{i=1}^n i*\sigma(i^2)$,那么有 $ans=2A-B$。

$B$ 随便搞一搞就好了,主要看 $A$。

$$ \begin{aligned} f(i)&=i·\sum_{j=1}^i \sigma(ij)\\ &=i\sum_{j=1}^i\sum_{p|i}\sum_{q|j}[(p,q)=1]p·\frac{j}{q}\\ &=i\sum_{j=1}^i\sum_{d|i,d|j}\mu(d)\sum_{d|p,p|i}p\sum_{d|q,q|j}\frac{j}{q}\\ &=i\sum_{j=1}^i\sum_{d|i,d|j}\mu(d)·d·\sigma(\frac{i}{d})\sigma(\frac{j}{d})\quad\color{red}{[1]}\\ &=i\sum_{d|i}\mu(d)·d·\sigma(\frac{i}{d})\sum_{j=1}^{\frac{i}{d}}\sigma(j)\\ \end{aligned} $$

$$ \begin{aligned} \color{red}{[1]}:&\sum_{d|p,p|i}p=\sum_{p|\frac{i}{d}}p·d=d·\sigma(\frac{i}{d})\\ &\sum_{d|q,q|j}\frac{j}{q}=\sum_{q|\frac{j}{d}}\frac{\frac{j}{d}}{q}=\sum_{q|\frac{j}{d}}q=\sigma(\frac{j}{d}) \end{aligned} $$

$$ A=\sum_{i=1}^nf(i) $$

于是这道题就做完了。

code

bzoj3561 DZY loves Math VI

求 $\sum_{i=1}^n\sum_{j=1}^m \text{lcm}(i,j)^{\gcd(i,j)}$,$n,m\leq 5*10^5$。

老套路题了,挺好做的。令 $n≥m$。

$$ \begin{aligned} ans&=\sum_d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[(i,j)=1]i^dj^dd^d\\ &=\sum_dd^d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{g|(i,j)}\mu(g)i^dj^d{g^{d}}^2\\ &=\sum_dd^d\sum_{g=1}^{\lfloor\frac{n}{d}\rfloor}\mu(g){g^d}^2\sum_{i=1}^{\lfloor\frac{n}{dg}\rfloor}i^d\sum_{j=1}^{\lfloor\frac{m}{dg}\rfloor}j^d \end{aligned} $$

于是你惊奇地推到这一步之后感觉推不动了,但是观察柿子发现暴力算的时间复杂度已经只有 $\mathcal O(n\log p+n\ln n)$ 了。

$n\log p$ 是算 $d^d$ 的,$n\ln n$ 是对于每个 $d$ ,暴力地 $\mathcal O(\lfloor\frac{n}{d}\rfloor)$ 算 $i^d$ 及其前缀和的。然后就过了。

code

CodeChef LCM-Adding Least Common Multiples

求 $\sum_{i=1}^n\sum_{j=1}^m\mu^2(\gcd(i,j))[i,j]$,$T$ 组数据,$n,m\leq 4*10^6,T\leq200$,时限 $0.2s$。

很朴素地展开:

$$ \begin{aligned} ans&=\sum_{d=1}^n\mu^2(d)·d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[(i,j)=1]·ij\\ &=\sum_{d=1}^n\mu^2(d)·d\sum_{g=1}^{\lfloor\frac{n}{d}\rfloor}\mu(g)·g^2· S(\lfloor\frac{n}{dg}\rfloor)·S(\lfloor\frac{m}{dg}\rfloor) \end{aligned} $$

其中 $S(n)=\sum_{i=1}^n i=\frac{n(n+1)}{2}$。

至此,已经可以两次数论分块做到 $\mathcal O(Tn^{\frac{3}{4}})$ 了,但是常数大到离谱,时间复杂度也难以通过(指本地需要跑 $2s$)。

于是继续考虑改为枚举 $T=dg$。

$$ \begin{aligned} ans&=\sum_{T=1}^n\sum_{d|T}\mu^2(d)\mu(\frac{T}{d})·\frac{T}{d}·T·S(\lfloor\frac{n}{T}\rfloor)·S(\lfloor\frac{m}{T}\rfloor)\\ &=\sum_{T=1}^nT·S(\lfloor\frac{n}{T}\rfloor)·S(\lfloor\frac{m}{T}\rfloor)\sum_{d|T}\mu^2(d)\mu(\frac{T}{d})·\frac{T}{d} \end{aligned} $$

考虑设 $f(n)=\sum_{d|n}\mu^2(d)\mu(\frac{n}{d})·\frac{n}{d}$,这东西由 $\mu^2,\mu,\text{id}$ 组成,容易证明是个积性函数。

于是考虑 $f(p)=1-p,f(p^2)=-p,f(p^3)=0$ 之后就可以暴力线筛出来了。

$$ ans=\sum_{T=1}^nf(T)·S(\lfloor\frac{n}{T}\rfloor)·S(\lfloor\frac{m}{T}\rfloor) $$

线性筛出 $f$ 之后算个前缀和就可以数论分块了,时间复杂度 $\mathcal O(T\sqrt{n})$,可以轻松通过。

code

2021/4/25

今天主要练习了基础的莫队。

以下描述默认 序列长度 和 询问次数 同阶,都是 $n$。

$\texttt{Part 1}$ 普通莫队

莫队是为了处理一些 离线 的区间询问问题而生的。

举个例子,多次询问求一个区间内有多少数只出现了一次。

这玩意放普通的 $\log$ 数据结构貌似不太好做,所以我们考虑放到莫队上。

莫队的思想基于分块。我们把序列分成 $\sqrt{n}$ 级别个块,对于所有询问离线下来,按左端点所在块为第一关键字,右端点为第二关键字排序之后逐个处理询问。

对于一个询问的处理,我们就把当前的 $l,r$ 指针暴力地移到对应的位置,此时的答案就是这个询问的答案。

普通莫队的特点是一个元素的插入,删除都可以做到 $O(1)$ 处理对答案的影响,比如出现次数和,出现次数的平方和等等。

时间复杂度:很明显,对于左端点在同一个块内的询问,右端点的移动不会超过 $n$ 次,左端点的块一共有 $\sqrt{n}$ 级别个,总时间复杂度在 $O(n\sqrt{n})$ 级别。

奇偶优化:考虑对于奇数块让右端点升序,偶数块让右端点降序,这样右端点就不会在左端点换块的时候一路无用地移动回来,但是是常数级别的优化。

例题:P2709

$\texttt{Part 2}$ 树上莫队基础

链的部分待补。

对于树上子树信息的查询,显然可以按照 dfs 序转换为序列问题之后直接莫队。

例题:CF375D

$\texttt{Part 3}$ 带修莫队

时间复杂度证明待补。

先放个别人博客里的证明。

考虑在维护 $l,r$ 的情况下加一个维度 $t$,实际上我们可以用一个数 $t$ 来表示当前已经处理到了第 $t$ 个修改,处理询问的时候让这个 $t$ 也跟着到询问对应的那个 $t$,需要方便回退。

排序的时候不奇偶分块,按照 左端点所在块,右端点所在块,$t$ 作为三元组排序,时间复杂度 $O(n^{\frac{3}{5}})$,块长记得开 $n^{\frac{2}{3}}$ 级别。

例题:P1903

$\texttt Part 4$ 回滚莫队

对于一些问题,我们发现元素的加入和删除,只能很方便 ( $O(1)$ ) 地处理其中一个。

以只能加入为例。P5906

插入一个新的元素很简单,只需要更新一个元素出现位置的 $\min/\max$ 再更新答案即可。但是删除的时候,最坏情况需要 $O(n)$ 才能准确地维护信息,这种时间复杂度是极度不平衡的,我们考虑如何减少删除的操作。

依然和普通莫队一样排序,但是不加奇偶优化。

我们发现对于左端点在同一个块内的询问,右端点可以是 单调递增 的,我们非常喜欢这个性质。

于是每次左端点更换块的时候,我们就暴力地 $O(n)$ 重置维护的信息,再让右端点一路扫过去。左端点每次的左移也是临时的,需要随时回退。相当于围绕着一个右端点,分别不断向左右扩展。

暴力重置维护信息的次数是 $O(\sqrt{n})$,时间复杂度 $O(n\sqrt{n})$,左端点在同一块内的询问,端点的移动不会超过 $n$ 次,这里的时间复杂度和上面的重置的复杂度达到了平衡,所以效率相对比较优。

放一份代码方便理解

小 $\texttt{Trick}$

有时候我们做莫队题的时候需要时间复杂度的平衡,比如下面这题。

P4867。求区间 $[l,r]$ 内 权值在 $[x,y]$ 之间的数的种数,也就是重复的只算一次。

随便套一个数据结构可以做到 $O(n\sqrt{n}\log n)$,瓶颈在这个 $\log$ 上。

我们发现,端点的移动有 $n\sqrt{n}$ 次,而查询只有 $n$ 次。时间复杂度是 $O(n\sqrt n \log n+n\log n)$ 的。我们需要让移动的时间复杂度小下来,查询的复杂度大一点也没什么。

于是考虑一种 $O(1)$ 修改,$O(\sqrt n)$ 查询的东西,那就是 值域分块。我们更新的时候更新到这个值对应的块上是 $O(1)$ 的,查询的时间遍历散块和整块是 $O(\sqrt n)$ 的,于是就能达到时间复杂度的平衡,总时间复杂度 $O(n\sqrt n)$。

放一份代码

2021/4/26

T2:给定一个 $01$ 串 $S$,定义一轮操作为顺次把每个 $1$ 找到后面第一个目前非 $0$ 的位置移动过去,每个 $1$ 在每轮只会被移动一次,求无限轮之后从左到右每个极长 $1$ 段的长度。

串的生成方式是这样,给定奇数个 $a_{1...n}$,对于奇数 $i$ ,放 $a_i$ 个 $1$,对于偶数 $i$,放 $a_i$ 个 $0$,最后在串的末尾补上无限个 $0$。

把 $1$ 看作左括号,$0$ 看作右括号,每次操作的本质就是对于每个左括号去贪心匹配右括号。

考虑记录 $A_i$ 表示 $i$ 层嵌套的括号的个数,嵌套层数定义为从一组括号匹配中尽可能多的选出能嵌套的括号能构成的层数。

考虑这样一个事情,操作之后 $A$ 序列的值不变。

证明的话可以只看相邻两轮。我们把 $1$ 的位置作为关键点,分为两种情况:

1:关键点作为左括号,向右找右括号。

2:关键点作为右括号,向左找左括号。

$A$ 的计算可以看作找到连续的 $01/10$ 作为 $A_1$ 并抹除,接下来继续找连续的 $01/10$ 作为 $A_2$ 并抹除...

在左右都补上无限个 $0$,容易发现这样的操作是等价的,生成的 $A$ 序列自然也等价。

于是考虑最后一定是若干个互不嵌套的层数有序的括号在向前分别走,于是随便求出 $A$ 序列再排序输出即可。


*T3:给定一棵树和点权 $a_i$,边权 $b_i$,最大化 $\frac{\sum_{(u,v)\in E}b_{(u,v)}\times w_u\times w_v}{\sum_{u\in V}a_u\times {w_u}^2}$,其中 $w_i$ 取非负实数。

均值不等式:$a^2+b^2≥2ab$,证明显然。

考虑一个部分分:树的形态是一个以 $x$ 为中心的菊花图,叶子分别标号为 $y_{1..n-1}$,点权就用编号来代指,边权挂到叶子节点上,中心的点权标为 $c$。

假设答案是 $\lambda$,就有 $x*\sum_{i=1}^{n-1}b_iy_i\leq \lambda·(c·x^2+\sum_{i=1}^{n-1}a_iy_i^2)$。含义是任意一种 $x,y_i$ 的取值都不会优于答案是 $\lambda$ 时的值。

考虑拎一个 $y_i$ 出来,就有 $?+\lambda a_iy_i^2≥x·b_iy_i$,这个问号我们可以用上面的均值不等式解出来,它应该取得 $\frac{b_i^2}{4\lambda·a_i}x^2$,此时 $a=\frac{b_i}{2\sqrt{\lambda a_i}}·x,b=\sqrt{\lambda a_i}·y,2ab=x·b_iy_i$,自然有 $a^2+b^2≥2ab$。

在这个子任务中,移项之后就有 $\sum_{i=1}^{n-1}\frac{b_i^2}{4\lambda·a_i}=c·\lambda$,可以解出 $\lambda$ 对应的表达式。

回到原问题,对于答案是 $\lambda$ 的情况,我们就有 $\sum_{(u,v)\in E} b_{(u,v)\times w_u\times w_v}\leq \lambda \times \sum_{u\in V}a_u\times {w_u}^2$。

于是我们对于每一条边 $b_{(u,v)}\times w_u \times w_v$,我们都需要从 $u,v$ 里抽出 $A·{w_u}^2,B·{w_v}^2$,于是带回均值不等式,有 $a=\sqrt A·w_u,b=\sqrt B·w_v$,则有 $b_{(u,v)}\leq 2\sqrt{AB},AB≥\frac{{b_{(u,v)}}^2}{4}$。

于是就是每个点有 $\lambda·a_i$ 的总系数,要求恰好分配给每条连出去的边,每条边 $(u,v)$ 分到的系数乘积要不小于 $\frac{{b_{(u,v)}}^2}{4}$。

发现在叶子结点的时候特别好做。于是我们设 $f_u$ 是结点 $u$ 传给父亲的边的系数,对于叶子结点是唯一的,减去儿子结点还需要分配出去的系数,剩下的上传给父亲即可。

即 $f_u=\lambda·a_u-\sum_{v\in son(u)} \frac{{b_{(u,v)}}^2}{4·f_v}$,这个一次 $\mathcal O(n)$ 的 $dfs$ 就可以解决。

所以我们先随便猜一个 $\lambda$ 吧!

最后根节点 $1$ 的 $f$ 如果恰好是 $0$,那此时的 $\lambda$ 就是答案,否则我们考虑 $\lambda$ 是偏大还是偏小。

如果 $\lambda$ 偏大了,首先第一个影响的是叶子结点的 $f$ 会偏大,上传的时候 $\lambda·a_u$ 项偏大,后面要减去的项又偏小,所以最后的 $f_1$ 应该偏大,也就是 $f_1>0$。

如果 $\lambda$ 偏小了,叶子结点的 $f$ 偏小,上传的时候两项又分别导致 $f$ 更小,所以自然最后的 $f_1$ 偏小,也就是 $f_1<0$。

那么这明显是可以二分的,注意在 $dfs$ 来 $check$ 的时候,如果有 $f_u<0$ 那显然就是 $\lambda$ 偏小了导致这个点被预支了系数,这当然是不行的,所以需要把 $\lambda$ 调大。

那么就是一个 $\mathcal O(n|\log eps|)$ 的二分答案了。


2021/4/27

T2:给定长度为 $n$ 序列 $a$,$m$ 次询问,每次询问给出 $l,r,x$,求 $\max_{i\in [l,r]} a_i\ \text{and}\ x$ 或 $\max_{i\notin[l,r]}a_i\ \text{and}\ x$。

$a_i,x\leq 2^{20},n,m\leq 3*10^5$,土豆机子略卡常(指虽然复杂度貌似不正确,但是本机跑的飞快上面过不了)。

考虑按照常规 $\rm xor$ 的操作放到 $\rm 01Trie$ 上,但是发现如果 $x$ 的某一位是 $0$,可以走 $0$ 或者是 $1$。那么我们就暴力地类似线段树合并,从下往上把 $1$ 儿子的信息暴力合并到 $0$ 儿子上,这样就可以有 $1$ 走 $1$,没 $1$ 走 $0$了。

由于合并之后的树不支持快速插入,删除,所以考虑操作分块,每 $S$ 个操作重构一次 $\rm Trie$,多出的部分直接暴力扫。

于是我们就可以分析复杂度:(块长为 $S$)

$\mathcal O(\frac{n}{S}n\log^2n+n\log n+n·S)$

第一个是重构的复杂度,第二个是插入的复杂度,第三个是暴力扫的复杂度。

于是容易得到 $S=\sqrt{n\log^2 n}$ 的时候最优,最后的复杂度是 $\mathcal O(n\sqrt{n\log^2 n})=\mathcal O(n\sqrt n\log n)$,虽然但是它在 $3*10^5$ 的数据下 $3s$ 跑过去了...

特殊的,$a_i\notin[l,r]$ 的时候可以特殊处理,即不用重构,所以我们常数其实没有那么大。


2021/4/28

题越来越毒瘤了,连续两天只补了一道题了...

T1:给定一个定义在 $L$ 元集合 $S$ 上的数组 $A$,初值为 $0$,有两种操作:

  • 给定子集 $T\subseteq S$,$A_T \leftarrow A_T+v$。
  • 给定子集 $T\subseteq U\subseteq S$,求 $\sum_{T\subseteq I \subseteq U}A_I$。

$L\leq18,q\leq 5*10^5$。

考虑如果维护了子集和,我们可以暴力地求出答案。

但是如果 $1$ 比较多的时候,我们维护超集和会更优。

于是看 $0$ 和 $1$ 的数量比较,分别贡献到子集和或是超集和里面,这一步是至多 $2^{\frac{L}{2}}$ 的。

然后询问的时候就可以考虑对于两边的分别算答案,当然,如果 $*$ 比较少,我们也可以暴力枚举 $*$ 位置的取值。

code


2021/4/29

T1:给定两个串 $A,B$,求 $A$ 中有多少子串包含子序列 $T$,满足 $T$ 可以这么得到:

初始一个空串 $T$,接下来顺次把 $B$ 的每个字符任意加到空串的开头或末尾,最后得到的串即为 $S$。

$|A|\leq4096,|B|\leq2048$。

我是sb,不会dp。

考虑一个合法的串 $T$ 在随意插入若干字符后仍然合法,于是就设 $f_{l,r}$ 表示 $A[l,r]$ 至多能匹配到 $B$ 的第几位,最后答案就是 $\sum_{l=1}^{|A|}\sum_{r=l}^{|A|}[f_{l,r}=m]$。

这个东西枚举是用 $l,r$ 匹配或是不匹配就好了。

code

T3:你要遍历一棵以 $1$ 为根的 $n$ 个节点的外向树,你走过一条边 $i$ 需要 $val_i$ 的时间。

另外,你可以在节点放置分身,你可以瞬移到任何一个分身处;同时,你可以在任何时候收走一个点上的分身。整个树最多同时存在 $k$ 个分身。求最小时间。

对于 $k\in[1,p]$,输出对应的答案。

$1\leq n,p\leq 10^3,1\leq val\leq 10^9$。

首先,肯定是按照某个 $dfs$ 序遍历的,所以到达点 $u$ 之后,要遍历完 $u$ 的子树才会离开;所以分身一定全部在当前所在点到根的路径上。

其次,如果要收回某个分身,一定是收回离自己最近的,于是我们就可以设置状态 $f_{u,z,k}$ 表示遍历完 $u$ 的子树,最近一个分身点是 $z$,还剩 $k$ 个分身可以使用的最少时间。

于是就有常规的转移

$$ f_{u,z,k}=\sum_{v\in son_u}\min\{f_{v,z,k}+dis_{z,u},f_{v,u,k-1[k≠0]}\}+val_{u,v} $$

第一个的意思是不在 $u$ 放分身,那么每棵子树处理完之后就需要瞬移回 $z$ 再走到 $u$,所以在这里就计算上,第二个的意思是在 $u$ 放一个分身。

特殊地,对于我们遍历的 $u$ 的最后一棵子树,我们是不需要回到节点 $u$ 的,所以我们可以选择一个儿子 $v$,把它的贡献改为 $f_{v,z,k}+val_{u,v}$。其实还有一个状态是 $f_{v,u,k-1}+val_{u,v}$,但这显然是劣于上面说的转移的。

这样看起来转移是 $O(n^2p)$ 的,但是有一个结论改变了复杂度。

当 $k>\log_2 n$ 之后,所有的答案都是 $\sum_{(u,v)\in E}val_{u,v}$。

证明可以考虑把原树轻重链剖分一下,上面说的选择的特殊贡献的子树就是重儿子所在的子树,那么同时存在的分身个数至多是一个节点到根路径上轻边的条数,这是 $O(\log_2 n)$ 级别的。

于是时间复杂度 $O(n^2\log n)$,就做完了。

code


2021/4/30

T1:两个人在一棵 $n$ 个节点的树上玩游戏。两人轮流选择一个未被选择过的点,直到无法操作。最后这场游戏的权值就是先手选择的点中两两之间的最大距离。先手希望最小化这个权值,后手希望最大化这个权值。求最优策略下最终的权值。

$3\leq n\leq10^5$。

md我怎么就看不出博弈题的做法。

这道题看起来是个结论博弈题,但是是个大力分类讨论的恶心题...

考虑直径长度是 $d$,那么后手一波操作,可以让最终权值不小于 $d-2$,证明考虑后手无论如何不会同时选到一条直径的两个端点。

于是就是大力讨论属于哪种情况。

考虑找到直径的中心作为根,这里把 $u\to v$ 拆成 $u\to k\to v$,即强制直径长度是偶数,直径中心是个点。但是下面所有的操作描述的直径都指的是原树上的直径,带有 $\frac{1}{2}$ 也是可能的。

然后考虑对于根的每棵子树来讨论。设第 $i$ 棵子树中深度是 $\frac{d}{2}$ 的点的集合是 $G_i$。因为有直径的存在,所以这样非空的 $G$ 至少有两个。

首先考虑这样一个事情,当 $n$ 是偶数的时候,可以看作 $n$ 是奇数并且先手任意选择删掉一个节点。

那么对于 $ans=d$,有这样几种情况:

  • 有至少四个非空的 $G$。这个很显然,两人都会把 $G$ 里的点放到最后选,而这样先手就会选到至少 $2$ 棵子树里的 $G$。
  • 有三个非空的 $G$ 并且 $n$ 是奇数。先手最后操作的话也会导致选到 $2$ 个 $G$。
  • 有三个非空的 $G$ 并且至少有一个 $|G|≥2$。最劣的就是后手优先选 $G$ 里的点,直接选择 $|G|≥2$ 的那一个,剩下的就让先手任意选择,至少会撞到 $2$ 个 $G$。
  • 有两个非空的 $G$ 并且对于每一个非空的 $G$ 都存在 $|G|≥2$,考虑两人任意选择总会至少选到每个集合里的至少一个点,先手就没法操作了。
  • 有两个非空的 $G$ 并且至少一个 $|G|≥2$ 并且 $n$ 是奇数。先手肯定不会主动去选那个大小为 $1$ 的,那么由于他要进行最后一次操作,所以就自然会被迫选到那个 $1$。

现在剩下的情况有:

  • 有三个大小都为 $1$ 的 $G$,$n$ 为偶数,删掉一个,剩下两个至少选一个,答案是 $d-1$。
  • 有两个非空的 $G$,$|G_1|=1,|G_2|≥2$,$n$ 为偶数,删掉那个 $1$,剩下的选一个,答案是 $d-1$。
  • 有两个大小都为 $1$ 的 $G$。

对于暂时不太能直接判断的第三种情况,在 $n$ 是奇数的时候,先手的最后一步至少选中一个 $G$,故答案是 $d-1$。

剩下的就是 $n$ 是偶数的情况了。显然最后两步两人会分别取走两个深度是 $\frac{d}{2}$ 的点 $u_1,u_2$,所在的子树分别是 $T_1,T_2$。

先手无法避免答案是 $d-1$ 而不是 $d-2$ 的情况有:

  • 在 $T_1,T_2$ 以外的子树里选了一个深度是 $\frac{d}{2}-1$ 的点。
  • 在 $T_1,T_2$ 内同时选了深度是 $\frac{d}{2}-1$ 的点。

于是我们就类似地记录 $F_i$ 表示第 $i$ 棵子树里深度是 $\frac{d}{2}-1$ 的点的集合。我们只关心 $T_1,T_2$ 的 $F_1,F_2$ 和其他所有子树合成的 $H_3$。

当 $F_3\geq 2$ 的时候显然答案是 $d-1$。

当 $F_3=0,1$ :

如果 $F_3=1$ 那先手选择的就是尽力不选择这个点,先后手交换,所以后手的策略是尽量让先手在 $F_1,F_2$ 中都取点,于是这个时候就类似上面 $G$ 的讨论,只有 $F_1,F_2\geq 2$ 的时候才能同时被选到,此时答案是 $d-1$,否则才能让答案取到 $d-2$。

真是一道在阳间不可多得的好题。

code


T2:给定第二象限里的 $n$ 个红点 $(x_{r_i},y_{r_i})$,第一象限里的 $n$ 个蓝点 $(x_{b_i},y_{b_i})$,点带权,$q$ 次询问给定 $L,R$,求满足下列要求的红蓝点对的最大点权和:

  • $y_{r_i} < y_{b_j}$
  • $(L\leq x_{r_i}\text{ and }x_{b_j}\leq R)\text{ or }(x_{r_i}\leq L\text{ and }R\leq x_{b_j})$

考虑一个结论,对于两个不相交的纵坐标区间 $[l,m],(m,r]$,可能成为答案的点对中至少有一个点是区间内权值最大的点。如果都不选,那么说明最大值都被卡在另一段区间里面,选那个区间里的两个大权值点显然更优。

于是就对 $y$ 分治,得到 $O(n\log n)$ 个可能的点对,把询问挂到左端点上双指针 + 树状数组就做完了。

code


2021/5/1

T2:在一个 $n\times m$ 的矩阵 $A$ 中,满足 $\max_{j=1}^m \{A_{i,j}\}=a_i,\max_{i=1}^n\{A_{i,j}\}=b_j$,求有多少个满足条件的矩阵。

$1\leq n,m\leq 10^6,0\leq a_i,b_i\leq 10^9$。

首先把 $a,b$ 排序后并不影响最终的答案。

如果 $\max a_i\not =\max b_i$ 那么答案显然是 $0$。

接下来考虑容斥

设 $f_s$ 为填满最大值限制恰为 $s$ 行列的方案数。$x,y$ 是行、列限制大于 $s$ 的数量,$x',y'$ 是行、列限制恰为 $s$ 的数量,于是有:

$$ f_s=\sum_{i=0}^{x'}\sum_{j=0}^{y'}(-1)^{i+j}\binom{x'}{i}\binom{y'}{j} s^{i(y+y')+j(x+x')-ij}(s+1)^{(x+x'-i)(y+y'-j)-xy} $$

$i,j$ 是分别在枚举不合法的行列数,$s$ 的含义是从 $[0,s-1]$ 里面任选,$s+1$ 同理。指数是看有多少个位置需要这么放,指数上减掉的东西是重复的部分。

枚举两个数太慢了,这个组合数的形式让我们想到二项式定理,于是就尝试改变指数让其中一个可以被消掉。

$$ f_s=\sum_{i=0}^{x'}(-1)^{i+y'}\binom{x'}{i}s^{i(y+y')}(s+1)^{(x+x'-i)(y+y')-xy}\sum_{j=0}^{y'}(-1)^{y'-j}\binom{y'}{j}s^{j(x+x'-i)}(s+1)^{j(i-x-x')} $$

于是把后面那坨用二项式定理合成 $(s^{x+x'-i}(s+1)^{i-x-x'}-1)^j$,就可以 $O(\sum x\log p)=O(n\log p)$ 计算了。


T3:给定一个长度为 $4n$ 的排列 $c_{1...4n}$,给出一组 $x_{1...4n}\in\{0,1\}$ 满足 $\forall i \in[1,n],x_{4i-3}+x_{4i-2}+x_{4i-1}+x_{4i}=2$ 并且最大化 $\min\{\sum_i [x_i=1]c_i,\sum_i [x_i=0]c_i\}$。

$1\leq n\leq 10^6$。

题意要最小化取 $\min$ 两项的差值。由于 $c$ 是一个排列,我们大胆猜想这个差值可以取到 $0$,考虑如何做到。

$\sum c_i=(2n)(4n+1)$,所以 $\sum_i[x_i=1]c_i=\sum_i[x_i=0]c_i=n(4n+1)$,我们只需要让同色的元素能够被两两分成一组,每组的和是 $4n+1$ 即可。

类似 CF1404D,我们把每组(四个 $x_i$)看作一个点,把和为 $4n+1$ 的数所在的两个点连一条边。不难发现,这样连边出来每个点的度数都是 $4$。

我们需要删掉一些边,让每个点的度数都恰好是 $2$,那么剩下的边连着的数字就染成 $1$,其余的是 $0$ 即可。

不难发现按照这样连出来的图长得非常漂亮,每个点的度数都是 $4$,所以我们直接 dfs 即可,把经过的第奇数条边选中。


2021/5/4

T1:对长度为 $n$ 的排列 $a$ 计数,需要满足一个给定的长度为 $m$ 的序列 $x$ 是 $a$ 中字典序最小的长度为 $m$ 的子序列。

$n,m\leq 2*10^5$。

考虑先令 $a=x$,再从小到大依次插入元素。

令 $[x]$ 表示一段都大于 $x$ 的数,那 $a$ 序列就形如 $[x_1]x_1[x_2]x_2...[x_m]x_m[x_m]$,于是计数就很简单了。

T2:区间取 $\max$,区间玩 $Nim$ 游戏问先手第一步有多少种走法可以必胜。

裸 $\rm SegmentTreeBeats$,直接上就好了。

T3: $n×m$ 的网格,网格上有一些障碍和星星,以及一个球。
每次移动可以令球上下左右任意方向滚动直到撞到边界或障碍停下。
球在移动过程中会收集经过的星星。求是否能收集所有星星。
$n,m≤50$。

把一段极长的连续段(上下或左右)看成一个点,连边跑 $\rm 2-sat$。

最后修改:2021 年 05 月 04 日 03 : 56 PM