题3

10.24

P5658 [CSP-S2019] 括号树

这个实际上就是给定一个括号序列$a$，然后对于每一个$i$，来说，求出$[1,i]$的所有合法括号子串（发现这个其实只需要求以$i$为结尾的合法括号后缀然后做前缀和就行了）那么只需要找出以$i$为结尾最短合法括号后缀就行，（设最短长度为$g_i$,总数为$f_i$(设最短的位置在$j$)），因为所有合法后缀一定是以$j-1$结尾的合法后缀再拼接$[j,i]$就行。（当然包括$[j,i]$)所以$f_i=f_j+1$)，所以，问题又成了求以$i$结尾的最短合法括号序列了。这个用$g_i$更新好了，挺好想的，然后没了。

10.28

唐题

给定一个序列$a$，和一个数组$k$, 定义函数$r(x)=x\text{的因子数}$,需要构造出序列$b$满足$\prod b_i | k$,使得$\prod r(a_i*b_i)$最大。

警示：一定要关注是连乘，所以给一项乘$x$相当于给最后的答案乘$x$。。。。。。。

这个其实很好想到了，就是把他唯一分解掉，那么$r(a)=\prod (a_i+1)(a_i\text{是每一个质因数的系数})$，那么最终的答案就是$\prod\prod(a_{i,j}+1)$，然后，因为$b$的限制，所以我们考虑一个质因数一个质因数的乘，我们发现给某一个$a$乘上一个质因数$b$，就相当于给相应的$a_{i,j}++$，所以最终给答案的贡献就是$\times \frac{a_{i,j}+1+1}{a_{i,j}+1}=1+\frac{1}{a_{i,j}+1}$，那么肯定就是$a_{i,j}$越小越好，用堆维护一下就行。然后分析一下复杂度，就是$O(n\log^2 n * 7)$,这个$7$是$k$最多的不同的质因子个数。$\log^2$是因为一个是堆的，一个是枚举每一个质因子在$k$中出现了几次

10.30

P5664 [CSP-S2019] Emiya 家今天的饭

关注到（看题解到）一个性质是，最多只有一个列会有多于$\frac{k}{2}$个数（绝对众数就是）。直接做没啥思路，然后就是正难则反环节，考虑容斥掉，答案就是：每行选不超过一个的方案数-每行选不超过一个且有一列超过了$\frac{k}{2}$。然后前面这个比较好算用一个$dp$算就行。然后就看后面这个。因为只有一列，所以直接枚举。假设枚举的是$col$列，那么设$f_{i,j,k}$表示在前$i$行中，第$col$列选$j$个，其他列选$k$个的方案树。那么最最后$\sum_{j=[0,n],k=[0,n].j>k}f_{n,j,k}$
转移就是

\[f_{i,j,k}=f_{i-1,j,k}+a{i,col}*f_{i-1,j-1,k}+(sum_i-a_{i,col})*f_{i-1,j,k-1}(sum_i\text{表示第$i$行一共有多少个数}) \]

复杂度$O(n^3m)$炸飞了
又观察（看题解到）到$j>k$即$j-k>0$，所以理论上只需要找到所有$j-k>0$的状态就可以了，那么状态就可以变为$f_{i,j}$表示在前$i$行里，选$col$列的数比选其他列的数多$j$个，然后转移差不多，不过复杂度变为了$O(n^2m)$。

总结：1. 转化题面，当正面做题不好做时，把题目进行转化，看这个是否好做（注意要是等价转化）2. $dp$过程中，要关注最终实际要求的值的性质，如这道题，有$j-k>0$的性质，所以就可以将维数减少，起到降低复杂度的目的。3. 性质性质性质性质！！！

11.16

P10680 [COTS 2024] 双双决斗 Dvoboj

~~考场上想了个假做法似~~

暴力：像维护线段树一样，为了求$l,l+(1<<k)-1$的答案，我们就去递归求$l,l+(1<<(k-1))-1$和$l+(1<<(k-1)),l+(1<<k)-1$的答案，这样修改复杂度为$O(1)$，查询复杂度为$O(n\log n)$，总体复杂度$O(n^2\log n)$
倍增：这个$2^k$很引导人向倍增哪里向，那么我们就设$f_{i,j}$为$i,i+(1<<j)-1$的答案，显然有$f_{i,j}=\operatorname{abs}(f_{i,j-1}-f_{i+(1<<(j-1)),j-1})$,每次修改$i$都需要把$[1,i-1]$的$f$都修改了，查询就直接访问就行了，这样修改复杂度为$O(n\log n)$，查询复杂度为$O(1)$，总复杂度就是$O(n^2\log n)$
倍增+根号分治：不难发现上面两个都不行啊，那么考虑如何优化，看到上面这个结构，要想根号分治了。那就想办法让$n\to\sqrt{n}$。发现其实倍增可以只维护长度小于$\sqrt{n}$的，然后查询的时候大于$\sqrt{n}$的，就除以二然后递归求就行了，这样查询和修改复杂度就都是$O(\sqrt{n}\log\sqrt{n})$了，总复杂度就是$O(n\sqrt{n}\log\sqrt{n})$可过

总结：碰到像$1,2$这样结构的复杂度就要考虑把$n\to\sqrt{n}$了。

11.17

P11024 [COTS 2020] 定序 Redoslijed

暴力：$O(n!n)$不说
稍微优化一下：我们发现直接做染色会面临先涂的颜色可能会被后面的颜色覆盖这样就很不好做，那么我们考虑正难则反，后涂的颜色不会被前面的颜色覆盖，所以我们倒过来看这个顺序。这样就对问题进行了一个转化：相当于我们要把最终状态的颜色一个个扣掉直到变成全空，不妨用$0$来表示空，那么，一个操作什么时候能够执行？答案是：每个格子处于$0$或和当前操作的颜色相同时。那么新的暴力也就出来了，就是每次暴力判断哪个可以操作，能操作就操作，然后把该操作对应的区间都改成$0$。code
最后也就是正解（题解）了。这个思路还差最后一个优化。上面的复杂度主要是用在暴力判断和区间修改上了。有一个 经典(题解说的) 优化是把判断的区间拆成线段树上的$\log n$个区间，每个区间要记录这个区间是否可以涂色了，如果所有都可以，那么整个区间也自然可以。那么考虑要维护什么东西。我们发现一个区间只有几种情况：1.全都是$0$,2.除掉$0$后有一种颜色3.除掉$0$后有$\ge 2$中颜色。对他们分别进行设状态：$0,c,-1(c\text{代表一种颜色是什么})$。发现转移也很好转呀不说了。再说区间修改，每个数只有两种状态$0,!0$，然后修改也只会把$!0\to 0$，所以暴力改是没问题的，类似势能分析的复杂度感觉，只需要在向下递归的时候判断状态是否为$0$就行。ACcode

总结：1. 注意这个优化：如果之和一个区间的种类有关而与量无关的话，那么可以考虑用上面的优化方法2. 如果对一个数的修改最多只有常数的话，利用势能分析是可以判断暴力是否可行的。

P9102

这个啊，我的做法有点过于麻烦了啊我去我真服了。就是当$j\ge maxn$时，没必要真的存下来，都存放到$f_n$里面就行了，因为一定当$j\ge n$ 时，一定能更新了我真是sb

11.20

P7961 [NOIP2021] 数列

这个属于是不看题解一万年也想不出来的那种。
一开始被这个有序集合限制住了，如果是无序的那一定是从大到小开始考虑，所以有序集合其实也可以这么做，套一个组合数就行了
不过想到这也不会。
怎么想到：？设$f_{i,j,k,p}$表示在$0~i$中选了$j$个数,他们加起来的和$0~i$位共有$k$个$1$，并且向$i+1$位进了$p$个$1$的权值和。那么转移就是枚举第$i+1$个数选了多少个，设为$t$,那就能转移到$f_{i+1,j+t,k+(p+t)\text{&}1,(p+t)>>1}$，然后组合数就是算在$n-j$里有多少个放$i+1$的方式，就是$\binom{n-j}{t}$，然后贡献，因为是和，所以就是$f_{i,j,k,p}*{v_{i+1}}^t$.转移方程就随之出来了。

f[i + 1][j + t][k + (p + t & 1)][p + t >> 1] += f[i][j][k][p] * C(n - j, t) % mod * v[i + 1][t] % mod;`

没了。

总结：1. 看到有序的思考是否可以通过套组合数的方式变成无序的。2. 注意转移状态是一定是合法的转移到合法的，比如这里的$p$一定要$\ge n$，(因为最多才能进位$n$个$1$),所以写for时就要限制$p\ge n$，否则会出错。3. 关于二进制的一些dp，还有数位dp还不会要多做两道

11.22

CF1706E Qpwoeirut and Vertices

首先能想到的是$ans(l,r)=max_{i=l}^{r-1}ans(i,i+1)&，然后这个很显然就可以用st表做。问题在于 $ans(i,i+1)$怎么求。那就到题解了
我们发现$ans(i,i+1)$就是表示加了$ans(i,i+1)$条边以后$i,i+1$在同一个连通块里。然后我们顺序放边，每放一条边就会合并两个连通块，这时就要考虑更新答案了。那就免不了要遍历连通块中的元素了。根据启发式合并的思路，我们就应该遍历小的连通块，这样，每个元素最多会被遍历$\log n$次，这样也就保证了总体复杂度为$O(n\log n)$了。那么这道题也就做出来了。

总结：把题意进行转化，转化成可做题。多做题，多积累思路。这道题的思路就是把最小值问题转化成了连通性问题。该方法能在关于两点之间路径的边权上有作用

11.23

CF1416D Graph and Queries

这个感觉是$kruskal$重构树的板子，就是把删边的过程反过来看，当作从后向前做加边，这样就能建出一棵重构树，然后发现删边的操作就是删去一个点，然后每次询问就是问一个连通块（也就是一棵子树）里最大的点是谁，这个用线段树就行了。所以我们只需要维护每个点的根是谁（因为删点后就可能变成森林）。这个看也能用线段树做。所以这个题就没了

11.24

P10795 『SpOI - R1』Lamborghini (Demo)

嘻嘻第一次独立写紫（虽然是板子。
这个就是，关注到$tx$互不相同，然后还要满足$tx$必须是最小的限制。那么能得到一个思路就是反着放点，然后这个点和之前的点构成的联通块中，任意两个点的路径经过这个点都满足这个点是最小点，但是这个连通块中不能有$t$比他小的，所以自然的可以想到把$tx$放到边上$u\Leftrightarrow v$ 的$t$就是$\min(t[u], t[v])$。然后把边从大到小放到连通块里，这样就能保证连通块里所有的点都比$tx$大了。然后贡献呢，就是对每一个连通块建一个权值线段树，然后访问加入边的两个端点所在连通块的线段树，根据题意的要求更新一下答案就行了，加边就是合并两个连通块，也就是要合并两个权值线段树，嗯，所以要写线段树合并。最后要思考的就是，在上述给边赋值的过程中，不同边的权值是可以相同的，但是合并的顺序不会影响算法的正确性。

总结：如同CF1706E Qpwoeirut and Vertices。该题就是把最小值这个限制改成了加边后是否联通的问题，再次印证了这个做法的应用场景：图中限制或要求的值是一个最值时，可以考虑通过顺序加边来转化成连通性问题

11.25

sjz2505

这个就是能把$a_i a_j < a_i + a_j$转化成$(a_i-1)(a_j-1)<1$，然后这样又因为$a_i,a_j$都是整数，所以只要异号就一定小于$1$，当然$0<1$，所以记录一下$>1,=1,<1$的个数就行了，时间复杂度$O(n)$

总结：
$n=1e6$想$O(n)$,我真是服了，写$O(n\log n)$以为能过。。。。。

11.26

P8315 [COCI 2021/2022 #4] Šarenlist

想到容斥是比较简单的，但是容斥的过程就不好想。就是，肯定是用所有的方案减去不合法方案的并集，那不合法方案可以分为第$i$条边不合法或$i,j$条边不合法或$i,j,k$不合法。所以就是容斥原理的系数即$-1$或$1$，那么设$f_i$ ($i$为钦定不合法的集合)表示钦定$i$这个集合不合法的方案数，那么有$an=k^{n-1}-\sum(-1)^{popcount(i)}f_i$，那么就考虑如何求$f_i$了。我们设$cnt$为$i$集合里本质不同的边的个数，那么如果$i$集合里的路径都无交，$f_i=k^{n-cnt}$。如果有交呢？我们把有交的路径看作一条路径就好了。答案也好统计。不过问题在于怎么判断两个路径是否在$i$里能不能看作一条路径，也就是是不是一个连通块，这个可以用并查集维护。那么这道题就好了。感觉比$t3$难

11.27 P8029 [COCI 2021/2022 #3] Akcija

是一道$A*$题目。
首先定义两种状态的相加，$(a_i,b_i)$表示买了$a_i$个物品，花费了$b_i$，那么有$(a_i,b_i)+(a_j,b_j):=(a_i+a_{i+1},b_i+b_{i+1})$,大小也是相同的。
简单介绍一下$A*$。$A*$是$BFS$的优化，也是$dij$的优化。重要步骤是一个股价函数$f_i*$，$f_i*$表示从$i$到最终目标的预估代价，当然不准确。$f_i$表示从起点到$i$点的实际的最小代价，这个是精确的。那么在搜索的时候会根据$f_i+f_i*$的大小进行顺序搜索，比如$f_i+f_i*$最小的最先搜索。这样能省去很多步骤。能发现当去掉$f_i*$，那么该算法就成了$dij$。所以复杂度是比$dij$优的。搜索的时候就是用$f_i+f_i*$最小的更新。
那么在说这道题，这个是要求前$k$优的。首先需要对$d_i$排序因为这些一定是先买的。那么暴力的话就是设$f_{i,j}$为在前$i$个里面选出$j$个物品进行买，其前$k$优的方案。（一个集合），然后就遍历枚举第$i$个选还是不选进行转移，$O(nk^2)$肯定不行。那么就要思考能不能再$i$这个位置只拿$k$个，而不是拿$nk$个。一个错误的想法是把所有的$f_{i,j}(j\le i)$放到一个集合里，然后取出前$k$优，因为即使$f_{i,p}<f_{i,j}$，也不能确定在之后的选择中，$i,p$会不会更优于$i,j$，这时就要用股价函数了。就是设$h_{i,j}$为在前$i$个里面选择$j$个后，能在后面获得的最优状态，也就是保证数量最大的情况下最便宜的状态。那么就考虑用后面的信息更新$h_{i,j}$，也就是考虑$i+1$选不选，那么能得到一个转移方程：

\[\begin{equation} h_{i,j}= \begin{cases} h_{i+1,j} & d_{i+1}\le j\\ \max(h_{i+1,j},h_{i+1,j+1}+{1,w_{i+1}}) & d_{i+1}\ge j+1 \end{cases} \end{equation} \]

得到这个就可以写搜索了。具体的，在处理好$i-1$的前$k$优后，枚举$i$加不加，也就是$f_{i,j}=f_{i-1,j-1}+{1,w_{i}}$或$f_{i,j}=f_{i-1,j}$。然后把这两个$f_{i,j}$放入堆或数组里，最后以$f_{i,j}+h_{i,j}$排序保留前$k$优就行。

注意：不管$i$加不加，都要更新原状态的股价函数，因为已经达到了一个新的状态，具体的，如果$i$不加，则$f_{i,j}\leftarrow f_{i-1,j}$,然后再以$f_{i,j}+h_{i,j}$排序，这样才是对的。

总结：遇到前$k$优，或搜索最短路问题，可以想$A*$,然后注意更新每个状态的估价函数来保证整体答案的正确性。

sez654

这个题想说的就是，一个区间中先操作区间最大值是更优的，所以枚举的时候直接枚举是否是区间最值就行了

12.7

sez840

设$f_i$表示$a_i$在$1$~$i$的出现次数，那么查询$[L,R]$中大于等于$k$的实际上是查询$f_i=k$的数量。那么此时不同区间之间的答案就有了可合并性。然后因为关于区间，所以想到离线下来。然后就从$1$到$n$遍历。发现从$i$变到$i+1$只需要把所有$a_j=a_i$的$f_j--$即可。暴力做肯定是不行的。这时我们把数分为两类：一类是出现次数小于$\sqrt{n}$的，第二类是出现次数大于$\sqrt{n}$。第一类修改就是$O(\sqrt{n})$，第二类数一定不会超过$\sqrt{n}$个。所以我们考虑对两类分别来求答案。第一类就是记下所有出现的位置，然后暴力修改。但是此时发现查询是$O(n)$的。用分块就能解决了。第二类就更简单了，直接记录下位置，然后做一个前缀和，然后查询$[L,R]$内他出现的次数是否大于等于$k$就行了。

注意：当$k>\sqrt{n}$时，应当直接进行第二类计算，如果是第一类可能会越界。

总结：遇到出现次数可以根号分治；把不可合并的区间转化成可合并的区间可能会更好做；区间和分块。

12.13

AT_arc147_d

不看题解一辈子想不出来的那种
性质1：因为这道题有集合只能有一个不同的，所以可以设$S_i$和$S_{i+1}$间不同的位是$p_i$，那么只要确定了$S_1$和$p_i$，就确定了$S_2$~$S_n$，那么每个数出现的次数也就知道了。但是这时候还是不能求解答案。
性质2：假设现在有了$S_1$和$p_i$。设$j\in [1,m]$,$a_j$表示$j$在$S_1$中出现过时在$S_1\text{~}S_n$中总过出现的次数，$b_j$表示$j$在$S_1$中未出现过时在$S_1$~$S_n$中总过出现的次数。有$a_j+b_j=n$，这个比较好证明，不好想。
结合上面两个式子，当我们给定了$p_i$时，$S_1$所有可能序列所产生的贡献就是:

\[a_1\times a_2\times \dots \times a_m+b_1\times a_2\times \dots\times a_m+\dots+b_1\times b_2\times\dots\times b_m=\prod(a_i+b_i)=n^m \]

然后又因为有$m^{n-1}$个这样的序列，所以答案就是$m^{n-1}\times n^m$

P5400

恰好转钦定，设$f_k$表示钦定$k$个极大值，$ans_k$就是恰好$k$个极大值。又因为极大值最多有$maxn=\min(n,m,l)$个二项式反演得：

\[f_k=\sum_{i=k}^{maxn}\binom{i}{k}ans_i\leftrightarrow ans_k=\sum_{i=k}^{maxn}\binom{i}{k}(-1)^{i-k}f_i \]

暴力二项式反演得过程是可以过得，所以只需要求$f_i$就行。
那么为了求$f_k$，有$f_k=\text{钦定k个极大值位置得方案数}\times\text{被影响得数得填数方案}\times\text{不被影响得填数方案}$
首先定义一些数组方便书写$g_i=(n-i)*(m-i)*(l-i), G_i=(nml-g_i)$
下面分别来求：

钦定$k$个极大值得位置：
因为两个极大值不可能在同一个面上，所以每填一个数就会有一部分不能再填。那么从第一个开始，发现第一个能填的位置就是$nml$，但是第二个能填的位置就变成了$(n-1)(m-1)(l-1)$,剩下以此类推。所以$k$个极大值得位置的方案数就是$\frac{1}{k!}\prod_{i=0}^{k-1}g_i$,$\frac{1}{k!}$是因为这$k$个值得位置是无序的，应当是$C$,但刚才的算法就是$A$。
被影响的方案数:
首先需要挑选被影响的数填什么，也就是$\binom{nml}{G_k}$
这个要满足极大值得限制，所以不能直接求，比如：
第一个极大值填了后，有三个面的数不能比他大。
第二个极大值填了后，有三个面的数不能比他大。
但是六个面有交。
解决办法：如果第一个极大值比第二个极大值小的化，那么第一个极大值和他所影响的三面的数都不会对第二个极大值产生影响。所以就思考从小向大填。还有一个性质：如果一个立方体满足$k$个极大值的限制，那么任意交换两面不会影响正确性。所以我们可以把这$k$个极大值放到一个对角线上。（具体可以看题解的图）。此时思考怎么填数，此时我们从里向外填更好理解。因为$k$个最大值所影响的数的个数就是$G_k$，那么按照刚才的性质，我们再$k$这个极大值时只需要填$G_k-G_{k-1}$个数，同理得到在$i$这个极大值时只需要填$G_i-G_{i-1}$个数。那么填第$k$个极大值所影响的数时的方案数就是$A_{G_k-1}^{(G_k-G_{k-1})-1}=\frac{(G_k-1)!}{G_{k-1}!}$，$-1$是因为$k$这个极大值一定是$G_k$个数里最大的，所以就不填了。然后$k-1$呢，因为把$k$的都填了，所以现在就相当于变成了一个子问题了，剩下的也是。所以最终的式子就是$\binom{nml}{G_k}\prod_{i=1}^{k}\frac{(G_i-1)!}{G_{i-1}!}$
未被影响的方案数：这部分随便填就行了，就是$g_k!$
所以最终

\[f_k=\frac{1}{k!}\times \frac{1}{k!}\prod_{i=0}^{k-1}g_i\times \binom{nml}{G_k}\prod_{i=1}^{k}\frac{(G_i-1)!}{G_{i-1}!}\times g_k! \]

\[=\prod_{i=0}^{k-1}g_i\times \frac{nml!}{g_k!G_k!}\times g_k!\prod_{i=1}^{k}\frac{(G_i-1)!}{G_{i-1}!} \]

\[=\prod_{i=0}^{k-1}g_i\times \frac{nml!}{G_k!}\prod_{i=1}^{k}\frac{(G_i-1)!}{G_{i-1}!} \]

因为最终要算概率所以可以直接除以$nml!$

\[=\prod_{i=0}^{k-1}g_i\times \frac{1}{G_k!}\prod_{i=1}^{k}\frac{(G_i-1)!}{G_{i-1}!} \]

我们发现$(G_i)\text{和}(G_{i-1})$很接近了，所以考虑是否能把$G_{i-1}!\to G_i!$。我们发现差的就是$G_{i}-G{i-1}$这部分，我们结合一下$G_i$的意义，不难发现$\sum_{i=1}^{k}G_i-G_{i-1}=G_k$，也就是说所有的$G_{i-1}\times (G_{i-1}+1)\times \dots G_i$拼起来刚好等于$G_k!$，所以我们把$G_k!$乘进去得到：

\[=\prod_{i=0}^{k-1}g_i\times \prod_{i=1}^{k}\frac{(G_i-1)!}{G_{i}!}=\prod_{i=0}^{k-1}g_i\times \prod_{i=1}^{k}\frac{1}{G_{i}} \]

到此位置，我们就做完了！剩下就维护就好了

总结：1.恰好和钦定互相转化，二项式反演记清楚。2. 找出一些性质，如这个的交换两个面合法性不变，两个极大值不在同一个面，如果先填一个小的极大值不会对更大的极大值产生影响。对接替很有帮助。3.式子尽可能的化简，使最后的答案更好求。

P4351 [CERC2015] Frightful Formula

这个，看起来很像通式啊。
首先一定是不能$n^2$暴力求得，所以最终的答案一定是关于$f_{1,i}$和$f_{i,1}$和$a,b,c$的。所以我们就考虑$f_{1,i},f_{i,1},a,b,c$对答案的贡献是什么。首先考虑$c=0$时。那么认为向右走就是$\times a$，下走就是$\times b$，然后$f_{1,i},f_{i,1}$都有不同条路径贡献到$f_{n,n}$，所以套一个组合数和$a,b$的几次幂就行了，不是很难。
考虑$c\ne 0$时，$f_{1,i},f_{i,1}$的贡献不会变，现在就只考虑$c$的贡献。因为每次转移都会加上一个$c$，所以相当于每个$i,j$都有一个$c$，所以对每个位置的$c$拆贡献就行了。得到的式子就是$c\sum_{i=2}^{n}\sum_{j=2}^{n}\binom{2n-i-j}{n-i}a^ib^j$，那么我们倾向于让$2n-i-j$相同这样就可以用二项式定理了。所以就枚举$2n-i-j$，$\sum_{k=0}^{2n-4}\sum_{i=0}^{k}\binom{k}{i}a^ib^{k-i}=(a+b)^k$，然后发现这样会算多，因为当$i+j>=n-2$时，一部分起点是不合法的，所以需要容斥剪掉。容斥过程还是比较简单的就不说了。

总结：1. 这种有递推式的但只求一个值的，考虑初始值对其的贡献。2. 遇到$\binom{i+j}{i}a^ib^j$这样的形式，尝试让$i+j$变成相同然后利用二项式定理。
坑：时刻取模

AT_arc139_d [ARC139D] Priority Queue 2

最后的答案就是$\sum_{i=1}^{n}a_i$，进行一个很好的转化$=\sum_{i=1}^{n}\sum_{c=1}^{+\infty}[c\le a_i]=\sum_{c=1}^{+\infty}\sum_{i=1}^{n}a_i$。那么因为数都$\le m$，所以$C$枚举到$m$就行。那么现在我们就可以单独领出来一个$i$，求他的$c$了。我们发现当选出的数$\ge i$时$c ++$,小于时不变；在$pop$的时候，当$c\ge n+1-x$时，$c--$否则不变；那么这个$--$的操作其实不用管，最后与$n+1-x$取$\min$就行。但是因为只有$k$此操作，那么当$c-k>n+1-x$时，贡献就应该是$c-k$而不是$n+1-x$了。特判一下就行了。求答案就是$\sum_{j=0}^{k}val\times\binom{k}{j}\times(m+1-i)^j\times(i-1)^{k-j}(val\text{就是上面的所说的贡献})$。然后对不同$i$统计就行了。

总结：$\sum_{i=1}^{n}a_i=\sum_{i=1}^{n}\sum_{c=1}^{+\infty}[c\le a_i]=\sum_{c=1}^{+\infty}\sum_{i=1}^{n}a_i$很好的转化，能把$=$的问题转化成$\le$的问题。

坑：在枚举放的数时，不仅要枚举$\ge i$的还有枚举$<i$的数，这样的正确性才是正确的。如果只枚举一个，那么就会出现统计多或少的问题。

12.14

CF1097G Vladislav and a Great Legend

第一步转化：$x^k=\sum_{i=0}^{k}\binom{x}{i}S(k,i)i!$，所以问题转化转化成了$\sum_{X}\sum_{i=0}^{k}\binom{f(x)}{i}S(k,i)i!=\sum_{i=0}^{k}S(k,i)i!\sum_{x}\binom{f(X)}{i}$了。前面你都好说。那么考虑计算$\binom{f(X)}{i}$。考虑他的组合意义，就是建成的树中选$i$个的方案数。那么我们设$g_i=\sum_{i=0}^{k}\binom{f(x)}{i}$，现在求这个就好了。因为树是可以合并的，所以我们设$f_{x,i}$为$x$的非空建成的树里所有选$i$条边的方案数。然后这个树形dp来做。那么枚举儿子的时候把贡献分成三类：

只有原来的，不加任何新点或新边
只有新点，也就是只有$son$，没有原来的任何一个点或边
两个都有。

$f_{x,i}$是好转移的了，然后答案呢？我们发现，简单的将$f_{x,i}$累加起来并不是答案，因为有算重的部分。那么我们把答案在选出所有点的$LCA$处更新，也就是只更新$3$所产生的贡献。这样就好了（脑子是狗屎想了一天）

总结：1. 遇到$k$次方，转化成第二类斯特林数。2. 看到组合式子时，考虑他的组合意义，对问题进行转化。3、取模的常数大，可以用``add(x, y) return x + y > mod ? x + y - mod : x + y```前提是$x, y<mod$4. 不转移无用状态，例:乘积中有一方为$0$

AT_agc045_d

第一步思考他会怎么灭灯。由于并不知道到底是哪一个阶乘，所以相当于任意一个数都是本质相同的，所以他就按照$1$~$A$顺序点就行了。（注意顺序点的意思是连续点下去知道点完他所对应的环，由于他知道亮的点是谁，所以当他将一个点从亮点到暗的时候他完全可以再点回去，这样就能一直点下去了知道点完一个环）
第二步思考他什么时候会死什么时候不会死。第一点，如果$1$_{$A$中有一个$i=p_i$，那么他点了以后一定会死。第二点，设第一个出现$i=p_i$的位置是$t$，那么如果在点到$t$前都亮了，那么就不会死。然后，当$A+1$之后的数都可以被$1$}$t$点到，也就是他所在的环有$< t$的值。所以前$1$~$t-1$个值就包含了所有的非自环

那么我们要做的就出来了。
接下来，我们都将采用插入法，及，先确定若干个环，然后再向里面插入一些数。
枚举$t$,然后计算前面没有$p_i=i$，$A+1$之后每个数都能被$< t$的值点到，中间任意了。

计算$1$~$t-1$没有$p_i=i$，也就是个数恰好等于$0$，然后恰好转钦定，设$f_i$表示钦定$i$个自环，那就是$\binom{t-1}{i}(t-i-1)!$前面$C$不说，后面是因为插入法，让前面先形成若干个环。
计算$A+1$后的部分。因为我们采用插入法，所以就是将一个数放到一个前面环之中，也就是放到任意一个数后面。一开始一共有$(t-i-1)$个数，插入一个以后就变成了$t-i$个数了。以此类推。贡献就是不断乘的过程。
计算中间的部分。还是插入法啊。现在已经有$t-1-i+n-A$个数了。因为中间的部分也可以单开一个自环，所以每次的选择就多了$1$,也就是$(t-1-i+n-A+1)\times\cdots$

总结：~~不知道总结啥感觉以后还是不会~~1. 遇到有操作的题先思考有没有通用操作2. 恰好转钦定。

坑：因为前面可以没有自环，所以$t$可以$=A+1$，此时$c$应该等于$0$而不是$t-A=-1$，因为中间的数还是$0$个

12.15

qoj9904

暴力的想法就是将$a$排序，然后一条一条连边。这样显然是会炸的。我们考虑，有时候$i,j$之间会连好多条边，但只有一条边才会考虑，所以我们就不想让这样的事情发生。然后如果在$i,j$时再判断是否连过就不会有实质性优化，所以我们考虑$st$表，就是维护$(l,t)$是否$r,t$与连过边，$(l,t)$表示的就是$[l,l+2^t-1]$。那么我们对于$l,r,t$及连$[l,l+2^t-1],[r-2^t+1,r]$连边时，首先判断是否连边(用并查集)，如果连过边就返回，否则就递归取处理$l,r,t-1$和$l+2^t,r-2^t,t-1$。当$t=0$时，说明此时到单点了，那么就判断$l,r$是否连边，如果没有，连上，并且将答案加$a_i$。再分析复杂度，因为一共有$n-1$条边，那么均摊到每一个单点上就会连一条边（约等于）也就是遍历两次，那么单点的父亲被访问两次，但是只会访问$n/2$次，所以均摊也是$O(n)$，一共$n$层，所以就是$O(n\log n)$

总结：遇到区间与区间连边的，可以这么优化

QOJ14718

暴力的想法时先跑$dij$求出$mx$，然后对于每一个$i$来说，枚举一个$j$，再枚举一条边$(u, v)$，然后让$i$和$j$都走到这条边上（所以要判断一下，如果走到上面，但是会浪费步数，就不走）。具体的就是让$i$到$u$，$j$到$v$，然后从$u$和$v$的中间再向$1$走。所以$j$一定是离$v$最近的一个点。然后考虑$i$。如果$i$不是离$u$最近的朋友，那么存在一个更近的朋友$x$到$u$，那么走到$i$和$x$的中点一定比走到$u$和$v$的中间更优，因为显然可以不走重复的边走到$u,v$中点，所以就不在这里统计$i$的答案。因此我们得到一个很nb的结论：对于一条边$u,v$只更新到这两个点最近的朋友的答案就行了。

总结：1. 找一个图上，距离一个点$x$最小的点，并且，有多个$x$等待统计，可以用多源$dij$进行。2. 从暴力起步，然后逐步强化条件，或缩小需要做的范围。实现方法就是找性质。

qoj4218

我服了构造交互题。
最值得一提的是这个的$k+1$染色。因为这个限制了任何一个导出子图度数$\le k$，所以可以选择先删掉一个点，剩下的点染色，然后这个点的颜色就是与他相连的点的$mex$。没了

细说一下怎么染色：
首先取出当前点里面度数最小的点，将其度数改为$0$，并将与其相连的点的度数$-1$，然后递归进行染色。该染它的时候就暴力走一遍$mex$。然后维护度数最小的点不能暴力，因为会$T$，这里采用可删堆，（也是复习到可删堆了）

总结：$k+1$染色的方法好用。可删堆还要练

12.16

P2891 [USACO07OPEN] Dining G

以前写过的题。将每一头牛拆成两个，连一条流量为$1$的边，表示一头牛只会使用一次。然后就将食物和牛连边就行了，跑网络流。

注意：在$bfs$分层的时候$dep[s]=0$；当前弧优化在$dfs$中体现就行。

12.17

P14344 [JOISC 2019] 两道料理 / Two Dishes`

两道菜必须连续做且不能休息，所以整个问题相当于问从$(0,0)$（左上角）走到$(n,m)$（右下角）所获得的最大贡献是多少。现在我们定义贡献：我们对$a,b$求前缀和得到$s1,s2$数组。然后对每一个$i$来说求出一个$p_i$，表示完成第一道菜得前$i$步时，最多能做$p_i$步第二道。对每一个$j$求出相同含义的$q_j$。然后我们发现对于做到$i$来说，当做第二道的步数$\le p_i$，$i$的贡献才能加上。也就是$(i,p_i)$要在路径的右上方才有贡献。同理$(q_j,j)$只有在路径的左下方才有贡献。此时这里有两边不太好维护，于是我们只维护在左下方的。处理方式就是将所有的$i$的贡献都加上，然后处理严格在路径左下方的$(i,p_i)$的贡献。只要把$(i,p_i)\to (i-1,p_i+1)$然后值赋为相反数就行了。然后能够得到一个转移方程:

\[f_{i,j}=\max(f_{i-1,j}+S_{i,j},f_{i,j-1}+S{i,j}-S{i,j-1})(S_{i,j}=\sum_1^j val(i,j))) \]

我们发现这样还是不好转移，此时关注到最后一行的答案一定都会加上，所以考虑转移时加上上一行的贡献，于是转移方程就比变成了:

\[f_{i,j}=\max(f_{i-1,j}+S_{i-1,j},f_{i,j-1}) \]

发现这个形式就是给$f_j+S_j$，然后前缀取$\max$，并且$S_j$也是一个前缀和，所以就想到于后缀加，然后前缀取$\max$，所以我们可以维护$f$的差分数组，然后怎么维护最大值呢，就是如果有值$< 0$，那么就将其变为$0$，然后改变后面的差分数组，就是将一段区间变为$0$，用线段树维护就行了。

总结：后缀加，单点加然后维护前缀$max$，可以转化为差分数组。通过暴力$dp$不断优化得到解法

P4696 [CEOI 2011] Matching

发现数字串和字符串的匹配很像。然后想用$kmp$。但是这个相等就不对了，所以要重新定义相等。我们定义两个序列相等为他们离散化后的序列相等，那么$kmp$的过程怎么模拟？例如序列$a,b$，后面加数$c,d$，我们假定$a=b$考虑如何判断$a+c=b+d$，发现序列离散化后就是每个数的排名，所以只需要判断$c$在$a$中的排名是否等于$d$在$d$里面的排名也就是有几个比他小的数就行了。然后跑$kmp$就行了。第几小用权值树状数组就行了

12.18

P2178 [NOI2015] 品酒大会

$SA$板子题，求出$height$用单调栈维护左右边第一个比他小的就行了。因为$i,j$后缀的$lcp$是$min(height_{rk_i\text{~}rk_j})$，然后就做完了。

服了卡我好久，注意：线段树维护一个区间的两个数乘积最大值维护$ans,max,min$就行了；然后$SA$板子别写错；想清楚到底怎么求个数

CF1408F Two Different

构造题：首先发现如果是$2^k$很容易就有构造方案。然后考虑不是$2^k$的，受到刚才的影响，我们考虑把他拆成二进制位，每一位为一的都能合成一个数，然后考虑怎么合别的，我们发现不同二进制位之间问题就是长度不同没法合，所以我们考虑如何改变这种状况。例如，我们想合成$2^i$和$2^j$,因为都是$2^k$，所以$\times$若干个$2$就能变成想要的。此时我们发现如果没有恰好相等的，那么就找一个大于$2^i$的，所以就用最高位的二进制位的长度给$2^i$合成，就能合成$2^{i+1}$，以此类推。最高位是用不完的这是显然的。然后就构造完了，代码也很好写啊

CF1442D Sum

非递减指的就是非严格递增。通过调整法得知选择后的数组只有一个是没有选满的。然后用缺一分治做。分治，我们枚举那个数组没有选满，那其他数组都是选满的，所以其他数组就相当于大小为$t_i$，权值为$sum_i$的物品，剩下跑背包。发现背包只能合并不能拆开，所以直接遍历不太好做。
缺一分治：$l,r,b[N]$，表示去掉$l,r$之间的物品时的背包是什么,目标状态是$i,i,b[N]$，然后呢对于$l,r,b[N]$，求出加入$l,mid$ 的背包$c$和加入$mid+1,r$的背包$d$，然后递归操作$l,mid,d$,$mid+1,r,c$，合并一次背包为$O(\text{背包大小}\times\text{物品数})$,所以每层的复杂度是O(nk)$的，一共$\log n$层，复杂度就是$O(nk\log n)$能过

12.19

P13552 鱼类考古学

这个通过调整法能发现现与后加一定比现加后与更好，$(x$& $y)+z\ge z, (x+y)$&$z\le z$，贪心的策略就出来了。题目要求有$n-k$次与操作也就是$k$次加操作，又因为与操作具有结合律和交换律，所以答案的方案可以看作：一堆数的与加上另一堆数的与等等等等。也就是说，题目要求我们把这$n$个数分成$k$个集合，求出每个集合与的和。此时我们按位考虑，比如现在在考虑第$i$位。贪心的想，我们一定想让第$i$位是$1$的与在一起，并且因为与会有损失，所以我们当然想让每一个数在一个集合。那么当第$i$位是$1$的个数$<k$时，我们就可以把这些数单独放一个集合，然后再操作$0$的部分，（相当于一个子问题）为什么呢？因为第$i$位是$0$的和第$i$位为$1$的与在一起的代价是补不不来的，单独放一个集合又是不劣的所以这样的操作就是对的。那么对于$\ge k$的情况呢？由于上面我们已经知道，第$i$位是$0$的和第$i$位为$1$的与在一起的代价是补不不来的，所以第$i$位是$0$的数一定放在一个集合。那么我们可以把这些数直接等效为一个数就行了。对于剩下的数，因为他们第$i$位与上都是$1$，所以不管怎么放都会产生贡献。又因为前面的数已经合成了一个集合，所以后面的数只有$k-1$个集合可选，所以贡献就是$k-1$个。那这道题就做完了

总结：遇到有不同操作的问题，首先考虑操作与操作之间存不存在贪心的关系。

12.20

CF1172D Nauuo and Portals

构造题。
考虑，我们如果建了一些传送门，那么每个点走过都会有一些路径。我们不希望后面建的传送门影响到他们，也就是我们考虑是否可以不在这些路径上建传送门。答案是可以的，把这些路径删了就行。我们从头开始考虑。发现如果在第一行和第一列建了一对传送门，能够让该去到$(1,n),(n,1)$的点满足。但是也会让一些点的位置发生改变，就是一些点通过传送门到了另一行另一列。不过这样刚好让剩下的点都能聚集到$(2,n)*(2,n)$，很好，因为这样就可以转化成子问题了。那么就构造完了。方案就是找到到达$(i,n),(n,i)$的点，然后在$(i,n)*(i,n)$的矩阵的边缘上建传送门让他们满足条件，把身下的信息修改了。就行了。通过构造发现一定存在方案。

总结：如果构造操作可能收到后面操作的影响，考虑是否可以有策略消除影响，或把影响操作的方面删去考虑是否还能构造出方案。

CF1810G The Maximum Prefix

这个一层一层的想。
首先考虑$k$固定的时候怎么做。一个想法是设$f_{i,j}$为前$i$个数前缀和最大值为$j$的概率，但是这样转移的时候发现不能确定再填一个数后前缀最大值是多少，因为长度不一定等于$i$。这是有一个常见的转化（感觉见过很多次了），就是在考虑在前缀前面加数，这样前缀最大值就好办了，于是我们从后向前$dp$，设$f_{i,j}$表示以$i+1$为开始的后缀的前缀和最大值为$j$的概率，那枚举$a_{i}$填什么更新$f_{i-1,j}$就好了。答案就是$\sum f_{0,S}*h_S$。但是$O(n^3)$并且无法推广到所有的$k$,原因就在于是从后向前填的。填每个数的概率都是不同的，所以不能推广到所有的$k$。那只能从前向后填。又不希望放弃向前缀加的思路，于是结合一下，设$f_{i,j}$表示，填了$1$~$i$，钦定$i+1$到结尾（不固定）的前缀和最大值为$j$，的概率。转移是好说的，但是问题是怎么统计答案。答案就是将$f_{0,S}=h_S$，然后输出$f_{k,0}$就行。因为在转移的过程就相当于在填数，所以概率已经乘上了，权值又是$h_S$，从$S\to 0$已经说明了前缀和最大值是$S$，然后长度为$k$的数组$k+1$后的前缀和最大值显然是$0$。然后就无了

总结：遇到与前缀有关的填数问题，可以考虑向后加也可以考虑向前加；遇到期望题，牢记$E(x)=P(x)*val(x)$。概率和贡献不需要一起求，这里就是先将$val(x)$乘上再乘上概率。

AT_agc061_c [AGC061C] First Come First Serve

这个题一开始没什么思路，相当于一个计数，但是这个判重很难受，我们考虑能不能把重复的方案设为不合法，然后统计合法的方案数。首先来考虑什么时候会重复。就是说，一个数选左端点和选右端点后的序列是相同的，也就是该数的位置是相同的。也就是说这个数对应的区间之中没有一个选的数。这时，我们肯定只保留一种方案，那么我们就保留左端点。那么定义一个区间不合法为：该区间内部没有点，并且这个区间选了右端点。计数部分就是考虑怎么减去不合法的，我们发现，如果一个区间不合法，那么左边的区间所有与他有交的只能选左端点，右边区间与他有交的只能选右端点，所以一个区间不合法，那一段区间的方案就确定了。这时我们设$f_i$为前$i$个区间的合法方案数目。首先如果都合法，那么$f_i+=2f_{i-1}$。然后此时考虑$i$区间不合法。设$l$为$i$区间影响的最左边的区间，$r$为$i$区间影响的最右边的区间。那么当我们计算$f_r$时，$[l,r]$这段不合法的方案就会被计算上，计算的次数？就是$1*f_{l-1}$，所以$f_r$应当$-f_{l-1}$。那这道题就没了。

总结：遇到判重，考虑是否能把重复当作不合法方案，然后对合法方案计数；容斥不一定只能用容斥原理和二项式反演。

12.21

集训题：

给定一个长度为$n$的序列$a,a_i\le 10^7$，求不重集$\left\{ x|\gcd(a_i,a_j)=x,i\ne j\right\}$的大小，也就是不同的$\gcd$个数。

然后这个想一会能想到一个容斥:$g_x$表示$x|\gcd(a_i,a_j)(i\ne j)$的个数，$f_x$表示$x=\gcd(a_i,a_j)(i\ne j)$的个数，那么$g_x=\sum_{x|y}f_y$，那么$f_x=g_x-\sum_{i=2}^{+\infty}f_{x*i}$。然后发现复杂度在于后面的这个求和。能知道复杂是$10^7\times(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}\cdots)$，发现后面这个是调和级数。然后这个调和级数算成$\log n$了然后就分析错了然后就挂了服了。然后调和级数大概是$\ln n$的，然后就过了。我服了我服了我服了

P9339 [JOIST 2023] 曲奇 / Cookies

首先找到一些性质。假设现在用了$t$个桶$X$，并且$X_i\ge X_{i+1}$，那么这$t$个桶最多能装（不一定能装下）$\sum_{i=1}^{n}\min(t, A_i)$。然后能得到一个暴力的式子$f_{i,j,k}$表示用前$i$个从大到小的盒子，用了$j$个盒子，放下$k$个饼干是否可以$(0,1)$，然后$f_{i,j,k}\to f_{i+1,j,k},f_{i,j,k}\to f_{i,j+1,k+b_i}$，然后可以滚掉一维，变成$f_{j,k}\to f_{j,k},f_{j,k}\to f_{j+1,k+b_i}$。然后呢，题目给了$b_i$互不相同，而$k\le sum A/ b_i$，所以调和级数，一共有$S\log S(S=\sum A_i)$，个状态数。复杂度$O(S^2\log S)$发现这样还是不行。然后又发现这个$dp$只有$0/1$，所以$bitset$优化一下。就变成$O(S^2\log S/w)$。过了。

总结：这道题还有很多不理解的地方啊：为什么一定要降序，为什么找答案的时候要顺序。$bitset$优化好。

注意：只有$bitset$和$bitset$之间的位运算才能吃到优化。然后$bitset$的空间复杂度只占两位很小。

12.22

P8511 [Ynoi Easy Round 2021] TEST_68

这个题提了个醒就是看到样例里面有好多都是$15$，然后就想到可能只有一些值不是异或最大值，然后假设两个值$a_i,a_j$异或起来是最大值，那么当$x$的子树里没有$i,j$，那他的值就是最大值。所以最有只需要求$1,i$和$1,j$这个链上的答案就好了，这个用脚做。

总结：感觉这个性质很牛逼但是也很瞪眼。就是有关于子树外的，两点之间的问题之间的极值的问题，然后这样就能把问题转化成只求链上的，然后就简单死了。

注意：注意把该插入字典树里的值都插入，要不然会喜提调好长时间

CF407E k-d-sequence

首先发现能够构成等差数列的数 $%d$的值是一样的。有了这个性质后我们就可以把区间分成若干个区间进行求值了。然后对于$%d$相同的数发现他们如果是等差数列，那么他们$/d$后的值就是公差为$1$的等差数列。那问题到这就好多了。那么我们从左到右枚举$r$，然后发现一个区间能插入$k$个数成为等差数列，当且仅当$\max-\min-r+l\le k\to \max-\min-r+l-k\le 0$，那我们在线段树上二分找最左边的$l$满足这个就行了。$\max,\min$指的是$/d$后的值。然后对于$\max,\min$，可以用单调栈维护，维护后缀最大值和后缀最小值。就是每次弹栈都相当于把一段最大值（最小值）相等区间修改（加或减）。这个配合线段树就能做了。然后弹栈的次数是$O(n)$，所以复杂度有保证。那这道题就好了。

总结：对于维护动态维护后缀最大值（右端点不断动的这种，如果是全局该的话就不太好了）可以用单调栈。

12.23

P9809 [SHOI2006] 作业 Homework

首先思考暴力。1. 就是设$f_i$数组表示当前集合里$%i$最小值，然后每插入一个就更新$n$个，$O(n^2)$ 2. 这个有点操作。就是发现对于一个$i$来说，将值域分割成$n/i$个区间，然后对于每一个区间来说，找到最左边的内个数，然后找到$n/i$个区间内所有数的最小值(这个用$set.lower_bound$维护就好了)，这样就好了，$O(n/i\log n)$。然后关注，第一个暴力和$i$有关，第二个暴力和$n/i$有关。当$i$比较小的时候第一个暴力快，大的时候第二个暴力快，所有我们考虑结合一下，也就是根号分治。就是找到一个块长$B$，然后$i<B$的部分第一个暴力，$i\ge B$的部分第二个暴力，时间复杂度$O(n(B+\frac{n}{B}\log n))$，然后通过基本不等式得到$B=\sqrt{n\log n}$，复杂度$O(n\sqrt{n\log n})$，然后就过了。
总结：遇到题可以先想暴力，可以多想几个；猜复杂度的时候不一定只与$n$有关，可能和值域也有关，例如这道题就是$X,Y\le 3e5$，所以猜到是关于值域根号分治得到做法。

P14050 [SDCPC 2019] Connected Intervals

嗯这个有一个套路前几天讲的。就是一些森林连通块数等于点数-边数。（很想蛋白质，肽键啊）然后这道题啊就是一个思路每条边都有两个端点，我们令较大值为$\max$，较小值为$\min$，然后我们要求的是满足$l\le min<max\le r$的个数，设个数为$g$，然后我们要求的就是$r-l+1-g=1\to r-l-g=0$的个数。这个感觉很套路就是枚举$r$，判断有多少个$l$就行了。考虑一下这样怎么做。首先只需要保证$l\le \min, \max\le r$就行了，所以用一个$vector$，把$\max$相同的放到一起，然后每次扫$r$的时候前缀加就行了。维护过程和昨天写的最后一题挺像的。

总结：这个想肽键的东西很好用，要记住

CF1822G2 Magic Triples (Hard Version)

这个直接说吧，考虑枚举中间的数也就是$a_j$，然后发现$a_i$是$a_j$的约数，枚举出了$a_i$后然后就能推到$a_k$了.但是因为值域$v$是$1e9$，所以开$map$所以可以$n\sqrt{a}\log n$做。然后发现不太行。于是优化。发现当$a_j$特别大的时候$b$就不能很大了，也就是枚举$b$，$b\le \frac{v}{a_j}$。那这部分的复杂度就是$n\frac{v}{a_j}\log n$。然后这不就有一个两个暴力，然后还是在不同范围内跑的各有快慢的，所以考虑根号分治。也就是找$a_j$的分界线，啊，基本不等式$\frac{v}{a_j}=\sqrt{a}$了。得到$a=v^{\frac{2}{3}}$，就是$1e6$，然后就$1000*n*\log n$过去了，卡常大题。

总结：多想暴力，想不同方面快的暴力，然后看能不能结合。$map$在调用前用$.count()$判断一下有没有，比差值快不少。

12.24

P5071 [Ynoi Easy Round 2015] 此时此刻的光辉

一个数的约数个数是$\prod (P_i+1)$，$P_i$就是唯一分解后每个质因子的次数。我们要求的是一个区间乘积的答案，也就是所有数的每个质因子次数加起来再求答案。答案就是一个质因子在区间内每个数中的出现次数和。区间和？可以想到用前缀和优化一下。但是数组会爆。当然我们也会有另一个暴力：莫队做法（不太熟练得多用的）。但每次拓展需要把所有质数都遍历一遍所以复杂度爆炸。那么我们思考如何才能降低拓展的复杂度。嗯那就是减少需要枚举的质数个数。也就是说我们需要把一些质数在另一种方法统计。这时我们用第一种暴力，统计较小的质数。降低莫队的复杂度。但是这个较小是多少呢？嗯就是一个数$v$，大于$v^{\frac{1}{3}}$的质因数最多有$2$个。$v\le 10^9$，所以$1000$就是分界线。小于$1000$的质数只有$168$个，打表可得。那我们发现这两边的复杂度都对了，那这道题就过了。

总结：约数个数的转化见了好多次了。遇到区间问题，并且一个点的值只与自己有关或在一定范围内很好求的想莫队。

P9174 [COCI 2022/2023 #4] Bojanje

就是暴力$dp$就枚举时间$t$，然后枚举两个数。然后转移就好了。最后要求的是颜色数$\ge k$的概率。所以只关心每个颜色出现的次数。然后我们通过数的划分得到最多一共会有$42$个不同的形态（降序排序），每一个形态里包含着不同的顺序集合，每个元素向下转移的概率都是一样的，所以可以直接转移。但是$t$是$1e18$的。所以直接考虑矩阵快速幂。然后就没了

总结：遇到有确定状态数，且相同状态转移相同的，那么可以考虑矩阵快速幂优化$dp$。

P14775 [ICPC 2024 Seoul R] String Rank

这个想了一会就好了。后悔没打今天的模拟赛了。

就是$i<j$，则$Q_x{c[i:]}\subseteq Q_x{c[j:]}$，所以直接判断$c[i:]$和$c[(i+1):]$的最小$x$就行了。接着发现如果第$i$位为$c$，$i$右边第一个等于$c$的位置为$j$，那不一样序列一定是$i+[i+1,j]$。原因很简单不说。现在问题转化成了找到$[i+1,j]$中最短的序列使他没在$[j+1,n]$中出现过。接着我们考虑以$[i+1,j]$中每一个数开头的序列进行分析。发现长度就是他们的答案。因为他们的答案也是通过这样分析出来的，所以直接取最小值就行了。这时候相当于求一个前缀最小值（没处理过的地方认为是$+\infty$就行，但不用在代码中体现）这个$trick$和CF407E k-d-sequence一样但是还是没反应过来，见得少。

总结：单调栈维护前后缀最小值最大值的好用死了。线性谁不心动

P10224 [COCI 2023/2024 #3] Vrsar

有一个性质没想到。就是如果一个人爬到一个山上然后再下来再去另一座山上滑，那么会有$s_i$的浪费，所以不如一开始就直接去内座山上滑。所以只会滑一座山。有了这个就好做了。

总结：贪心，就是纯贪。

oi水平已变为0

P14636 [NOIP2025] 清仓甩卖

贪心+计数+卷积+双指针考察的还是挺全的

贪心：小$R$的策略其实就是一个假贪心。然后我们考虑一下什么时候会贪错，这个其实也是这道题的核心部分。在钱充足的时候，这样贪就是对的。但是问题是有$1$块的有$2$块的，当钱不够的时候就可能因为买了$1$快的而不能买$2$块的，但是实际上买两块的更优。具体的，当最后还剩下两元，$w=1$的$a_i>a_j$,和$w=2$的$a_k$，当$a_i+a_j<a_k,a_i>a_k/2$时会贪错。然后考虑对这个计数就好了。

计数：这个部分相对简单，就是枚举$i,j,k$，假设在买到这个的时候已经买了$x$个$w=1$的，$y$个$w=2$的，由于定义有$x+2y=m-2$,然后因为贪心的时候一定是从大到小贪，所以$y$个一定比$a_k$大，同理$x$个都比$i$大。并且$a_j,a_i$之间不能再有$1$了，要不就不能让$a_i,a_j$连着了，然后套组合数和卷积及举行了。

总结：贪心

P9906 [COCI 2023/2024 #1] Kocke

就是倒着算挺好想的。然后有数的是连续的也能想到。然后这个$dp$的部分感觉有点吃操作，不太好理解。就是设$f_{x,y}$表示长度为$x$，边缘是$y$的方案数，不重复。然后有$f_{x,y}\to f_{x+1,y+1}$直接走到旁边去，$f_{x,y}\to f_{x+1,x+y}$跨过区间去另一边，$f_{x,y}\to f_{x,y+2}$，就是在中间游荡，相当于浪费的。因为浪费一定会重复走点，所以浪费的步数一定是偶数，所以加$2$相当于是做前缀和。然后不重复是为什么呢。可以考虑$f_{x,y}$是不重复的，那么有新的序列就一定是前两种转移，所以这部分是合法的。然后就会有一个疑问，有$f_{x,y}\to f_{x,y+2}$这个操作，那么$f_{x+1,y+1}$可以由$f_{x,y}$和$f_{x,y+1-x}$转移过来，但是$f_{x,y}$也可能被$f_{x,y+1-x}$转移过来，这样也是不重复的吗？是的。原因在于当$f_{x,y+1-x}$转移到$f_{x,y}$后，$f_{x,y}\to f_{x,y+1}$这一步和原来$f_{x,y}\to f_{x,y+1}$这一步将$y+1$放的位置就不同了，就处于两端了。然后最后统计答案的时候需要统计$f_{x,n-1}+f_{x,n}$，统计$n-1$的原因是因为最后可能放到$n-1$了，这是一个方案，但是没有办法把这个方案贡献到$f_{x,n}$这部分，但是实际上是可以有这个方案的，就是游荡一下。所以要加上。

arc212_e

CF1059E Split the Tree

要写，好题。想$dp$，用子树信息更新父节点。一开始是想到$f_{i}$表示$i$子树被最小路径覆盖此时的到$i$最短的一条路径的权值，但是不可做。问题在于：有$L$的限制没法处理。那么我们设$ans_{u}$表示$u$子树的最小路径覆盖，那么$ans_1$就是答案。最好的情况$ans_{u}=\sum ans_v$，就是所把$u$放到子树的一条路径里。但是路径里可能塞不下$u$，就是由于$L,S$的限制。所以我们要记录是否能塞下。当然我们不能简单地记录$f_{u}$表示是否能装上$fa_u$，因为$fa_u$有好多装法，所以这样的话我们就不能更新$f_{fa_u}$了。答案是记录最长能塞下的长度，即$f_{u}$表示当$u$里面的路径最小时，能向上拓展的最多的点。这样就能做了。转移啥的都好说。$f_{u}=\max(f_v)-1$，特判$\max(f_v)=0$的情况。

总结：由贪心得到的$dp$;

P2467 [SDOI2010] 地精部落

暴力的想法是$f_{i,S,j}$表示前$i$个位置，填了$S$集合里面的数，且最后一个数填的是$j$的方案数，$O(n^3\times 2^n)$。炸飞了。然后说是有个经典优化就是抛去$S$，因为最终一定会把$S$填满，所以就相当于用$1$_{$n$之间的数填满。所以在之前的方案中，我们可以把填过的数离散化一下，这样就变成了$1$}$i$个数。然后我们就得到了$f_{i,j}$表示用前$i$的数填前$i$位，最后一位为$j$的方案数。怎么转移呢？假设$i-1\text{位}<i$，因为是离散化，所以相当于$j$在前$i$位中排$j$位，所以第$i-1$位就要放$i-1$里面排名$le j-1$的数，也就是由$\sum_{k=1}^{j-1} f_{i-1,k}$转移过来。那么如果$i-1\text{位}>i$也就同理了，就找$j$~$i-1$位的就行了。然后如果直接转移发现要枚举一个$k$，为$O(n^3)$的，不过都是加前后缀，所以前缀和优化就行了。

这道题比较特殊的是，不模$p$的情况下答案总是偶数。因为两种情况总是成对出现，就是比如一个合法序列$a_i$，那么序列$b_i=n-a_i+1$也是合法的，所以就是成对的。

总结：填数的时候如果是大小关系的限制，那么可以考虑离散化后变成排名。

CF1775F Laboratory on Pluto

挺有意思的题。根据小学学的平移，能知道，最优的时候一定相当于一个矩形扣掉一个阶梯状的东西。所以想要求最优的只需要枚举短边$i$，然后$(i+ceil(n/i))*2$最小就行了，注意这个$i\le \sqrt{n}$，因为$>\sqrt{n}$的部分一定是$n/i$，能枚举到。确定了周长，就可以枚举边长然后看需要扣掉多少块然后算。我们发现矩形的四个角都可以扣掉，不妨先考虑一个角。因为是阶梯状，可以用拆分数来表示（重点），我们设$f_n$为拆分$n$的方案，$g_{k,n}$表示$k$个角拆$n$个点的方案。$g_{4,n}=\sum_{a,b,c,d,a+b+c+d=n}f_a*f_b*f_c*f_d$，然后如果直接算肯定会炸啊，然后这又有一个对于这样式子的优化，就是令$g_{1,a}=f_a,g_{k,a}=\sum_{i,j}g_{k-1,j}*f_{a-j}$，这样就能讲到$O(\sqrt{n})$了（因为要拆的点数是$\sqrt{n}$级别的）。那就做完了

AT_abc290_h [ABC290Ex] Bow Meow Optimizati

贪心型的$dp$。就是用贪心的到一个结论然后在$dp$，比较常见，需要掌握。
这道题因为和左右边猫狗的数量相关，首先能得到的是权值最大的猫左右两边狗的数量差不超过$1$，狗同理。也就是他们两个在中间（他两个不绑在一起是不优的，因为这样边界就是全猫或全狗了，这样乘的系数一定没有他俩绑一起小），那两边呢？两边的猫（狗同理不再多说）越靠近中间，他旁边的狗的数量差越小，猫的权值一定是越靠中间越大的。那么就是一个降序的，那猫和狗之间有没有权值大小关系呢？有，通过邻项交换法，假设有一猫一狗相邻且都在中间的左侧，猫权值为$a_i$,狗$b_i$，猫左右两边的狗的数量为$x_1,y_1$显然$y_1>x_1$，同理狗的为$x_2,y_2$，那么有$a_i*(y_1-x_1)+b_i*(y_2-x_2)\to a_i*(y_1-x_1-2)+b_i*(y_1-x_1+2)$，可得当$a_i>b_i$时猫在右侧，否则在左侧。所以就得到了重要性质，左右两边都是单调的。所以我们排个序后，设$f_{i,x,y}$表示用前$i$个权值，将左侧填了$x$猫$y$狗剩下的填右边的最小代价，转移是好说的。注意，当$m,n$都是奇数时，也就是说中间有权值最大的猫和狗，那么他们两个也会对答案产生乘积系数为$1$的贡献。其他情况则不会。

SP4420 KPGRAPHS - Counting Graphs

图计数。核心思路是容斥，用总的情况减去不连通的情况，不连通的情况是用枚举$1$所在连通块大小利用以前的信息。然后具体看代码也就会了应该。（欧拉图定义是度数为偶还联通的，这个就是将度数为偶的先算出来，就是$2^{\binom{n-1}{2}}$，就是$n-1$个点随便建，最后一个点看谁度数是奇数就给谁连一条边）重点是二分图计数，首先是枚举左部点和右部点，但是问题是左部点和右部点是相同的，实际上并关心一个点是左边还是右边，只关心这个图怎么样，所以只枚举左右部点还有除以$2^{\text{连通块数}}$,但是不知道几个连通块。但是呢，一个二分图可以看作是一个连通二分图或两个联通二分图或三个\dots，所以我们考虑求联通二分图，那这部分就和上面差不多，接着我们要看多个联通加起来的，这时我们还是枚举$1$所在的连通块的大小，和上面也差不多了。所以二分图就是步骤多了两个。

总结：模板，容斥

CF932F Escape Through Leaf

这个是李超线段树优化$dp$的板子题。$f_{u}=\min_{v\in son(u)}(f_v+a_u*b_v)$是显然的，然后这是$n^2$的。把$b_v$看作$k$，$f_v$看作$b$，这样就转化成了在许多线段里面挑$a_x$处取值最小的了。因为是树上所以要写合并，李超线段树的合并写法为:

void merge(int &c1, int &c2, int l, int r) {// c1 <- c2
    if(!c1 || !c2) return c1 = c1 + c2, void();
    int mid = (l + r) / 2;
    insert(c1, l, r, sum[c2].k, sum[c2].b);
    if(l == r) return;
    merge(ls[c1], ls[c2], l, mid);
    merge(rs[c1], rs[c2], mid + 1, r);
}

这个也是板子。
插入写法就是先判断中点谁优，然后再分别判断左端点和右端点谁优递归进行。

总体复杂度就是$O(n\log n)$了。

总结：李超线段树优化$dp$；线段树合并

CF1965E Connected Cubes

构造题，MC题。把每一列拉开然后联通一个颜色然后都垫高一层继续处理子问题

1.23 讲题

CF482C Game with Strings

这次讲课带给我们的就是先考虑这个题的简化版，然后在推广例如：
简化版为如果只有一个要猜的字符串，该怎么求。这个题的$m\le 20$，所以引导向状压方面想，那不妨把猜了那些数做状态。因为计算期望的式子都是从后推前面的，所以期望$dp$也一般从后向前$dp$（这个还是挺重要的）。那我们设$f_S$，表示猜了$S$集合里面的东西，然后期望再猜多少次能猜到。答案就是$f_0$。转移式子就是$f_{S}=\sum_{S\subseteq T}\frac{f_T}{tot}+1/0$,$tot$表示$S$中有多少$0$，就是还能猜几个数。$1/0$就是说，如果$S$这个状态已经能猜到了，那$f_S=0$，此时$f_T$必定等于$0$，显然。所以式子里就是$+0$，否则就是$+1$。那简化版就解决了，考虑强化版。一个暴力的想法就是对每个字符串求一下，然后讲$n$个字符串的答案加起来再$/n$。但是这样复杂度是$nm2^m$包爆的。这时考虑是否能一起算$n$个串的期望，因为最后都是加的部分，所以相当于把所有的$f_0$加到一起，那我们考虑其他的是不是加到一起也不影响转移呢？发现是的，因为系数都是一样的，所以可以当作是乘法分配律了。所以$f_S=\sum_{S\subseteq T}\frac{f_T}{tot}+cnt$，因为只有$S$不能猜到的才会产生贡献，所以加的$cnt$是$S$状态不能猜到的字符串数量。那现在问题又来了，怎么求$cnt$。暴力肯定炸，这里直接说结论了，感觉有点套路。对于每一个$S$，找出恰好猜不出的数量，然后做一个高维前缀和就行了。恰好猜不出的数量就是暴力找两两相同的最多的位置集合，设为$s$，贡献到$cnt_s$上。注意高维前缀和部分是异或所以不用容斥，如果是其他操作可能就需要容斥了。

总结：由简单版推强化版；高维前缀和想好要不要容斥。

CF1342F Make It Ascending

首先一个重要的转化是操作相当于是找到一些数然后把他放到一个数上面。所以我们发现，最后按照这样做出来的序列，他下标的相对大小关系和原数组是相同的。于是我们设$f_{i,S,j,val}$表示在最终序列里放了$i$个数，用了原序列集合$S$中的数。第$i$个数是原数组中第$j$个数，（因为上面提到的，我们需要保证坐标的相对大小关系），第$i$个数大小为$val$是否可到达。空间时间都炸。此时$dp$是一个可行性$dp$，只存$0,1$，有点浪费。那这个是这次讲课学到的第二个东西，就是可行性$dp$，把状态想办法放到答案里面。这个呢？因为要保证递增，贪心的想，在$i,S$相同的情况下$j,val$都要尽可能的小。那么我们的$dp$值就可以放较小值，所以我们肯定是把$val$放到里面去，因为$val$比较大。那状态就变成了$f_{i,S,j}$表示$\dots$ 第$i$个数最小是$f_{i,S,j}$了。转移的时候就枚举$i+1$选原数组数的集合$X$，因为贪心来说，$j'$要尽可能小，所以$j'$就取$X$中恰好大于$j$的$j'$。知道了这些就转移了。然后因为是枚举子集的子集，所以复杂度是$n^2\times 3^n$ 看起来有点悬对吧。不过没关系，时限是$7s$。

总结：可行性$dp$尝试把状态塞到答案里。一般是贪心的找。对于状态转移过程，判断是否能贪心的转移，使需要转移的地方变少。

AT_arc100_c [ARC100E] Or Plus Max

要求找$i or j\le k$，那不妨找$i or j = k$然后取前缀$\max$，这样发现必要条件为$i\subseteq k, j\subseteq k$，这时发现如果找$i or j\subseteq k$很容易，就维护$i\subseteq k$的最大值和次大值就好了。那怎么找到$=k$呢？需要容斥吗？其实不需要找，因为$i or j\subseteq k\to i or j\le k$,就找到了。我们对$k$求出$i\subseteq k, j\subseteq k$的最大值次大值维护$g_k$，然后对$g_k$取一个前缀$\max$就好了。

总结：这个是$\max$所以根本无法容斥，但思考一下发现其实不需要容斥。1. 因为或的性质，就是$i or j\subseteq k\to i or j\le k$,2. 因为这个题是在求$max$而不是求和，所以不需要容斥。

CF449D Jzzhu and Numbers

这个暴力方程就是$f_{i,S}$表示考虑前$i$个数，然后与起来是$S$的组数，复杂度就是$na$,滚动数组一下就是$f_S$。但是时间还是炸。这时我们借鉴上一道题的思路，是否能将$=$转化成包含的关系。我们发现，与起来等于$S$的$a_i$都包含$S$。所以我们考虑能否求出$g_S$表示与起来包含$S$的组数。然后最后容斥一下就行了。那包含$S$的组数也比较好求，就是统计$cnt_S$表示$S\subseteq a_i$的个数，然后$f_S=2^cnt_s-1$，$cnt_s$使用高维前缀和求出。此时我们发现$f_S$相当于是一个高维前缀和后的数组，那我们想要得到$=S$的就只需要高维差分一下就行，就是前缀和的逆过程，类比二维前缀和和二维差分。当然这道题直接容斥也行对吧，因为只需要求$f_0$。直接容斥。

总结：位运算的性质好用，与和或都有大小关系，可以利用；高维前缀和，高维后缀和。

CF1584F Strange LCS

弱化版就是每个字符最多出现一次，那很简单了，就是设$f_{i,c}$表示最长公共子序列第$i$为是$c$的是否可以，然后这个可行性，那我们直接把状态塞进去，发现$c$不能塞进去，因为没有确定的偏序关系（其实是发现转移不了）。所以放$i$，那贪心的想就是放$i$最大的，也就是$f_c$记录的是最大值。那现在推广到最多两个，因为上一个的转移依赖两个字符在每个字符串的相对位置，如果是两个就无法确定放的是那个，所以把放的是哪个放到状态里，就是$f_{c,S}$表示$c$字符在每个字符串里出现的是哪一个$1/2$第$1,2$个。然后就能转移了。但是问题又来了，转移的太多怎么办，直接炸了。这时需要用到贪心了，同一个字符，一定是选尽可能前的好，这样就能给后留出更多的空间了。

总结：$dp$过程中时常可能用贪心，就像不等式的放缩一样。所以遇到转移太多的时候思考一下贪心能否剪枝。

CF1187F Expected Square Beauty

弱化版是$E(B(x))$，那就是计算$E(\sum_{i=1}^{n-1}[x_i\ne x_{i+1}]+1)$,期望有线性型，所以$=\sum_{i=1}^{n-1}E([x_i\ne x_{i+1}])+1$，因为这道题期望就是概率，所以就是$=\sum_{i=1}^{n-1}(1-\frac{c}{ab})+1$，$c$是$x_i,x_{i+1}$代表区间的交的长度，$ab$是$x_{i},x_{i+1}$长度乘积。现在来考虑$E(B(x)^2)=E((\sum_{i=1}^{n-1}[x_i\ne x_{i+1}]+1)^2)=(\sum_{i=1}^{n-1}[x_i\ne x_{i+1}])^2+2\sum_{i=1}^{n-1}[x_i\ne x_{i+1}]+1$，那现在就是第一项问题。这里有一个知识点，看到平方的期望一般是把式子暴力拆解开来，即$\sum_{i}^{n-1}\sum_{j}^{n-1}E([x_i\ne x_{i+1}][x_j\ne x_{j+1}])$。又因为这道题的期望等于概率，所以当事件$a,b$独立时，$P(ab)=P(a)P(b)$，所以$[x_i\ne x_{i+1}]$与$[x_j\ne x_{j+1}]$无关联就是$i\ne j,i+1\ne j(i<=j)$。那我们只需要统计$i=j\text{或} i+1=j$就行了。其余的都好说，先说第一项，就是$[x_i\ne x_{i+1}][x_i\ne x_{i+1}]$，那他其实就是$[x_i\ne x_{i+1}]$，好说。然后$[x_i\ne x_{i+1}][x_{i+1}\ne x_{i+2}]$，这个就是找两个同时不等于的时候，发现这个不是很好找于是考虑容斥，就是将相等的减去，那就是$1-\text{前两个相等}-\text{后两个相等}+\text{所有都相等}$,这样就好了。那这道题就没了。

注意：如果钦定$i<j$，那需要在适当的位置$\times 2$。

总结：遇到平方的期望考虑是否能把式子拆开；遇到不好求的集合，可以考虑求出补集。

Contour Multiplication

弱化版不太好想，是所有$D$都相等。然后还有一个不太好想的$dp$状态。就是$f_{i,S,d}$表示考虑了前$i$位，前$i$位与$S$位有$d$位不同也就是异或有$d$个$1$的所有$C_i$的$X_i$之积。那答案就是$f_{n,j,D}$。考虑转移，也就是考虑$i+1$怎么放。$f_{i,S,d}$里的$C_j$因为都和$S$后面的位相同，所以可以转移到$f_{i+1,S,d}$，以此类推，如果改变$S$的第$i+1$位，那就是$f_{i+1,S^(1<<(i+1)),d+1}$了。正确性可以从不重不漏两个角度来思考，这里不再多说。初始化为$f_{0,C_i,0}=X_i$,然后考虑不全相等的情况。因为一个$C_i$唯一对应一个$D_i$,所以可以将状态设为$f_{i,S,d'}$表示考虑前$i$位，与$S$有$d'=D_i-d$个相同的数。那最终就是$f_{n,j,0}$。转移时类似的，不过是把$d+1$换成$d-1$。

总结：挺好的一道题，转化都比较好，状态设的也比较好，需要多复习。

CF1700F Puzzle

会了以后发现这道题挺有意思的。也挺好的。
单层的记录$\sum|{sum_a-sum_b}|$。双层呢？就是加了上下交换的操作，那执行上下操作一定时不劣才会执行。分别记$s1=\sum|sum_{a_{0,i}}-sum_{b_{0,i}}|$，$s2$同理。因为加的是绝对值，所以当$s1,s2$同号的时候没必要进行上下交换。只有当异号的时候才会进行交换，因为令$k=min(|s1|,|s2|)$，那上下交换$k$次就能让其中一个为$0$，但是左右交换的话就需要$2k$次才能达到相同的效果。所以此时上下交换会不劣。为什么不劣呢？因为当这个操作可能说是左右操作对后面的一段更优，但是如果现在就上下交换了后面就还要换回去，此时交换$2k$次与原来是相同的，所以说不劣。此时可能还有问题就是具体操作中能不能上下交换。我们可以形象的来理解，假设现在下面$<0$，上面大于$>0$，说明上面堆积了$1$, 下面少了$1$，又因为在先前答案中加入了$s1,s2$的绝对值，所以可以看作把多出来的$1$放到一个待处理的地方，放到这个位置的时候一定会经过现在的这个位置。那么我们就可以在放到这个位置的过程中通过这个位置上下交换，把$1$运到下面缺$1$的代办位置中。这样感觉就能理解了。

总结：贪心。先想弱化版。挺有意思的。需要复习

sez857

线段类的$dp$。
这个首先$n$是假的，因为可以离散化变成$m$级别。然后$f_{l,r}$表示使用$l,r$内的线段得到的最大值。然后就枚举$k$，让$l,r$内经过$k$的线段都聚集到$k$，然后转移。注：这样可能不是最优的方案，但是最优的方案一定会考虑到，因为当$k$中可能更优的方案会在其他的$k$中考虑到，然后$M^3$。（假贪心拿了好多分笑了

CF2159D1 Inverse Minimum Partition (Easy Version)

这个做法比较多样啊。我们一一介绍：

比较好想的做法。暴力方程肯定是$f_i$表示结束在$i$位置的答案的最小值。$f_{i}=\sum_{j=1}^{i-1}f_{j}+\lceil\frac{b_i}{\min(j+1\text{~}i)}\rceil$,有个最小值就很麻烦，所以一个比较自然的想法是用单调栈维护后缀最小值。那发现此时$\min$单增，然后简单的也能证出单调栈里的$f$是单增的，这个有点显然了（因为$b_i<b_j$若$f_i>f_j$的话完全可以用更新 $j$的来更新$i$那一定不劣）。所以此时就有单调性了。但是呢有一个问题就是当$r$动的时候单调栈里的数也会改变，但是我们知道斜率优化的东西一般是不带修的，怎么办呢？这时有一个比较妙的性质就是其实单调栈数之间的数（也就是不单调的数）是没用的，因为他一定不会作为段的右端点，因为找到右边第一个比他小的数跟他放到一起是更优的，并且他也不会作为最小值，因为他都比右边第一个比它小的数大了。所以我们发现，其实只需要用单调栈跑一遍就行了，那我们斜率优化也能做了，李超线段树什么的也行。时间复杂度是$O(n\log n)$或$O(n)$
这个做法需要一些性质。就是上面做法$f_i$表示的是结束在$i$位置的答案最小值是多少，我们将状态和答案换一下，设$g_i$表示使用答案为$i$能到达的最右端点是多少，那转移就$O(n)$转移，时间复杂度是$O(n^2)$一点也不优。此时我们考虑一下性质。发现转移过程不太好省（注意是不太好）那只能在状态数上下手了。我们考虑在最坏的情况下答案是多少。（需要构造的思想）就是说从$b_1$开始，从后面找到第一个大于$2b_i$的数（当然我们还是在构造出递增的序列的前提下)设为$j$。把$b_1$和$b_{j-1}$放到一段，那这一段答案就是$2$，同理，找大于$2b_j$的那个数以此类推，我们发现这样构造答案一定不会超过$2\log V$（$V$表示值域），也就是$128$。那就很好了啊，那就是$O(128*n)$过了啊
此做法依旧是对上面的方法的优化。注意到转移过程只是不太好省。我们发现我们转移到时候其实是枚举下一个段的右端点，我们发先这完全没有用到上面的性质对吧。因为答案一定$\le 128$所以我们可以直接枚举下一个端的答案为$k$，（例如现在在$g_{i}$)就是找到第一个$\ge kb_{g_i+1}$的数$j$，那么我就可以直接将$j$转移到$g_{i+k}$了，中间内些实际上根本没必要转移对吧。那这个复杂度就是$O(n+\log^2V)$ $O(n)$是输入
还能优化还能争！！！依旧是基于转移过程中的优化。思考我们是否真的需要转移那么多$k$吗？能不能想高维前缀和一样知转移一点呢？例如当前在$i$，我们某次$dp$的过程中将$i\text{~}j$放到了一段。那这段答案就是$x=\lceil\frac{b_i}{b_j}\rceil$，那我们找到这之中的刚好$>2b_i$的那个数$k$，那$i\text{~}k$的答案$\le 2$，$k\text{~}j$的答案$\le \lceil\frac{b_i}{2b_k}\rceil=\frac{x}{2}$，那什么时候会把$i\text{~}j$分到一段上呢？就是$x<2+\frac{x}{2}$上。那么我们会惊奇的发现$x<4$，也就是我们枚举$k$就是$O(3)$的了，此时复杂度来到了$O(n+3\log V)$已经接近神了。用这个基本上就能把困难版本解决了。

总结：看到题目的时候先想一下所有数是否都有用，如果不是的话考虑怎么缩减数，以及缩减出来有什么性质；判断转移过程是否能够省去一些，常见的省去的方法有：高维前缀和，贪心，构造找性质；构造判断答案的下界是比较好的方法。

第$k$小子序列和

答案就是维护一个堆，然后堆顶放的是第$j$小元素，（因为这个做法的原理是基于第几个$pop$的就是第几小，所以是第$j$小）。首先大小排序，每次取出堆顶集合，设为$S$（设其中最后放的数是$i$)，然后考虑两种情况。1.S+a_{i+1}放到堆里。2.$S-a_{i}+a_{i+1}$放到堆里。考虑一下正确性。就是说，他是由一个暴力过来的。就是最暴力的方法就是维护一个堆，然后枚举一个数（顺序），把这个数放到堆里代表的所有的序列的后面。那太暴力了。进一步的，我们可以把已知的必定会成为前$j$小的数拿出来不在考虑，然后对剩下的序列考虑找出最小的。那我们每次pop后拿到一个集合$S$(和上面一样)，那我们只需要把$i+1,\dots,n$加到$S$后面然后放进去就行。那接下来就是正解了，就是发现把$i+1,\dots,n$都加进去的操作其实就相当于1.放$a_{i+1}$2.放$a_{i+1}-a_{i}$。这两个方法是等价的。所以就好了。

听了第二遍了，才听懂，行

AT_arc084_b [ABC077D] Small Multiple

不会。就是建出来一张图分别是$%k$下的剩余系，然后一个点连$10$条边，分别表示$+1,+2,+3,\dots,+9$和$\times 10$，边得贡献就是,数位和增加的数。但是这样看起来就是会爆。然后优化就是只建$+1,\times 10$的边就行了。贡献就是$1,0$。确实可能转移错啊，就是进位的时候，不过我们发现转移错的情况一定可以被更优的方案替代掉，所以不用担心。说一下初始化的时候啊，除了$0$状态，其他的状态$i$都可以初始化为$i$，因为他再到达$0$状态一定加了$k$的正整数倍，所以是对的，然后就以$1$为起点$01$bfs就行了。

posted @ 2025-10-24 18:24 lghjl 阅读(12) 评论(0) 收藏举报

刷新页面返回顶部