三轮省集

Day 1

模拟赛

A

Qoj4907 djq 学生物

容易想到一张图,然后邻接矩阵的幂,然后要求$\sum_i M^i=\dfrac{1}{1-M}$.

然后容易想到换成”排列幂级数”多项式,转移多项式$F(x)=\sum_p c_p x^p$,$p$为一个排列,$x^p\cdot x^q=x^{p\circ q}$,要求$\sum_i F(x)^i=\dfrac{1}{1-F}$,就是要给这个东西求逆.容易发现若答案存在逆一定存在.

因为每一位分别做,容易想到类似FWT的形式,回想 “FWT本质” 类似物,比如试着找矩阵$C$使得$C_{i,j}$为$i\to j$的贡献,然后变换完之后点积就对应卷积.但是这里不适用(找不到合法的$C$).$p\circ q$不交换本身性质不好,拆成三个矩阵也是未知数少于方程数的.

然后感觉这里见识到更本质的FWT,我们实际上是在找可逆线性变换$T$使得$T(a)\cdot T(b)=T(a\times b)$,$T$把数变换到矩阵也是合法的.用矩阵强行模拟$S_3$的结构,构造出

$$
M_{123}=(\begin{Bmatrix}
1 & 0\0 & 1 \
\end{Bmatrix},1,1)\
M_{132}=(\begin{Bmatrix}
1 & -1\0 & -1 \
\end{Bmatrix},1,-1)\
M_{213}=(\begin{Bmatrix}
0 & 1\1 & 0 \
\end{Bmatrix},1,-1)\
M_{231}=(\begin{Bmatrix}
-1 & 1\-1 & 0 \
\end{Bmatrix},1,1)\
M_{312}=(\begin{Bmatrix}
0 & -1\1 & -1 \
\end{Bmatrix},1,1)\
M_{321}=(\begin{Bmatrix}
-1 & 0\-1 & 1 \
\end{Bmatrix},1,-1)
$$

三个元素间做乘法是点乘,矩阵做乘法就是矩阵乘.

你会好奇为什么要构造这个大小的而不直接用$3\times 3$的置换矩阵,但先别管

然后这个构造方式的话,后面两维写全$1$ 和 排列奇偶性显然是对的,第一列可以考虑几何构造,选择平面上三个点$(0,0),(0,1),(1,0)$分别代表$1,2,3$,找到一个矩阵可以交换两个点而第三个点位置不变即可.

构造出矩阵之后我们现在会做$n=1$的情况,就对于原序列是$\sum_i c_i x^{p}$,$i\in [0,5]$是$p$的字典序编号(题目中的),则设$M=\sum_i c_iM_i$,把$M$求逆,再变换回来(容易发现上面的线性变换满秩)即可.

现在要做高维的情况,考虑矩阵的直积,即$A\otimes B=(a_{i,j}B){i,j}$(把$A$的每个位置乘上$B$这个矩阵,得到一个新的巨大矩阵).它有性质$(A\otimes B)\times (C\otimes D)=(A\times C)\otimes (B\times D)$($\times$表示矩阵乘法).所以多维用直积变换,若$a$一个位置表示成$a{p_1,p_2,p_3\ldots p_k}$,那么我们实际上算的是$\sum\limits_{p_1\ldots p_k} a_ {\Large \otimes}i M{p_i}$.

然后变换完了你得到一个矩阵套矩阵的东西,我们不看点积那层关系(认为形如$(A,B,C)$的是三个不同的矩阵)你要对这个东西求逆,求逆复杂度是$\sum_i \binom{n}{i}2^{n-i}2^{3i}=10^n$

然后就做完了.

你会发现我们平时写的FWT都可以认为是这种矩阵直积的形式,只不过底层是$1\times 1$的矩阵.

B

Qoj8359 travel

看南外题解吧:

C

CF947I

todo

课

CF1924F Anti-Proxy Attendance

把题目转化为有$n$个vector,每次给定一个区间,交互库会把区间内部pushback$0$,外部pushback$1$,或者正好相反($1$表示答案在这一侧),那么如果出现连续$3$个$1$或连续$3$个$0$则这个位置必然不是答案,可以被排除.

则只用考虑每个vector最后两个位置,如果是00或11赋权值$1$,若为01或10赋权值$\phi$,若已经排除了赋权值$0$,则设上一次权值和为$A$,下一次交互库选择区间内部pushback$1$的权值为$B_1$,区间内部pushback$0$的权值为$B_0$,发现必然有$\phi A=B_0+B_1$.最后$A=O(1)$,一开始$A=O(n)$,所以交互库希望尽量大,会选择$\max (B_0,B_1)$给你,则每次$A$最多减小到$\dfrac{\phi}{2}A$,操作次数有下限$O(\log_{\dfrac{2}{\phi}} n)$

考虑所有前缀,问空前缀和问整个序列$B_0,B_1$必然恰好交换,则必然存在某处$\vert B_0-B_1\vert$很小,在这里问显然就是最优的.就能做到$O(\log_{\dfrac{2}{\phi}}n)$的次数了.

uoj883

大贪心讨论

显然我们要走所有黑点虚树的一个欧拉序,考虑dp,容易发现只要记录$f_{u,0/1,0/1}$表示 遍历$u$的子树,从$u$/$u$的儿子开始,$u$/$u$的儿子结束 的最小代价就是一个子问题,考虑转移.

对于两个子树之间的问题,只有$(0,0)\to (0,0)$花费$0$,其他花费$1$.由此,每个子树的选择应该是先游先取$f$小的,再取$0$多的状态转移.

对于$u$和自己第一个儿子,只有$u$是$(1,x)$,$v$是$(0,y)$花费$0$,其他花费$1$,同理对最后一个儿子只有$u,v$分别是$(x,1),(y,0)$花费$0$.

于是显然有

• 对$f_{u,0,0}$,儿子排列是$u\to (1,0)?\to (0,0)\ldots \to (0,1)(1,0)\ldots\to (1,1)\ldots \to u$,$?$表示不一定有.
• 对$f_{u,1,0}$,儿子排列$(0,0)\ldots \to (0,1)(1,0)\ldots \to (1,1)\ldots \to u$.对$f_{u,1,0}$同理.
• 对$f_{u,1,1}$,注意此时一个取$(1,1)$的点变成取$(0,0)$可能加$2$,所以可能把所有子节点变成$(0,0)$,且此时可能遍历不到$u$需要加$1$次操作.而一般情况只要做$(0,0)\ldots \to (0,1)(1,0)\ldots \to (1,1)\ldots\to (1,0) \to u$即可.

uoj884

显然的暴力是$f_{i,j}$表示走到这个格子的方案数.$f_{i,j}=f_{i-1,j-1}+f_{i,j-1}$,有障碍的格子为$0$.

考虑GF优化这个东西,设$F_i(x)=\sum_j f_{i,j}x^j$,如果没有障碍则$F_i(x)=\dfrac{F_{i-1}(x)}{(1-x)}$,存在一个障碍就要把那个位置设为$-\sum_{j<p} f_{i,j}$来抵消前面的贡献,于是只要支持快速查单项式系数,加单项式,除$1-x$.

但还是很慢,时间分块重构,每$B$个重构,于是维护$\dfrac{F_i}{(1-x)^k}$的形式,但这样底下的项数是$O(n)$的,不如维护$G_i(1-x)^k$的形式,在每块开始时设$k=B$,每次减$1$,这样查可以$O(B)$,修改时再维护修改的项$\dfrac{H(x)}{x^l}$,则因为$H$项数也是$O(B)$的就好做了.然后只要每$B$次进行重构,也就是计算$\dfrac{F(x)}{(1-x)^B}$,注意到$(1-x)^{509}\bmod 509 = 1-x^{509}$,于是取$B=509$,除$1-x^{509}$可以线性.

总复杂度是$nB+\dfrac{n^2}{B}\approx n\sqrt n$

Day2

模拟赛

A

P3993 [BJOI2017] 同构

考虑区分的点在反图上点也是区分的,于是相当于加最少的边让所有点区分,然后你发现$n$比较大的时候一个树肯定就弄完了,然后你发现过不了样例,可能是多个连通块省边,那如果这个连通块$m\ge n$就不能省一条边没有意义,于是都是树,且每个连通块互不同构,最大化连通块数量.于是显然从小到大选,只要求每个大小的,不自同构的无根树数量.

考虑一棵树不自同构的充要条件是,不存在一条边/点,使得删去它后剩下的若干连通块中有两个相同.发现一个子树和一个子树补的不会做,发现选重心为根就做完了,

Qoj4898. 基础图论练习题

考虑直接若干个等差数列合并在一起就是公差取gcd,但限定长度之后不能直接这样做.

容易证明${d_i\vert 2d_i\le n}$可以合并成一个gcd,可以考虑弱周期引理,考场上没有意识到它和字符串的相关性,那你就直接注意到任意时刻位置$x$必然要么可以走集合中的至少一个,否则终点一定在$[1,n]$外,即可.

那你现在应该想到弱周期引理啊,你会意识到$d$相当于给了一个周期,$n-d$就是一个border,那么容易得到border/d构成$\log n$段值域不交的等差数列,于是周期,那么有用的$d$只有$\log n$个.

考虑现在要能做到给你一个$d$的集合$S$找到等差数列,这里不像普通字符串那样简单,因为$d$的集合是不完全的.

别字符串了,类比TopCoder 12832 Huge Graph可以得到一个类似辗转相减gcd的方式:考虑拿出最小的$d_1$,那么若当前节点编号$x>d_1$,你一定可以走$x\to x-d_1\to x-d_i$,于是用$d_i-d_1$替换掉$d_1$,而对$x\le d_1$不能进行下面的变换,单向后连一个$d_1$,容易发现变换前后图等价.此时前$d_1$个点不对连通性产生影响(只有一条$+d_1$连到后面),可以删掉,可以递归下去.把不断相减变成取模(辗转相除),容易发现只会递归log次,复杂度是$\vert S\vert\log n$

现在每个$d$有不同的边权,需要从小到大加入$O(n)$次,注意到这个过程中只有曾作为最小值的$d$是有用的,可以只保留它们做,复杂度就$a\log^2 n$了.

但还有一些散边,考虑我们希望找到一个点在这个连通块中最小的代表元,发现这个可以在上面的递归中同步进行,找一个点复杂度是$\log n$.于是只要找到所有散边端点对应代表元,考虑先算出所有整边($a$条)的答案,那么散边的贡献只取决于散边代表元 在 加入整边的过程中的Kruskal重构树 上的虚树(其实是代表了它们每个点之间的整边边权最小值),抽出这棵虚树之后跑Kru即可.

考虑怎么建这棵虚树,显然对两个点什么时候连通可以二分,那么整体二分,$f(l,r,S)$表示加入第$l$组整边前$S$中点两两不连通,加入$r$后两两连通,求解出其中的点何时连通.那么算出$[1,mid]$的整边加入后的连通块是$S_1\ldots S_k$,递归计算$f(l,mid,S_1)\ldots f(l,mid,S_k)$,每个集合拿出一个元素组成$T$调用$f(mid+1,r,T)$即可.

复杂度是$(a+b)\log^2 n$

课

开胃菜

有一个未知$01$序列,每次可以询问子集中$1$的个数,要求$O(\dfrac{n}{\log n})$的次数问出序列.

分治,考虑若已经能构造$q$次解决长$n$的问题,拓展到$2q+1$次解决长$2n+q$的问题,则把$2n+q$分成$n,n,q$三段,设第一段的$q$个询问是$S_1\ldots S_1$,第二段是$T_1\ldots T_q$,那么我们把新的询问分成$q$个$ pair$,每个pair询问$x=S_i+T_i$和$y=S_i-T_i+a_{2n+i}$(用多的一次询问$[n+1,2n]$,通过询问补集算$-T_i$),则容易通过$x+y$的奇偶性判断$a_{2n+i}$,然后求$S$和$T$是简单的,分析一下就是$\dfrac{n}{\log n}$.

P6837 [IOI2020] 数蘑菇

luogu题解写的很清楚

重点在于充分利用奇偶之类的信息.

P8531 [Ynoi2003] 戌亥彗星

先考虑一次询问怎么做.

考虑处理限制,容易发现第二/三个限制有单调性,第一个没有.

对于第二个限制考虑从小到大扫右端点,lct维护最大编号生成树,则左端点是编号上的一个区间$[l_{1,i},r_{1,i}]$,用两个lct双指针,一个一直删直到变成树求出$r$,一个维护不考虑$r$这条边一直删直到变成树求出$l$.

对第三个限制我们在上面的过程可以知道那条环上的非树边,维护环点度数大于等于$2$的数量和非环点大于等于$2$的数量即可找到$[l_{2,i},r_{2,i}]$,取个交,记为$[L_i,R_i]$

对第一个限制,由于上面两个已经满足,只要$\vert V\vert=\vert E\vert$.而$V$相当于数颜色.

考虑扫描线扫$r’$,则问题相当于维护序列$a,b,c$,支持:

• 对$a$区间加
• 对$b$所有$a_i=0$的位置区间加
• 全局$c_i\gets c_i+b_i$

注意$a$最小值是$0$,那么第二个操作其实是最小值加,考虑怎么设计标记和信息,这里可以先不考虑$c$的操作,那么一次对$a$的区间加后面接一次对$b$的加后面这次一定无效,,同理一次对$b$的加后面接一次对$a$的减前面这次也一定无效,于是只要维护 $(a,b)$表示对$a$区间减,对$b$加 或 $(b,a)$表示先对$b$加再对$a$加两种标记,容易合并.

复杂度单log.

Uoj463

todo

Day3

模拟赛

A

写了一个假贪心然后似了.

不能观察得到,较短的串选的一定是原串的一个前缀,后面全填$0$,于是直接枚举前缀,$O(1)$维护值即可.

B

ZR 香雪兰

C

考虑连通块就是$V-E=1$,设$f_{i,j}$表示前$i$个选$j$个,扫描线扫$i$线段树维护$V-E$dp,复杂度$nk\log n$,卡常可过.

看看怎么做到$nk$,首先给根也加一个父亲,然后把是连通块转化成有且仅有一个点满足$i$在区间内而$fa_i$在区间外,即对$[l,r]$贡献是$\sum_{i\in [l,r]} [fa_i<l]+[fa_i>r]$.dp的时候扫$r$的话,显然后面这部分是单调的,一个后缀,前面的相当于加入一个点$i$时对区间$(fa_i,i]$做区间加.而注意这个是只有区间加没有减的,我们只要能维护和为$0/1$的区间.

于是维护仅考虑$[fa_i<l]$的部分,所以满足条件位置的dp值即前缀和(以便查区间和),而因为我们只有后缀加,只要开俩栈,加的时候从一个里取出来放到另一个即可.复杂度$nk+n\log n$.

课

GYM102028J

设$f_i$表示只被$i$覆盖的格子数.

若两个矩形无交只要求$f_i$最大的两个.

然后枚举每个格子,若它恰被两个地毯覆盖给这个对的贡献$+1$.然后只要找覆盖一个位置的两个元素,于是二维前缀和,查询覆盖每个位置的个数,编号和,编号平方和.

cf16_exhibition_final_e

容易发现不会有中转.

若有$u\to v$连边$(u,v)$,考虑一个连通集合$S$,它一定是一棵树(否则有中转),则每个点都会变成$\dfrac{(\sum_i a_i-\sum_{(u,v)\in E} dis(u,v))}{\vert S\vert}$.证明考虑新加一个叶子归纳.

于是一个点集只要求最小生成树.

于是求出每个集合最后会变成多少,然后直接跑子集卷积,复杂度$n^22^n$

CF1239E

容易发现第一行单增第二行单减.

容易发现下凸,于是最大值一定在两侧.

于是最小值放在左上角和右下角,跑背包$n^3V$就过了.

Qoj5874

meet in the middle,枚举问号少的一半.

如果高位问号少,你可以几乎确定平方根,直接把后面全填$0$开方然后往后找$O(1)$个即可,然后再确定低位是容易的.

如果低位问号少,注意到若最低位是$1$,则高位加$1$

[ARC160E] Make Biconnected

显然每个叶子都需要至少连一条边,否则删掉它的父亲一定不合法.

我们希望这也是上界,则叶子跑匹配,于是考虑关于子树内叶子个数的带权重心,那么一定能找到一个匹配使得任意一对点在两个不同的子树,此时容易发现合法.

若叶子数为奇数,

CF1558F Strange Sort

todo

Day4

A

区间加,区间对固定数取模,区间和.

容易发现修改容易复合,变成$+a$,取模,$+b$的形式,然后$+a$需要做区间rank,所以分块.每块维护$a,b$和所有值的有序数组就做到$n\sqrt n\log n$.

然后可以把一些log去掉,比如修改散块重建的时候不sort而使用归并,离线逐块处理干掉二分,就可以把log放到根号底下.

然后可以单根号,不离线逐块二分,分散层叠掉/cf

B

喵的为啥以前做过的题一点也想不起来!

JOI Open 2019 三级跳

C

容易发现很局部,想到一个dp是$f_{i,j,k}$表示长$i$的区间,还有$j$次操作,第$k$个位置的答案,然后在$[l,r]$的第一次操作一定是在$[l,r]$的一个中点,把它分成两部分,此时枚举$k$表示左边分到$k$个操作,右边分到$i-k$个操作,把操作在时间轴上插起来分配系数转移.转移是卷积可以优化到$n^2\log n$

然后$k$这一维显然必须杀了,容易想到$f_{l,r,i}$表示$l,r$这个区间剩$i$次操作,转移还是一样分配系数,然而把复杂度算错了,注意到复杂度是$n\log^3 n$.(而不是$n^2\log n$)

再优化就搞成单侧递归,显然长度为奇数的区间只要递归到一侧再把答案复制到另一边,复杂度就是$n\log n$了.

尝试不要ntt,概率转方案数,时间轴上分配操作的标号考虑EGF,则$F_{l,r}(x)=\sum_i \dfrac{x^i}{i!}f_{l,r,i}$,有
$$
mid=\lfloor \frac{l+r}{2} \rfloor\
F_{l,r}(x)=
\begin{cases}
2n\int F_{l,mid-1}(x)(1+x)^{r-(mid+1)+1}+1,2\nmid n\
n\int F_{l,mid-1}(x)(1+x)^{r-(mid+1)+1}+\int F_{l,mid}(x)(1+x)^{r-(mid+2)+1}+1,2\mid n
\end{cases}
$$

课

loj2159. 「POI2011 R1」收缩点 Plot

显然先二分,但判定是最小圆覆盖,不能动态加点,可以$O(k)$解决规模$k$的问题.

此时不能二分,因为最坏每次只加一个点就似了,我们希望它和下一段长度有关,于是先倍增尝试,若以$i$为左端点,$i+2^k$可行而$i+2^{k+1}$不可行,再在这个区间二分,复杂度就$n\log n\log V$了.

Timus 2057

考虑什么时候无解,全$a$无解,考虑整个串一定是回文串,那么拿到$a$后第一个$b$,显然回文中心不在这之前,然后如果回文中心恰好是这个$b$显然无解,回文中心在这之后,尝试在第一个$b$后面砍一刀,剩下的递归下去,得出最后一种无解可能是$abababa\ldots$这样的.

于是就会判无解.

然后直接dp,让$j$能转移到$i$当且仅当这个区间有解,然后处理$i$往前极长的$abab$和$a$区间,会对奇数/偶数的$j$分别有上界限制,然后对$aa\ldots baa\ldots$的情况对每个$i$是唯一的,就做完了.

Qoj7303

考虑模$2$很关键,考虑给每个集合$S$一个容斥系数$w(S)$,使得对连通的集合是$1$而其他的是$0$,想到算$2^{c}\bmod 4$,$c$为连通块个数,于是最后只要算$(\sum_S 2^{c_S})\bmod 4$,等价于把连通块染色,或者说把每个点黑白灰染色,要求不存在黑白边.

于是扫编号维$3^13$状压dp即可.

[ARC160D] Mahjong

考虑建立操作序列到原序列的双射,对同一位置的$k$次区间加替换成单点加,证明考虑把原序列模$k$然后差分应该对应操作序列.

然后数数是GF简单题.

loj3911

显然是最终子序列的一个前缀/后缀拼接,于是先预处理$f_{i,j}$表示前缀和为$j$的本质不同子序列个数.

这个也得dp,设$f_{i,j,k}$表示前$i$个字符,前缀和为$j$,长度为$k$的,每次枚举子序列下一个字符转移.

然后拼接的时候也可能有重复,钦定求$s_a+s_b$的问题时拼接得到的$s_a$极大的匹配即可,那么若我们希望下一个匹配的是字符$c\in {L,R}$,就要求$s$在最后一个位置之后没有出现过,然后就做完了.

[AGC056B] Range Argmax

要构造$x$到$p$的双射,从大到小每次填一个最大值,删去包含这个最大值的$x$,递归到两边,为了避免数重我们希望这个最大值是满足条件的最前面.

于是dp,要从$[l,r]$以最大值$k$处分开,那么对$[l,k-1]$的最大值$k’$,有$k$是合法的最左位置当且仅当存在区间同时包含$k’,k$,否则容易发现可以让$k’$当这个最大值,于是$f_{l,r,k}$表示区间$l,r$且最大值位置必须在$k$之后的方案数,即可dp.

[ARC165E] Random Isolation

考虑转化成可以任意删点,但只统计连通块大于等于$k$的次数,然后拆贡献算一个点$u$被删时连通块大于等于$k$的概率.

让连通块以$u$为根,设这个连通块大小为$a$,和这个连通块有边但比它早删的点数为$b$,数数.

后面是二维卷积树形dp.

Day5

模拟赛

A

容易想到一个$n^3$的区间dp.

容易想到$n^3\log n$的区间dp.

容易想到把二分干掉改成枚举答案,每次把一个区间点亮.

但是复杂度都很劣.

不容易想到这个题正解是bitset的$n^3$.然后用bitset的find_first/next查找下一个点亮的区间就做完了.

B

容易发现$b$从大到小排序,得到一个$n^2$dp,$f_{i,j}$表示前$i$个,已经选了$j$个的最小值.有$f_{i,j}=\min(f_{i-1,j},f_{i-1,j-1}+a_i+(j-1)\cdot b_i)$容易发现固定$i$dp值是凸的.

不知道怎么发现,dp的两种转移分别是一个前缀和一个后缀,于是只要支持区间加等差数列,区间加,区间平移$1$,平衡树维护即可.

怎么发现呢,zzk表示注意到$b\le 10$的部分分,此时对每个$b$把$a$排序,每个$b$要选$a$的一个前缀$a_{1\ldots k}$,这个$k$是有决策单调性的,然后类比过来.

另一个做法是考虑贪心,容易发现一开始最小的$a_p$一定会被选,删掉它之后考虑剩余的数贡献变化,若$b_i>b_p$则$a_i\gets b_i$,否则按$b$排序后$i$会插入到$p$前面,$a_i\gets a_i+b_p$.然后接着选最小的重复即可.

于是只要支持区间加,区间加等差数列,区间和,复杂度$n\log^3 n$.(tocheck)

C

首先转化到,每个人让$[l_i,r_i]$加$1$,可以翻转为让$[1,l_i)\cup (r_i,n]$加$1$,最小化最大值.

然后注意到,若存在两个不交的区间都被翻转,他们翻转后覆盖完全包含他们翻转前,所以一定不优,于是有存在一个位置被所有翻转的区间包含.

于是一个部分分是二分答案$mid$,枚举这个被所有区间包含的位置$x$,对$i<x$,一个包含$i$的区间翻转后必然不包含$i$,于是设$pre_i$表示左端点在$i$及之前的翻转区间个数,有$(a_i-pre_i)+(pre_x-pre_i)\le mid$,可以得到$pre_i$的下界,枚举$pre_x$可以得到每个$pre_i$的限制.

然后显然左边翻转的区间的$r$越大越好,于是从$1$到$x$贪心,到$i$时把所有$l=i,r\ge x$的区间按$r$加入大根堆,取走并翻转堆顶若干个区间直到满足$pre_i$的限制,最后判断右边是否合法.$n^3\log^2 n$

设未翻转前每个位置覆盖次数为$a_i$,翻转后为$b_i$

然后注意到,存在一种最优方案,使得若所有被翻转区间的交是$[l,r]$,有$[l,r]$中$b$的最大值和全局$b$最大值最多差$1$.考虑若差$2$以上选择$[l,?]$和$[?,r]$翻转不劣.

然后注意到,存在一种最优方案,使得设$t=\argmin_{i\in [l,r]} a_i$,$k=\argmin_i a_i$,$a_k=a_i$.证明考虑反证,若$a_k>a_t$有$k\notin [l,r]$,一开始有$a_k\ge a_t+1$,由上面的性质有$b_t\ge a_k-1$,相加并调整就有$a_k-b_k\ge a_t-b_t$,矛盾.

于是不需要枚举$pre_i$,有$mid\in {b_t,b_t+1},b_t=a_t-pre_x$,于是$pre_x\in {a_t-mid,a_t-mid+1}$.$n^2\log^2 n$

然后注意到,我们枚举的$x$可以选择任意$a_x=\max_{i=1}^n a_i$,考虑反证,设$k\notin [l,r]$且$a_k$也是$a$的全局最大值,于是有$a_k-b_k\ge a_x-b_x-2$(翻转一个区间有$2$的差),由上一个注意知道$a_x=a_k$,于是$b_k-b_t\ge 2$与第二个注意矛盾.

课

「Dwango Programming Contest 6th」Cookie Distribution

把$\prod_i c_i$拆组合意义,表示每个人再从自己的cookie中选一个.然后直接按天dp,每天分配若干个选中的和若干个没选中的.

「JOISC 2015 Day2」Keys

对每个时间间隔分类讨论,什么时候一个间隔可以关门:

• 前一个人进入,后一个人出门,总是可以.
• 两人都进,要求后一个人有钥匙
• 两人都出,要求前一个人有钥匙
• 前一个人出后一个人进要求两人都有钥匙

注意到只有第四种情况和两人都有关,此时把两个人连边,一定得到若干条链,对每条链分别dp最后卷起来,复杂度$n^2$.

「JOISC 2020 Day4」治疗计划

好离奇.

设$f_i$表示当前的方案推到某个时刻$t_i$可以治疗$[1,r_i]$的最小代价.若$i<j$,则$[1,r_i]$推到时刻$j$应该是$[1,r_i-t_j+t_i]$这样的感觉.

有了这个之后因为我们不知道转移顺序,用仿dij的形式每次拿最小的更新即可做到$n\log n$.

有一种从扫时间到扫序列维的感觉,所以这个神奇的状态是怎么想到的.

「JOISC 2020 Day3」星座 3

对楼建大根笛卡尔树,设当前处理最大值为$a_u$的区间,注意到两边低于$a_u$的星星是子问题,高于$a_u$的左右子树分别至多剩一个,我们只关心它的高度,于是设$f_{u,i}$表示$a_u$为最大值的区间,保留的最高的星星高度为$i$的答案,有$f_{u,i}=\max(f_{l,i}+\max_{k<i} f_{r,k},f_{r,i}+\max_{k<i} f_{l,k})$,对$u$这一列的单独转移,容易发现都可以线段树合并维护.

AGC033D Complexity

考虑设$f_{l,r,u,d}$表示这个矩形的凌乱度,容易做到$n$,而你注意到凌乱度不超过$\log (n+m)$量级,于是交换一维变成$f_{l,u,d,v}$表示最大的$r$使得凌乱度为$v$

把它分成横着两个矩形的转移时容易的,对竖着的需要一个分界点,注意到这个分界点有单调性可以二分,或者双指针.

就过了.

PKUSC2024 独立

容易想到一个暴力时$f_{u,i,j}$表示$u$子树内,可选可不选$/不选u$的最大独立集分别是$i,j$的方案数.结合小N的独立集容易想到只需要记录$j-i$的差,有$f_{u,a}*f_{v,b}\to f_{u,\max(a+b,0)}$.

转移显然是卷积形式,但问题是值域很大,不过容易发现一个方案是否合法只和相对大小关系有关,一般这种情况可以猜多项式,归纳容易证明$f_{u,x}$是关于$x$的$siz_u$次多项式,于是只存前$siz_u$个点值即可.

转移的时候,要先把点值扩张到$siz_u+siz_v$,即我们要支持已知一个多项式的点值快速求另一些点值,直接写成拉格朗日插值,形式就是卷积,扩张完了之后直接卷即可.

Day6

模拟赛

A

原题是P5972 [PA2019] Desant

考虑dp,则若从前往后dp到第$i$个,我们只需要记录前$i-1$选了哪些数,在注意到我们只要记录考虑$[i+1,n]$把整个序列划分成若干个区间,只要记录每个区间里有几个数,以这个为状态就过了.

分析考虑你的状态数实际上是求$\sum_i a_i=n,\max \prod a_i$,容易发现是$3^{\dfrac{n}{3}}$的.

B

先考虑$n=2$,显然每个点值经过一次,而且这种东西应该考虑分治,且若从第$l$列走到第$r$列($l<r$)一定只会从左往右走,于是一个分治区间内的子问题不会走到外面,此时只要对$(mid,1),(mid,2)$处跑单源最短路,设左边第$i$个点经过$(mid,x)$的距离为$a_{x,i}$,右边是$b_{x,i}$,那么你想算$\sum_{i,j} \min(a_{0,i}+a_{1,i},a_{2,i}+a_{2,j}$

C

经典结论是背包在体积模$\mathrm{lcm}(w_1\ldots w_n)$的每个等价类是凸的,而显然$b_i$相同的时候模$b_i$的位置是凸的,跑闵和即可.

另一个做法是凸函数和非凸函数做max+卷积可以决策单调性单log,所以就不依赖背包数组的凸性了.

课

AGC043C

首先图的笛卡尔积在说什么,相当于你在三个图上各有一个点,每次挪动一个位置,形成的图.

显然我们要贪心,按$x+y+z$从大到小能选就选,那么把边从$(x+y+z)$小的连到大的,则你会选所有没有出边的点,然后连到他们的点不能选,再往下可以选,那么我们看成三张图的组合游戏,于是答案就是所有先手必败点的权值和.而因为三个图独立所以直接求SG值做异或就是合并的SG值.

注意到SG值最大是$\sqrt m$,暴力做异或卷积即可.

AGC034D

把曼哈顿距离转化成$4$个max,于是建$4$个点表示四种绝对值是否取负情况,$S$向所有代表红球的连边,红球向$4$个虚点连边,再向蓝球连边,再连到$T$.

可以模拟费用流做到$n\log n$.设点是$S\to R_i\to F_{1\ldots 4}\to B_i \to T$.就是最短路一定是从$S\to R_i\to F_{q_1}\to R_{p_1}/B_{p_1} \ldots F_{q_k} \to B_j \to T$,用堆维护出$S\to F_i,F_i\to T$,$F_i\to F_j$(只经过一个中转点)的最短路径,然后跑全源最短路.

loj6703. 小 Q 的序列

考虑一个dp,直接做自然是$f_{i,j}$表示前$i$个选了$j$个,$f_{i,j}=f_{i-1,j}+f_{i-1,j-1}(a_i+j)$,然后直接GF,容易发现这里对$i$列GF是困难的($a_i$是点
乘),于是$F_i(x)=(1+a_ix+x^2\mathrm{D})F_{i-1}(x)$,然后不会了.

做一个转换,$k=i-j$,有$f_{i,k}=f_{i-1,k-1}+f_{i-1,k+1}(a_i+i-k)$,就又$F_i(x)=(x+(a_i+i)-x\mathrm{D})F_{i-1}(x)$.

再做变换$G_i(x)=e^{-x}F_i(x)$,有

$$
e^{-x}F_i(x)=x(e^{-x}F_{i-1}(x)+e^{-x}F_{i-1}’(x))+(a_i+i)F_{i-1}(x)\
G_i(x)=xG_{i-1}’(x)+(a_i+i)G_{i-1}(x)\
g_{i,j}=g_{i-1,j}(a_i+i+j)
$$

于是直接有$g_{n,i}=g_{1,i}\prod_{j=1}^n(a_j+j+i)$,设多项式$\prod_{j=1}^n(a_j+j+x)$多点求值就做完了.

[think] 感觉关键在于我们的目标是让后面的项和前面尽可能少的项有关,另外导数的次数是重要的(会有较大影响),对此多尝试一些变换.然后就是用$e^x$合并导数和常数部分.

ARC105F

考虑一个连通二分图只有两种染色,那么对于一种点的染色相当于要求一些边能选一些边不能选,选出连通图的方案数.

考虑容斥,对任意一个图,是一个包含$1$的连通块和剩下一个任意图,于是设$f_S$表示子集$S$是连通二分图的答案,$g_S$表示子集$S$是二分图的答案,就有$f_S=g_S-\sum_{T\subsetneq S} 2f_Tg_{S/T}$.

暴力是$3^n$,可以半在线子集卷积搞成$n^22^n$

别容斥了,不如集合幂级数ln,对$g$直接ln就好了啊.

loj2398. 「JOISC 2017 Day 3」自然公园

首先怎么确定一条链,若已知两个链头链尾,容易找到一个$i$使得保留$1\ldots i$连通而$1\ldots {i-1}$不连通,此时必有$i$在这条链上,分成左右两边递归下去,复杂度是$n\log n$.

于是现在考虑维护一个与$0$相连的连通块,每次加入一个与这个连通块有边的点,那么对连通块dfs序编号,容易二分到这个点和这个连通块第一个相连的点,删掉它分裂成多个连通块递归找到其他所有边,每个连通块只要一次二分.

最后要能找到一个与连通块有边的点,那么随便找到一个点和连通块中一个点,用链的方法递归的找即可.

loj3038. 「JOISC 2019 Day3」穿越时空 Bitaro

经典套路先给$L_i,R_i$分别减去$i$,就没有走路需要消耗$1$个时间的代价了.

然后考虑线段树,若序列$[l,r]$中的所有区间有交我们只要记录这个交,如果无交那么发现进去之后走法是唯一的,一定是贴着边走,仍然可以线段树维护(记录进入区间和出口).

复杂度单log.

JOISC 2020 Day1 扫除

首先考虑如果没有加点,那么发现所有被操作过至少一次的点是一个左上到右下的阶梯,于是可以用平衡树维护阶梯实现操作.

但现在有加点会破坏阶梯的性质,考虑线段树分治,用修改和查询把点的存在时间分到区间上,每次先处理左区间,然后把左区间处理完后每个点传到右区间作为起始位置.

复杂度$n\log^2 n$

P5606 小 K 与毕业旅行

看到这个相邻两项乘积/和不大于啥,考虑扫值域dp连续段,把每个数在$\min(x,m/x)$(在对于$x>m/x$,$x$在这之前必须是孤立点)处插入,可以做到$n^2$.

考虑构造更好的转移顺序,使得可以把点分成两类,A类点和后面每个点都满足条件,B类点和后面每个点都不满足条件,那么每插入一个B类点已让空位减少$1$,每增加一个A类点让空位增加$1$,就能线性了.

然后考虑负数,显然一正一负一定能拼

Day7

模拟赛

A

容易发现一定有一个全集一个空集,对剩下的四个集合容易想到它们之间的”结构”不多,于是想到考虑有2^{m-2}$种不同状态的元素(被哪几个集合包含),每个状态的元素是一个集合,若确定这些集合显然就确定了答案,然后$2{2^{m-2}}$的枚举每个状态集合是空的的情况去check,显然若有$f_i$种方案有$i$个非空集,答案就是$\binom{m}{2}{n\brace i}f_i$,就做完了.

B

容易想到匹配,但匹配之间的限制不能直接做,考虑网络流,直接二分答案,然后每个时间建一层图,每层图的每个点再拆两个点中间连$1$限制不能相交,然后跑最大流就行了.

C

容易想到枚举相同的前缀,于是问题变成了一棵树儿子大于父亲拓扑序,且限制若干点等于某值,限制一个点大于某值的方案数,这个东西就直接从大到小排序二项式系数选一选就行了啊.

课

CCPC Final 2022 E

因为排列设$(x,y)=(a_u,b_v)$.

不妨设$u<v$,那么$u$之后的每次取$max/min$是确定的,且设$y$在$u$时刻是$y$,经过若干次取max/min后最后得到的值一定是$\min(\max(y,c),d)$的形式,于是$y$一定是$c,d$中的一个.只要能维护$y$可能取值的最小值或最大值即可,这个用值域线段树维护$x=i$处时$y$的值,每次是对一个区间取max/min.

对$u>v$同理,考虑$u=v$,前面一定都取max/min,后面要满足$c,d$的限制,也容易判断..

Shenzhen 23 C

首先注意到$k$可以模$7$,只要考虑$k=1\ldots 6$.

直接dp是$f_{i,s_1\ldots s_6}$表示考虑前$i$个,前$i$个$k=1\ldots 6$的和模$7$分别是多少,复杂度$n7^6$看起来就过不了.

注意到模$4,5,6$分别相当于模$-1,-2,-3$,即若某个$k\in{4,5,6}$的奇数位和偶数位带权和分别是$a,b$,则要求$b-a\not\equiv 0\pmod{7}$,于是对奇数偶数分别跑dp,然后枚举顶到的上界位置合并,枚举偶数的一项,把对$b$的限制$[a\ne b]$容斥成$1-[a=b]$,容斥复杂度是$3^3$,总复杂度$n21^3$

ECF2023C Equal Sums

直接dp,设$f_{i,j,s}$表示一边前$i$个,一边前$j$个,差为$s$.

转移的时候若$s>0$加一个$y$,$s<0$加一个$x$,就能保证$\vert s\vert\le 500$,优化到$n^3$.

Day8

模拟赛

A

显然看起来大多数数都直接相同的两两匹配消了,现在还剩下若干个$x\bmod 2$.另外容易发现奇数的话我们已经钦定了大小关系,后面可以直接确定;偶数的话,考虑一定是前面一段上下相同的,紧接着两个可能不同的,直接枚举这两个数,此时大小关系又被确定,可以按照奇数的填.

然后就是一些细节,比如答案可能很大需要高精度;若枚举的两个数正好差$1$,可能存在前面把两个$0$或$9$放到后面的情况;若枚举完前面只剩$0$需要把这些$0$放到后面填.

B

容易想到LGV,于是只要能算$1/2 \to n-1/n$的方案数.

注意复杂度关于交点个数是没啥问题的,dp即可.

为了减小常数,std是每次加入一条弦,记录$f_i$表示第$i$条弦最后一个交点处的方案数.

C

首先你可以直接根据排列得到唯一的$n-1$项rand序列,容易想到设一开始种子的每一位是$x_0\ldots x_w$,则可以表示出之后的每一个数为$\sum_i w_i \sum_{j\in S_i} x_j$的形式,同时,若$x\equiv a\pmod p$,$p=q\times 2^t$,就能列出关于$x$的$2^t$个同余方程,然后可能不满秩,但可以枚举自由元的取值,就做完了.

课

Qoj7901. Basic Substring Structure

考虑修改一个位置$x$时,若一个后缀的lcp$y<x-1$一定没变,若$y\ge x$一定会变成$x-1$,只要考虑$y=x-1$的后缀,显然每个后缀只在$x$的一个修改方案有$y=x-1$,那你就直接枚举所有有至少一个$y=x-1$的修改方案暴力算lcp即可.

P9623 [ICPC2020 Nanjing R] Baby’s First Suffix Array Problem

考虑先假装后缀的顺序就是sa中的顺序,而不对,即$rk_a<rk_b,s_{a\ldots n}>s_{b\ldots n}$当且仅当仅考虑这个区间,$b$是$a$的前缀,在这个区间外能比出来,考虑数这种反例.

那么分成两类,设询问的是后缀$s_{k\ldots n}$,而$i$与其构成反例.

若$i<k$,则限制为$l\le i\lt k\le r,rk_i\lt rk_k,lcp(i,k)\ge r-k$,容易发现$lcp(i,k)\ge r-k$在$rk$的限制上是一个区间,所以这是个二维数点.

若$i>k$,则限制为$l\le k<i\le r,rk_i>rk_k,lcp(i,k)\ge r-i$.考虑这其实是一个$[k,r]$这个区间的border,于是只要能求区间字符串的border,这个东西考虑基本子串字典.

另一种做法是对着上面的上DS,考虑cdq分治,计算右边的$i$对左边的$k$的贡献,那么扫出$pm_i$,$sm_i$分别表示左右两边的前缀min,则限制就是$pm_i+i\ge r,sm_k+i\ge r,k\lt i$这样,这样剩下的问题是个二维数点,直接做就好了.复杂度$n\log^2 n$.

Uoj608. 【UR #20】机器蚤分组

首先考虑这是一个最小链覆盖,那么转化成最长反链覆盖,而一个反链一定可以调整成长度相同的,所以答案其实是 某长度的本质不同子串个数 的最大值.

再注意到,当长度大时主要收区间限制,当长度小时主要是字符串内容限制,于是注意不到,当且仅当长度$k$满足区间内所有长度$k$的所有串互不相同时,答案由$k$产生.直觉考虑若这个长度有两个串相等,那么这两个串的所有对应子串都相等,容易发现长度更短不优.

于是对全局,答案既是$n-\max_{i<j} lcp(s_{i\ldots n},s_{j\ldots n})$,放到后缀树上就对应lca,那么在后缀树上对endpos启发式合并,每次合并两个集合时,有贡献的只有合并两个集合归并起来后,相邻两项来自不同集合的对,这个显然只有$n\log n$对.剩下就是简单ds.

Uoj656. 【ULR #2】霸占排行榜

对AC自动机跑DAG剖分/kx

考虑肯定是把$T$在AC机上跑一遍,考虑先求$dir_{u,i}$表示$u$走过$s_i$后的位置,$end_{u,i}$表示最大的$j$使得$u+s_{i,1\ldots j}$还在AC机中.把匹配$s$的过程分成$u\to end_{u,i}\to fail_{end_{u,i}}\to dir_{u,i}$,考虑$v=fail_{end_{u,i}}$,若$dep_v\le dep_{end_{u,i}}-dep_u$,相当于$u$的信息全丢了,可以直接从$1$开始匹配,即$dir_{u,i}=dir_{1,i}$,否则可以看出只有$u$长为$l=dep_v-(dep_{end_{u,i}}-dep_u)$的后缀是有用的,那么在 fail 树 上跳直到这个串的长度(即$dep$)为$l$即可.

则若已知每个$end_{u,i}$,我们可以$O(nl)$求出每个$dir_{u,i}$,然后对每个$s$单独做,我们知道它在每个位置被插入了多少次,求每个节点被经过次数.仍然沿用上面的讨论,把一个节点开始走一个$s$的过程拆成$u\to end_{u,i}\to dir_{u,i}$,第一部分是一个祖先链加,第二个部分可以递归的做,就可以$O(nl)$的解决这个问题.

于是考虑怎么求$end_{u,i}$,树剖,则对于一条链能走多远是一个lcp的问题,可以exkmp,直接跳容易做到$nl\log n$.然后把要从一个位置开始跳一个$s$的后缀这个询问挂在轻儿子上.把所有$s$的后缀排序,对一个轻子树,按照字典序从小到大遍历这些后缀则每个点只会经过一次.于是复杂度就是轻子树大小和$l\log l$了.

总复杂度是$nl+l\log l+S\log S$,$S=\sum_i \vert s_i\vert$.

重点是,把AC自动机上匹配分成$u\to end_u\to dir_u$使得可以递归处理,以及把问题分成重链+轻子树.

Uoj772. 【UER #11】企鹅游戏

考虑AC自动机后,问一个串就是走一遍,每次到根的链加.但你当然不用都加,注意到$s$在$t$中的出现次数是$L^{4/3}$量级,那么只要记录AC自动机上每个点到根的链上第一个代表$s$中元素的节点,往上跳,且不跳相同的节点即可.

CF1909G Pumping Lemma

枚举$s$中$y$和$z$的分界线,则现在要求$y^{k-1}$有多少个循环节同时是$x+y$的后缀.而是$x+y$的后缀就是要求$\vert y\vert \le LCS(s_{1\ldots i},s_{i+1\ldots i+(n-m)})$,那么当$i$增加的时候只要比较$s_{i+1}$和$s_{i+n-m+1}$,若不相等清空可行集合,否则可行的$y$集合中增加一个,而原来集合的每个都是可以的,于是只要hash检验新增的这个,就做完了.