本篇博客记录了从2019.9.1至2020.2.24日在CF（不包括Gym）做的共143道题的收获（查漏补缺）。
在补了，在补的路上了
图论
Tarjan算法
点双的tarjan算法中通过dfn序压栈，并更新low的值if(vis[q])low[p]=min(low[q],low[p]);，当某个节点$p$的dfn序和low相等时，就将栈中从$p$开始的所有元素全部染色。
另外还有无向图求割点的Tarjan算法，这里更新low的时候注意应是min(low[p],dfn[q])，因为有可能在父节点已经有过一个返祖边更新过low，这样会导致割点的缺漏。
两个算法的low表示的含义并不一致，一个是表示能联通到的最早的地方，一个是表示可以绕到的割点的地方。于是在求割点时，如果是根节点且有多于一个子树；或者不是根节点且存在某个孩子的low大于等于当前节点的dfn（此时这个孩子没有路径回到这个点），这个点就是割点。
边双连通分量只需要割掉桥，在实现中如果孩子的low大于当前节点的dfn，那么这条边就是割边。
CF1220E Tourism
给一个无向连通点权图，问从$s$出发、不连续经过同一条边的情况下能得到的最大权值和。
能够显然的观察到，最终一定是一堆环加上一条只能通到叶子的链。
解法1：当时用到的做法，通过求出点双、进行各种分类讨论的$dfs$，码量和$debug$难度都很大。
解法2：边双，$dfs$一下就能发现哪些节点只能通到叶子，并记录下相关权值。
解法3：通过解法$2$，其实已经得出这种做法：将叶子逐个删去，并将权值信息合并到它的父亲节点上，最后剩下的节点一定是都能到达的，对于所有叶子链的值再取一个最大值即可。这里令起点$s$的度数为$inf$，很巧妙。
CF1230D Marcin and Training Camp
$n\leq 7000$个人，每个人有个能力值，一共有60个算法，每个人知道其中一个集合，用一个$long\text{ }long(a_i)$表示。$i$觉得自己比$j$厉害当且仅当$i$知道某个$j$不知道的算法。一个集合是好的当且仅当没有人觉得自己比别人都厉害；一个集合的权值是集合中所有人的能力值之和。问这些人组成的好集合中权值的最大值。
解法1：$i$不觉得比$j$厉害，当且仅当$a[i]|a[j]=a[j]$。此时，连边$(j,i)$，表示$j$克制住了$i$，即如果选中了$j$那么可以选择$i$。对图进行缩点，缩出来的点如果包含大于等于两个元素那么就成立（连通块内互相牵制）；如果某个点的祖宗成立，那么这个点也成立（连边条件），故在形成的$DAG$上跑一遍即可。
解法2：可以注意到这个题有一个隐含条件：上述解法所谓“缩点”的结果只会是几个相同的元素，而连边$(j,i)$则必然是$j$的$a_j$包含了$i$的$a_i$，即$a_i$是$a_j$的子集。故首先将所有的具有相同$a_i$的元素加入最终答案集合，然后枚举所有集合外的元素，如果是集合中某个元素的子集，那么加入其中即可。
2-sat
CF1215F Radio Stations
$p$个广播电台，每个广播电台$i$有一个可行区间$[l_i,r_i]\in[1,M]$，有$n$个要求（$x_i$号电台或$y_i$号电台至少选一个），$m$对不能同时选择的广播电台$(u_i,v_i)$，求一个可行的方案满足要求且对应的可行区间的交非空（即$\exists f,\forall i\in[1,p],f\in[l_i,r_i]$）。$n,p,M,m\leq 4e5$。
解法：首先对$n$个要求和$m$对互斥的条件进行普通的$2-sat$连边，然后对于每一个电台，有“选中了$i$那么$f\in[l_i,r_i]$，这里考虑连边，不可能抽象出$M^2$个点$[l,r]$，而是考虑抽象成$f\leq x$的形式，即满足$f\leq r_i$且不满足$f\leq l_i-1$。然后$f\leq x$和$f\leq x+1$之间进行联系补全关系。
最短路
CF1209F Koala and Notebook
给一个$n\leq 1e5,m\leq 1e5$的图，每个边有一个编号$i$。一条路径的长度是把这条路上所有边对应的编号连起来（如$1+2\rightarrow 12$），问从$1$到每个节点的最短路。
解法：将边拆成多个点，相当于每个点然后跑一遍bfs即可。
数据结构
线段树
CF620E New Year Tree
给一棵$n\leq 400000$的树，$m<400000$次操作，每次操作染某子树所有点为某个颜色$c\leq 60$或查询颜色数。
解法：$dfs$序上线段树，用二进制状态压缩表示区间包含的颜色种类情况。
CF750E New Year and Old Subsequence
给一个$n\leq 200000$的串，$q\leq 200000$次询问一个区间里最少要去掉几个元素才能满足包含子序列“2017”但不包含子序列“2016”。
解法：详细题解（C题）用线段树维护状态转移矩阵$f$，其中$f[i][j]$表示区间中当前构成的串具有$2017$前缀长度为$i$的子串转化为长度为$j$的子串至少要删掉的元素个数，则最后答案就是询问区间的$f[0][4]$。合并时用类似矩阵乘法的$min(a[i][k]\times b[k][j])$合并。
CF1221F Choose a Square
平面上$n\leq 5e5$个带权点，问在直线$x=y$上选两点$(l,l)(r,r)$作为正方形左下角、右上角，问圈起来的所有点的权值减去正方形边长的最大值。
解法：容易想到枚举左端点找右端点最值，一个点$(x,y)$（设$x\leq y$）位于正方形$[l,r]$中当且仅当$l\leq x\leq y\leq r$，故从大到小枚举$l$，依次加入合法的（$x\geq l$的）点即可。
Trie
CF888G Xor-MST
$n$个点的完全图，每个点有一个数值$a_i$，某个边$(u,v)$的权值为$a_u\oplus a_v$，求最小生成树。
解法：首先对节点排序。画一下$trie$可以发现，我们要尽可能让连边位于两点$LCA$较低的地方，所以从高位到低位遍历一下$trie$，设$calc(pos,l,r)$表示$i\in[l,r]$连通的代价，$minxor(pos,l_1,r_1,l_2,r_2)$表示左区间位于$[l_1,r_1]$，右区间位于$[l_2,r_2]$的两元素最小异或值，有
$calc(pos,l,r)=calc(pos-1,l,mid-1)+calc(pos-1,mid,r)+minxor(pos-1,l,mid-1,mid,r)+(1<<pos)$
即：$pos$位为$0$的自己内部连通、$pos$位为$1$的自己内部连通、两部分连通。有些特殊情况判断一下即可。
求$minxor$也可以通过类似的方式递归进行。
CF778C Peterson Polyglot
给定一棵字典树，问删掉哪一层剩下的节点最少。删掉某一层是指把字典树所表示字符串集合中所有字符串某个位置的字符清空。字典树$size\leq 3e5$。
解法：从下到上暴力枚举每一层并进行合并，用左偏树或者线段树合并的方式进行合并（如果两个子树都有那么新建节点递归继续合并，否则返回），则总复杂度为合并的节点的数量级。合并的节点的数量级证明极为巧妙，记录一下。
（这里需要回来看，感觉证明不太严谨！）不妨设总合并次数为$x$，再设任意节点$q$子树的大小为$siz_q$，。对于节点$p$，对$x$的贡献来自于对其某些（并非全部）祖宗节点（从下到上依次为）$v_1,v_2,…,v_c$（$p$分别做$v_i$节点的第$d_i$深子树）合并时的贡献之和，而由于字典树合并时显然有合并长度小于等于较短的那个的长度，于是$siz_{v_i}\leq \frac{siz_{v_{i+1}}}2$，于是$siz_{v_1}\leq \frac{siz_c}{2^{c-1}}\leq \frac{n}{2^{c-1}}$，故$c$为$\log n$级别，即$p$对$x$的贡献是$\log n$级别的。于是总合并次数在$n\log n$次，复杂度即可保证。
玩游戏
分类讨论
CF1221E Game With String
给一个只含有.X两种字符的字符串和两正整数$a,b(a>b)$，AB两人轮流走，谁不能走就输了。A每回合能把连续的$a$个.变为X；B每回合能把连续的$b$个.变为X。两人都采取最优策略，问先手能否赢。
解法：暴力讨论。首先将所有连续且长度不小于$b$的‘.’区间找出来。对区间长度$l$分类讨论：
$b\leq l<a$：存在则显然后手胜。
$a\leq l<2b$：两人都只能玩一次，记录下来这种区间的个数$num$。
$l\geq 2b$：如果后手操作这块区间，那么必然可以构造出长度为$b$的一块区间，直接胜利。故如果有$\geq 2$块这种区间，则先手负；否则先手要试图破坏这种区间，使之成为第二种区间。
Nim博弈
字符串
数论
FFT
CF993E Nikita and Order Statistics
给定数组$a$和整数$x$，问对于每一个$i\in[0,n-1]$，有多少个区间满足比$x$小的元素个数恰为$i$。
解法：将数组$a$转化为01数组$b$，$b_i=1$ 当且仅当$a_i<x$。枚举区间左端点$l$，假设$l$左边（不包含$l$）的$b$中元素之和为$y$，则若右端点$r$左边（包含$r$）的$b$元素之和为$y+i$，就满足$[l,r]$中比$x$小的个数恰为$i$。记$b$的前缀和为$s$，$s$中元素出现次数为$cnt$，则$i>0$时有答案$ans_i=\sum_{y=0}^{n-i}cnt_ycnt_{y+i}$，这个式子在$i=0$的时候不能保证左端点$<$右端点，故需要特判。这是个卷积形式，用FFT处理一下即可。
神秘性质
CF1230E Kamil and Making a Stream
定义一个路径$(u,v)$的$f$为$\gcd(u,…,v)$，给定一棵树，求$\sum_{i,j}f(i,j)$。
解法：暴力在每个节点上打一个一直到根的$\gcd$的$map$记录各种出现次数。这样复杂度正确的保证是，一条链从上到下依次$\gcd$，最多不会超过$\log max$个不同的数。
CF990G GCD Counting
求每个$f(i,j)$出现的次数。
解法：通过同样的性质进行点分治。
推式子
CF933D A Creative Cutout
当二维直角坐标系的格点上有$n$个以原点为圆心的圆，下标分别为$1,2,…,n$，半径分别为$\sqrt 1,\sqrt 2,…,\sqrt n$时，平面上所有点的美丽值之和设为$f(n)$，对于正整数$m(m\leq 10^{12})$，求$\sum_{i=1}^{m}f(i)$。
一个点$(x,y)$的美丽值为：所有包含（包括在边界）这个点的圆的下标之和。
解法：首先我们注意到，$\sqrt {10^{12}}=10^6$，故可以考虑枚举$x$，$O(1)$求出所有$y$的贡献之和。
需要记住这个式子：$\sum_{i=L}^{R}C_{i}^{x}=C_{R+1}^{x+1}-C_L^{x+1}$。其实就是对$C_i^{x}=C_{i+1}^{x+1}-C_{i}^{x+1}$求和。
按照定义大力推式子，当圆个数为$n$时，点$(x,y)$的美丽值为$\sum_{j=x^2+y^2}^{n}j$。故点$(x,y)$对答案的贡献为
$\sum_{i=x^2+y^2}^{m}\sum_{j=x^2+y^2}^{i}j=\sum_{i=x^2+y^2}^{m}C_{i+1}^2-C_{x^2+y^2}^2$
$=C_{m+2}^3-C_{x^2+y^2+1}^3-C_{x^2+y^2}^2(m-x^2-y^2+1)$
$=\frac 16((m+2)(m+1)m-(x^2+y^2+1)(x^2+y^2)(x^2+y^2-1)-3(m-x^2-y^2+1)(x^2+y^2)(x^2+y^2-1))$
$=\frac 16 ((m+2)(m+1)m-(3m+4)(x^4-x^2+(2x^2-1)y^2+y^4))+2(x^6-x^4+(3x^4-2x^2)y^2+(3x^2-1)y^4+y^6)$
预处理出来$y$的$2,4,6$次幂前缀和即可。
DP
状压DP
CF1209E2 Rotate Columns (hard version)
$t\leq 40$组数据，每组一个$n\times m(n\leq 12,m\leq 200)$的矩阵，列可以随意旋转，问最后每行最大值之和的最大值。
解法：首先观察到，只需要考虑最大值在前$m$个的列。然后用$f[col][state]$表示到第$col$列，最大值状态为$state$的最大和，转移通过$3^n$的子集枚举，预处理一下$sum[col][state]$表示第$col$行，$state$位置的最大和即可。复杂度$O(t(3^n+2^nn^3))$。
SOS(Sum over Subsets) DP
子集和$dp$，本质就是$FWT$
dp思路：设$F[mask]=\sum_{i\subseteq mask}A[i]$，$mask\in[1,2^k-1]$，我们要快速求得所有$F$。
思路1：直接枚举子集，复杂度$O(3^k)$
思路2：设$g[mask][i]$表示和$mask$只有最后$i$个位可能不同（$x\subseteq mask,x\oplus mask<2^{i+1}$）的$A[x]$的和。则
$g[mask][i]=\begin{aligned} &g[mask][i-1],&2^i\not\subseteq mask\\ &g[mask][i-1]+g[mask\oplus 2^i][i-1],&2^i\subseteq mask\end{aligned}$
$F[mask]=g[mask][k-1]$。
滚动一下第二维，实现：
1 | for(i=0;i<(1<<k);i++)F[i]=A[i]; |
这样就能$O(k2^k)$地快速求出$F$了。
Special Pairs
（混入了奇怪的东西）给序列$a(a_i\leq 1e6)$，问有多少对$(i,j)$满足$a_i\text{ and }a_j=0$。
解法：$g[i]$表示$i$出现的次数，$f[i]$表示$\sum_{j\subseteq i}g[j]$，答案即为$\sum_{i}g[i]f[((1<<k)-1)\oplus i]$。
CF165E Compatible Numbers
$(a,b)$好当且仅当$a \&b=0$。给定一个数组，对于每一个$i$，求出使得$(a_i,a_j)$好的$a_j$。$n\leq 1e6,a_i\leq 4e6$。
解法1：观察到如果求出来了$(a,b)$好，那么对于$a$的子集$s$，有$(s,b)$好。$f[i]$表示让$(i,a_j)$好的$a_j$即可。
解法2：也可以通过SOS DP解决，类似上题，其中$g$记录的是任意一个位置或值本身即可。
CF383E Vowels
给定$n$个$a-x$组成的单词$len=3$，定义一个单词是好的当且仅当这个单词中存在元音。对于每个$i\in[1,2^{24}-1]$，求出$f[i]$，表示$i$所表示的集合作为元音时，好单词的个数。
解法：令$g[1<<i]$表示字母$i$作为元音的时候好单词的个数，那么$F[i]=\sum_{j\subseteq i}g[j]$可以通过SOS DP求得。对于一个单词中的每一个字母都使得$g[1<<i]++$，在求和的时候会有重复计算，故使用容斥。
CF1208F Bits And Pieces
给定一个数组$a(a_i\leq 2e6,n\leq 1e6)$，求出$max(a_i|(a_j\&a_k))(i<j<k)$。
解法：从后往前枚举$i$，添加“与”操作有关的值。每添加一个数，就将其所有子集加入$cnt$数组，当某个数$num$的$cnt[num]\geq 2$时，表示后面有两个数可以将$num$的某个父集与出来，故询问的时候从大到小试探$cnt$数组，加入的时候记忆化一下，$cnt>2$就不要往下走了（注意，=2的时候不能保证所有子集的$cnt$都被更新！），保证复杂度即可。
SOS DP的递推式$F[mask]=\sum_{i\subseteq mask}A[i]$中，即是求满足$i|mask=mask$或者说$i\&mask=i$的$A[i]$之和，因此在求$g$的时候，才会有$x\subseteq mask,x\oplus mask<2^{i+1}$的设定。
$g[mask][i]=\begin{aligned} &g[mask][i-1],&2^i\not\subseteq mask\\ &g[mask][i-1]+g[mask\oplus 2^i][i-1],&2^i\subseteq mask\end{aligned}$
而如果想求$F[mask]=\sum_{mask\subseteq i}A[i]$，保持$g$的意义不变，设定变为$mask\subseteq x,x\oplus mask<2^{i+1}$，递推式变为：
$g[mask][i]=\begin{aligned} &g[mask][i-1],&2^i\subseteq mask\\ &g[mask][i-1]+g[mask\oplus 2^i][i-1],&2^i\not\subseteq mask\end{aligned}$
CF449D Jzzhu and Numbers
给定一个数组$a(a_i\leq 1e6,n\leq 1e6)$，求有多少个子集满足所有元素相与为$0$。
解法：通过如上所述的变形SOS DP，容斥即可。
普通DP
CF1189F Array Beauty
给定一个$n\leq 1000$的数组$a(1_i\leq 1e5)$，定义一个长度为$k\leq 1000$的数组$b$的美丽值为$min_{i,j}|b_i-b_j|$。求所有长度为$k$的$a$的子数组的美丽值之和。
解法：NB结论1：假设$f(x)$表示美丽值至少为$x$的子数组个数，那答案就是$\sum_{x=1}^{upp} f(x)$。NB结论2：$x$的上界$upp$只需要取到$\frac{max(a_i)}{k-1}$。然后这题就做完了。（排序后直接$DP$，$O(nk)$地求出$f$即可）
CF687C The Values You Can Make
给一个$n\leq 500 $的数组$c(1\leq c_i\leq 500)$，问每个元素最多取一次，组成一个集合$S$，其中$S$中元素之和为$k$的时候，$[1,k](k\leq 500)$以内的数哪些可以被这个集合表示。
解法：看数据范围$nk^2$是可行的，容易想到用$f[n][k_1][k_2]$表示在前$n$个元素中，如果能表示出$k_1$，能否表示$k_2$。状态转移是如果$f[n-1][k_1][k_2]=1$，那么$f[n][k_1+a_i][k_2]=f[n][k_1+a_i][k_2+a_i]=1$。
杂项
思维转化
CF1244E Minimizing Difference
给一个数组，求$k$步（每步可以让某个元素减一或加一）以内之后，极差的最小值。
解法：如果没有考虑到，让极差每减一花费最少的贪心方式（从左或右减去有关个数），可能不太容易做出本题。
CF957E Contact ATC
在一位坐标系上，有$n$个朝着原点飞的飞机，给定速度和位置。给定风速的范围$[-w,w]$，保证风速赶不上任何一架飞机的速度，问有多少对飞机满足$\exists v\in[-w,w]$使得它们共同到达原点。
解法：求出风速分别为$-w,w$时每架飞机到达终点所需时间，分别计为$a_i,b_i$，答案即为$a_i\leq a_j$且$b_i\geq b_j$的$(i,j)$的对数，这是经典的二维偏序问题。
01分数规划
CF994F Compute Power
$n\leq 50$个任务，每个任务$a,b$两个属性$(1\leq a_i\leq 10^8,1\leq b_i\leq 100)$。有一些机器，每台机器可以执行最多两次任务，执行两次的时候要求第二个任务比第一个任务的$a$小。设第一次执行任务的集合为$S$，最小化$\frac{\sum_{i\in S}a_i}{\sum_{i\in S} b_i}$。
解法：根据01分数规划套路，二分答案$m$，即求${\sum_{i\in S}a_i-mb_i}\leq 0$能否满足。按$a$从大到小排序，合并一下相同的项（可以在$dp$的时候进行这一步，要记录第$i$项有$cnt_i$个），按顺序枚举，分别加入$S$或补集$C_US$，有任意时刻$S$中元素多于$C_US$。于是设$f[i][j]$表示到$i$，有$j$个分配到$1$且可用（可分配一个$2$）的任务的最小值，则对于一个$i$，枚举分配给第二个任务的个数$k\in[0,cnt_i]$，有
$f[i][j+(cnt_i-k)-k]=min(f[i][j+(cnt_i-k)-k],f[i-1][j]+(cnt_i-k)\times (a_i-m\times b_i))$
这题需要记录的地方在于，将相同的项合并，从而简化$dp$过程。