跳转至

算法竞赛一句话解题&经典问题分析 ©ntsc 2024 镜像 上次同步： @2024/09/09

image.png

原名：算法竞赛一句话解题&经典问题分析 ©ntsc 2024

处理进度（仅仅处理了作者做过的题目，且不保证顺序！） - 绿：P10475 - 蓝：P10239

致CSDN网友： 本文章不定期更新！文章链接：https://blog.csdn.net/hzx616599/article/details/139567004

经典问题分析

基础知识与编程环境

  • 了解树的中序遍历的性质来设计算法→P1040

  • 按二进制每一位分开算→记前缀异或值X[0...N]，一段区间[L, R]的异或值就是X[L-1] xor X[R]→那么就是统计有多少个区间的异或值是1，那只需要统计X[0...N]中是0和1的分别有多少个，两个个数相乘就是区间个数。→P3917

  • 每一位拆开→定义f_j为以a_j结尾的答案，g_i为到a_j时第i位为1的长度→P4310

  • 预处理→P8865

  • 构造一个x，使得满足a_i^（异或）x<k的i最多→对每个a_i考虑，发现使a_i^x<k的x是连续的一段→逐位考虑，求出x的区间，相当于一条线段→求出覆盖线段最多的那个x就是答案→P6824

  • 简单构造→P7049→先黑白相间，然后再在一整块颜色a中点几个b。行宽为1时特判。

  • H形计数→枚举H中的横线，矩形中的“扫描线”优化→P7715

  • 模拟→P8289

  • 栈的模拟→P8815（不是普通的模拟，而是含有递归结构的模拟，是一类重要的题目）

  • 考虑异或和有前缀和的性质，化简式子→逐位考虑→P9236

  • P9571→用map<,map<>>存每个k,b线段即可。

  • P9588→set记录队尾，维护每个序列的队尾下标s[]，以及弹出了多少数字pre→对操作3，直接在s上二分出pre+pos，找到对应队列即可。操作4直接找set中最大值

  • O(n)求mex→桶+指针→P10032←模拟后发现会出现周期为2的循环，于是在模拟几次后直接讨论奇偶性

  • 诈骗P10114→看上去又是类似求所有(a_i,a_j)的\(a_i\text{xor} a_j\)之类的，但是发现不是特别好写→观察数据范围，有一项很特别，为\(\sum a_i\)→推导出不同的a值为1e3范围→\(O(cnt^2)\)两两枚举不同的a值，然后算上计数，暴力统计。

  • P10500→二进制套路：逐位判断，分类讨论，计算期望

  • 插队求最终排列问题→P10497→\(O(n^2)\)暴力模拟→更优的做法：从后往前考虑，使用树状数组维护（二叉查找树）

  • P1966→必须让第一列中第i高的火柴与第二列中第i高的火柴对齐。这好像是一个不等式（顺序积的和≤乱序积的和）→我们把A序列作为标准，B计算逆序对即可

  • P3941→\(O(n^3)\)的扫描线，再加上一个同余桶→即\(ton_i\)记录的是扫描线前\(pre_j\mod K=i\)的j的个数

  • P5512→打表

  • P5763,P9754→模拟

  • P6852→我们从小到大考虑每个数可以填哪→mex限制了区间[l,r]中不能包含k。这我们需要特殊处理一下。由于不能包含的是连续一段，我们可以用线段树来处理。→线段树每个节点只用维护对应区间内是否有空位置，然后支持单点修改和区间查询空位。

  • P10455→考虑如何快速找到以l为起点的最远合法右端点r→一个集合的校验值，最大的情况一定是最大对最小，次大对次小。→考虑倍增p，每次考察[l,r+p]是否合法，合法则更新r，p*2，否则p/2→考察[l,r+p]是否合法时，将mid=r，将[mid+1,r+p]排序，然后计算校验值，如果合法，则让[l,r+p]变成排好序的形式，否则还原原顺序

思维

  • 考虑每一个数字的贡献而不是考虑每一种情况那个数字做贡献→mna.816/p4

  • 观察数据访问，发现一个范围很小→将这个数据作为最外层循环，每次考虑这个数据取特定值时的答案的求解→P1311

  • 求最优化一个计算式，并且里面有一个值需要你来确定，并且不好直接求→二分→优化每一次计算过程→O(n)求多个询问区间内>m的数字的个数之和→先把≤m的数字赋0，然后跑前缀和，再对每个询问O(1)处理→P1314

  • 将字符串哈希后离散化→双指针，右端点不断扩散（右移），左端点贪心地缩小（右移）→P1381

  • 正确计算求因数的复杂度（是\(O(\sqrt n)\)而不是O(n)）→发现暴力可行→P1483

  • 转化为模型→求集合中小于k的最大值和大于k的最小值→set→P1503

  • 简单的数学贪心→连接1n加热第1杯，再连接2n加热第2杯，再……→P1984

  • 结论题→P2041

  • 逐位考虑后贪心取每一位的最大值→P2114

  • 直接搜索不行，因为发现m较小，考虑结合贪心→贪心先分出最短的木板→二分答案→搜索验证→剪枝→P2329

  • 贪心的线段覆盖问题→线段按右端点排序后，再从小到大将每个点排序→P2887

  • 直接模拟→先把所有牛的高度设为最高值，如果某两头牛之间能互相看到的话，那直接把中间这些牛的高度都减一→证明合法：唯一不合法的就是给出关系[a,b][c,d],且b>c，那么按上面模拟就会不满足[a,b]，但是发现这种情况本来就无解，所以上面的是正确的→P2879

  • 结合数据范围，直接使用map记录每个单词的出现文章，规避正解→P3879

  • 当贪心有时不能证明时，就在时间复杂度允许的情况下多算一点→P4395，——也许会像只填1或者2，但是实际上可能填3，所以我们考虑只填\(1\sim 20\)即可。

  • 等价集合问题→把 能够被其他钱凑出来的钱 给筛掉，剩下的就是我们必须要保留的面值→P5020

  • 合并果子加强版，每次取出最小的两堆，不能使用优先队列（log n）→维护两个递增队列,p,q，p为原果子桶排后的结果。每次从两个队头比较并取出两个最小的，然后放入q的队尾。可以保证单调性→P6033

  • 日期转化模拟→P7075

  • 廊桥分配→先忽略限制，我们维护2个空闲的廊桥队列，每到达一架航班，就给它安排编号最小的廊桥（分国内/国外）供其使用→处理 cnt1 和 cnt2 数组，分别表示国内和国际航班分配 i 个廊桥的答案数→最后答案就是 \(\max​(cnt1_i​+cnt2_{n−i}​)\)

  • 从双端队列中取数，使得取出来的是回文→找出与 a1​ 的唯一一个位置，记作 p。则序列被划分为两段（看成两个栈）→转化为每次可以取走这两个栈之一的栈顶，令最终得到的串是回文串→只有存在某个数 x，既在栈顶，又在栈底才能取走。否则无解→构造→P7915

  • 乘客优先选择最近的座位，并且让位给离那个座位更近的乘客，求矛盾（多个乘客到同一目标距离相同）数→贪心，按第一目标从近到远排序→逐个考虑每个乘客，分类讨论→P8073

  • P9744→观察数据范围，发现时间复杂度和m有关→考虑每次最多只进行一次前缀染色→枚举那次前缀染色的i→发现i+1只能在P中选，于是时间复杂度和m挂钩→前缀和，树状数组优化使得枚举了i后可以O(\log n)计算代价

  • 在稀疏图上选一个点，使得其与其它点的哈夫曼距离和最大→结论：**最优选点必定为上述四个点之一，或者某个已知点的邻点→**维护一下横纵坐标前缀和，问题变成多次回答某定点到所有点距离之和→P10025

  • 打表找规律，发现答案是等差数列→贪心求出首项和末项→根据序列中存在F的位置确定公差，因为公差\(\in[1,2]\)→P9183

  • 找规律。我们发现每一个连通块在竖着划分时都可以划分为\(2^0+2^1+\dots+2^i\)个方块，并且每一个连通块的第一竖（即\(2^0\)）都在第一行，也就是说我们只需要找到其右端点即可→找到右端点为第j列后，答案就是\(2^0+\dots+2^j\)。如果j>64，就直接顶到n→P9915

  • 数字变化类题目：-1或者\times 2，求最小操作数→转化为+1,\div2​（a 为偶数时可选）。他们的最小次数也是一样的→考虑尽可能多的 \div 2 即可→P10026

  • P10033→构造特殊填法

  • P10118→x+y=2×(x AND y)+x XOR y，记C=x XOR y→并且为了保证y>x，于是C的最高位1必须分配给y→剩下的popcnt(C)-1位自由分配，会产生\(2^{popcnt(C)-1}\)个方案

  • P10412→当且仅当 ∑a_i​≥0 时，数列 b 美妙，将 a_i​ 升序排序，之后依次考虑每个 ai​，判断使用加一操作和删除操作哪个更优

  • P10454→将序列展开后，考虑移动带来的影响→发现无论如何逆序对数量不会改变→比较前后两个情况的逆序对数量以得出答案。

  • P10449→美剧第一行的情况后发现，为了实现目标，后面的操作情况是确定的→模拟即可。

  • P1712→题目要求的答案跟“最大”，“最小”有关，所以我们就会联想到单调性→将区间按长度排序后，逐个加入区间直到有点覆盖≥m（线段树）→统计答案，弹出旧区间，加入新区间，重复过程。

  • P2332→我们花 O(n4) 来枚举一下 x,y 轴，对于 z 轴，我们通过同余+桶来优化。时间复杂度为 \(O(n^5)\)

  • P2512→考虑类似均分纸牌→推式子→转换为求到数轴上n个点最近的点→中位数

  • P3620→反悔贪心→题意简化为选择两两点配对使得总距离最短→每次从优先队列中取出最优的一对，如果和当前有冲突，就把冲突对减去最优对加入优先队列，作为一个候选项→如果后来选上了这个，那么就相当于“反悔”操作

  • P2827→考虑\(O(m\log m)\)的做法，优先队列模拟即可→但是题目卡\(\log\)，我们想到了一道题“石子合并”，也是用多个队列替代了一个优先队列→这种方法适用于原数据是单调的，新产生的数据也是一样单调的→本题就可以开3个队列，每次比较对头数据，取出最大的，然后把拆分后的数据加入另外两个队列尾部

  • P2859→贪心，类似区间覆盖问题的思路→将每段时间的左端点从小到大排序，然后一个个插入，插入时比较是否先前的牛棚中已经有牛挤完了奶，如果没有就新增一个牛棚，否则用挤完奶的牛棚，类“廊桥分配”

  • P2862→\(O(n^3)\)扫描线即可

  • P3045→我们先把c值最小的k个元素的c值之和变成答案→再维护c的小根堆，为c值最小的+p和c的差值最小的。即为这个东西的价格+这个东西替换的那个东西的差价→再维护p值的小根堆→那么我们比较两种取值的花费，那个小就取哪个即可。

  • P3514→重要结论1：如果 k(k>2) 可以得到，则k-2 也可以（考虑从区间两端减点）→找到最大的奇数，最大的偶数即可

  • P4280→从左往右每个-1位置填写的数字一定**单调不下降→**dp[i][j]表示从右往左第i个-1位置填j增加的最小逆序对数，dp[i][j]=min(dp[i−1][k])+第i个-1位置填j增加的逆序对数，其中k≥j

  • P4521→见每一个数字拆成\(i\times m+j\)的形式，然后考虑对每一个操作在对应的行列上打tag→统计答案时，先统计第一行的答案，再统计所有行是第一行的几倍，再加上几个m。

  • P4801→在数轴上考虑，先把偏移维度使水温成为0点→考虑贪心地交替取两个端点→取完一个半轴后，再考虑什么时候用水

  • P6608→如果我能知道序列长度是多少，也能知道操作次数是多少，我们能还原出这个序列→二分一下序列长度，算一下操作次数够不够

  • P7366→模拟,贪心→为了让这些树的高度差尽可能小，要把化肥给那个矮的→判断谁能先生出种子，如果它到达了可以获得种子的等级，那么我们就贪心的让它获得种子→在选择化肥的时候我们就贪心的选择最容易获得种子的那一个

  • P7514→对所有的值按大小排序，记录每个值对应是 a 面或者 b 面，得到一个长度为 2N 的序列。→我们的答案就是这个序列的某个子**序列**两端的差值→用双指针→我们可以删除前面一段和后面一段，中间的删除我们可以忽略，要求是删除的 a 面总数不能超过要求且不能同时删除同一张卡的两面→对于第一条就拿个变量动态记录一下删了多少个，第二条开个桶维护就好

  • P7521→我们将 a 升序排序→设答案所取的模数是 a_x​，可以 O(nlogn) 计算答案→我们将除了 ax​ 的数都 mod ax​ 后存入 \(b_1​,…,b_{n−1​}\)。设答案取 (b_y​+b_z​)mod ax​，分成两类：若 \(b_y​+b_z​≥a_x\)​，由于 \(b_y​+b_z​≤2a_x​−2\)，所以我们选择最大的两个 \(b_y​,b_z​\)。若 b_y​+b_z​<a_x​，我们排序后用双指针维护最大值。→我们**降序**枚举 a_x​ 为模数，当**当前答案** \(ans≥a_x​−1\)，则我们输出 ans 直接终止程序。

  • P7961→我们考虑到选择两个a_i等效于选择一个a_{i+1}，所以我们考虑先选k个不同的a_i，然后进行拆分→怎么样统计权值和呢？还是要用dp。计数类要不组合，要不dp。→设f(i,j,k,p) 表示：讨论了 S 从低到高的前 i 位，已经确定了 j 个序列 a 中的元素，S 从低到高前 i 位中有 k 个 1，要向当前讨论位的下一位进位 p→考虑刷表法

  • P8365→我们先看出几个性质：如果a=1我们考虑+b；除非a=1，否则只有第一个数我们会选择+b，否则一定选择*a→所以我们先将a=1的都加上，然后其余数都选择乘→如果没有a=1的，那么假设我们选a_i不乘，答案就从\(\prod_{i\in[1,n]} a_i\)变成了\(\frac{b_i}{a_i}\prod_{i\in[1,n]} a_i\)，所以选比值最大的即可。如果没有比值>1的则不选

  • P9378→考虑到实验i的价值是2^{-i}，因此极力保证最小的i不被破坏→我们先从小到大枚举i，把i加入答案集合，并判断当前集合是否合法→为了判断合法，我们记\(lim_i\)为i必须在第i次实验或之前被完成/破坏。我们枚举每一次射线，找到 pj​ 中第一个不在 S 中的之前没有被影响过的 pj,t​，标记其被射线影响。那么在\(p_{j,t}\)前的那些\(p_{j,k}\)的lim应该被更新为min(lim,j)。最后按lim排序，如果有lim_i<i的那么就不合法

  • P9755→二分答案，那么就要考虑 check 函数怎么写。考虑我们现在在判断时刻 m 是否合法，那么我们对于每个点再去求一个值 ti​ 代表最晚要在第 ti​ 时刻把这个点的树种上。→得到 ti​ 后，我们贪心地将所有点按 ti​ 排序，然后依次从其一直向根节点种树。

  • P10478→考虑系列是正负交替的，我们先把所有正数块进去，再考虑退款。→我们发现无论是合并两块还是去掉一块，我们都是要选影响的绝对值最小的→将所有块按绝对值加入小根堆，考虑弹出若干元素→如果堆顶为负数，那么相当于合并，将[x-1,x+1]删除，加入值为\(a_{x+1}+a_{x-1}+a_{x}\)；若为正数，则表示删除块，相当于合并负数。

  • P10465→避免无解，我们发过来考虑：有一个有序序列，什么样划分队列可以使得队列合法→把每个数加入的时间作为权值，发现合法队列的权值为单谷→设A为原数据排序后的序列，B是其权值对应，A={[0],[3,3],[6,6],[9]},B={[3],[1,6],[2,5],[4]}，发现同一个数字的权值可以任意排列→贪心得维护当前填到的队列是下降还是上升状态，贪心地填数

  • P10453→判断有无解可以用是否整除判断→求最少步数，我们对行列单独查看：发现是环形均分纸牌问题→均分纸牌有一个性质，就是必然有一对相邻的不会有派的交流，所以枚举，断环为链

STL 模板

  • P2161→使用自定义数据类型的set要重载运算符，自定义两个区间重叠为相等

  • P2202→先对所有点排序，然后维护与当前点横坐标差值小于k的所有点的集合，每次查找点集中纵坐标最接近当前点的点，更新答案即可

排序算法&分治

  • 在DAG中，更新一个点的信息如果需要先更新其来点→拓扑排序→P1038

  • 一些偏序问题（非计数类），考虑拓扑排序进行顺序确定→考虑不同情况反映在DAG中的情况→一定有序：存在n长链/错误：有环→P1347

  • 分层问题→给出一些节点的层级关系，要求分层→P1983

  • 考虑使用分治→扫描左部，将答案记录到树状数组中，然后扫描右部u，在树状数组中取符合要求的范围的区间和即可→权值树状数组→P5459

  • cdq分治→P5459

  • 点分治→P1429，P10461

搜索算法

  • 打表→P1549，P1790（也可使用搜索究极优化，插头dp）

  • \(O(2^{40})\)的搜索→Meet in the middle→P4799，P10484

  • 数据范围小的时候可以考虑直接搜索（填表）→P1004

  • 有些时候看上去n不适合搜索（e.g. n=50），但是加上剪枝也许就是正解→剪枝优化时间复杂度的证明和计算→P1034

  • 常见数矩阵个数优化（n4变n3）→P1191

  • 结合计算性质进行剪枝→P1092

  • 枚举/搜索→P1378，P1441，P1731，P1120。P2476,P4537

  • 结合dfs继续树上递推→\(f_{x,dep}=\sum f_{v,dep-1}\)→P3047

  • bfs→P3956，P5195，P10485

  • P10488→有“超过X步就输出more”→迭代加深→优化：估价函数

  • P1528→可行答案是一段前缀，考虑二分答案→贪心分配蛋糕，得到局部最优解

  • P3067→考虑对于每一头奶牛来说有3种状态，放在一组，放在另一组，不放任何一组，如果暴力枚举时间复杂度为\(O(3^n)\)→折半搜索

  • P3716→广搜，一步一步去走的话一定会TLE→冰块的数量不多，可以在广搜的时候枚举所有冰块，求出距离当前点上下左右最近的冰块，判断一下能否直接跳到终点

  • P4872→bfs，不过要多传递一些参数

  • P10027→状态f_{x,y,k}为位于(x,y)出且使用了k次药水的方案数，考虑在bfs时维护→如何求出从(x,y)出发，使用k次药水回到(x,y)的方案数呢？我们可以考虑\(f_{x,y,k}=\sum f_{xx,yy,k-1}\)，其中(xx,yy)为(x,y)的邻点。回溯时计算，或者对每个k分层bfs

图论算法

  • 应用分层图思想【模型】→P1073

  • 记录附加信息的最短路→P1078，P1144，P1608，P2047

  • 给定关系求层级数最小值→先整理出约束（e.g. A在B之上），连有向边→求最长链→拓扑排序→P1983

  • 总结出最后的图的特点→生成树→最大生成树→证明某些很难解决的情况不存在→简单解决→P1265

  • 结合数据范围，考察floyd算法可以实现的内容→求出任意两个点之间的距离→枚举配对→考察答案的几个情况→P1522

  • 预处理图后再跑最短路→删除不合法的点→P2296

  • 考虑到一个点要是有出度到v，那么一定要有从v来的入度，这个点才可能全员可达→点属于强连通分量→强连通分量找到唯一一个没有出度的集合，集合内所有点都合法→如果有两个集合满足，则无答案。→P2341

  • 将决策转化位图论模型→留在原地：自环，自爆：超级汇点→从floyd算法的角度考虑，A^k（A为邻接矩阵）的第i行第j列的数字含义是从i到j经过k步的路径方案总数→矩阵快速幂→累加\(A_{1,i}\)→P3758，P5789

  • 二分图最大匹配→P3386

  • Tarjan→P3387,P3388,P2863

  • Tarjan处理链和环→P2921

  • 判断x和y之间是否存在长度为k的非简单路径（无环）→路径长度可以是\(l+2k,k\in \N\)，l为最短距离→P5663

  • 差分约束→将不等式条件转化为图（\(x_i≤x_j+d_k\)，就按照最劣的建边，把x看成点，x的值看成dis，所以就建\(x_i→x_j,w=d_k\)）最后跑最短路，得到x的解。如果有负环，则无解，可以跑出来，就有解→P5960

  • P5663→考虑在一条边上往返奇偶性不变→对要求的阶段分奇偶讨论→求出1到其它节点的最短奇/偶数长度路径，O(1)回答

  • 对有大量边权相同（分组）的图建最小生成树→考虑kruskal本质：不断取出边权最小的边且保证没有环出现→一次取多条边

  • 每次构造一条边（损坏或者完好），使得最后一条边构造出来后才知道图是否被完好边联通→首先必须是生成树，并且最后被询问到的边一定要是树边，并且最后一条边的建立要实现这颗生成树而不能不联通→让每个点最后被构造的连边为树边→可以证明是生成树且符合要求→P5884

  • 对每个水流模拟→拓扑排序→附带分数的运算→P7113

  • 欧拉路径→P7771

  • 在一个 n 个点 m 条边的无向图中构造出每条边的长度 zi​（1≤zi​≤k），使得点 1 到任何一个点的最短路径都是**唯一**的→先写 dijkstra 板子，然后边权全部初始化为 1，如果碰上路径长度相同，则将当前这条边的边权加一，最后判断如果最大边权超过 k，则无解，否则有解，输出答案即可→P10178

  • P1407→将所有 现在或曾经交往过的 男孩和女孩连接起来，可以发现出现了一些环，而处在环中的婚姻不安全。→给无向图定向，均为男女之间连边，但是夫妻和前任的连边方向相反→如果一对夫妻在同一个scc内，则不安全

  • 次短路模板→P1491→首先找出一条最短路，之后一次去掉一条最短路上的边，对于每一次去掉一条边后的图都跑一次最短路

  • P1613→我们把每对可以1s内到达的点都连上1的边，跑最短路即可→为了预处理每对符合要求的点，我们记录g_{i,j,k}为i,j能否通过2^k路径到达，类floyd预处理。

  • P1653→先按题目所说的条件建边，然后scc缩点→考虑选择有n个入度0的点和m个出度0的点，那么答案就是max(n,m)

  • P1772→先看懂题目，发现都是从1到m，且路径\(+k\times\) 改变次数 最小→预处理\(c_{i,j}\)表示\(i\sim j\)天都走同一条路径的最小划分，\(f_i\)为前i天的最小花费→f_i很好转移，c_{i,j}的预处理：断掉i\sim j内所有不行的边，跑最短路。→结合数据范围，可以暴力完成。

  • P2057→将源点和汇点相连的人视为两个立场，要求立场相同的关系建一条有向边→为了解决冲突，我们就要断掉所有流量→最小割

  • P2149→对两个人分别建出其最短路DAG，然后用有向图dp求出最长重叠部分→注意可能是反向图的重叠，即答案可能是甲A→B，乙B→A时的最长路径

  • P2656→scc缩点后每个scc内的边都可以全部取完，其它的边只能走一次→最长路

  • P2756→网络流的建图策略

  • P2761→我们参考网络流建图的策略，将111..作为初始状态，000...作为最终状态（这里的1表示存在bug）→将每一个补丁作为一条边，边权为1跑最短路→不需要建边，只需要在最短路转移时枚举每一个补丁看看能否使用即可。

  • P3627→Tarjan scc缩点

  • P2746→第一问：我们采用局部思想：如果一个点有入度，那么就不用管他，所以我们统计出入度为0的点即可→第二问：问加多少边可以让图变成一个scc→设入度为0的点有S个，出度为0的点有T个，那么就是max(S,T)。这是一个常用结论！（证明https://www.luogu.com.cn/article/vmrnb8m9）

  • 最小费用流→将最大流中的bfs改为spfa即可。

  • P2860→我们要做的，就是连边将整张图变成一张边双连通图→缩点，建树，现在我们就要将一颗树变成一个edcc→ans=(leaf+1)÷2

  • P2865→次短路模板

  • P2886→floyd维护信息转移→矩阵快速幂优化

  • 【重要模型】P2939，P4822→可以存下KM条边→经典模型：分层图

  • P3403→模型：同余最短路

  • P3225→讨论割点→用Tarjan跑出割点，然后DFS搜索所有的联通快→计算每一个联通快中的割点数目：如果没有割点，需要从任意非割点的地方选择两个点建立；只有一个割点，设立在任意一个非割点的地方；如果有两个及以上个割点，则无需建立

  • P3254→网络流的建图

  • P3275→差分约束

  • P3469→vdcc→如果是割点，那么乘法原理，否则无影响→记得加上自己和其它点的答案（n-1）

  • P8867→缩点后在每一个点只有两种情况，选或者不选→如果选，那么用乘法原理计算出这个点选的方案（即这个点代表的边双里面的点的选择方案）→选一个点，就要求这个点和其他点联通→使用树形dp解决→统计u上的答案时，强制 u 子树外的所有点都不选，不选 \(fa_u​→u\) 的边，再累加方案数，即可保证不重不漏

  • P4171→2-SAT→将每种材料的每种做法拆成选与不选，在“不选汉式做法”和“选满式做法”间连边，在“不选满式做法”和“选汉式做法”间连边→对于每个评委的要求，从“不做第一道菜”向“做第二道菜”连边，从“不做第二道菜”到“做第一道菜”连边→tarjan之后，看是否有同一种材料的“选汉式做法”和“选满式做法”在同一个SCC中，是否有同一种材料的同一道做法的“选”与“不选”在同一SCC中，有就不行

  • 2-SAT→P4782→每一个人的条件都是a或b，然后问是否可以满足所有人的要求→考虑对每对命题建有向边，然后对每个命题拆成两个点，为满足或者不满足。→要求 (a∨（或）b)，转换为 ¬a→b∧¬b→a。对于这个式子，可以理解为：「若 a 假则 b 必真，若 b 假则 a 必真」。这里我们建边代表的是“必定要”的关系。对于那些非强制的关系，我们就不建边了。比如我们不建a→b。→最后跑强连通分量，看有没有¬a和a在一起即可。有就是矛盾。

  • P5304→我们肯定要建立超级源点，一次抛出批量的点对时间的答案→我们可以把点分组A,B，对A建源点，对B建汇点，这样就可以跑出一些最短路→那么怎么样分组可以使得每两个点之间都至少有一次分为不同的组呢？二进制分组！第i次分组，我们把第i位为1的和为0的分组。

  • P6768→构建网络流模型，二分答案

  • P6830→原图必须是一个由树或基环树组成的森林→如果题目中要求 u,v 之间有三条路径，此时无解。→我们先按题目给定的连通性 dfs 一遍**求出连通块**，如果有两个点之间路径要求为零或者为3，无解→剩下的点对里，如果要求为1，则直接连树边，如果要求为2，说明在基环树环上的不同子树内→先不考虑路径数为二的边，在剩下的路径数为一的边里面再次 dfs 求出环外的连通块，然后每个环外连通块取一个点，将这些点依次连成环即可。

  • P7608→等价于给 n 个点的环染色，不能有连续 k+1 个点的中颜色存在 2 个相同。→考虑当 n 很大的时候此时答案不是 k+1 就是 k+2，因为可以用 k+1,k+2 去凑出 n。当 n 不大的时候暴力枚举 ans 从 k+1 到 2k，当能用这些数凑出 n 时，此时就是最小的答案。→算出答案后与 x 比较即可。

  • P8817→时间复杂度要求\(O(n^2)\)，那么我们考虑枚举最多两个景点→我们考虑枚举景点B，这样我们就很容易找到最优的景点A，也可以找到次优的景点A。那么实际上景点C,D的选择和A,B的选择是对称的。我们再枚举B计算A时，可以得到景点B的最优价值和次优价值。我们再枚举景点B，找到合法的景点C，然后对B,C的最优价值和次优价值进行合法组合（即不能出现重点）即可。→怎么样找到两个点两两之间距离<k？对每个点bfs，\(O(n^2)\)。

线性结构

  • 单调队列优化dp→P1725

集合与森林

  • 使用并查集额外维护集合信息→将集合信息统一整理至某一个集合的代表元素上去，注意清空过期的代表元素→P1196

  • 断边维护连通块个数→化断边为加边→P1197

  • 扩展域并查集→P1525，P1892，P2024

  • 简单并查集维护，先处理相等的约束→P1982

  • 、先解决环的情况→缩点→然后拓扑排序→P1262

  • 区间2反转求和问题→线段树维护异或tag→P3870

  • 树上的括号栈问题→括号序列计数问题→出现一个)，它可以和之前的形成一个(..)的括号序列，这个序列还可以和前面的一些序列并列，形成更多合法序列→对每一个位置x记录以其为结尾的括号序列个数c_x，下一次若以son(x)为开头形成了一个括号序列，那么实际上有\(c_x+1\)个序列被形成，并且维护c数组→P5658

  • 给出若干条件：[l,r]之和为奇数/偶数，求最早矛盾→扩展域并查集→维护左右端点处前缀和的奇偶性→若给出区间[l,r]为奇数，那么\(pre_l\)，\(pre_r\)应该在不同并查集内，检查矛盾；另外一种类似。→P5937

  • P2391→倒序模拟→考虑优化，用并查集加速往前跳的流程。即维护f_i表示i前面的最靠近i的那个未染色的下标

  • P5903 →树上 K 级祖先→树上倍增，或者长链剖分

树形结构

  • 维护树链上的信息→树上倍增，树剖

  • 维护子树信息→dfn线段树

  • 从题目中整理出树的性质→设计树形dp进行最优方案求解→P1131

  • 结合数据范围，预估复杂度→搜索→设计搜索→因为每一层只能切断一个，所以就可以对每一个节点搜索其最优的切断方式（使用回溯的数据来贪心选择）→P1041

  • 理清题意→整理出答案的几种来源/情况→对于每一种情况独立思考做法，最后组合起来→P1099←答案有两种情况：来自直径两端，来自最长的侧链。并且来自最长的侧链的那个答案只需要计算侧链端点到直径的距离即可。不需要考虑侧链+一部分直径的情况，因为如果这种情况可以作为答案，那么直径就要改了！

  • 考虑每一个路线对那些点有贡献→树上路径加→树上前缀和→P3128

  • 判断树上两条路径是否有交→分类讨论→求lca→P3398

  • 求树上所有一段为根节点的串上的合法括号串数量→dfs中维护栈→P5658

  • 树上子树修改，单点查询→dfn序对应→P7746

  • 树上有点权，多次询问路径上点权和→预处理任意点到根的点权和，询问时求lca→P8805

  • P9619→答案肯定是k\sum w，k为每条边在所有生成树中出现的次数，可以证明k对每条边都是相同的。w为边权→由 Cayley 公式知完全图 \(K_n\) 有 \(n^{n-2}\) 个生成树。由于是无向图，每条边是等价的，所以所有边共出现了 \(n^{n-2} \times (n-1)\) 次，共 \(\frac{n \times (n-1)}{2}\) 条边，所以一条边出现次数为： \(\frac{ n^{n-2} \times (n-1) }{\frac{n \times (n-1)}{2}} = 2 \times n^{n-3}\)→再考虑快速计算\sum w→因为是异或，所以每一个二进制位分开讨论，想要产生贡献的情况只能是一条边所连的两个端点同一二进制位一个为 1，另一个为 0，又因为是完全图，所以组合计数即可。均摊。

  • P1505→树链剖分

  • P1967→这道题可以用很多经典算法解决，如树链剖分，树上倍增，kruskal重构树

  • P2573→我们发现最后最优的走法是一棵树→建边后跑最小生成树

  • P3942→令f(x)表示编号为x的节点与以其为根节点的子树中最近一个未被控制的节点的距离+k，如果没有这样的节点，则f(x)表示编号为x的节点与以其为根节点的子树中最近一个驻有军队的节点的距离→当f(x)>k时，在以x为根节点的子树中，存在不被控制当节点。f(x)>2k时，节点x必须驻扎军队。

  • P2634→可以使用点分治，但是有dp做法→定义 f[x][i=0,1,2] 表示在点x及其子树中，距离点x的距离在模3意义下为0,1,2的点分别有多少个→统计答案时匹配i和3-i即可

  • P2680→二分答案→Check函数：判定对于len>t的所有链，能不能找到找到至少一条长为k公共边，使得最长链的长度len-k≤t

  • P3621→性质题→考虑最少交换次数：其实对于每一个节点的左右子树，三种情况需要交换，1，左边全是小深度的，右边全是大深度的2，左边全是小深度的，右边大小深度都有3，左边大小深度都有，右边全是大深度的→dfs搜一遍就好了。

  • P3605→ans[x]=x的下属中比x强的=树状数组中加了x下属后比x强的−原来就比x强的→dfs过程中线段树/树状数组维护即可

  • P3541→交换子树只会对**横跨左右子树的逆序对**产生影响→只需要在**合并线段树**的过程中统计交换子树的逆序对个数和不交换子树的逆序对个数，取 min加入答案

  • 【典】P4185→每次询问跳过边权≥K的边可以从x出发到达的点的数量→可以将询问按 k 的值降序排序后离线解决→用并查集维护连通块，对于每个询问，我们将边权大于等于给定的边权 k 的边加入图中

  • 严格次小生成树→P4180→首先求出最小生成树→枚举没被选中的边来替换最小生成树中的边。→当我们把一条边加进去的时候，会形成一个环，我们只用找出环上除新加边的且不与新加相等边最大边删掉。→求树上路径上边权的最大/次大值，倍增可以实现

  • P4281→首先考虑到答案应该就是某两个点的lca→发现3个点两两求lca，最后总会有两个lca在不同的位置→答案在这两个lca中产生→后面发现**不重合的公共点才是最优解**

  • P5021→先二分那个修建的 m 条赛道中长度最小的赛道的长度 k→对于每个结点，把所有传上来的值 val 放进一个 multiset ，其实这些值对答案有贡献就两种情况：val≥k；vala​+valb​≥k→第一种情况直接答案 +1 。第二种情况就可以对于每一个最小的元素，在 multiset 中找到第一个 ≥k 的数，将两个数同时删去，答案+1，最后把剩下最大的值传到那个结点的父亲

  • P5838→询问树的路径上所有有权值为i的点→树剖，用vector维护链上的点的种类

  • P5854 →笛卡尔树

  • P5874→推导式子→线段树维护区间最值→为了防止取模后丢失大小信息，用对数来比较大小，以实现化乘为加

数据结构

  • 动态维护数字序列信息→权值线段树→P1168

  • 线段树模板→P1198，P1253,P3372,P3373

  • 偏序问题，又带有一点dp（上升序列）→使用数据结构优化dp→树状数组优化转移→P1637

  • 平衡树查询寻值前驱和后继→P1110

  • 维护区间极值+正负性分讨→P8818

  • 树状数组→P5094

  • 统计区间和在[l,r]的区间个数→考虑类似逆序对的树状数组做法，右端点扫右边，左端点O(1)统计→离散化→P5459

  • 可以使用multiset模拟二叉搜索树→P5076

  • 快速求01序列区间内最长上升子序列长度→预处理前后缀0/1个数，因为一定是0..01..1→\(max​:i∈[l,r]{pre_i​+lst_i​}−pre_l−lst_r​\)→结合时限，采用ST表求区间最大值

  • 区间修改，求区间gcd→发现区间修改很难办→证明差分数组的区间gcd和原数组的gcd相同（更相减损术）→维护差分数组→P10463

  • P10589→树状数组/权值线段树

  • P1456→多个可合并集合，多次询问合并后求集合max→线段树合并，或者可并堆→使用平衡树实现（merge）

  • P1533→因为区间不互相包含，所以将区间排序后从前往后双指针，每次在线段树中弹出一些，插入一些，然后线段树上二分查找即可。

  • P2073，P6136→平衡树

  • P2146→一道树链剖分的模板题→每次安装软件，把根节点到x软件路径上的值全部变为1，每次卸载软件，把x以及它的子树的值变为0、

  • P2572，P2894→线段树维护区间最长连续1串

  • P2590,P4092，P4116→树链剖分

  • P1471→推导出方差图中的公式为： \(S^2=\frac{(x_1^2+x_2^2+\ldots +x_n^2)}{n}-\overline{x}^2\)后，用线段树维护。

  • 使用平衡树也可以首先可并堆→P3377

  • P3105→qzw[i]-qzw[j-1]>=qzs[i]-qzs[j-1]转化为qzw[i]-qzs[i]>=qzw[j-1]-qzs[j-1]→线段树维护最小的j-1

  • P3466→枚举一个**长度为k**的所有区间→很明显是变成中位数最优→将**中位数左边**的数分别加到中位数，**右边的数**分别减到中位数→使用平衡树来维护，或者权值线段树

  • P3567→主席树→也可以使用随机化算法，因为一个数字出现次数多余一半，则随机到的次数也应该在一半左右以上

  • P3834→主席树

  • P4145→考虑到一个数被开方的次数很少，所以暴力修改→为了优化，记录每个区间还有没有可以开方的数，如果没有就直接跳过

  • P4344→线段树维护区间连续01序列

  • P4513→线段树维护区间内和最大的连续子区间

  • P4514→二维树状数组/二维线段树

  • P4560→线段树

  • P5490→扫描线

  • P6327→sin(a+x)=sinacosx+cosasinx，cos(a+x)=cosacosx−sinasinx→线段树维护一下

  • P5787→线段树分治

  • P6035→第一问，每个为 -1 的位置 i 都会造成 n−i+1 种可能，由乘法原理，乘起来就是答案。→第二问。贪心地从前往后拼凑。假如 a 之后有 b 个比他小，就从小到大找第 b+1 个还没被选到的数 x，并令 a←x。假如是 -1，就找当前没有选到的最小值→树状数组维护

  • P1728→发现如果一个车能停到目标位置那么只要这两个位置之间每辆车的宽度与这个车的宽度之和不大于w就行。对于两辆车x,y如果他们当前的相对位置与目标相对位置不同(即当前是x,y，目标是y,x)那么这两个车的宽度之和就要<=w。

  • P7497→线段树，维护区间封锁tag

  • P7706→ 线段树

  • P8065→显然离线处理，将询问和球员分别按照年龄排序，然后依次处理询问的时候先每次添加当前可行的球员的 skill 值。然后根据贪心，将当前已经添加的球员的 skill 值从大到小排序，然后隔一个选一个即可，时间复杂度 O(mnlogn)。→也可以先去掉age不符的，然后按skill排序，dp解决隔一个选一个的问题，单调队列可以做到O(mn)

算法策略

  • P2464，P1972，P1494→莫队模板

  • P2709→莫队维护计数平方和

  • 维护4指针2区间信息→莫队，将4指针拆为2指针及多个询问→P5268

  • 查询最大的和≥0的子矩阵→\(O(n^3 \log n)\)的做法可以枚举i,j，扫描线一遍，用线段树维护信息→\(O(n^3)\)的做法可以用**最优化剪枝**，即在扫描线时，设之前的已有答案宽度为l，那么此后答案至少为l。即双指针l,r，r向右一格，l也向右一格，并尝试左移→需要找到单调性，可以是对前缀和进行前缀最小值→P1565

  • P1903→带修莫队

  • P4462→我们可以维护异或前缀和，问题就变成了询问区间 [l−1,r] 中，有多少对 l 和 r 满足 al−1​⨁ar​=k。→莫队，每次加入一个数就计算出他前面和他异或和为k的数的数量

  • P5268→莫队，对每个询问拆开为两个子询问，独立处理，记录每个子询问的询问标号。

字符串算法 哈希表

  • kmp→P3375，P10475（将kmp数组进行横向扩展、寻找循环节类题型），P2375

  • 字典树→建树技巧与树上匹配→P2922

  • P1383→带撤销的打字机→将操作视为在trie树上的操作，每一次操作就是从当前节点向外连边，并走到指向的点出→撤销就是当前节点向之前的每一个节点连边。为了快速找到这个节点，我们使用倍增。

  • 字符串ss的**最小循环子串**，就是ss的**最大公共前后缀→**P4391

  • 树哈希（树同构）→P5018，P5043

  • 二维哈希→对横着的哈希再次哈希，并且维护其**类二维前缀和性质**→P10474

  • P1659→求一个字符串中前k长的奇回文串的长度之积→马拉车算法

  • P3065→设这个字符串的第 i 个字母为 u，我们可以连单向边 u→v，表示我们指定了 u 的字典序比 v 小，其中 v 是第 i 层的其它字母→若这个字符串是其它某个字符串的前缀，则这个字符串不可能成为字典序最小的串；当 26 个字母间的关系形成环时，也不能成为字典序最小的串。

  • P3455→一个字符串的最大周期长度就是这个字符串的长度减去它最短的公共前后缀长度→注意这个公共前后缀的长度必须小于等于字符串长度的一半，否则不存在周期→kmp求解

  • P3796，P5357→Trie树，ac自动机

  • P3805→马拉车

  • P4551→先求出每个点的前缀异或和（即每个点到根节点的异或和）→考虑异或的性质，我们发现就是要在这些前缀和中找到异或值最大的两个→01trie

  • P4683→我们发现，打印的过程就是在trie树上便利的过程，这个过程中我们无法减少操作数→那么哪里可以减少操作数呢？即打印最后一个单词后，我们不需要再清空了→考虑最后打印trie树上标记的最长的一个单词串即可。

  • P4810→考虑在trie树上模拟这个过程。trie树上有cnt标记的点代表有一个栈是从根节点到这个节点的。两个栈相同的数字就是这两个栈的公共链长度

  • P4824→一开始考虑kmp，并且用栈实时维护→开一个辅助数组pos，pos[i]表示S的第i位匹配到的T的长度。→每次在弹出后，跳到栈顶的pos重新匹配即可。

  • P5184→每次选择字典序最小的栈，将其栈顶的元素放入答案队列。→用后缀数组（后缀排序）来快速找到弹出顺序

  • P5410→exKMP

  • P5446→我们不断找到 当前字符串的最长翻转子串（即qwqwq 的最长翻转子串是 qwqw），输出其长度后把当前串变成这个子串→快速找到这个子串，我们只需要找到最靠后的一个对称中心，且它延伸到了串的结尾即可。

  • P5826→子序列自动机→多次询问给定串T是不是原串S的子序列

  • P7114→(AB)i 判断：字符串A的最短周期 =∣A∣−fail[A]，于是我们从二开始枚举 i ，只要 S∣(AB)i∣​ 的最短周期是 ∣AB∣ 的约数，则 (AB)i 一定是 S 的前缀→预处理出 S 每个后缀中出现奇数次字符数量即可确定 C 中出现奇数次的字符数量。统计答案同时更新到每一位时出现奇数次的字符数量 ≤ x(x∈[0,26]) 的 A 的数量

  • P7861→求最长子序列的题，可以 dp，fi​=j<imax​{fj​}+1(xj​为xi​的前缀和后缀)。→为了判断一个字符串是否是另外一个字符串的前后缀，把字符串 s1⋯n​ （注意s是一个字符串，s_i是一个字符）正反合在一起组成 n 个**字符二元组**，即 (s1​,sn​)(s2​,sn−1​)…(sn​,s1​)，那么这样就只用判断 xj​ 组成的二元组是否是 xi​ 的二元组的前缀就好了→我们建一棵字符集大小为\(26^2\)的trie树判断

  • 【哈希设计】P8085→我们考虑计算哈希，那么难道需要每次对明文的子串进行重编号？这样时间复杂度过不去→我们考虑设计哈希为：区间内和当前字符相同的上一个字符的下标，如果不存在即-1，这样就可以滑动窗口维护了！

  • P9753→如果字符都是成对出现的，那么我们括号栈就可以做→考虑出现奇数次的情况，那么肯定就是只能在合法串的两端了。我们在栈的位置上维护之前出现了几个，然后组合→考虑 dp，设 fi​ 表示以第 i 位作为结尾的合法子串数量，容易得出转移方程：\(fi​=f_{ g_{i​−1}}​+1\)，其中 gi​ 表示最大且能使 s[gi​,i] 成为合法子串的下标。答案即为 \(∑_{i=1}^n​fi\)​。

  • P10476→循环同构→哈希，或者最小表示法

动态规划

  • 用“非法情况一定更劣”来消去需要考虑非法的情况→P1006

  • dp不就是枚举情况并选最优吗？→P1040

  • 断环为链→P1043，P1063

  • 题目中有明显的“合并”流程，则考虑区间dp→P1063，P1880（与贪心的那道题区分），P1220，P3146

  • 依赖背包嗯可以看成树形dp来做→P2014，如附件数量很少则可以枚举每个主件和附件的配对情况并作为一个物品的多种情况。当遇到一个物品有多个挡位时的背包问题也可以参考本题→P1064

  • 从题目信息中构造出背包（f_{i,j}）的物品(i)及两个维度（价值(f)和容量(j)）→P1156，P1282,P5322

  • 考虑树形dp并考虑复杂度→P1273

  • 主要考验dp转移的设计以及dp优化→思维→P1070

  • 一开始考虑贪心→给定方案计算答案很快→不好实现，所以使用搜索（计算每一种可行情况）→使用dp实现记忆化搜索→压维优化→P1284

    • 期望dp→得出概率的计算式→使用dp求出计算式中的值并计算→本题：第i题对的概率=i-1题答案=i题答案→P1297→其它题目：P2111

  • 树形dp，最大权独立集→P1352

  • 简单树形dp→P2015，P2016,P2585

  • 非常规最长公共子序列→转化为最长上升子序列→P1439

  • 记忆化搜索（dp状态设计）→P1541

  • 数位dp→从高位到低位，逐位考虑非限制，递归非限制→P1836,P2602，P4999

  • 带方案输出的简单dp→P1854

  • 抽象出模型→转化为背包dp→P1941

  • dp状态的设计→在设计dp状态时，考虑如何使用最少的状态表现出我们所有需要的信息→f_{i,j}表示考虑了前i个人，1其中在窗口1打菜的总时间为t时完成所有活动的总用时→P2577

  • 查看数据范围，发现可以O(nmk)→定义\(f_{i,j,k}\)为\(S_{1→i}\)与\(T_{1→j}\)匹配且分为k块→循环i,j,k，要求快速判断S,T中两个片段能否匹配→预处理\(g_{i,j,k}\)为\(S_i,T_j\)结尾的两个长度为k的字符串是否相同→P2679

  • 小规模最优分组问题→状态压缩→f[i]代表当前状态为i时最小的分组数→P3052

  • 区间dp转移式的推导→P3205

  • 换根dp→P2986，P3478

  • 树形dp→考虑到有以及染色的，所以在dp时砍掉不符合的f值→P4084

  • 类似括号匹配的（如决策为扩展一边/同时扩展两边）→P4170

  • f_{i,j}定义为保留第i个点塔，差值为j的方案数,枚举上一个保留的塔→P4933

  • 看到数据范围n≤20→状态压缩→P8733，P10447

  • P10115→动态规划与括号序列结合→在栈上维护信息

  • P10236→一开始想搜索，然后发现期望复杂度为 O(n^2)→把搜索看成是dp，交换状态和值，我们就得到了有决策的填表搜索→其实就是dp，设 dp_{i,j,0}​ 为 i∼j 且从 左0右1 端开始取的最大值，模拟搜索即可

  • P1220→区间dp，定义f[i][j][0]表示关掉i到j的灯后，老张站在i端点，f[i][j][1]表示关掉[i][j]的灯后,老张站在右端点，转移即可。

  • P1270→考验从深度优先的顺序读入树→变成一道树形dp→设f[i,j]表示在结点i，拿了j幅画需要的最少时间，转移即可。

  • P1272→首先不一定存在一颗子树的大小恰好满足要求，所以我们设计dp→定义\(f_{i,j}\)为将i的子树切下大小为j的连通块，最少需要切断的边数。→转移为f[u][s] = min(f[u][s], f[u][s - sv] + f[v][sv])，这里枚举子树v可以给到的大小sv

  • P1365→期望dp，问\(\sum l^2\)，l是每一个1连通块的长度。→考虑向一个1连通块末尾加上一个1，那么应该是\(x^2→x^2+2x+1\)，因此维护两个期望数组，分别代表\(x,x^2\)的期望→当遇到0时，将x的期望清零，避免算成和前面的1相连的情况

  • P1450→有4种不同数量和面值的硬币，求凑出数值x的方案数→计算4种硬币都不超过限制不太好办，但是我们可以先让一个硬币超过限制，其它硬币随便，这我们可以得到→因此考虑容斥，把所有情况-至少一种硬币超过限制就是答案。

  • P1453→基环树版本的没有上司的舞会→短环为链，我们发现只需要随便选择一条边s-t断掉，然后从s,t分别跑一次树形dp，最后在\(f_{s,0}\)和\(f_{t,0}\)里面取最优值即可。

  • P1654→连续段贡献期望（段贡献为\(l^3\)）→分别维护\(x^3,x^2,x\)的期望。用低次的更新高次的。数学式子。

  • P1896→状态压缩，\(O(2^{2n})\)dp枚举当前行和上一行。

  • P1779→首先发现确定了技能集合，效果和顺序无关→先考虑集体攻击，枚举集体攻击的伤害，然后对剩余的单体另外攻击，O(NHp)可过→用背包对集体/单体攻击分别预处理出f_i为造成至少i攻击需要的最少代价

  • P1850→定义dp[i][j][0/1]来表示当前为第i个阶段，连同这一次已经用了j次换教室的机会，当前这次换(1)不换(0)的最小期望路程总和。→转移：这次不换： dp[i][j][0]= min(上次不换的dp+这两次之间的路程 , 上次概率换了之后的dp+p[i−1]×上次换了的教室与这次不换的教室之间的距离+(1−p[i−1])×上次不换的教室与这次不换的教室之间的距离)

  • P1879→带限制的状态压缩枚举方案计数→O(2^{2n})，类似P1896

  • P2034→题意变为选择一些数字使得和最小，并且间隔不超过K→写出转移式→单调队列维护

  • P2051→**每一行每一列的炮的数量≤2→**f[i][j][k]代表放了前i行,有j列是有一个棋子,有k列是有2个棋子的合法方案数.

  • P2167→关注到n很小，所以状态压缩记录前i个字符匹配那些字符串

  • P2215→首先求出最长的LIS，预处理f_i为i往后最长的LIS→对于询问L，从左往右扫，找到第一个满足 fi​ ≥L 的 i，显然它必定是答案序列的第一位；然后再从第 i+1 个数开始向右扫，找到第一个满足 fj​≥L−1 且 aj​>ai​ 的 j，那么 j 肯定是答案序列的第二位。以此类推

  • P2365→用 dpi​ 表示前 i 个任务都被完成，所需的时间最小值→优化

  • P2396→定义 f[i] 表示使用了集合 i 内的卡片有多少种赢的方案。

  • 求最长公共子序列的个数→要求长度为 d(i,j) 的 LCS 的个数，只需要知道长度为 d(i,j) 转移来源的 LCS 的个数→在dp时维护f,g分别代表长度和个数→P2516

  • P2567，P2657→数位dp

  • P2593→记忆化搜索→定义$ f_{i,j,k,0/1}​$ 为点数为 i，点数为 i−1 的有 j 张牌，点数为 i 的有 k 张牌，是否有对子，能否把 1∼i 出完，为一个 bool 数组→最后判断$ f_{100,a_99​,a_100​,1}​$ 即可。

  • P2606→题意转化为求1到n的所有排列中，满足小根堆性质的排列的个数。→\(f[i]=C_{i−1}^l​*f[l]*f[r]\)。

  • P2627→转化为选出若干奶牛，使得两两间距<K，且价值最小→f_i 为考虑前i且选i时的最优值→单调队列优化。

  • P2704→状态压缩

  • P2831 →dp[S] 表示已经死了的猪的集合状态为 S 时最少要发射的鸟数。dp[S∣line[i][j]]=min(dp[S]+1)，dp[S∣(1<<(i−1)]=min(dp[S]+1)，其中 line[i][j] 表示经过 i,j 两点的抛物线能经过的所有点的集合→考虑优化，若令 x 为满足 S&(1<<(x−1))=0 的最小正整数，则由 S 扩展的转移的**所有线都要经过 x**→优化原理：因为我们要消灭所有小猪，所以我们强制转移时一定要消除最小的，没被消除的小猪，这样可以减少搜索量（枚举line时少了一维）

  • P2890→区间dp→设f[i][j]为从i到j这段区间被修正为回文串的最小花费→当前区间[i,j]满足s[i]==s[j]，直接用[i+1,j−1]转移

  • P3147→由n的范围得出最后合成的数字很小（≤56） →定义f[i][j],里面存的值是左端点为j，能合并出i这个数字的右端点的位置→f[i][j]=f[i−1][f[i−1][j]]→ 很有意思的倍增dp

  • P3177→因为是要求max，所以我们考虑树形dp→考虑统计的常用套路，就是统计每条边的贡献，那么这里我们也这样做→定义f_u,j为子树u在有j个黑点的贡献，f[u][j]=max(f[u][j],f[u][j−k]+f[v][k]+tot∗e[i].w)，tot是边u-v被经过的次数

  • P3572→一眼动态规划→单调队列优化

  • P3694→状态：f[i]表示i状态下最小的出列（不一致）的个数。比如f[1101]表示从头到位为⅓/4乐队的偶像的最小出列个数→f[i]=min(f[i xor 2^j]+num[j]−(sum[length][j]−sum[length−num[j]][j])); j表示团队编号，sum表示某种团队的前缀和，length表示到此已经排到的长度。

  • P3861→先求出 n 的所有因数：$ x_1​,x_2​,…,x_d(n)\(​ →考虑 dp ，设 \(dp_{i,j}​\) 为把 \(x_i\)​ 分解成若干个\) ≤x_j​$ 的数的乘积的方案数→转移有两种情况，1，分解中不包含\(x_j\)，可以从\(dp_{i,j-1}\)转移；2，包含\(x_j\)，要求\(x_j|x_i\)，那么就是\(dp_{pos(\frac{x_i}{x_j} ) ,j-1}\)，其中\(x_{pos(\frac{x_i}{x_j})}=\frac{x_i}{x_j}\)

  • P3970→如果没有"两个上升子序列相同,那么只需要计算一次"，我们用dp[i]表示以i结尾的上升子序列个数，那么就有\(dp[i]=∑_{j=1}^{i−1}​dp[j]\)→考虑去重，什么时候会出现重复呢？我们之前更新了一个dp_i，后面有遇到一个i，此时我们可能会把之前的dp_i加入进去→我们记录下lst_i表示上一个i时新加入的答案\(∑_{j=1}^{i−1}​dp[j]\)，在遇到一个dp_i时减去它即可。→该题的下降子序列版本为P2687

  • P4158→f[i][j]表示前i条木板粉刷j次的情况下能正确粉刷的最大格子数，g[i][j][k]来表示第i条木板上粉刷j次涂了前k个格子的情况下能正确粉刷的最大格子数→ f[i][j]=max(f[i][j],f[i-1][j-k]+g[i][k][m])→考虑前q个格子粉刷正确加上下一步粉刷正确的粉色格子多还是蓝色格子多，有g[i][j][k]=max(g[i][j][k],g[i][j-1][q]+max(sum[i][k]-sum[i][q],k-q-sum[i][k]+sum[i][q]));

  • 区间染色要求次数最少问题→P4170→区间dp→设 \(f_{l,r}\) 为给区间 \([l,r]\) 染色的最小步数→若 \(s_l=s_r\)。考虑对 \([l,r-1]\) 染色的方案，设覆盖了 \(l\) 的唯一一次染色的右端点是 \(x\)。我们把这次染色的右端点改成 \(r\)，并且把所有在 \([x+1,r]\) 上进行的染色保持原来的顺序挪到这次染色之后，因此此时\(f_{l,r}= f_{l,r-1}\)→\(s_l\ne s_r\)。此时不存在一次覆盖了 \([l,r]\) 的染色，故必然存在一个位置 \(l\le x<r\) 使得不存在一次左端点小于等于 \(x\) 且右端点大于 \(x\) 的染色，枚举这个 \(x\) 即可。即 \(f_{l,r}=\min\limits_{i=l}^{r-1}f_{l,i}+f_{i+1,r}\)。

  • P4206→期望dp→预处理出猫在点i，老鼠在点j，猫的下一个走位nxt[i][j]。→f[i][j]表示猫在点i，老鼠在点j，猫抓到老鼠的期望步数是多少。→若i=j，则f[i][j]=0；如果猫走一步或两步可以到达j，f[i][j]=1；否则f[i][j]=sum(f[sec][k]/(p[j]+1))+1（其中，sec表示猫走两步所到达的位置（因为走两步只算一次费用），k表示老鼠可到达的位置（含原地），p[j]表示点j的出度数（即不包含原地））。

  • P4322→分数规划，二分mid后问题转化为每个点点权为Pi​−mid∗Si​，选定一个点就必须选其所有祖先节点。问能否取k个节点使得取出的点点权大于零。→不防设dp[u][j]表示当前根为u，取j个节点所带来的收益最大值。→dp[u][j]=max(dp[u][j],dp[u][j−k]+dp[v][k])，j>0。dp[u][0]=0→看上去是O(n3)的，实际上**树上背包是O(n2)** 的→证明：因为每次合并一棵子树时付出的代价是”已经合并的兄弟子树的大小之和”*”正在合并的这棵子树的大小”,实质上是树上每对节点在LCA处贡献时间复杂度,

  • P4302→区间dp，暴力判断循环节→在枚举断点合并区间时，随便判断做区间是否可以作为循环节

  • P4317→数位DP(二进制)计算出G[i]为1~N中恰好有i个1的数值个数。→枚举一个i统计答案为\prod i^{G_i}

  • P4342→我们考虑到，断掉第一条边后实际上是在两条链的垄断不断合并→先断环为链，然后考虑区间dp→因为存在乘负数，所以在维护区间max时还要维护min

  • P4398→设f[x1][y1][x2][y2]表示，在第一个正方形中，以(x1,y1)为右下角，第二个正方形中以(x2,y2)为右下角，公共正方形最大的边长。→f[x1][y1][x2][y2]=min(f[x1−1][y1−1][x2−1][y2−1],min(f[x1][y1−1][x2][y2−1],f[x1−1][y1][x2−1][y2]))+1;

  • P4377→分数规划后用背包解决

  • P4544→状态：设fi,j​表示在第i个商店一共买到了j吨饲料，转移：\(f_{i,j}​=min{f_{i−1,k}​+k^2×(x_i​−x_{i−1}​)+(j−k)×ci​}\)→考虑见含j项目留在min内，用单调队列优化

  • P4977→设 ai​ 递增，把 ai​ 转化为一个只含有1的正三角形，第 i 行有多少个 1 就表示 ai​ 的值是多少。→假设目前已经用了 N 中的 k 个 1（我们把 N 拆分为 N 个 1 来分配），那么使得 k 增加有以下两个方法：新增一行；在当前行加 1→fi,j​=fi−1,j−1​+fi−j,j​。前者表示在当前行加 1，后者表示新增约一行。二维 dp 即可。→考虑滚动数组优化→统计所有方案总和，我们扫描一遍 f 数组，如果扫描到 fi,j​=x，那么就把答案加上 \(j^M×x\)

  • P5017→在时间轴上考虑，设f_{i}为在时间i车将人接走，此时\(0\sim i\)时间内所有人等待的时间→约束一下转移过来的时间点，目前是O™的→假设正在求 fi​，但在 (i−m, i] 中没有任何点，这个 fi​ 相对来说就是 “无用” 的。令 fi​=fi−m​，防止漏解

  • P6835→随机游走期望dp→利用期望的线性性→设要通过第 x 个点需要的期望步数为 E(x)，写出转移式化简

  • P5664→在一个方案中，只可能有一列的节点超过所有选的节点的一半。因此可以想到枚举这个超过限制的列，然后对于这个列进行DP求解。→设fi,j,k​表示前i行选j个节点，当前枚举到的列选k个节点的方案数→实际上我们想知道的只是j,k的大小关系，对于具体的值并不关心，考虑将它们合并到一维。

  • P5694→令f[i][j][k][l]表示选i组{},j组[],k组()且深度**小于等于**l的组合有几种→为了防止重复，对于每个**非空**SS串，有且仅有一种分法：找到两个SS串A,B，使得S=(A)B或[A]B或{A}B

  • P5851→f(i,j) 表示此时 [i ,j] 已被吃完的最大 ∑​w ；→f(i,j)=max( f(i,j), f(i,k−1)+f(k+1,j)+p(k,i,j) ) ，p(k,i,j) 表示当 k 还未被吃时能吃掉 k 且 i≤l≤k≤r≤j 的最大的一个 w ；

  • P7914→注意不是说只要括号都匹配，* 在哪里无所谓，只要连续的不超过 k 就可以→dpi,j​ 表示从位置 i 到位置 j 一共的合法序列总情况数量→再开个第三维表示不同的形态种类→对于***(...)(...)，(...)**(...)，(...)(...)(...)，(...)*(...)，(...)，...*分类图论其转移

  • P9745→设 fu​ 是以 u 为根的子树的所有断边方案的权值和。 gu,i,j​ 是以 u 为根的子树里断开若干边，所有断边方案中，与 u 相连的连通块的价值在二进制下第 i 位是 j 的，不与 u 相连的连通块的价值乘积的和。→初始状态：若 au​ 第 i 位为 1，则 gu,i,1​=1，否则 gu,i,0​=1。→对于每个儿子，枚举二进制下每位 i 转移。不断儿子相当于当前连通块的异或和第 i 位异或上儿子连通块的第 i 位，断掉儿子相当于异或上 0。→先保存 t0​=gu,i,0​,t1​=gu,i,1​。gu,i,0​←t0​×(gv,i,0​+fv​)+t1​×gv,i,1​ gu,i,1​←t0​×gv,i,1​+t1​×(gv,i,0​+fv​)​

  • P10975→状态压缩

  • P10974→树形dp

  • P10971→那么我们先把孩子按贪婪度降序排序，分配的饼干数一定是一个单调不增的序列→设 fi,j​ 表示考虑了前 i 个人，分配了 j 个饼干时的最小怨气和→考虑转移：若当前第i个孩子的饼干数>1，考虑将前i个孩子都-1，有\(f_{i,j}=f_{i,j-i}\)；如果=1，那么枚举一个 k，k 后的孩子都只有 1 块饼干，列式转移

数学与其他

初等数学

  • 总结出性质来优化枚举的复杂度→P1072

  • 要勤于推导式子→推导后得出贪心算法而不是一开始选择dp→P1080

  • 因子和的相关性质→因子和=\(\prod_j( \sum_{i(0~k)} p_j^i)\)→P1593

  • 给出数列递推公式快速求第K项目（K很大）→矩阵快速幂→特殊情况还要使用龟速乘→P2044

  • 数学推导约束优化枚举→前缀和优化方案统计→P2119

  • 推导数学规律→两个点一起向上走→由数学推导快速得出一个点的祖先编号→模拟上跳→P3938

  • 期望dp的逆推法→P4316

  • 递推逆元快速计算→P5431

  • 区间交换，求每次操作后的的逆序对数量奇偶性→若ABCDE，交换B,D，那么有影响的只有BCD→因为所有数都不相同 , 所以是/不是逆序对前后必发生转化，即逆序对数量=原顺序对数量→O(1)计算→P8449

  • 列出答案关于因子个数的表达式，发现是\(\prod a_i\)→每次操作都是在一个项目上+1→每次贪心选择最小的项目执行→P9836

  • P1463→求不超过n的最大highly composite number（高合成数）→高合成数一定是由另一个高合成数乘一个素数得来→发现这类数分解质因数，随质因数增大，指数显然单调不增（贪心）→体现高合成数在LL范围内很少，所以打表。

  • P1486→平衡树→不是修改验收员工的工资，而是堆工资标准反方向修改→辞职处理：按值分裂后丢弃

  • P2152→高精度求gcd

  • P2158→发现只要x,y坐标互质即可→问[1,n]中有多少对(x,y)互质→欧拉函数是小于x的整数中与x互质的数的个数，一般用φ(x)表示→用欧拉筛筛出即可

  • P2261→把mod写出除法形式，然后数论分块

  • P2303→设gcd(i,n)=d，i/d,n/d互质→计算出[1,n/d]中有多少个数和n/d互质，假设为x→当前贡献就是xd→欧拉筛

  • P2568→枚举质数：p∈prime∑​i=1∑n​j=1∑n​[gcd(i,j)=p]→对 gcd 进行套路式的变形：p∈prime∑​i=1∑⌊pn​⌋​j=1∑⌊pn​⌋​[gcd(i,j)=1]→整理后得到欧拉函数→欧拉筛，O(n)枚举统计答案

  • P3579→枚举 [1,min(b,d)] 的所有正整数 i，看看是否可以满足a≤b/i*i​ and c≤d​/i*i即可→发现b/i,d/i是一个区间，所以数论分块，每次取最大的i即可。

  • P3812→线性基

  • P4781→【模板】拉格朗日插值

  • P5316→k=2时，直接输出两数，易知正确→k=3时，考虑到，(a,b)[a,b]=ab，那么六个数乘起来就是(abc)2，考虑计算(b,c)b,ca,b[a,c]​=a2bc/bc​=a^2，然后就能算出a。→k=4时，考虑到k=3时可以直接解出，所以枚举哪三个lcm和哪三个gcd配对，最后检验最后一个

  • P6583→约分后，分母只含 2,5 两种因子的分数可以表示为十进制有限小数。→f(x)，表示 [1,x] 中**只含** 2,5 两个因子的数的个数→考虑合法数的形式为\(\frac{ac}{bc}\)，其中b是2或5的倍数，其他不是→对于每个合法的 c，合法的 a 的个数为 f(n/c)，则它对答案的贡献为 f(n/c)×⌊n/c​⌋。→容斥处理出每个分块内合法的c的个数

  • P10034→置换环→对于一个排列 p，我们连边 i→pi​，则其构成了若干个环→题目限制可以等价描述为：使所有满足 Si​=1 的点都位于一个大小为 l 的因数的环上。→注意到如果存在方案，则必然存在一种使所有环的大小都为质数的方案（否则我们就可以把其中大小不是质数的环拆成若干个大小为质数的环）→所有 ≤n 的质因数最多只有 15 个。环的大小只可能是这几种。→最终方案是有 k 个节点在大小为 l 的质因数的环上，n−k 个节点单独成一环（这些节点中不应有 Si​=1 的点），有约束条件 c≤k≤n,k≠n−1（其中 c 是 S 中 1 的数量）。→问题变成了用若干个质数拼成k，记录一下转移路径即可还原出方案。

  • P0239→暴力枚举三元组中最小的数是什么、次小的数是什么，容易计算出最大的数的方案数，乘系数即可得到有序的方案数。

  • ：P10499→我们将是否对第 i 盏灯进行操作定为变量 xi​, i∈(1,N)。那么将所有与第 i 盏灯有关联的灯的变量和初始状态异或起来就应该等于该灯的结果状态。→通过上述的转化即可得到有关于所有 N 盏灯的 N 个方程。这是一个线性异或方程组，可以使用**高斯消元**求解。这时分为两种情况：产生了 0=1 的等式，这种情况无解。另一种为有解情况，统计最后自由元的个数 k（即完成消元后 0=0 等式的数量），最后方案的数量即为 2k。

初等数论

  • 扩展欧几里得变形与理解→P1082

  • 扩展欧几里得→P5656，P2421

  • 矩阵乘法→P1349，P1962，P1306，扩展矩阵乘法→P1939

  • 同余方程组的求解→P1516,P2613

  • 先写出f的递推式→矩阵优化→P5789

  • 将题目转化为数学语言→欧拉函数求解→P8015

  • CRT→P1495

  • 莫比乌斯反演→P2522，P3455

  • 高斯消元→P3389

  • BSGS→P3846→类似折半搜索（匹配机制很像）

离散与组合数学

  • 考虑划分问题为子问题→考虑递推公式→卡特兰数→P2532

  • 数据范围允许杨辉三角递推→考虑答案的递推式→理解组合数的递推式→ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1]; if(c[i][j]%k==0)ans[i][j]++;→P2822

  • 简单组合→发现没有取模，需要高精度→P3223

  • Lucas 定理→P3807→$C(k_1p + r_1, k_2p + r_2) \equiv C(k_1, k_2) \cdot C(r_1, r_2) \pmod{p} $

  • 类似数位dp的逐位考虑→组合数计算方案→P5367

  • P5091→扩展欧拉定理

image.png

  • P5505→考虑容斥，ans=(>=0个人没分到的方案)−(>=1个人没分到的方案)+(>=2个人没分到的方案)...→考虑计算>=i个人没分到的方案，每个特产分开算，最后乘起来。根据插板法，第k个特产的方案为C(a[k]+n−i−1,n−i−1)。然后还要乘上强制哪i个人没分到的方案，即C(n,i)。

  • P5689→设 ai​ 表示以 i 为根节点的子树的填数方案总数。假设操作需要将 u 接到 v 上去。更新答案时，节点 v 所处的位置，一定只能填 0。→维护 wi​ 表示以 i 为根的树的节点数。→那么填入原来的 u 子树中的数字就有 w_v​−1 选 w_u​ 种不同的选择方案。剩下的数字填入原来的 v 子树中→又原本 u,v 子树中的填数总方案数分别为 au​,av​。那么根据乘法原理，就可以将 av​ 更新为 av​×au​×C(n,m​)

  • P6076→将限制分开考虑→行和列可以分开计算。先来处理第一个限制：颜色。设 fi​ 表示只用了 i 中颜色、并且满足行和列染色限制的方案数→再枚举选了多少列涂色

线性代数

高等数学

最优化

  • 博弈论→P1247，P2197

  • P10501→博弈论，分割矩形问题

  • 舞蹈链及其变形→P1074，P10481，P10482

  • 一个单调队列→P3522

  • P5653→首先不考虑 a 的限制，那么一个位置是加是减取决于这个位置对答案的贡献是正是负，而对答案的贡献显然为 w 的后缀和。再考虑 a 的限制，如果一个位置超出了限制，则应该不断地从之前贡献最小的位置减掉贡献，直到不超出，用一个堆维护即可。

  • P6737→构造最长路径→构造策略：对于普通道路，蛇形拐；对于要拿硬币的道路，设置一个死胡同，进去出来要从一个道路走

计算几何

  • 二维凸包→P2742

信息论