杂记+CF题记录

· · 个人记录

Why Not

锤子题乱做：

CF103E Buying Sets

最大权闭合子图。 牛逼建模。

AT3913 XOR Tree神题。

边权转点权，两两对消，再加结论：每一个异或为0的子集都可以使操作数-1. 变成了使全集划分出的子集尽量多。直接枚举子集转移即可。

满足交换律的运算，计算顺序不影响结果，都可以使用前缀和优化，每次只有一个子集转移，比如异或。

CF1144G Two Merged Sequences 在序列中不连续的取两个集合，或者点集中取多个集合，可以考虑在满足一个的时候使其他的限制尽可能的松，只要证明这样不会使答案更劣，贪心就是对的。

这题记录 f[i][0/1] 表示第i位在递减/递增序列中，且递增/递减序列的结尾最小/最大是多少，记录这个符合条件转移即可，如果不符合那就必然选不上。

CF906C Party连通性状压DP

状压要注意数组下标范围，最好预处理lim。操作顺序不影响操作结果的题，钦定某个状态由哪边转移，或者每次枚举单次操作更新。

CF1139D Steps to One 数论好题。

E(X)=\sum_{i\geq 1}P(X=i)i =\sum_{i\geq 1}P(X=i)\sum_{j=1}^i1 =\sum_{j\geq 1}\sum_{i\geq j}P(X=i) =\sum_{j\geq 1}P(X\geq j) =1+\sum_{j\geq 1}P(X\gt j) =1+\sum_{j\geq 1}(1-P(\gcd(a_1,a_2,\cdots,a_j)=1)) =1+\sum_{j\geq 1}\frac {m^j-\sum_{k\geq 1}\mu(k)\lfloor\frac{m}{k}\rfloor^j}{m^j} =1-\sum_{k\geq 2}\mu(k)\sum_{j\geq 1}\left(\frac{\lfloor\frac{m}{k}\rfloor}{m^j}\right)^j =1-\sum_{k\geq 2}\mu(k)\frac{\lfloor\frac{m}{k}\rfloor}{m-\lfloor\frac{m}{k}\rfloor}

P3749 [六省联考2017]寿司餐厅 网络流：最小割，最大权闭合子图。 注意强选的条件和 正权sum-flow的转化即可。

CF1348F Phoenix and Memory

一句话题意：问是否存在唯一一个 1~ n 的排列 c ，满足 a_i \leq c_i \leq b_i

首先构造出一个可行解，通过贪心。即对于每个位置我们选择满足条件的右端点最小的区间。这对之后的构造影响最小，故贪心正确。考虑如何构造出更多的可行解。

每个区间[l,r]都有确定的x 我们找到两个区间使得 [l1,y,r1] [l2,x,r2]。

可以考虑建出区间并ST表，对于每个区间二分答案，得到 O(nlog^2n)的解法。

我们给出的限制有些多余，事实上只需要满足 L_y\leq x\lt y\leq R_x

通过枚举y满足 x\lt y 将 y\leq R_x 的x加入set，再查询最大的x即可。

也就是说：枚举确定一个符号，set保证一个符号，剩下一个符号check

CF464E The Classic Problem

最短路，但是值域 2^{100000}

考虑用一个数据结构维护。要实现比较和单点+1

每次扩展直接主席树。

单点加一相当于一段区间置零，建一个全零的线段树用来连节点。比较直接主席树上二分。

CF1109E Sasha and a Very Easy Test

其实是个数论。

要取模，还要除，模数还不是质数。

考虑扩展欧拉定理。和模数互质的部分可以直接求逆元。

每次除一个数都可以分成 a*b 其中b有逆元 a的质因子是mod质因子的子集。

因为保证可以除下去，所以考虑把每个数都维护成 a*吧的形式，再做乘法和除法就很简单了。

P4224 [清华集训2017]简单数据结构

你分析暴力，就是对的。但是理论上插入后缀是根号乘根号的啊。问号？虽然必然跑不满，但还是严格劣于根号，分析一波似乎与根号同阶。

CF932F Escape Through Leaf

李超线段树合并或者树上启发式（指最后走重儿子不清空李超树，其他的儿子暴力插入）

事实是我还是不会容斥。像这种naive的容斥，有统计两个方向，一个是对于每个需要的集合每次统计元素（需要给每个集合一个编号），第二个是直接将每个元素加入它属于的集合中去。

这题直接将每个元素插入属于集合每次统计最多只有256个集合，直接暴力 2^k 枚举就好了。

私以为：容斥是在求某个集合的方案数时使用的，此时定义为某集合的子集的方案数和，显然会出现系数 +1-1 的情况，这里才是容斥出现的位置。

CF1365G Secure Password

分成若干集合使得可以单独挖出一个。显然按二进制位 01分组可以用20次询问。

只询问13次，所以我们只能分成13个集合。而且还好给1000个元素分配一个独一无二的编号。考虑 C(13,6)>1000

CF1526F Median Queries

人类智慧构造题。

首先，考虑怎么一次确定一个数，如果我们知道1 2或者 n n-1。

那么怎么找到连续的最大或最小的数呢？我们如果找到了任意一组连续的数

P1963 [NOI2009] 变换序列

一个位置最多对应两个数。显然可以构造一个两部点数都为n的二分图。一个可行的解就是这个二分图上的一个完美匹配。我们现在要求字典序最小的。显然在消去所有度为1的点后，我们剩下的若干点度为二的环。所有这样的环都只会有两种完美匹配方式，我们选择字典序大的那种就好了。

P5292 [HNOI2019]校园旅行

一个显然的 m^2 做法是从单点或者00，11的点对开始BFS扩展出所有的符合点对。考虑回文串的要求在所有对称的位置相同字符数量一样。如果一个单字符强连通分量是二分图那么每次进入再出去得到的字符数量奇偶相同，如果两端都扩展一个这样的玩意很容易构造成回文。所以对于所有这样的玩意都可以只留它的一个生成树。如果不是二分图，就只留一个基环树。处理之后的边数和点数同阶，可以DP通过。

CF817D Imbalanced Array

单调栈做法比较常用，但不会。

考虑一个常见的trick：关于max或min的区间计数，可以考虑每个关键点：max。所管辖的区间。每个数都会有一个 [l,r]，在这段区间中最值一定是它。这样就直接乘法原理计数。

怎么求这个东西呢？考虑max。给所有数排序，从小到大枚举，最小的管辖的只能是它本身，更大的考虑它的管辖区间两端，如果有已经枚举过的点一定比它小，直接合并区间。可以用并查集简单实现。

CF1111E Tree

也许虚树可以吧。考虑DP[i][j]表示第i个关键点，分j组的方案数。

DP的顺序很重要，一个点被加入时如果保证它的直系祖先都加入。

dp[i][j]=max(j-f(node),0)*dp[i-1][j]+dp[i-1][j-1]
f(node)=r到node中关键点个数

所以可以按DFS序dp，但是这题根不定，其实直接按到根的距离顺次DP就可以了。

至于关键点个数直接树剖求出。

P4688 [Ynoi2016] 掉进兔子洞

lxl超级大毒瘤，这破题它卡空间卡时限。

发现：如果我们把一个区间的信息压入一个bitset中，我们可以快速得出每个询问的答案。但是这 3*m个bitset不是很好求，所以考虑莫队。

以上就做完了，但是考虑 1e10 bitset是必然开不下的，所以要把m个询问分成若干段，每段单独做。空间开到 1e5*1e5/4 刚刚好。我的做法比较伞兵，需要开3*m个bitset，所以我分了12段。

P4690 [Ynoi2016] 镜中的昆虫

经典区间数颜色问题：考虑对每个位置维护 pre_i 表示前一个相同颜色位置。然后就变成了一个二维数点问题。加上单点修改，对每个颜色维护一个 set 方便修改 pre，带上时间维，变成三维偏序问题。

本题需要区间推平，考虑均摊复杂度，某部分已经被推平过了， 一大段的pre_i 变为 i-1 ，再次推平不会发生影响。所以把区间推平直接变成暴力单点修改不会影响复杂度。

CF1004F Sonya and Bitwise OR

一些位运算的性质：前缀或是单增的，前缀且是单减的。

一个序列的前缀或，前缀且序列中出现的不同值出超过 logv 种。（每次至少变化一位）

这题建线段树维护前缀后缀且是很显然的，加上刚刚那条性质，可以将每次合并的 O(l) 复杂度变为 O(log v) ，整体就是 O(nlog^2n)。

P7518 [省选联考 2021 A/B 卷] 宝石

倍增一般求两种，一种是树上路径的价值，只要满足可合并性。f[i][j] 其中ij记录树上位置，f记录价值。第二种就像这题，姑且称之为树上路径匹配，我们要在路径上选某些特殊点，总路径上某些点是不会计入的。ij的意义就可以改动，改为假设已经抽出的特殊点序列中的 2^j 的位置。

原本的ij可以直接求出位置，而改动意义后的ij，需要f来记录位置。一般这样改动， i 0 的位置是可以一次dfs确定的。

宝石这题的倍增数组换成这个定义就很简单了。

CF868F Yet Another Minimization Problem

这题就是分层的，也能证明单调性，而且 w(a,b) 函数不能 O(1) 所以只能套分治。

P1912 [NOI2009] 诗人小G

一个 O(n^2) 的dp是显然的。单调性使用四边形不等式证明。证明之后就可以队列维护三元组。维护的这个队列本质上是在维护数组 p 的压缩信息。 p_i 表示第i位的最优决策。显然一个位置得到了最优决策后，这个位置之后的最优决策都至少大于当前，所以p后缀赋值。每次查询当前位置的最优决策。

这些可以用一个三元组队列 j,l,r 实现，意义为：当前已知信息，区间 [l,r] 使用决策点 j 最优。

枚举每一个位置，得到当前位置的最优决策，以当前位置为最优决策更新队尾。

当然这玩意可以用分治做。每次取一个mid，暴力的找到决策点，然后再分治到两边，暴力找决策点的区间也被限制。这样每次减半也是 O(n \log n) 的。

这当然不能用分治做，因为dp过程中要调用之前的值，注定了mid要在 [l,mid) 之后算。只有再来第二维，有分层的题里面，这一层由上一层转移，而且还有单调性，套分治才很显然。

当然还是可以用分治做，只需要套一层CDQ，就能解决 1D/1D 的DP转移问题。

CF888G Xor-MST

考虑建出trie树

在trie的某个节点内的数肯定是先自产自销，如果节点两子节点内都有数，再互相连一条边。每次连边遍历一遍子树就行。考虑一个节点，只有在遍历他的祖先时会被经过，所以总遍历次数 O(n \log n) ，合并两个子树的过程很像启发式合并。

考虑这就是一种生成树算法：当前每个集合伸出去一条最短的边，然后把联通块缩成一个新的集合，因为每次缩集合个数减半，所以复杂度对。

CF875D High Cry

区间极值有关的计数。考虑在关心区间极值时，只剩下极值信息，于是可以处理出某数作为极值所管辖的区间进行计算。这样每次计算的极值是确定的。

CF868F Yet Another Minimization Problem

关于决策单调性：如果是一维DP，那证出这个就可以直接 O(n)

这题是二维，哪怕你要扫描取min你也要把并没有用的几个区间算出来，所以相应的最终需要把所有区间答案算出来。已知单调性算全局。

#CF258D Little Elephant and Broken Sorting

锤子期望，dp状态设错一去不复返。我至今也不知道怎么独立把这个玩意想出来。期望的线性性，逆序对的期望等于每个数对是逆序对的概率和。考虑怎么求这个东西，每次交换两位改变的 f_{ij} 是 O(n) 的，直接 n^2 做。

晚间看题，打标的是没想出来。

CF1268C K Integers

将数花费一定代价挤在一起后就是逆序对了，而挤在一起的代价最小，必然是以一个点为关键点，大家靠近它。（就跟某普及题打水井一个道理）这个关键点一定是最中间的一个或两个点，每次动态加入一个点，关键点只会相邻移动,用两个树状数组统计一下就行了。至于动态逆序对也能用树状数组套树状数组维护。马的动态，一个数插入时比它小的必然加入。

CF1267G Game Relics

显然分为两类：便宜的自己买，贵的尽量抽奖白嫖。注意到抽奖一定小于购买，我直接开局爆抽，抽了剩下一部分买。

一般我们讨厌特殊，要把多个操作转化成本质相同的操作。购买可以转化为 sum/k代价的必中抽卡，不影响结果，这样其实就干掉了物品单价，我们只用关心剩余的总价和总数。如果我们知道当前sum和剩的k个，我们就可以直接比较再抽一个的期望来选择方案。

总期望->所有物品插入期望->每组不同sum，k插入新物品期望*相应系数 总和

这样就变成了求系数，系数即出现当前情况的概率 总方案数/总次数，f[sum][k]/C(n,k) ，总方案数用01背包预处理。

#CF1279F New Year and Handle Change

套二分是个很显然的思路，剩下判可行性。

CF1280D Miss Punyverse

可以瞬间想到二分，DP等等。其实是套路树上背包，唯一麻烦的就是最终剩余那一段的合并，但只要处理好两个背包合并就行。4s 3e8 /jy

#CF1279E New Year Permutations

很容易发现一些性质，但是对字典序帮助不大，初步判断是把所求序列夹出来。那么就需要确切的式子，好在这个序列扩展性很强。

#CF1278F Cards

数学好题，一直不会。

CF954F Runner's Problem

标准矩阵加速DP板题，注意有障碍则转移矩阵当前列全为0

CF1067D Computer Game

炒鸡杂烩题。学一波，斜率优化矩阵加速好题，矩阵必须玩熟啊，后期DP咋全是矩阵。

矩阵一定要封装结构体！！

若注意到二分的前缀区间也具有可合并性，那么预处理倍增（类似建一个树状数组？）再二分就会比二分套快速幂啥的快。

本体关键在于升级，显然有升级点数直接就氪那个全局期望收益最高的游戏就行。

而在确认升级之前，我们要么氪当前期望收益高的，要么氪期望成功率高的。目测这里需要式子判定。所以dp的关键区分就是当前是否升级。若升级，则之后时刻的收益是固定的。

不妨设 f_i 表示剩下 i 时刻，且没有升级过的期望得分。显然最终答案为 f_t，有：f_i=max((1-p_j)f_{i-1}+(i-1)p_jMax+p_ja_j) 考虑了成功与不成功。

设 s_i=iMax-f_{i} 有 f_i=max(f_{i-1}+p_js_{i-1}+p_ja_j)

显然就变为了若干一次函数 y=p_jx+p_ja_j 在 s_{i-1} 处取最值的问题。

当然也可以使用扰动法，能发现决策j优于决策k的条件是 -s_{i-1}>\frac{p_ja_j-p_ka_k}{p_j-p_k} 这就是很典型的斜率式了。提醒我们把每一个游戏看成点 (p_j,p_ja_j)。

一般的斜率优化是转化成截距的比较而且用来截的斜率有单调性。我们能够发现 s_i 是单增的。我们将问题转化为用斜率为 -s_{i-1} 的直线去切每个点，取截距最大的。这个斜率如何选定？首先我们扰动法的左边是 -s_{i-1} 而且我们如果将 y=p_jx+p_ja_j 构造成我们期望的截距max，则令 y=b 有b=p_js_{i-1}+p_ja_j 唯一的定值是 s_{i-1} 我们肯定期望这个为斜率。就有 p_ja_j=-s_{i-1}p_j+b

那么 -s_i 单减，我们对于点集维护一个上凸包。对于某一特定段，转移方程为 f_i=(1-p_j)f_{i-1}+(i-1)p_jMax+p_ja_j 显然在这一整段转移方程都一样，可以使用矩阵快速幂。

再用倍增预处理优化二分过程，就可以做到 O(n \log t)

CF1553G Common Divisor Graph

考虑答案不大于2，直接将所有数与自身质因子连边。本身联通为0，走一步联通为1，否则为2.

走一步有三种情况：走s，走t，走不相干的数但是出现了相应的质因子。

所以考虑枚举所有数走一步的情况，枚举新产生的质因子，如果开始不相连，就标记这两个质因子是可以一步链接的。询问就直接枚举两数质因子即可。

因为1e6内每个数的质因子个数不超过7，所以可行。

P3225 [HNOI2012]矿场搭建

直接tarjan找割点，感性理解对于一个连通块我们以割点为边缩点，变成一棵树，只要每个叶子标记就行了。具体实现就是不经过割点，枚举所有点dfs，保证点不重复经过，搜出的某个连通块与一割点相连就是叶子标一个，与两个就是枝干不考虑，无割点就要标两个。乘法原理统计数量。

P3380 【模板】二逼平衡树（树套树）

/吐，完全不想再调一边，前驱后继大毒瘤。用树状数组套动态开点线段树显然是最优的，跑的比平衡树快一万倍。只需要维护一个线段树上二分和线段树前缀和。

我可以把平衡树扫进历史垃圾堆了，除了区间反转。

CF86C Genetic engineering

经典AC自动机上DP，套路设dp[i][j]字符串第i位，AC自动机上第j节点，因为这题可以延后统计，只要到tag点统计就可，还要支持按fail转移，所以再设一维k表示还有k位未统计。

计len[x]为这点以及相应的fail点有tag的最长字符串长度。

我们当前的状态为i,j,k，通过AC自动机的转移边（无论是trie树边还是AC自动机新添加的转移边）转移到了点x，那么我们有：

当 len_{x}>k时，f_{i,j,k}\rightarrow f_{i+1,x,0} 否则，f_{i,j,k}\rightarrow f_{i+1,x,k+1}

P3960 [NOIP2017 提高组] 列队

显然须实现单点增删，查询kth，在只有一行时可以直接线段树上二分。总之就是不写平衡树。

考虑很多行的情况，总修改点数有限，可以考虑动态开点。可是线段树初值是1-n为1，n+1-lim为0，并不是很行。考虑反过来维护区间0点数量，这时后面一段零可以先不考虑，因为这时0代表无意义位置，而非没有数。后面的零位必然经过upd出现，而总upd次数为q。再考虑一下最后一列补位的小细节，同时用vector维护一下所有新插入的数即可。

CF68D Half-decay tree

事实上，对题目不同的描述以及统计方向会带来不同的做法。

按x6的思路，直接求和，那就是差分sum后快速维护链max，使用动态开点线段树，考虑到点值单增，只需支持区间覆盖。

如果从期望意义，发现，单点修改维护的sum，只用暴力跳链。那考虑用map维护，然后直接递归求以u为根的子树期望query(u)，如果当前最值已经比子树和打，那该子树下的叶节点期望都为当前最值，否则当前点产生的连通块最值递归下去，合并为两子节点期望/2。

double query(int u,int maxx){
    if(maxx>=t[u]) return maxx;
    return (query(u<<1,max(maxx,t[u]-t[u<<1]))+query(u<<1|1,max(maxx,t[u]-t[u<<1|1])))/2.0;
}

两个做法的正确性都是由max的变化为区间覆盖保证。

CF60D Savior

有一个点快速得到能够与之相连的点？差不一样，不能DS维护。

维护能够相连的集合？连边不方便。

考虑直接枚举勾股数，显然可以证明总数是与根号1e7同阶的。使用勾股数公式即可。

CF57D Journey

按我自己的思路：考虑快速统计每个点，从前一个点转移，曼哈顿距离整体平移，只用考虑转移的当前行的特殊点。最终只算变化量，所以只关心横纵的数量。至于绕过+2的操作每个点另算。

以上一点都不清真，巨大细节。以上是错的，我太naive了。如果某一行或列都堵了，那不也要绕路吗。所以统计绕路点数量没这么简单。

考虑曼哈顿距离可以拆分成横纵。

考虑统计行，枚举列，对于其他的列要加的就是dis*sum。再考虑统计绕路点被堵住的图形一定是单峰的，而对于每一行或一列只有一个#，这就是这个的那封函数的起点。这样对于每一行或列，可以n或m统计。

CF55E Beautiful numbers

正难则反。类似于扫描线。

维护一个点是否在当前集合， 当前集合和扩展集合数量。 一圈枚举起点，到再次转回为止。 每次扩展的充要条件：前一点和询问点在直线两端

CF55D Beautiful numbers

经典数位DP，先差分，从高往低考虑。 显然因数只对 1-9 有要求，公倍数为2520.

计DP[18][2520][2520] 表示到第i位，应得的最小公倍数为j，已经得到的最小公倍数为k。显然开不下，考虑2520的因子只有48，可以把第三维压缩。

CF639E Bear and Paradox

临项调整法，得到排序的关键字，再按题目要求写表达式得出单调性，就可以实数域二分了。

P2178 [NOI2015] 品酒大会

这个问题问的就很像后缀数组。考虑问题一，可以转化为对于每一个len，询问有多少对后缀(i,j) 满足 lcp(i,j)>=len

显然就是height数组的传统用法。我们可以反过来，基于lcp(i,j)进行相应的累加。

前置认识：对于一段height，我们只关心最小值。直接枚举(i,j)是n^2的，我们需要快速统计，只关心数量的情况下常用的有【对于一个i快速查询所有j，构造两个集合使得两个集合中点两两之间都满足】，第一个本质上还是枚举，条件是(i,j)之间存在我们所需的最小值，可是最小值还是枚举的。那考虑第二个，要合并计算的两个集合一定是两段区间，中间隔一个min，将最小值从大到小枚举，就不用分裂集合，只要支持集合合并，可以使用并查集。

至于第二个问题，在并查集合并时维护一下相应a数组的最大值和最小值。

P7078 [CSP-S2020] 贪吃蛇

最长蛇吃后所在pos是单减的

最长蛇吃后不成为最短就一直吃

安全：3小 5小 7小,按照奇偶判断一下吃不吃。

把吃过的蛇另设一队，这一队也是满足单调性的。

P7115 [NOIP2020] 移球游戏 瞪大样例可能会收到奇效

先解决 n=2 借助一空一满柱完成操作柱的上提操作。

一个比较naive的想法是每次解决一种颜色，使问题规模-1，显然通过上提每个柱子中同一颜色可以实现，得到70pt。

考虑n=2是双色，猜想差分为每次处理双色。形象的理解为排序，如果最终将颜色严格排序，其实就是每个柱纯色。

若能模拟排序当然是log的，考虑近似于归并的做法。每次以mid处理，分成01的纯色柱，一次 5mn，总 5mnlogn

这种类似二分的思想最近总是见到。给出一个不太严格的限制，将条件限定在一段区间内，分治到最低层时自然是限制在单点。考虑某些限制能共同组成一个同样易于判断的条件，且限制划分连续时适用。

P4383 [八省联考2018]林克卡特树 转化问题：在树中选取k+1条互不相交的路径使价值和最大。

先考虑没有k限制的情况，显然贪心选正的。一般有数量限制可以考虑wqs二分。直接二分一个偏移量然后树形DP，判断一下最终取的路径条数就行。

[USACO21JAN 铂金] Minimum Cost Path

保序回归的 L_2 情况（二次保序回归）

设在第 i 列我们从 (s_{i-1},i) 移动到了 (s_i,i)（s_0=0），那么总代价为

\sum_{i=1}^{y-1}[s_i^2+(s_i-s_{i-1})c_i]+(x-s_{y-1})c_y \begin{aligned} \sum_{i=1}^{y-1}[s_i^2+(s_i-s_{i-1})c_i]+(x-s_{y-1})c_y\\=\sum_{i=1}^{y-1}\left[s_i^2+s_i(c_i-c_{i+1})\right]+(xc_y-c_1) \end{aligned} =\sum_{i=1}^{y-1}\left(s_i-\frac{c_{i+1}-c_i}{2}\right)^2-\sum_{i=1}^{y-1}\frac{(c_i-c_{i+1})^2}{4}+(xc_y-c_1) \end{aligned}

考虑忽略掉常数项，就是一个板子题。需要考虑每次取的必然是整点，这里只需四舍五入。

P7324 [WC2021] 表达式求值

一些简单的结论：每个数组各位分离。多次取 max，min 最终结果仍在数组中。直接暴力状态数 2^t 不现实。

考虑到结果的有限性，分离位考虑的各个状态结果重复出现，考虑怎么用乘法去做。转化为统计某个结果在所有状态中出现的次数。

考虑建出表达式树之后就可以在其上DP。

根据刚刚描述 naive 做：

枚举每一个 a ，其他值可以离散成 0 1（只关心相对a的大小）。

设 f_{u,0/1/2} 表示在表达式树结点 u 上，值小于、等于、大于 a 的结果数。可以简单容斥计算。

O(nm|E|)

考虑每次离散后的结果，只是一个长度为m的01序列。我们枚举这样的序列是 3^m 的（还要考虑等于的情况）。

按照一般的套路，只会离散成 0 1，所以我们定义大于等于a的为1。再枚举 2^m 最终答案差分计算。

P5643 [PKUWC2018]随机游走 在树上的随机游走，考虑在图上的需要高斯消元（方程构成环状）。在树上可以待定系数消成只与fa有关的形式。

这题推式子

一般的随机游走问题，由于后效性，必须考虑列方程组，通过高斯消元求解。但是，这题是树上的随机游走问题，只能从父亲与儿子转移，可以考虑直接dp。 由于本题要求点集 S 中所有点都被经过的步数期望，即到达点集 S 中最后一个点的期望步数。运用\min-\max容斥可以将其转化为到达点集 S 中第一个点的期望步数。

设 f_{S,i} 表示从 i 出发，经过 S 中的至少一个点的期望步数，deg_i 为点 i 的度数，可以得到这样的递推式：

\begin{aligned} f_{S,i} = \frac{1}{deg_i} (f_{S,fa_i} + 1 + \sum_{v \in son_i} (f_{S,v}+1)) \ = \frac{1}{deg_i} (f_{S,fa_i} + \sum_{v \in son_i} f_{S,v}) + 1 \end{aligned}

若 i \in S ，则 f_{i,S} = 0。

按照套路，将转移方程写成有关于父亲的函数，即f_{S,i} = A_i \times f_{S,fa_i} + B_i，分离儿子与父亲的贡献。

\begin{aligned} f_{S,i} = \frac{1}{deg_i} (f_{S,fa_i} + \sum_{v \in son_i} f_{S,v}) + 1 \\ = \frac{1}{deg_i} (f_{S,fa_i} + \sum_{v \in son_i} (A_v \times f_{S,i}+B_v)) + 1 \\ = \frac{1}{deg_i} (f_{S,fa_i} + (\sum_{v \in son_i} A_v) \times f_{S,i} + \sum_{v \in son_i} B_v) + 1 \\=\frac{1}{deg_i} (f_{S,fa_i} + sumA_v \times f_{S,i} + sumB_v) + 1\\ deg_i \times f_{S,i} = f_{S,fa_i} + sumA_v \times f_{S,i} + sumB_v +deg_i \\ (deg_i - sumA_v) \times f_{S,i}= f_{S,fa_i} + sumB_v + deg_i \\ f_{S,i} = \frac{1}{deg_i - sumA_v} f_{S,fa_i} + \frac{sumB_v + deg_i}{deg_i - sumA_v} \\ A_i = \frac{1}{deg_i - sumA_v} , B_i = \frac{sumB_v + deg_i}{deg_i - sumA_v}\end{aligned}

发现 A_i,B_i 的方程与父亲无关，可以直接树形dp求解。由于 root 不能从父亲转移，显然有f_{S,root} = B_{root} 。

在 i 属于 S 时，有 A_i=0 , B_i=0。

点集 S 的答案为 \sum_{T \in S,T \not= \varnothing} (-1)^{|T|+1} f_{T,root}。

预处理所有f_{S,root} O(n2^nlogn)。

考虑答案式，一个子集的贡献是固定的。考虑子集的基本定义，显然一个全集需要某个子集的贡献那必要该子集的子集的贡献。这就是所谓高维前缀和在这题的应用。这样是 O(qn) 回答。

P5473 [NOI2019] I 君的探险

神仙交互题。各个部分分的做法很有启发性不是启发正解。

考虑链和树的情况，01两种情况，而且亮灭只与本身以及相邻的点有关，按数量奇偶定01。种种限制不难想到按二进制位分组进而确定相邻数异或和，再从叶节点递推。

很抱歉正解完全不同。

正解类似于整体二分（tip：整体二分的实现方法就是线段树递归处理询问，对每个结点开vector记录问题）的思想。将一段前缀modify之后，显然后面的点连该前缀奇数个时会改变状态。我们将前缀钦定为线段树上某节点mid。将改变状态的点加入左子树vector处理就可。像这样递归下去，最终递归到叶子vector中还有的就是与叶子相连的点。显然做一轮那些有前缀奇数连边的点都会连出一条边。我们做若干轮，每次rand_shuffle一下序列。每轮期望解决 n/2条边，一共就2n条，所以 O(knlogn)能过。

P7323 [WC2021] 括号路径

这题给的图很特殊，正反同时给。合法括号串满足“结合律”“交换律”,uv+vw=vw，a+bc+d=ad，考虑维护若干个集合，集合中的点任意组成点对都是合法括号串。一个合法的串要么是基本括号，要么是合法串扩展而成。直接将括号对压入队列广搜，每次启发式合并。

P6628 [省选联考 2020 B 卷] 丁香之路

至少可以转化为只经过一次，转化为构造一个 s -> i 的欧拉路。直接连接 s i 转化为欧拉回路。每次贪心的消奇点。最后图可能不连通，构造最小生成树并增加答案。

CF232E Quick Tortoise

猫树：序列上的淀粉质，而且离线下来便于在线操作.

P4314 CPU监控

奇怪的线段树操作：区间历史最值。并不是主席树的某时刻最值，而是在所有时间取最值。

还要维护当前最值，区间加，区间推平

直接用每次的当前最值维护历史最值是错误的。

考虑到lazytag的滞后性，可以构造出同同一大段先加后减，在询问其中一个小段，询问pushdown时已经是先加后减的值了，中途先加的最值没有考虑。

考虑再维护一个区间最大加和最大赋值。

P5072 [Ynoi2015] 盼君勿忘 这东西比较复杂

首先套莫队

对于一次询问 根号讨论

维护出现次数小于根号n的数 按次数下标求和

unordered map 维护出现次数大于根号的数 暴力处理

2的幂次因为模数不一样，每次重新修改都要处理一遍光速乘。

预处理 2^1,2^2 ... 2^{blo},2^{2blo}, 2^{3blo}...2^{n} (blo=sqrt(n))

这样在n之内的幂次就可以 O(1) 求出。

P3793由乃救爷爷 基于数据随机和分块思想的2e7规模的静态RMQ问题 可以在 2e7 \log sqrt(2e7) 的时间内解决。 我可以怀疑NOI2021D2T1也是lxl的手笔了。

对每一块维护前缀和后缀max，对所有块维护块间ST表，在同一块内则暴力处理。

CF53E Dead Ends 求叶子节点为k的无根树个数。 n<10这种小数据目测 2^n 考虑状压，爆搜，枚举。 这题只要暴力就是 2^m m到50

事实上，总状态数只有1e6，这也就是状压为什么对。

考虑状压 设dp[i][j]表示当前生成树的状态为i叶子节点的状态为j

每次暴力枚举边插入，但是注意同一个无根树可以是不同的边插入顺序得到，所以必须固定每一状态是顺次填一，也就保证同一无根树的生成序列唯一。具体在代码上就是保证当前更新的1后全是0位

P3826 [NOI2017] 蔬菜 目测带悔贪心。naive 的贪心策略，每次取最大的。但是考虑日期和变质的限制，每次只能取到一个相对小的时，考虑能否使用变质完全的值进行替换。 带时间轴的不妨考虑时光倒流，类似CF505E。 每次跟买的菜无关，一定会冒出x个单位，然后维护最大的。

P7140 [THUPC2021 初赛] 区间矩阵乘法 交换求和，注意到i和k互相无关，把j项单独提出，变成先分别求和再相乘的形式，再预处理等差位sum。

P6773 [NOI2020] 命运 重点在于写出DP方程，线段树合并优化只是trick

我们一定要满足所有限制，考虑一个越过u的限制，要么在u子树内解决，要么在u上的边解决，分两种情况。我们的定义必须体现这两种情况，我们令 f[u][i]表示第u个节点，未解决的限制上端点最高为i的情况，相当于钦定u-i路径上为0.

考虑分u-v的01情况讨论

记 G_{u,i} 表示 \sum^i_{j=0}f_{u,j}

f_{u,i}=f_{u,i}G_{v,depu}+f_{u,i}G_{v,i}+f_{v,i}G_{u,i-1}

但是这个怎么优化啊，看着就不是很像线段树合并，各种数组搅来搅去。

这种奇怪的转化叫整体DP

P4768 [NOI2020] 归程 知道了kruskal重构树那就是真的锤子题了，主要是快速求出小于某个瓶颈的联通快。 注意要求最大生成树，，那我是脑瘫。

P6776 [NOI2020] 超现实树

搞清楚了看懂了实现不了，思路还是不清晰。

现在真懂了。

首先，只有单点是完全完备的。我们得到的树集只有最终等价与一个单点才是几乎完备的。

按照样例一，已经提醒我们，如下方式可以合成。

所以我们的树集中一定包括这样一个由单点分化而来的树集。考虑这个答案树集的性质，发现它一定是链树：由每个节点要么是叶节点，要么一边子树没有或只有一个节点。我们只需要保留这些树就行，其他的直接删去。

考虑怎么判断合法，一个叶节点肯定合法，非叶节点如果在树集中相应位置有上图一样的情况也合法。考虑合并，三棵树合并当且仅当其他部分相同而一个同位置的节点出现上图情况。

这提醒我们分出四种情况：

1.只有左儿子 2.只有右儿子 3.左儿子为叶节点，右儿子为子树 4.右儿子为叶节点，左儿子为子树。

其中3，4都是为了合并出上图同时有两个叶节点的情况。我们发现，一个节点必须有1 2 3 4的合法儿子才能合并为单点。

这提醒我们把二叉树拆成四叉树，对于某一个节点是否合法，判断其四个儿子是否合法就可，叶节点默认合法。

注意之前合并的前提条件：树的其他部分都一样，就该点一分为三。我们发现，在建出四叉树后，所有保留下的链树都在四叉树上被压缩为了一条链，这样天然就把其他部分一样这个条件合并，不需要再另行考虑。（就是这里推出前面条件之后自己没想清楚，导致难以实现代码，四叉树的本质是给链树编码，信息压缩）

事实证明 1900+的题我就有概率做不出来了

CF1545B AquaMoon and Chess

一个重大性质： 11 可以任意移动，定义 11 为一个自由元

然后我就陷入了 DP 的深渊，似乎可以先找连通块然后分奇偶讨论，偶数拆成自由元，奇数就是自由元+单点，把单点再分开计算，合并推推组合数式子，预处理一下前缀和和组合数就可以 O(n) 了。

上面的DP不美观的地方就是单点的处理很复杂，无后效性也只能通过各种钦定来保证，赛时并没有很好的优化。

DP为何消不掉单点？因为自由元在通过一个单点时会改变这个单点的位置。但其实我们还是能够消掉单点。

我们先钦定 111 的情况是自由元在右，单点在左，毕竟最终方案数只统计一次。这样我们发现，只要确定了所有自由元的位置，单点的位置必然确定。而单点必然占一个位置。至此我们消掉了单点（单点位置不再重要，只用关注数量）设有 m 个自由元， n 个 0 位，那么自由元能处在的位置总数 n+m ，最终答案就是 C^m_{n+m} ，至此我们预处理 O(nlogM) 预处理阶乘（M为模数），阶乘逆元就可以 O(n) 求得此题答案

再记一下手慢的Div3 Codeforces Round #731 (Div. 3)

CF1547F Array Stabilization (GCD version)

GCD具有结合律，我们可以二分，剩下的就是O(n)判断（大概？）

然后我就陷进去了，考虑分解质因数，维护每个因数个数啥的。

官方题解看不懂。。按照官方提了一嘴的 range GCD query 想想，这query不就是区间查询吗，那不就是线段树？具有结合律自然可以线段树维护。 然后就有了两只log的做法，CF机子2e5也跑过去了。

还是按照官方题解的思路，先除掉全局gcd，那么剩下最长的gcd非1的子序列的长度就是答案。好耶二分，好耶区间查询gcd，做完了。

记一下数学场翻车的 B和C Codeforces Round #729 (Div. 2)

CF每题推性质更为重要，充分利用所有性质才能解题

CF1542B Plus and Multiply

因为操作是每次 *a +b 化简这个式子，能够得到的数 a^x+by

所以我们枚举 x ,特判1，n 和 a^x 同余 b 就行

CF1542C Strange Function

赛时整出了做法不知为何调不过去。随便打个表发现 f(i) 有很多重复的数。对于一个答案f(i)=n,只有是1-n-1的倍数且不是n的倍数的数。我们可以随便筛一下，比如筛到3时只有三的倍数留存。显然这个筛的次数不会很大 (<=41)考虑4的时候2的倍数已经筛去，找4的倍数先除2，再再剩下的找2的倍数，这里用个gcd，每个n先除之前的处理的n乘积到现在的gcd。

订出来了，我当时为啥不老老实实用GCD,用了个for循环去除，这会导致重复计算，4本来已经用2处理了，后面取gcd，4只能贡献2但是我贡献了4.

CF1543C Need for Pink Slips

论eps的重要性

eps可以看成是epsilon的缩写，可以用来表示一个无穷小的量，通常取eps的值为：1e-10~1e-8 之间。 可以做什么？ 对于数字5，如果计算机存储的数据为5.000000000000001，显然对这种情况不需要用到eps进行补偿，而对于有缺省的类似于4.9999999999999998的数据，eps可以进行对它的缺省值进行一定的补偿，使其在计算机中的存储值变成5.00000000000000或者5.000000000000001，这样在后续的计算中就会解决因为存储的误差造成的不必要后果。

相当于设置一个偏差值，在这个偏差值之内我们可以就认为它是某个整数，以免后面不可靠的位对运算产生影响

CF627F Island Puzzle

CF小清新思维题，跟1-15移动滑块的游戏差不多

首先考虑树本身，0的移动是不改变数字相对位置的，直接把0移到目标位判断。考虑加上环，0此时能够造成的影响就是让换上的数字统一顺时针或者逆时针轮换。判断所有0在目标位后不符合的点是否能连成环，如果可以，判断是否能旋转得到。

P3992 [BJOI2017]开车

一个小结论：最小化曼哈顿距离和的问题把 a, ba,b 都暴力 \text{sort} 一遍，对位相减

aha树分块题

给定一棵存在n个节点且根为1的树，现在你需要执行q个指令，其中每个指令如下： 1 L X : 将所有深度为L的点权值加X（根结点深度为0 且 0<=X<=1e8） 2 X : 输出编号为X的节点子树内的所有节点权值和。

输入格式:

第一行两个整数n，q 接下来n-1行每行两个整数描述树上的边。 接下来q行每行描述一个指令。 输出格式:

对于每个输出指令输出一个值。 限制:

n<=1e5,q<=1e5

考虑将每一层（题中关键字）按照sqrt(n)进行分类，分为点数大于sqrt(n)的和小于的。小于的直接暴力，大于的打tag。

P6772 [NOI2020] 美食家

一定要注意特殊的数据范围。

考虑一个naive的DP，记录DP[i][j]表示第i号城市第j天的最大愉悦值，DP[i][j]=max(DP[u][j-w(u,i)])+c[i][j] 其中c[i][j]是第j天在第i号城市能够获得的愉悦值。发现在一次转移中答案与c无关，只需维护能够转移的城市的DPmax。这个集合是固定的,对于转移关系固定的显然可以考虑矩乘。

发现这个DP的瓶颈在第二维j上，T<=1e9

考虑w的特殊范围，最大不超过5，所以可以考虑拆点，在边中间插入一些愉悦值为0的点，使得该图中所有的边都为1，第j层只与第j-1层有关，滚掉了第二维。这样一层层转移，而且转移关系固定的DP，而且T还1e9，无不提醒我们要用矩乘。k=0是经典的矩乘，但k!=0如何？

k并不大，考虑直接暴力，对于每次造成的转移方程不同的情况，直接乘上以此构建的新矩阵，时间复杂度O(200n^2),而拆点做矩乘的复杂度O(n^2(n+4m)*logT)

发现并不可以通过此题，因为以上到达1e8，但是可以获得90pt的好成绩。

以上n,m同阶的90pt提醒我们，这次的瓶颈在m上，我们考虑直接把拆分缩到点上，把大于一的边看作在起点上停留，在最后一天转移，那么对于一个点开五个就能解决问题。最终时间复杂度O(5n^3logT)

代码实现：虽说是矩阵优化，但构建矩阵时仍可以从DP角度考虑，构造时会更简单。矩阵加速DP好题

P4592 [TJOI2018]异或

求一个集合中所有数异或一个数的最大值，常规做法对这个集合中的数维护一个01-trie，把询问的数丢进去跑。

现在这个被搬到了树上，而且询问的集合是子树或者树上路径。可以，这很树剖。现在考虑怎么维护这个01-trie。类比静态区间第k大，当时主席树可持久化的不是时间轴，而是用来差分。这里也是一样的，树剖时分配的编号在子树或者树上路径时是一段段连续的编号。我们只需按照编号顺序建立可持久化01-trie。把树剖板子的求和部分改成在01-trie上跑最大值。

好耶我还会01-tire，这题可以当01-trie板

可持久化的题数组要开够，尤其这题每个节点插入一次产生logn的空间，总空间O(nlogn),最好再开二倍。

[P4211 [LNOI2014]LCA](https://www.luogu.com.cn/problem/P4211) 应当学会从数据范围猜做法 这题要统计$ \sum dep[LCA(i,z)]

显然对于一次l r z的询问，不能直接求LCA再求DEP。也许可以快速得到LCA序列再快速DEP，但哪怕一次dep[LCA(i,z)]是O(1)的，仍然不够优秀。

这启发我们每次询问直接统计答案，应当构造一种方法，让dep[LCA(a,b)]拆分为单独对a,b在树上进行某种操作，需要时统计。从dep出发。dep的定义为lca到根的节点数,那么将每个要统计的节点到根的路径都+1，再统计z到根的路径上的权值和。

使用树链剖分logn修改，考虑到每次给定区间l,r，莫队离线处理。

在树上，询问两点考虑两点间路径，点到根再到点，树剖。统计路径和：点分治。 统计子树，方案数：树形DP，dfs

P2839 [国家集训队]middle

区间中位数套路化处理：二分mid将大于mid的设为1，小于mid的设为-1，本身设为0

只需要区间求和看是否大于等于0

对于该题同样如此处理，离散化后，每次二分一个mid，注意到[b+1,c-1]必选，只需要在转化后的序列中找到[a,b]中最大后缀和，[c,d]中最大前缀和。

或许对每一个mid值都建一个线段树就解决问题了？显然强制在线的情况下不行。

考虑主席树，发现相邻mid间的线段树节点修改是有限的，最终修改节点的总和是O(n)级别的。

建完主席树后再处理询问，维护区间和，前缀max和后缀max。

哪怕是相邻的两颗mid树之间也可能会有一万个叶子不同，但是主席树每次只能修改一个？不过考虑到总修改是线性的，每次都在同一颗树单次修改。

你可以永远相信分块

不要忘记简单有效的莫队、分块一类根号算法。。

对于此题，二分是要二分的，直接再直接分块维护块内和，前缀max和后缀max。 预处理时依旧使用线段树，-1，0，1修改仍然是有限的，本质上是避开主席树但仍然记录相当部分的主席树上信息。

码农题

主席树代码中有很多细节，应查看

[HNOI2008]GT考试

矩阵加速DP

串串题，不出现特定模式串，首先套路化的求出fail指针，每次转移到可到达的点，不转移Trie图终点，得到 O(mn) 的 DP，但是这题n=1e9，发现每个点被转移的点是固定的，也就是说 dp[i]=\sum dp[j]*g[i][j] 其中g[i][j] 取值为0/1，表示点i是否由j转移。

对于这种相关关系固定的式子，可以处理出相应矩阵进行加速

对于矩乘：封装一个结构体便于操作

P4408 [NOI2003]逃学的小孩

发现题目要求的相当于是在一颗树上面求 dis(A,B)+min(dis(A,C),dis(B,C))

为使其最大化，令 dis(A,B) 为直径，min(dis(A,C),dis(B,C))只要枚举 C 求最值

CF526F Pudding Monsters

加强版：CF997E，全局改为区间查询。

经典二维变一维。 对于一个棋子的坐标 (x,y) ,考虑令 a[x]=y , 这时满足条件的矩形即在序列a中一个子序列中的数字再次排序后是连续的。

统计这样的子序列有多少，可以考虑分治。两个区间进行合并时，新序列是由小到大产生的，每次取对差值贡献最小的值加入序列即可。合并复杂度 O(n) , 所以最终复杂度 O(nlogn)

以上是错的。

考虑一个左端点，可以有一万个右端点与之匹配。

一个合法区间应满足：r-l=max-min

那么如何合并，分情况讨论。大小都在左，判断右是否合法，都在右也一样。 大在左小在右，钦定一个大，有 左大-右小=左长+右长。长定义为端点到左右断点的距离。 显然已知左大、左长，在满足左大的情况下统计 右小+右长=左大-左长 的个数。大右小左同理。

如此一次合并 O(nlogn) ,分治后 O(nlog^2n)

法二：

xht37's solution击节赞叹徐老师码风

经典连续段计数问题。

套路的枚举 r , 对于每一个r，只用维护所有后缀区间 l+max-min 的数量。使用线段树统计，下标为 l 。每次移动新的 r 时，每个区间的 max,min 具有单调性。用两个单调栈记录 max,min 以及出现的位置。 每次更新 r 时，区间修改 max,min ，再进行查询。

线段树记得 pushdown ，区分清楚l,t[p].l，求 mid 时别错

CF527E Data Center Drama

显然最终得到的图是一个欧拉回路。但不是所有的欧拉回路都能满足。

显然整张图的边数要为偶数（考虑入边出边总数都为偶，一条边只能分别贡献1），那么若为奇数边就随便连一条自环。

Hierholzer算法

从一个可能的起点出发，进行深度优先搜索，但是每次沿着辅助边从某个顶点移动到另外一个顶点的时候，都需要删除这个辅助边。如果没有可移动的路径，则将所在结点加入到栈中，并返回。

最后得到的栈中保存的就是欧拉回路。

时间复杂度 O(n+m)

因为用过就删，遍历改为

for(int &i=head[u];i;i=e[i].next){

相当于同时修改head[u]，这里比 

for(int i=head[u];i;head[u]=e[i].next,i=e[i].next){

快很多，猜测是使用了i参与调用运算导致变慢

CF521E Cycling City

考虑有三条完全不相交简单路径的充要条件：图中有两个环有边重合

变为建好生成树后判断某树边被非树边覆盖两次的过程

建一棵树 树上边差分 维护LCA

但是考虑判定条件：覆盖两次。直接暴力判断复杂度最劣不会超过线性，故可行。

CF1227C Messy

完全的构造，不超过n次操作，考虑直接构造一个可行的括号串，每次和当前串不一样就直接翻转一个过来，肯定不会超过n

CF1239F Swiper

给定一个无向图，判断是否能删去一个不是空集且不是全集的点集，使得剩下的点的度数在模 33 的意义下不变。可行时输出任意方案。

CF1218D Xor Spanning Tree

给一张有n个点,m条边的无向图，且这张无向图是一个拥有不超过42个环的仙人掌。在图中选取一些边，使得只留下这些边时，整张图仍联通，且所有选取的边的边权的异或值最小。 求最小的异或值， 达到此最小值的边的选取方案有几种。

抄题解：我们发现仙人掌有一个很显然的性质，环的任意一条边只会出现在一个环里，那么说明了你每个环，最多删掉一条边，才能使它连通，所以枚举断边，然后对所有的环暴力 FWT 即可。

CF504E Misha and LCP on Tree

给定一棵 n 个节点的树，每个节点有一个小写字母。 有 mm 组询问，每组询问为树上 a \to b 和 c \to d 组成的字符串的最长公共前缀。

n \le 3 \times 10^5

，m \le 10^6 。

虽然可以 SA ，但不会啊。考虑如何维护树上路径 hash 值。

分别维护到根路径的正串哈希值和反串哈希值，每个路径直接找到lca然后拼起来。 再二分出公共前缀。 此处二分相当于求k级祖先，考虑用长链剖分预处理，倍增多一个 log 。

长链剖分重儿子的定义从所在子树最大的儿子变成了所在子树最深的儿子。

推论：任意一个点的k级祖先所在链的链长一定大于等于k。

如果这个点和他的k级祖先在一条链上，那么结论显然成立。

反之，如果不在一条链上，那么一开始这个祖先没有选择这棵子树是因为别的子树更深，故而所在链一定是大于k的，结论仍然成立。

首先我们进行预处理（时间/空间复杂度）：

对树进行长链剖分，记录每个点的链头和深度 倍增预处理出每个点2^n级祖先 如果某条链的长度是len，那么在链头处记录链头向上的len个祖先，并记录向下的len个链的元素 记录每个数最高位1是多少 对于每次询问k级祖先，我们执行以下步骤：

先利用倍增数组跳k的最高位的1层，设剩余层数为k'，可以发现k'<k/2 利用之前证明的性质，我们可以发现当前节点所在链链长一定严格大于k'。直接利用刚刚的数组得到答案。

CF505E Mr. Kitayuta vs. Bamboos

一眼题，最大值最小，二分。 考虑如何 check 。 发现由于取 max 操作，每次增加之后砍并不是很方便，考虑时光倒流，先都为二分的 mid ，再考虑最后都大于 h[i] 。用一个堆维护。

CF506E Mr. Kitayuta's Gift

CF1101D GCD Counting 求最长的 gcd 大于 1 的路径。

考虑有趣的性质：2e5以内的整数的质因子不超过6个

(2*3*5*7*11*13*17>2e5)

直接枚举这几个质因子作为 gcd 就可以了。然后发现成了求最长路径，直接树形DP就好了，淀粉质并不需要。

无向图G为二分图的充分必要条件是，G至少有两个顶点，且其所有回路的长度均为偶数。

CF166D Shoe Store

first think:可以按顾客、鞋子建二分图，转化为二分图最大权完美匹配

范围 1e5 ,考虑鞋子尺码都不同以及顾客只能穿两个尺码是特殊限制

提前将鞋价大到小排序,故求出的二分图最大匹配就是该图二分图最大权完美匹配，连单向边。

法二：分组，并查集维护

对于每一个连通块维护人数 p ，鞋数 s ，最便宜的鞋价格 price

对于 p==s-1 最便宜的鞋不能卖出，否则可以卖出该组所有的鞋

一个连通块中 p \ge s-1 .再只用在每个连通块内构造出可行的解。

CF521D Shop

= + * （转化思想）

与对象无关，可以贪心。考虑将+和=转化为

+可以表示为*一个比值，对于一个数显然从大加起，依次计算比值即可

=只用保留一个最大的，考虑到若=，则一定在+前，将=也转换为+

最终按照题目要求顺序输出。

关于 const,全局变量且不会改变时定义为const，编译器通常不为普通const常量分配存储空间，而是将它们保存在符号表中，这使得它成为一个编译期间的常量，没有了存储与读内存的操作，使得它的效率也很高。 比如使用Pi，或者存储mod

//快读
inline int read() {     
    int x = 0, f = 1; char s;     
    while((s = getchar()) < '0' || s > '9')     
        if(s == '-') f = -1;     
    while(s >= '0' && s <= '9')     
        x = (x << 3) + (x << 1) + (s ^ '0'), s = getchar();
    return x * f;     
} 

//快输 
inline void write(int x) {  
    if(x < 0)   
        x = -x, putchar('-');  
    if(x / 10)  
        write(x / 10);  
    putchar(x % 10 + '0');  
}

在输入输出多的时候会比scanf和printf节省很多时间

使用ceil函数。ceil(x)返回的是大于x的最小整数。

如： ceil(10.5) == 11 ceil(-10.5) ==-10

基环树：基环树是一种图，它由一个环组成，环上每个点都是一棵树点树根，所以称为基环树。当然，一棵树上连一条边也会变成基环树。

一树+一边=基环树

快速幂取模

long long mod=100003;
inline long long qpow(long long a,long long p){
    long long ans =1;
    while(p){
        if(p&1) ans =ans *a%mod;
        a=a*a%mod;
        p>>=1;
    }   return ans;
}

stirling数，递推公式s[i][j]=s[i-1][j]*j+s[i-1][j-1]

S(p,k)的一个组合学解释是：将p个物体划分成k个非空的不可辨别的（可以理解为盒子没有编号）集合的方法数。

k!S(p,k)是把p个人分进k间有差别(如：被标有房号）的房间(无空房）的方法数。

S(p,k)的递推公式是：S(p,k)=k*S(p-1,k)+S(p-1,k-1) ,1<= k<=p-1

边界条件：S(p,p)=1 ,p>=0 S(p,0)=0 ,p>=1

random_shuffle(p+1,p+n+1);//随机打乱数据 ok

stable_sort(p+1,p+n+1,cmp); 排序时遇到相等的元素不做任何改变，保留原来顺序

对于strlen(s)，每次调用时都会再次计算，所以不能在循环中多次调用，而是提前赋值给一个变量

比如for(int i=1;i<=strlen(s);i++)时间会白给

对于何时考虑二分，问题可以转化成最小值最大或者最大值最小，本质上为保证单调性

struct L{
   int d,p;
}e[100005];
bool operator<(L a,L b) {
    return a.p<b.p;
}    //自定义排序规则
priority_queue<L> q;//大根堆

XingLing's 数论板块

积性函数 积性函数：对于任意互质的整数 a,b 有 f(ab)=f(a)f(b) 则称 f(x) 的数论函数。

完全积性函数：对于任意整数 a,b 有 f(ab)=f(a)f(b) 的数论函数。

莫比乌斯函数

分别为

cows in bed

离散化：

sort(num+1,num+1+tot);
int len=unique(num+1,num+1+tot)-num-1;
a=lower_bound(num+1,num+1+len,a)-num;

auto

auto可以在声明变量的时候根据变量初始值的类型自动为此变量选择匹配的类型

目前应用：遍历vector

for (auto x:v[i])