# Olympiad in Informatics **Repository Path**: rizzohou/olympiad-in-informatics ## Basic Information - **Project Name**: Olympiad in Informatics - **Description**: Olympiad in Informatics - **Primary Language**: C++ - **License**: WTFPL - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 9 - **Forks**: 0 - **Created**: 2023-01-20 - **Last Updated**: 2025-07-16 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README 目录 - [Olympiad in Informatics](#olympiad-in-informatics) - [做过的题目](#做过的题目) - [标记的题目](#标记的题目) - [未解决的题目](#未解决的题目) - [未标记的题目](#未标记的题目) - [有用的链接](#有用的链接) - [知识类](#知识类) - [其他](#其他) - [代码模板](#代码模板) - [A FEW TIPS](#a-few-tips) - [思维方式](#思维方式) - [对算法思想的理解](#对算法思想的理解) - [思想](#思想) - [单调性](#单调性) - [单调队列优化](#单调队列优化) - [二分与三分](#二分与三分) - [二分](#二分) - [三分](#三分) - [单调栈](#单调栈) - [费用提前计算](#费用提前计算) - [斜率优化](#斜率优化) - [贪心](#贪心) - [二进制拆分 / 倍增](#二进制拆分--倍增) - [空间换时间](#空间换时间) - [离线 + 在线](#离线--在线) - [记忆化](#记忆化) - [其他应用](#其他应用) - [降维思想](#降维思想) - [控制变量法](#控制变量法) - [数据降维](#数据降维) - [递归](#递归) - [分治 / 分治型递归](#分治--分治型递归) - [dfs型递归](#dfs型递归) - [随机](#随机) - [构造思想](#构造思想) - [算法](#算法) - [基本算法](#基本算法) - [搜索](#搜索) - [深度优先搜索（*dfs*）](#深度优先搜索dfs) - [广度优先搜索（*bfs*）](#广度优先搜索bfs) - [迭代加深搜索（*iddfs*）](#迭代加深搜索iddfs) - [哈希表（*hashmap*）](#哈希表hashmap) - [前缀和 \& 差分](#前缀和--差分) - [前缀和](#前缀和) - [差分](#差分) - [动态规划（*DP*）](#动态规划dp) - [区间类动态规划](#区间类动态规划) - [树形动态规划](#树形动态规划) - [数位动态规划](#数位动态规划) - [状态压缩类动态规划](#状态压缩类动态规划) - [字符串算法](#字符串算法) - [字符串Hash](#字符串hash) - [KMP](#kmp) - [Trie（字典树）](#trie字典树) - [AC自动机](#ac自动机) - [图论](#图论) - [最小生成树](#最小生成树) - [*Prim*](#prim) - [*Kruskal*](#kruskal) - [最短路](#最短路) - [*Dijkstra*：单源最短路](#dijkstra单源最短路) - [*Floyd*：多源最短路](#floyd多源最短路) - [*SPFA* / 队列优化的*Bellman-Ford*算法：单源最短（长）路](#spfa--队列优化的bellman-ford算法单源最短长路) - [强连通分量](#强连通分量) - [*Kosaraju*](#kosaraju) - [*Tarjan*](#tarjan) - [割点和桥](#割点和桥) - [*Tarjan*](#tarjan-1) - [欧拉回路](#欧拉回路) - [LCA](#lca) - [2-SAT](#2-sat) - [树的dfs序、欧拉序](#树的dfs序欧拉序) - [数据结构](#数据结构) - [并查集（*Disjoint Set*）](#并查集disjoint-set) - [树状数组（*Binary Indexed Tree*）](#树状数组binary-indexed-tree) - [RMQ问题：ST算法](#rmq问题st算法) - [线段树](#线段树) - [扫描线](#扫描线) - [分块 Chunking](#分块-chunking) - [点分治](#点分治) - [离线分治算法](#离线分治算法) - [基于时间的分治算法（CDQ分治算法）](#基于时间的分治算法cdq分治算法) - [基于值域的整体分治算法](#基于值域的整体分治算法) - [平衡树 Treap](#平衡树-treap) - [数学部分](#数学部分) - [快速幂](#快速幂) - [质数](#质数) - [素数筛](#素数筛) - [质因数分解](#质因数分解) - [约数](#约数) - [求N的正约数集合——试除法](#求n的正约数集合试除法) - [求1 ~ N每个数的正约数集合——倍数法](#求1--n每个数的正约数集合倍数法) - [最大公约数与最小公倍数](#最大公约数与最小公倍数) - [同余问题](#同余问题) - [拓展欧几里得算法](#拓展欧几里得算法) - [线性同余方程](#线性同余方程) - [乘法逆元](#乘法逆元) - [中国剩余定理](#中国剩余定理) - [拓展欧几里得解同余方程组](#拓展欧几里得解同余方程组) - [高次同余方程](#高次同余方程) - [矩阵乘法](#矩阵乘法) - [容斥原理](#容斥原理) - [经典问题](#经典问题) - [均分纸牌](#均分纸牌) - [货舱选址](#货舱选址) - [其他技巧](#其他技巧) - [离散化](#离散化) - [`bitset`优化](#bitset优化) - [其他总结](#其他总结) - [图论](#图论-1) - [判环的技巧](#判环的技巧) - [数论](#数论) - [比较好用的几个质数](#比较好用的几个质数) - [调试代码](#调试代码) - [测试总结](#测试总结) - [CSP-S2023](#csp-s2023) - [NOIp 2023](#noip-2023) # Olympiad in Informatics 本仓库用于记录本人的信息竞赛学习 ## 做过的题目 ### 标记的题目 1. [小A点菜](https://www.luogu.com.cn/problem/P1164) 2. [P1036 NOIP2002普及组 选数](https://www.luogu.com.cn/problem/P1036) 3. [P1990 覆盖墙壁](https://www.luogu.com.cn/problem/P1990) 4. [P1228 地毯填补问题](https://www.luogu.com.cn/problem/P1228) 5. [P1803 凌乱的yyy / 线段覆盖](https://www.luogu.com.cn/problem/P1803) 6. [P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G](https://www.luogu.com.cn/problem/P1090) 7. [P1044 [NOIP2003 普及组] 栈](https://www.luogu.com.cn/problem/P1044) 8. [P1106 删数问题](https://www.luogu.com.cn/problem/P1106)：复杂贪心（已写题解） 9. [P1478 陶陶摘苹果（升级版）](https://www.luogu.com.cn/problem/P1478)：简单贪心（刚开始时想麻烦了） 10. [P5019 [NOIP2018 提高组] 铺设道路](https://www.luogu.com.cn/problem/P5019)：贪心策略想出来了，但算的较慢，现给出一个算的较快的贪心策略： > 这道题我用了递推，在考场上推出了一个莫名其妙的式子。大致思路是这样： > 用f[i]表示前i个坑所铺设的最少天数那么要做的只需比较一下当前的a[i]（就是坑的深度）和a[i-1]， > 分两种情况：如果a[i]<=a[i-1]，那么在填a[i-1]a[i−1]时就可以顺便把a[i]a[i]填上， > 这样显然更优，所以f[i]=f[i-1];否则的话，那么在填a[i-1]时肯定要尽量把a[i]一块填上， > a[i]剩余的就单独填。。所以，f[i]=f[i-1]+(a[i]-a[i-1])。初始化f[1]=a[1]， > 向后推就行了。复杂度大概是O(n)。 11. [P1094 [NOIP2007 普及组] 纪念品分组](https://www.luogu.com.cn/problem/P1094)：题解的证明很精彩 ![贪心证明过程](Images/%E7%BA%AA%E5%BF%B5%E5%93%81%E5%88%86%E7%BB%84%E8%B4%AA%E5%BF%83%E8%AF%81%E6%98%8E%E8%BF%87%E7%A8%8B.PNG) 12. [P4447 [AHOI2018初中组]分组](https://www.luogu.com.cn/problem/P4447) - 仔细审题，理解清楚题目的意思； - 题解很精彩（方格划线）。 13. [P1080 [NOIP2012 提高组] 国王游戏](https://www.luogu.com.cn/problem/P1080) - 贪心 - [题解](https://www.luogu.com.cn/problem/solution/P1080)的证明很精彩 - 当手推遇到难处理的式子时，可以从简单的情况开始推 - 例如这题，如果直接从全局的角度来推，要考虑的未知量有点多 - 那么就可以从排在最前面的两个大臣推起，得到前两个大臣的排序方式，再推而广之 14. [https://www.luogu.com.cn/problem/P1163](https://www.luogu.com.cn/problem/P1163) - 二分法 - 需注意精度问题 15. [P3743 kotori的设备](https://www.luogu.com.cn/problem/P3743) - 二分法 - 条件判断方法比较难想到 - 再注意一下精度判断 16. [P1019 [NOIP2000 提高组] 单词接龙](https://www.luogu.com.cn/problem/P1019) - dfs - 可将单词数据**预处理**，用一个数组表示第i个单词与第j个单词接龙后的结果（题解中有） 17. [P1101 单词方阵](https://www.luogu.com.cn/problem/P1101) - dfs - 可以借鉴dfs函数返回bool值以来确认搜索是否成功的做法 18. [P1596 [USACO10OCT]Lake Counting S](https://www.luogu.com.cn/problem/P1596) - dfs - 有一篇题解把dfs和bfs(Breath first search)都写了出来，比较了优缺点 19. [P1162 填涂颜色](https://www.luogu.com.cn/problem/P1162) - dfs/bfs - ![题解](https://gitee.com/rizzohou/olympiad-in-informatics/raw/master/Images/p1162%E9%A2%98%E8%A7%A3.PNG) 20. [P1032 [NOIP2002 提高组] 字串变换](https://www.luogu.com.cn/problem/P1032) - 因为要搜索所有的转换路径，只要有一种能成功就行，因此**相当于求一个最优解**，正好利用***bfs*****首解即最优解**的性质。 - 详细代码见[链接](https://www.luogu.com.cn/blog/xfz-woailuotianyi/solution-p1032) 21. [P1825 [USACO11OPEN]Corn Maze S](https://www.luogu.com.cn/problem/P1825) - bfs - 一般来说，只要有关bfs求地图内的最短路径的问题，一般不能**二次访问同一个点**，因为***bfs*****首解即最优解** 22. [P1449 后缀表达式](https://www.luogu.com.cn/problem/P1449) - 栈 23. [P2058 [NOIP2016 普及组] 海港](https://www.luogu.com.cn/problem/P2058) - ***queue*** - 挺复杂的，值得一看 24. [P4387 【深基15.习9】验证栈序列](https://www.luogu.com.cn/problem/P4387) - ***stack*** - 验证方法想复杂了，只需要将入栈序列一个个入栈，同时判断栈的top元素与被检验出栈序列是否相等，若相等，则可以出站，最后看栈内是否还有剩余元素即可 25. [P2234 [HNOI2002]营业额统计](https://www.luogu.com.cn/problem/P2234) - ***list*** - 可以将序列排序后连成链表，然后从最后读入数字到第一个读入数字的顺序删除数字元素，同时记录要删除的数字相邻元素的差统计答案 26. [P1827 [USACO3.4] 美国血统 American Heritage](https://www.luogu.com.cn/problem/P1827) - ***二叉树*** - 通过一个二叉树的先序遍历和中序遍历，求该二叉树的后序遍历结果 - 遍历的思维过程比较难捋 27. [P1229 遍历问题](https://www.luogu.com.cn/problem/P1229) - ***二叉树*** - ![题解](https://gitee.com/rizzohou/olympiad-in-informatics/raw/master/Images/p1229%E9%A2%98%E8%A7%A3.PNG) 28. [P1087 [NOIP2004 普及组] FBI 树](https://www.luogu.com.cn/problem/P1087) - ***二叉树*** - ![代码](https://gitee.com/rizzohou/olympiad-in-informatics/raw/master/Images/p1087%E9%A2%98%E8%A7%A3%E4%BB%A3%E7%A0%81.PNG) - 首先，此代码的`maketree`部分给了我启示： - 建树时，可以结合***dfs***的思想（不撞南墙不回头），先通过递归直接到达树的底部，从底部向上开始建（可以将***dfs***原本用于判断递归到底部就`return`的`if`改为用于判断是否递归到底部，若未到底部，则继续递归的`if`判断） - 很多关于建树的题其实都不需要建树 - 但是，代码中的判断01字符串的类型的代码效率不高，这里改进方法可以采用***动态规划***或***递推***的思想，建立一个数组dp[N][2^N]大小的数组即可提高一定的效率。 29. [P1185 绘制二叉树](https://www.luogu.com.cn/problem/P1185) - ![题解表格](https://gitee.com/rizzohou/olympiad-in-informatics/raw/master/Images/P1185%E9%A2%98%E8%A7%A3%E8%A1%A8%E6%A0%BC.PNG) - 还有就是在***dfs***过程中可以用`if`语句做到**剪枝** 30. [P1525 [NOIP2010 提高组] 关押罪犯](https://www.luogu.com.cn/problem/P1525) - ***贪心***, ***set*** - **整体的思路** 1. 先对数据按照怨气值以降序排列 2. 从前往后处理数据：对第一组数据，直接分配到两个监狱即可；对剩下的数据，因为数据是由大到小处理，因此只能将这两个人分配到两个监狱中，至于每个人到底分到哪个监狱，需要选使最大怨气值在当前看来最小即可 3. 因为每个人有可能与多个人有怨气，因此处理数据时会出现有两个人必须分配到一个监狱中的情况。若出现这种情况，由数据是由小到大排列的可知，此怨气值即为最大怨气值，剩余数据无需再处理，此怨气值即为答案。 31. [P1892 [BOI2003]团伙](https://www.luogu.com.cn/problem/P1892) - ***并查集*** - “敌人的敌人就是朋友”可以这么理解：**如果一个人有两个或更多敌人，这些敌人就应该被合并**。 32. [P1955 [NOI2015] 程序自动分析](https://www.luogu.com.cn/problem/P1955) - ***并查集*** - 思路很简单，但是有一点要注意的：**先排序，把所有处理相等关系的操作放在前面，然后再进行处理不等关系的操作** 33. [P4305 [JLOI2011]不重复数字](https://www.luogu.com.cn/problem/P4305) - ***哈希*** - 此题最方便的是用`map`做，但是`map`判断的时间复杂度是logn，但c++11有`unordered_map`，是用**哈希**实现的，时间复杂度为o1（当然也可以自己实现） - **另一种思路**：![另一种思路](https://gitee.com/rizzohou/olympiad-in-informatics/raw/master/Images/p4305%E5%8F%A6%E4%B8%80%E7%A7%8D%E4%BB%A3%E7%A0%81%E5%A5%BD%E5%86%99%E7%9A%84%E6%80%9D%E8%B7%AF.PNG) 34. [P1807 最长路](https://www.luogu.com.cn/problem/P1807) - ***图***, ***拓扑遍历***, ***dp*** 35. [P2853 [USACO06DEC]Cow Picnic S](https://www.luogu.com.cn/problem/P2853) - ***图***, ***dfs*** - 每次从一个奶牛出发，遍历整个图，最终被遍历的次数等于k的即是答案 36. [P1363 幻象迷宫](https://www.luogu.com.cn/problem/P1363) - ***图*** 37. [P1347 排序](https://www.luogu.com.cn/problem/P1347) - ***图***, ***拓扑排序*** - **思路** 1. 每读入一对关系，对入度为0的节点进行统计，当且仅当入度为1的节点只有一个时，进行拓扑排序 2. **拓扑排序时，如果已遍历的节点数小于总节点数，可判断出图出现了环**，就可判断该序列不可能实现，即可结束程序 3. 若全都遍历到，但总结点数小于n，则证明关系不够，继续读入 4. 若所有n个节点全都遍历到，则可从queue中取出最后的元素即为结果（可创建queue，在每次加入元素时顺便构建答案） 38. [P1469 找筷子](https://www.luogu.com.cn/problem/P1469) - ***位运算*** - ![题解](https://gitee.com/rizzohou/olympiad-in-informatics/raw/master/Images/p1469%E9%A2%98%E8%A7%A3.PNG) 39. [P2789 直线交点数](https://www.luogu.com.cn/problem/P2789) - ***计数*** - ![题解](https://gitee.com/rizzohou/olympiad-in-informatics/raw/master/Images/p2789%E9%A2%98%E8%A7%A3.PNG) - 数的拆分可以用***dfs*** 40. [P2651 添加括号III](https://www.luogu.com.cn/problem/P2651) - ***最大公约数*** - ![题解](https://gitee.com/rizzohou/olympiad-in-informatics/raw/master/Images/p2651%E9%A2%98%E8%A7%A3.PNG) 41. [P2660 zzc 种田](https://www.luogu.com.cn/problem/P2660) - ***贪心*** ```cpp #include using namespace std; int main(){ long long x,y,ans=0; cin>>x>>y; while(x&&y){ //如果x,y中有一个为0，就结束了 swap(x,y); //交换x和y，为什么？马上就知道了 ans+=4*y*(x/y); //种完剩下的所有最大的正方形。很像GCD是不是？ x%=y; //然后x就只剩下x%y了，因为x%y [从填数最多的一行开始填，这样要选择的数就少了，不合法的情况就可以省掉一些](https://www.cnblogs.com/loceaner/p/12103359.html) 49. [#2427. 「POI2010」珍珠项链 Beads](https://loj.ac/p/2427) - ***哈希***, ***set*** - 可以通过比较两段序列的正向和反向哈希中**较小的哈希值**来匹配忽略方向的序列; 50. [#10041. 「一本通 2.1 练习 7」门票](https://loj.ac/p/10041) - ***哈希表*** 51. [#10046. 「一本通 2.2 练习 2」OKR-Periods of Words](https://loj.ac/p/10046) - ***kmp*** - 注意两点： - 答案**数据类型**要用`unsigned long long` - 其实就是要**求最短前后缀** 52. [1674. 使数组互补的最少操作次数](https://leetcode.cn/problems/minimum-moves-to-make-array-complementary/) - ***数组差分*** - [题解](https://blog.csdn.net/qq_36025591/article/details/110311658) 53. [#10051. 「一本通 2.3 例 3」Nikitosh 和异或](https://loj.ac/p/10051) - ***Trie***, ***异或***, ***动态规划*** - 这是一本通的例题，题解就在书上; - 这道题注意运用**转化法**和**异或运算的性质** - **转化法**的体现 1. 将要求极值的式子分为左右两部分，分别求特定情况的极值，最后在通过枚举选出一个使整体值最大的 2. 因为分开求极值的式子均为一个**连续数列**的一部分的数的总异或值，所以可以通过运用**异或运算的性质**，将原始式子转化为求两个数的异或值，这样就好求极值了 - 注意在求数组l(或r)时，要运用***动态规划***的思想，就是将当前求出的异或和最大值**与上一次求的最大值比较** - 在写代码时又发现一个新点：书上的题目不一定对，注意**要看网站上的原题** - 出现`Error: value of 00000001dcd6513d too large for field of 4 bytes at 00000000000000fd`**这类错误的原因之一是某个数组大小过大** 54. [#10057. 「一本通 2.4 例 1」Keywords Search](https://loj.ac/p/10057) - ***AC自动机*** - 注意：单词会有重复 - 还是那句话：当不能确定题目中的数据的某些特征时，**尽可能编写能解决最多种问题的代码**，保证结果正确 55. [#10058. 「一本通 2.4 练习 1」玄武密码](https://loj.ac/p/10058) - ***AC自动机*** - `terminated ifndef`错误是因为没有`endif` - 注意**状态更新语句在循环中的位置**，要模拟极端情况 56. [#10059. 「一本通 2.4 练习 2」Censoring](https://loj.ac/p/10059) - ***AC自动机*** - 在编程过程中，想要**将程序恢复到原来的某种状态，可以使用`stack`** 57. [#10063. 「一本通 2.4 练习 6」文本生成器](https://loj.ac/p/10063) - ***AC自动机***, ***dp*** - dp[i][j]表示长度为i的字符串匹配到trie树的j节点时字符串无法匹配任何一个单词的字符串数 - 显然dp[i + 1][child(j)] += dp[i][j], 但该由j转移到该子节点的路径k（即child = ch[j][k]） - 需要满足j每一次转移fail指针到达的节点的路径k都没有被标记为任何一个单词的末尾 - 填dp表 ``` for (int i = 1; i <= m; i++) for (int j = 1; j <= tot; j++) if (dp[i - 1][j] && !end[j]) 状态转移 ``` - `end`数组可以在`trie.add`和`trie.make`时填充 58. [黑暗城堡](https://blog.csdn.net/zbchencent/article/details/113107952) - ***最小生成树*** - 不需要真的去建一个最小生成树，分别将每个节点当成最短路径生成树的最后一个要加入的节点 - 统计dist[cur] = dist[p] + edge[cur][p](cur为外层循环，p为内层循环)的p的个数，最后将结果乘起来即可； 59. [#10065. 「一本通 3.1 例 2」北极通讯网络](https://loj.ac/p/10065) - ***最小生成树*** - 当正向思考受阻时，逆向思维可能有效 - 定理：如果去掉所有权值大于d的边后，最小生成树被分割成k个连通支，则图也被分成k个连通支 - 证明过程见书P113 60. [#10066. 「一本通 3.1 练习 1」新的开始](https://loj.ac/p/10066) - ***最小生成树*** - 这个题就是个最小生成树。 就拐了个弯而已。 - 想一下：这个跟其他最小生成树不同的点不就是每个点就想有了个点权一样吗？ 那怎么办呢？ - 只需要再建一个0点，把所有点向它连一条边，边权值为建发电站的费用(也就是点权)， 再跑最小生成树就行了。 61. [#10067. 「一本通 3.1 练习 2」构造完全图](https://loj.ac/p/10067) - ***最小生成树***, ***kruskal算法*** - [Solution](https://blog.csdn.net/weixin_52115456/article/details/117573443) - 大体思路都正确，但在完全图构建时新加边数的细节上出现了问题 62. [#10068. 「一本通 3.1 练习 3」秘密的牛奶运输](https://loj.ac/p/10068) - ***最小生成树***, ***kruskal算法***, ***次小生成树*** - [Solution](https://www.acwing.com/solution/content/121528/) - 注意这里用存储兄弟的形式存储树比较方便 63. 营救大兵瑞恩（一本通提高篇p125） - ***宽度优先搜索***，***最短路***, ***分层*** - 当人在图中的行为能够影响到图本身的性质时（e.g. 找钥匙开门） - 可以采用**分层图**的思想建立模型 - 详见课本 64. [#10075. 「一本通 3.2 练习 1」农场派对](https://loj.ac/p/10075) - ***最短路***, ***SPFA*** - [Solution](https://loj.ac/p/10075) - 可以建两个图，一个正向图，一个反向图 - 正向图用于求解从派对地回家的最短距离，反向图用于求解从家到派对地的最短距离 - 这样只需要对派对地跑两遍***SPFA*** 65. [#10077. 「一本通 3.2 练习 3」最短路计数](https://loj.ac/p/10077) - ***最短路***, ***dijkstra*** - [Solution](luogu.com.cn/blog/Otto-Apocalypse/solution-p1144) - 注意：题上只是说所给的是一个**图**，而非**连通图** 66. [#10078. 「一本通 3.2 练习 4」新年好](https://loj.ac/p/10078) - ***最短路*** - 思路很简单，但要注意几个细节 - ***SPFA***在将一个节点从`queue`中取出时，要将`visit`设置为`false` - 虽然题上最大边数为1e5，但是要开2e5大小的数组，因为是无向图 67. [#2590. 「NOIP2009」最优贸易](https://loj.ac/p/2590) - ***最短路***, ***dfs***, ***dp*** - [分层思想](https://www.luogu.com.cn/blog/user15019/solution-p1073) - [dfs + dp](https://www.luogu.com.cn/blog/jerryzheng2005/solution-p1073) - 分层思想：只需要分三个层，最底层是初始层，由初始层到中间层模拟的是买入，且单向（避免了负环） - 由中间层到顶层模拟的是卖出，且单向（避免了负环） - 那个dfs + dp比较巧妙，在dfs中所设置的flag其实是剪枝操作 - 设置的flag其实就是当节点的信息需要更新时再进行搜索，其实就是spfa的队列优化，整体复杂度近似于spfa - 如果不设置flag的话，再加上bellman-ford算法的层数限制，其实整体复杂度就与bellman-ford无异 68. [#6223. 「网络流 24 题」汽车加油行驶问题](https://loj.ac/p/6223) - ***最短路***, ***分层***, ***网络流*** - [Solution](https://www.luogu.com.cn/blog/ChenXingLing/solution-p4009) > 其实是有点贪心的味道，由于往回走有花费且为正整数，所以不会回到已经走过的地方去 > 生成加油站也是一样的，反正早点生成晚点生成都没有影响，在一条路走到底后再生成不是更好吗 - 启示：**当问题的复杂度变得不可接受时，可以对某些情况用贪心的思维重新考虑一下，排除某些不可能情况** - markdown编辑提示：在引用块内需要换行时，需要在行尾加两个空格 69. [#10081. 「一本通 3.2 练习 7」道路和航线](https://loj.ac/p/10081) - ***最短路***, ***dfs***, ***DAG***, ***拓扑排序***, ***dijkstra*** - [Solution](https://blog.csdn.net/m0_73386348/article/details/132174825) - ***dijkstra***算法当遇到稠密图时效率要比***SPFA***在***SLF***和***LLL***优化后都高 - 注意把每个强联通块**缩点**后成为*DAG*用**拓扑排序的顺序来求单源最短路的思想** 70. [P7913 [CSP-S 2021] 廊桥分配](https://www.luogu.com.cn/problem/P7913) - ***堆***, ***模拟*** - [Solution](https://www.luogu.com.cn/problem/P7913) 71. [P7075 [CSP-S2020] 儒略日](https://www.luogu.com.cn/problem/P7075) - ***模拟*** - 基本上纯纯考验代码量 - 做与日期有关的题目时，注意在对一个日期做一个类似取余的运算后，要对该日期是否变成0检验 - 若变成0，则一般要将日期往前推移一次 72. [P8817 [CSP-S 2022] 假期计划](https://www.luogu.com.cn/problem/P8817) - ***0/1最短路***, ***bfs***, ***贪心*** - 在我写的85分代码的情景下 - 注意用于跳出多层循环的`flag`在跳出最后一层循环后要赋值为false，防止在再次进入这几层循环时直接跳出 - 注意可行性剪枝和最优性剪枝 - [Solution](https://www.cnblogs.com/crab-in-the-northeast/p/luogu-p8817.html) > 注意：对于满足边权全为 1 的图，单源最短路可以做到 o(n) 的复杂度（采用 bfs） > 对于满足边权只有 0，1 两种的图，单源最短路也可以做到 O(n) 的复杂度（采用 0-1 bfs） > 但有一种贪心是对的，那就是确定了 a，b，c，选择 d 的时候。如果我们确定了 c，那么直接选择 c 可达的， > 在家附近的，不为 a 也不为 b 的权值最大的景点作为 d 即可。反正 d 之后没有景点了， > 所以可以直接贪心，没有后顾之忧。 > 由于**环的对称性**，可以发现确定了 $b$，$c$，$d$ 之后，也可以贪心地选择 $a$. > 我们定义 f(u) 表示 u 可达，且在家附近的权值最大的景点。 > f(u) 是可以**预处理**出来的 73. [#10114. 「一本通 4.1 例 2」数星星 Stars](https://loj.ac/p/10114) - ***树状数组***, ***排序*** - 如果不加任何预处理，那么该题还需要开二维树状数组，但题目空间限制不允许 - 但是，如果将原数据按照x或y按非降序排序后，那么再按排序后的顺序读取，只需要比较一种坐标大小就可以判断等级了 77. [#10115. 「一本通 4.1 例 3」校门外的树](https://loj.ac/p/10115) - ***树状数组***, ***线段树*** - 本题看似是一个有关区间修改和统计的题目，那么一定可以用线段树 - 但是可以通过适当的转化，将其转化为单点修改 - 可以将区间\[l, r]看做是在l点的一个"\["和在r点的一个"]" - 查询区间\[l, r]时，可以分别查询在r点之左的"]"个数和在l点之右的"["数，然后在作差即可 - 所以可以分别维护两个树状数组，分别维护"\["和"]"即可 78. [#10131. 「一本通 4.4 例 2」暗的连锁](https://loj.ac/p/10131) - ***LCA***, ***树上差分算法*** - [树上差分算法（在链接文章的后半部分）](https://www.luogu.com.cn/blog/RPdreamer/ci-fen-and-shu-shang-ci-fen) 79. [#10132. 「一本通 4.4 例 3」异象石](https://loj.ac/p/10132) - ***LCA*** - 在一棵树中取多个点，比较有特殊含义的遍历顺序：***dfs***, ***bfs*** - 也不需要真的为了这几个点重新遍历整个树，可以在第一次遍历的时候打上时间戳，之后按此序遍历 - 例如：求将选中点连通的边集的总长度的最小值可以用在dfs序中相邻的顶点之间的最短距离之和（第一个和最后一个也算相邻） - 再除以2，即是答案 - 还有就是，这道题不需要真的在每次查询时重新计算，而是可以**动态**维护ans，每次位置变动时都用当前的ans计算出变动后的ans - 等到查询时直接输出即可 80. [#10149. 「一本通 5.1 例 3」凸多边形的划分](https://loj.ac/p/10149) - ***区间dp*** - 直接分析题目没有头绪时，可以从样例入手 - 这里的f\[i]\[j]数组的意义可以设定为从i号顶点到j号顶点所形成的多边形的最大三角边权乘积和 - 注意这道题要攻克的点是如何**将一种状态由有序数对(i, j)唯一表示，并且满足区间dp的转移性质** - 这类问题的基本特征是**能将问题分解成为两两合并的形式** 81. [P9118 [春季测试 2023] 幂次](https://www.luogu.com.cn/problem/P9118) - ***容斥原理***, ***dp*** - [Solution](https://www.luogu.com.cn/blog/590600/solution-p9118) 82. [#10154. 「一本通 5.2 例 2」选课](https://loj.ac/p/10154) - ***树形dp***, ***背包*** - 这是信息学奥赛一本通上的例题，不理解的地方在于更新状态时倒序枚举背包容量 - 解释 - 之所以要倒序枚举，是因为要避免重复选同一个物品 - 首先区分两个概念 - 老值：在重复更新dp表格的同一行时，上一次更新该行所计算出的值 - 新值：在重复更新dp表格的同一行时，当前更新该行所计算出的值 - 再明确几个方向名词：上下左右即为在dp表格中的方位 - 如果要用某个方向DIR的老值更新当前位置时，则要从与DIR相反的方向开始，沿DIR方向更新 - 如果要用某个方向DIR的新值更新当前位置时，则要从与DIR相同的方向开始，沿DIR的反方向更新 - 这道题中，我们要依次考虑CUR的每个子节点X - 我们需要用之前考虑过的所有子节点PRES得出的dp表格来更新当前位置，即用左侧的老值更新 - “左侧”是因为更新dp\[CUR]\[T]时，需要枚举每个dp\[CUR]\[T - i] - 用“老值”是因为要避免重复选某个商品（老值所涉及的子树与当前考虑的子树没有交集） - 因此要从右往左更新，即在重复更新dp同一行数值时，要倒序 83. [#10163. 「一本通 5.3 例 1」Amount of Degrees](https://loj.ac/p/10163) - ***数位dp*** - [Solution](https://blog.csdn.net/qq_43328040/article/details/106834572) - 这道题的数位dp从图的角度比较好理解，可以把满足条件的数以每一位分别想象成一个节点， - 然后每次对结果加上的数其实就是左子树中满足条件的链的个数 - 还有就是，本题区间满足区间减法，\[a...b]之间的满足条件的数的个数即为dp(b) - dp(a - 1) 84. [#10184. 「一本通 5.6 例 1」任务安排 1](https://loj.ac/p/10184) - ***dp***, ***费用提前计算*** - dp状态转移通常与题目上给出的处理项数（总递推次数）无关，这就丧失了一个可用信息 - 而**费用提前计算的思想充分利用了总处理项数的这个信息**，它从一个更为**全局**的角度简化了状态转移 - 即如果把最后结果的计算过程列成一个式子时，可以发现有部分**在一个或多个有规律的区间内累加，而这个规律本质上与某个解的特殊性质无关** - 那么可以在状态转移/设计时，**直接在某个区间的最开始把那部分对整个区间的贡献直接算上** 85. [#10185. 「一本通 5.6 例 2」任务安排 2](https://loj.ac/p/10185) - ***dp***, ***费用提前计算***, ***斜率优化*** - 当得到一个不定dp转移方程时(有`max`或`min`等)，可以把`max`或`min`去掉，把转移方程看做一个方程f(i, j) = 0 - 尝试探索这个方程本身的性质，可以把包含j的多个项分别看做是因变量、自变量 - （因为这样在坐标系中能确定一部分元素的位置），探索状态转移（求最值）本身的几何意义 - 还有就是因为浮点数有精度限制，故尽量把涉及到浮点数的计算转换为整型计算 86. [#10186. 「一本通 5.6 例 3」任务安排 3](https://loj.ac/p/10186) - ***dp***, ***费用提前计算***, ***斜率优化***, ***二分*** - 判断单调队列是否“非空”的条件也不固定，如果该单调队列单调性的维护至少需要用到2个位置，则为`rp > lp` - 而非`rp >= lp` - 如果某个单调队列的队头不一定是最优值时，可以仅仅维护单调性，用（二分）查找的方式查找最优解 87. [#10187. 「一本通 5.6 例 4」Cats Transport](https://loj.ac/p/10187) - ***dp***, ***斜率优化*** - 思路： - 要求所有猫等待时间的最小值，我们**先从最简单的情况考虑** - 先考虑如何表示一个猫的等待时间 - 如果一个饲养员想要接到第i只猫，那么就必须在Ti - ∑Dj(1 ≤ j ≤ Hi)时刻之后出发，将该值设为Ai - 如果该饲养员在t时刻出发(t >= Ai)，那么猫的等待时间是t - Ai - 然后就可以很自然地把Ai按非降序排序，然后就可以发现思路就会和题 [任务安排2](https://loj.ac/p/10185) 的很像了 - 启示 - 考虑问题**从最基本的问题思考** - 要善于运用数学**将原问题数学化**（公式化） 88. [#10197. 「一本通 6.2 例 1」Prime Distance](https://loj.ac/p/10197) - ***埃氏筛*** - 想要筛出\[L, R]范围内的素数，只需要把\[2, sqrt(R) + 1]范围内的质数筛出，然后用埃氏筛筛\[L, R]即可 89. [#10203. 「一本通 6.3 例 1」反素数 Antiprime](https://loj.ac/p/10203) - ***数论***, ***打表** - 首先可以考虑从搜索入手 - 这题要求最大反素数，因为涉及到约数个数，考虑从素因数分解的角度思考 - 即探究反素数的素因数分解后的性质，缩小搜索范围（**剪枝**） - 并且因为我们探究的是其**性质**，而**非等价判定** - 故满足这个性质的数并不一定都是反素数，而有可能是反素数 - 但如果我们按照这个性质搜索，一定能搜到**所有可能是反素数（约数最多）的数** - 故我们在搜索的同时，先要判断当前搜到的最优解是否合理（**可行性**） - 之后还要判断当前结果是否比当前的最优解更优（**最优性**） - 还有一个剪枝是最多搜索10层（**可行性**），因为把前十个素数乘起来的积已经超出了数据范围 - 其次，这道题可以**打表**，把题设范围内的反素数全部求出 - 直接打表时间会不够，那么可以**先打一个小表，观察规律** - 再**利用规律打一个大表** 90. [#2589. 「NOIP2009」Hankson 的趣味题](https://loj.ac/p/2589) - ***数论***, ***质因数分解***, ***排列组合***, ***最大公约数***, ***最小公倍数*** - 思路一：用质因数分解来得到相关性质 - 启示：在对每一个因素分类讨论后，要用类似**叉乘**的思想进行全局分类讨论 - 思路二：利用最大公约数和最小公倍数的性质缩小枚举范围 - 推导过程 > lcm(x, b0) = b1 > b0 \* x = b1 * gcd(x, b0) > x = b1 / b0 * gcd(x, b0) - 则可以在[1, sqrt(b0)]的范围内枚举x，判断x和b0 / x分别是否符合条件即可 91. [P8251 [NOI Online 2022 提高组] 丹钓战](https://www.luogu.com.cn/problem/P8251) - ***栈***, ***模拟***, ***倍增*** - 思路一：纯模拟，用二分求每次要插入的位置，O(q\*n*log2(n))，15分 - 思路二 - 对题意理解更深后，就可以发现**只需要对整个序列模拟一次**，预处理出每个元组压入栈后它底下的元组编号 - 对于每一次询问，统计之前预处理的数组中编号小于l的元组的个数即为答案 - 常数较小的O(n + qn)，15分，但速度快了近一倍 - 思路三：倍增优化 - 可以**设计一个倍增数组**，position\[i]\[j]表示以元组i为开头入栈后第2^j个成功元组的位置 - 注意这里的成功元组的计数不包括开头的元组（区间**半闭半开**），这样保证最后统计累加时不会对某一个元组重复计数 - 全局只模拟一次，O(n)，**当i把j弹出时, 记录position\[j]\[0] = i** - 整体复杂度 O(n + n log2(n) + q log2(n)) 92. [P8252 [NOI Online 2022 提高组] 讨论](https://www.luogu.com.cn/problem/P8252) - ***集合*** - 暴力思路：排序，归并，常数较小的O(n^2 *m)，30分 - 优化思路 - 考虑到暴力算法大部分时间全部花在试错上：**减少枚举总量**，**优化枚举顺序** - **利用限制条件**：对于题目i，将所有会该题的人放在一起，此时只用考虑集合的包含关系 -> 减少枚举总量 - **利用性质优化枚举顺序** - 如果两两配对的话，O(n^2) - 想一想，**假定**此时我们按照某个既定的顺序枚举判断其中相邻的人的关系，这个顺序需要满足什么条件呢 - 需要满足**如果此顺序中每次枚举都不符条件，那么将原序列中任意两个人之间的关系都不符条件** - 不符条件 => 存在包含关系；如果任意相邻两个都存在包含关系，那么原序列中任意两个人之间都存在包含关系 - 故易想到：序列中任意相邻两个包含关系的方向应该都一致 => 按k递增/递减顺序排列 - 易得递增较好（计算量由小到大） - 那么我们真的要对每组会特定题目i的人都排序一次吗 - 可以对所有人整体递增排序一次，顺次考虑；对于当前的人x，对于任意题i属于Sx，比较上一个会这道题的人lasti的S与Sx的包含关系 - 如何比较包含关系呢？ - 一条可能的思路：一次枚举Sx中的题目i，每次利用计数数组对Slasti与Sx的交集大小sizei进行统计， - 比较sizei与集合Slasti和Sx的大小之间的关系，即可判断包含关系 93. [P7114 [NOIP2020] 字符串匹配](https://www.luogu.com.cn/problem/P7114) - *** 94. [P9753 [CSP-S 2023] 消消乐【民间数据】](https://www.luogu.com.cn/problem/P9753) - ***类模拟***, ***区间dp***, ***字符串哈希***, ***哈希表*** - 在考场上的第一个思路是：区间DP - 只能拿部分分：35分左右 - 算法复杂度：O(n^3) - 转移方程：f\[i, j] - 若f\[i + 1, j - 1] == true且str\[i] == str\[j]，f\[i, j] = true - 否则，枚举分界点 - 下考场后，得到的满分思路为：一次模拟，记录信息，利用性质来统计 - 分数：100 - 算法复杂度 - 利用红黑树`map`：O(n* log2(n)) - 利用哈希表`unordered_map`：O(n) - 思路 1. 因为这个题涉及到某种字符串变换规则，可以考虑尝试模拟一次，在模拟中寻找特殊性质 - 最原始的思路是直接处理整个字符串，进行模拟，但是这样每次操作复杂度为Ω(n) - 那么可以换一种模拟思路：**由局部到整体** - 可以**从左往右依次加入每个字符来考虑**（用**栈**模拟） - 好处：**信息可以转移计算**，**每次操作复杂度Ω(1)** 2. 这样模拟，就会发现如果某部分字符串可以消去，那么会和之前出现过的某个字符串相等 3. 那么相等可以用哈希（这里用了**双哈希避免哈希冲突**）来判断 4. 每次处理完后看当前字符串的哈希值在之前出现过几次，答案就加上几 95. [P9754 [CSP-S 2023] 结构体【民间数据】](https://www.luogu.com.cn/problem/P9754) - ***模拟***, ***二分查找***, ***树形结构*** - 这道题在考场上**没注意到有提示**，在考场上写了两个小时还差一个操作 - 下考场之后，按照提示的思路用了大约1h30min编写完后AC - 但在下考场后调试过程中，在这个地方出现了一处难以调试的错误 ```cpp int i, tst = 0; for (i = 0; tstr[i] != 0 && tstr[i] != '.'; i++) if (tstr[i] == 0) { printf("%lld\n", vst[vnmmp[getHash(tstr)]]); return; } ``` - 最后发现是**本应没有代码块的`for`循环因为在那行末忘加了`;`**而使得`if`语句也在`for`循环内 - 还有就是一个刚刚发现的调试技巧 - 对于多次询问的题目，如果输出文件只有其中一个询问错了，但是不好定位错误的询问在输入文件的位置 - 可以**在输出时将本次询问的相关信息加上** - 还有一个刚刚发现的针对本题的技巧 - 内存本身其实可以抽象成一个结构体 - 这样就可以省去对变量的单独讨论 96. Paradise - ***贪心***, ***递归*** - 思路 - 这道题如果只是让求f(n)的话，而不是求和，那么思路很简单 - 求每个的f(n)其实也可以求和（**局部的角度**），但是这样对于这道题1e18的数据规模而言太慢了 - 故可以**从全局的角度思考**，**探究特点**，**找寻规律** - 但是这道题让求和，求和本质上是积分，故可以将f(n)的图像画出来，再求面积 - 在实现时肯定不是求面积，只是这样可以发现其中的规律 - 因为这样便于**从全局的角度**思考 - 然后结合题境发现，整个其实是**一个不断嵌套的等差数列** - 故可以用**递归**来求 - 可以将**整块的提前预处理**出来，每次只需要递归地求剩余的和即可 - 实现过程中的问题 1. 这道题因为是要求结果对2^64取模，故不需要用高精度，只需要用`unsigned long long`即可实现自动取模 2. 关于取模的具体问题 - 因为过程中用到了等差数列求和公式，会用除法（除以二）操作 - 然而，如果被除数溢出（对2^64取模），除后的结果就会出现错误 - 故解决方案：让被除数不溢出 1. 可以用高精度，但是常数较大 2. （推荐）改变被除数，提前将被除式中的不可能溢出的偶数除以二 3. 关于比值比大小 - 过程中会出现两个分式比大小的问题，因为浮点数有精度，故一个常用的技巧是化除为乘 - 但是，因为两个相乘的数的规模都为1e18，故结果会溢出 - 故解决方案 1. 仍采用化除为乘的技巧，但过程采用高精度（常数较大） - 其实也可以用`__int128__` 2. 直接对分式比大小 - 先用整除来比大小，如果比不出来的话，可以将原分数用取余技巧等价转化为另一个更小的分数 - 在翻转此分数的分子和分母，递归进行以上操作，直到比较出大小为止 - 需要注意的是无论什么时候，都要对0值单独讨论 97. [异或](https://contest.xinyoudui.com/contest/157/problem/633) - ***异或***, ***逆序对*** - 刚开始有三十分暴力分 - 然后看了题解，先后搞出了另外30分的做法和满分做法 - 分析可能的思路 - 因为这道题只有一个原序列，其他的每次询问都将这个序列整体异或上一个值 - 且求逆序列的基本操作是大小比较 - 故考虑一对数在异或前后的大小如何变化 - 因为异或涉及到了二进制，故从二进制角度比较大小 - 易想到两个数的大小关系只与最高的不同二进制位有关 - 如果用于异或的数在此位上为0，则异或前后大小关系不变 - 否则，大小关系变相反 - 故可以想到，枚举用于异或的数的二进制位，根据此位的值加上相应的满足条件的数对的个数 - 而所有满足条件的数对的个数可以在O(n ^ 2)的枚举下处理出来 - 此算法的复杂度为O(n ^ 2 + m *log2(V))，可以拿下另外30pts - 考虑此算法的瓶颈，主要在O(n ^ 2)的预处理 - 枚举所有的数对计算贡献的过程实际上是一个找公共前缀的过程 - 那么，容易联想到用*Trie* - 倒序加入，每次在加入前统计与当前数某部分不在同一个子树的数的个数，即可计算贡献 - 这道题还涉及到了**反向统计贡献**的思想，实际上属于**离线 + 在线** - 注意 - *Trie*的根节点为1，tot初始值为1，而非0 98. [#NOIP002. 美丽子区间](https://actiku.com/p/NOIP002?tid=6550aa857d896604f1cf919c) - ***单调栈***, ***容斥原理***, ***正难则反*** - 优美的定义是最大值和最小值都不出现在开头或结尾，这个条件难以限制，可以从容斥的角度考虑（正难则反） - 最大值在开头的子区间数量，可以使用单调栈，其余类似的同理 - 求最大值在开头且最小值在结尾的子区间数量，继续考虑单调栈 - 根据上面的分析，∀j ∈ \[i, ri)，子区间\[i, j]都是最大值在开头的子区间，那需要求有多个j满足pj是\[i, j]的最小值 - 那么就需要一个从i开始的单调递减序列来二分求解，而这个单调递减队列可以维护单调栈来得到，时间复杂度O(n* log(n)) - 其实还可以用倍增的思想 - 可以通过一遍单调栈来得到每个元素后一个更小的元素的位置 - 然后再用O(n *log(n))的时间来预处理出每个元素之后第2 ^ n个更小的元素的位置 - 求解时再用**二进制拆分**思想，计算出有多少个j - 整体复杂度O(n* log(n))，但常数比直接二分单调栈大一点 99. [#515. 「LibreOJ β Round #2」贪心只能过样例](https://loj.ac/p/515) - ***bitset***, ***动态规划*** - 因为这道题要统计S的种类数，考虑到同一个S可能有多种计算式，故可以开一个足够大的bool数组，计算出特定结果后标记即可 - 当然不能用暴力，考虑用动规优化 - 设f\[i]\[j]表示从第一个处理到第i个后，j是否满足条件 - 转移方程：f\[i]\[j] = any\{f\[i - 1]\[j - k * k] | k ∈ \[a\[i], b\[i]] ∩ Z} - 然后可以考虑用`bitset`优化 - 则状态转移代码如下 ``` f[0][0] = 1; int i, j; for (i = 1; i <= n; i++) for (j = a[i]; j <= b[i]; j++) f[i] |= (f[i - 1] << (j * j)); ``` - 左移的作用其实就是对上一个的结果整体加上j ^ 2 101. [P7514 [省选联考 2021 A/B 卷] 卡牌游戏 ](https://www.luogu.com.cn/problem/P7514) - ***前缀最大值***, ***后缀最大值***, ***三分***, ***单调性*** - 因为这道题与最值有关，如果考虑时马上没有思路的话，可以尝试根据题目中的某些性质对数据进行变形，然后再考虑 - 且这道题也有提示：牌正面的数字是按照升序给出 - 有一个很简单的性质（**可以先从很简单的性质出发，然后尝试将此性质推广**） - 如果牌正面的最大值和最小值不翻面的话，其他地方的翻面都没有意义 - 然后**可以掐头去尾将次性质推广到整个升序数列** - 然后**控制变量**：固定一个端点，观察另一个端点的最值 - 发现最值具有**单峰性**，可以用三分 - 时间复杂度：O(n *log(n)) - 但是有点问题：如果被三分的函数有斜率为0的点，那么三分可能出错 - 这可能导致了样例二没过（其他的过了） - 但是官方数据和所有民间hack数据都过了 - 启示：**如果在考场上出现少部分样例没过的情况，可以果断放弃调试，先拿其他题的暴力分** 102. [#10087. 「一本通 3.4 例 1」Intervals](#10087. 「一本通 3.4 例 1」Intervals) - ***差分约束系统*** - 因为这道题涉及到了区间选特定数目的点，**某一个区间内选的点的个数满足区间减法** - 则可以将这道题转化成一个差分约束系统 103. [P7515 [省选联考 2021 A 卷] 矩阵游戏](https://www.luogu.com.cn/problem/P7515) - ***差分约束系统*** - 这道题要求用(n - 1)* (m - 1)的信息量复原一个n * m大小的矩阵，故有可能存在多解 - 那么根据信息量，如果这道题没有范围限制的话，就可以把某一行和某一列全部填充好后，就可以得到一个解 - 那么可以尝试将此解**调整**为该范围内 - 考虑到，当将某一行或列隔着加减同一个数时，得到的新矩阵仍是符合条件的一个解 - 那么，可以将此题转化为差分约束系统 - 但是，还要注意该矩阵的某个地方可能为同加或同减某两个变量，因此可以尝试将行号或列号为偶数或奇数的所有变量取相反数，可以转化为差的形式 104. [D1. Maximum And Queries (easy version)](https://codeforces.com/contest/1903/problem/D1) - ***贪心***, ***二分***, ***按为与*** - 这道题刚开始用二分答案来做 - 结果交上去后，有一个点没有过 - 经测试，发现，二分答案做不了，因为答案在极小概率下，答案不具有单调性 - 时间复杂度：O(q * n * log2(R)) (R 为答案的范围) - 看了答案 - 可以用贪心来做，从高位到低位构造答案即可 - 这个感觉也会在极小概率下出现错误答案，但是能过 - 时间复杂度：O(q * n * log2(R)) 105. [#YDRS003C. 香老师？牙幂老师？树老师！](https://www.yundouxueyuan.com/p/YDRS003C) - ***统计链***, ***状态转移***, ***换根DP*** - 要想统计满足条件的链的数量，**首先要为每个满足条件的链取一个唯一的身份标识来保证不会重复统计** - 因为为有向链，故可以用每个链的起点和终点唯一定位这个链 - 可以枚举起点，求出满足条件的链的个数 - 首先**可以以任意一个点为根，用O(nm)的时间以dfs的枚举顺序预处理出以每个s点为链的起点在以s为根的子树中可以匹配到目标字符串的后k个字符的满足条件的链的数量num\[s]\[k]** - 然后在以dfs的枚举顺序，**用状态转移（换根）依次得到以每个点为起点的满足条件的链的数量**，再加和即可 106. [249. 蒲公英](https://www.acwing.com/problem/content/251/) - ***分块*** - 这里详细的分析过程在《算法竞赛进阶指南》P228上，这里只记录其中的一个技巧 - 对于一个给定的序列，如何快速求\[l, r]上某个值出现的次数 - 可以先对每个值开一个vector，用O(n)的时间预处理出每个值出现的位置（按原序列中的位置） - 然后用二分查找，用O(logn)的时间得出在此区间内该值的第一个位置和最后一个位置 - 然后在vector内的下表差加一即为答案 107. [250. 磁力块](https://www.acwing.com/problem/content/252/) - ***分块*** - 详细思路见《算法竞赛进阶指南》P229 108. [1132G - Greedy Subsequences](https://codeforces.com/problemset/problem/1132/G) - ***dfs序***，***序列问题转化为图论问题*** - 乍一看，这个东西似乎与树没有什么关系。但考虑到不论怎么选l,r点x的后继都是确定的，也就是它后面第一个比它大的数的位置。所以我们定义p;表示i后面第一个比a大的数的位置。若不存在则p1=n+1。 - 我们把i向p连一条边。显然这会形成一棵树。考虑使用扫描线的思想，把r依次向右挪动。我们定义f(i)表示在限制内，以i为开头的最长贪心严格上升子序列的长度。挪动到1+1相当于f()不能做出任何贡献，故直接将f()设为负无穷即可。 - 将r挪到r+1,相当于r子树中所有点的f(x)都将加一。由于子树的dfs序是一个区间，故直接使用你喜欢的数据结构维护区间加，单点改，区间最大值即可。 - 时间复杂度O(nlogn)。 #### 未解决的题目 1. [P3884 [JLOI2009]二叉树问题](https://www.luogu.com.cn/problem/P3884) - 题解中说思路有***LCA***、***Floyd***、***树剖***、***树链***等 2. [P1127 词链](https://www.luogu.com.cn/problem/P1127) 3. [P1363 幻象迷宫](https://www.luogu.com.cn/problem/P1363) - ***dfs***, ***bfs***, ***图论*** - ![题解dfs/bfs思路](https://gitee.com/rizzohou/olympiad-in-informatics/raw/master/Images/p1363%E9%A2%98%E8%A7%A3.PNG) - 图论目前还不知道怎么做 4. [P2638 安全系统](https://www.luogu.com.cn/problem/P2638) - ***排列组合*** 5. [P1414 又是毕业季II](https://www.luogu.com.cn/problem/P1414) - ***最大公约数***, ***dp*** 6. [DIVCNT1 - Counting Divisors](https://www.luogu.com.cn/problem/SP26073) - ***约数*** 7. [P1593 因子和](https://www.luogu.com.cn/problem/P1593) - ***约数*** 8. [#10008. 「一本通 1.1 练习 4」家庭作业](https://loj.ac/p/10008) - ***贪心***, ***并查集***, ***线段树*** 9. [#10010. 「一本通 1.1 练习 6」糖果传递](https://loj.ac/p/10010) - ***贪心*** - [题解](https://loj.ac/d/2988) 10. [#10029. 「一本通 1.4 练习 1」棋盘游戏](https://loj.ac/p/10029) - ***bfs*** - 太难调试，最后最高60分 11. [#10042. 「一本通 2.1 练习 8」收集雪花](https://loj.ac/p/10042) - ***哈希表***, ***离散化*** - [正解](https://loj.ac/d/751) 12. [#10047. 「一本通 2.2 练习 3」似乎在梦中见过的样子](https://loj.ac/p/10047) - ***kmp*** - 没时间了，先学其他的 13. [#10048. 「一本通 2.2 练习 4」Censoring](https://loj.ac/p/10048) - ***kmp*** - 没时间了，先学其他的 14. [#2012. 「SCOI2016」背单词](https://loj.ac/p/2012) - ***贪心***, ***Trie*** - 题意无法理解 15. [#10056. 「一本通 2.3 练习 5」The XOR-longest Path](https://loj.ac/p/10056) - ***Trie***, ***异或*** - 样例过了，但提交后错的很离谱 16. [#10061. 「一本通 2.4 练习 4」最短母串](https://loj.ac/p/10061) - ***Trie***, ***状态压缩*** 17. [P4208 [JSOI2008] 最小生成树计数](https://www.luogu.com.cn/problem/P4208) - ***最小生成树*** - 直接枚举的方法倒是能想到，但是更快速、更高级的方法看不懂，详见洛谷题解 18. [#10069. 「一本通 3.1 练习 4」Tree](https://loj.ac/p/10069) - ***最小生成树***, ***kruskal算法***, ***二分答案*** - [Solution](http://www.manongjc.com/detail/12-bfqkkyvjvozmvpc.html) - 网上搜到的题解都无法得到满分，二分太难调试 19. [#10076. 「一本通 3.2 练习 2」Roadblocks](https://loj.ac/p/10076) - ***最短路***, ***dijkstra***, ***SPFA*** - 太难调试 20. [#10082. 「一本通 3.3 例 1」Word Rings](https://loj.ac/p/10082) - ***spfa***, ***dfs***, ***正环***, ***二分*** - 将数据下载到本机成功执行，但提交后却显示re 21. [#10083. 「一本通 3.3 例 2」双调路径](https://loj.ac/p/10083) - ***spfa***, ***动态规划***, ***树状数组*** - 这是一本通的例题，在p146 22. [#10088. 「一本通 3.4 例 2」出纳员问题](https://loj.ac/p/10088) - ***差分约束系统*** - 这是书上的一道题，就是书上的最后一个不等式看不懂 23. [P4766 [CERC2014] Outer space invaders](https://www.luogu.com.cn/problem/P4766) - ***区间动规***, ***离散化*** - 前两个测试点都过了，但是第三个测试点有一个数据没过 - 还有一个要注意的：当一次测试会给出多组数据时，每次计算前要将相应的变量变回初值 24. [P8819 [CSP-S 2022] 星战](https://www.luogu.com.cn/problem/P8819) - ***图论*** - **如果一个图中所有点的出度都为1，那么这个图中一定有环** - 目前只拿到了暴力分40分 25. Firstsnow - ***枚举***, ***bitset*** - 目前只有75分的算法 26. [#3997. 「CSP-S 2023」种树](https://loj.ac/p/3997) - ***二分答案***, ***正难则反***, ***高精*** - 思路 - 首先，这道题想要通过动规或贪心很难直接得出最少时间 - 那么可以考虑将**最优性问题**转化为**判定性问题** - 通常每次判定的复杂度都较小 - 且这个问题也具有单调性 - 二分答案的第一个用到的地方 - 因为这道题中涉及到等差数列，且有求和之类的操作，在算天数时可能要解二次函数 - 但是，树的高度一定是随着天数单调递增的，故可以考虑二分答案求解 - 现在就可以解决特殊性质B了 - 注意 1. 如果不用__int128的话，就要用高精 - 在高精加法中，加完最高位（就是最后一次加完后）后要注意对下一位进行进位 27. [~~异或~~](https://contest.xinyoudui.com/contest/157/problem/633) - ***异或***, ***逆序对*** - 目前只有30分的算法，因为没有利用异或的性质 28. [Essence of Twilight](https://contest.xinyoudui.com/contest/157/problem/786) - ***逆序对***, ***线段树***, ***区间修改，区间询问***, ***树状数组***, ***正难则反*** - 目前只有64分的算法，目前算法的瓶颈在于每次统计区间内在某个范围的数的个数较慢，为O(n) - 但是，因为给定范围内的区间内统计某个范围的数的个数较慢，可以考虑反向考虑 - 考虑单个数对多个区间的贡献 - ![题解](https://gitee.com/rizzohou/olympiad-in-informatics/raw/master/Images/Essence%20of%20Twilight%E9%A2%98%E8%A7%A3.PNG) 29. [数表](https://contest.xinyoudui.com/contest/157/problem/647) - ***数位DP*** - 只拿了暴力分10分 30. [#NOIP003. 字符序列](https://marsoj.xiemaedu.com/p/NOIP003?tid=6550aa857d896604f1cf919c) - ***动态规划***, ***字符串***, ***排列组合*** - 有题解，但是题解写的太简略了，转移方程看不懂 31. [#NOIP004. 网络攻防](https://marsoj.xiemaedu.com/p/NOIP004?tid=6550aa857d896604f1cf919c) - ***图论***, ***桥***, ***生成树***, ***树上差分***, ***哈希表***, ***概率近似*** - 首先，这道题的枚举算法（期望得分为10分）和当要删除的边的数量为一时的求桥的算法（15分）我是能想到的 - 但是，当要删除的边的数量为二时，我们需要做一点点转化 - 用**控制变量**的思想，设一条边E1要被删除，则要使另一条边E2被删除后不连通，那么删除E1后E2为桥 - 这样，枚举E1，然后再求桥即可 - 结合以上的思想可以得到30分 - 如果从当前的角度去思考的话，这个基本上就是优化的极限了 - **换一个角度去思考，因为这道题涉及到了连通，在图论中，与此相关的概念不止有割点和桥，还有生成树和强连通分量** - 因为强连通分量缩点后得到的是DAG，没有什么好的连通性质，且每个分量内的边连通度有的还等于2，还需要继续转化成其他形式去考虑 - 故可以从生成树的角度去思考 - 当要删除的边数量为1时，用之前的求法即可，以下讨论的边数皆为2 - **根据原图生成一棵树，删除的边的类型有两种：树边和非树边** - 删除2条非树边毫无影响 - 删除一条树边和一条非树边 - 若树边是桥，非树边任意 - 否则，当且仅当树边被非树边唯一覆盖时，可以破坏连通性 - 可以用树上差分 - 删除两条树边 - 若一条是桥，另一条任意 - 否则，有一定理：删除树边 a, b 后原图不连通的充要条件为 - 覆盖了边 a 的非树边集 Sa 与覆盖了边 b 的非树边集 Sb 满足 Sa = Sb. - 依据现在的讨论，可以得到O(n ^ 2 + m)的算法，使用`bitset`优化后可以得到40~60分的分数 - 如何优化Sa = Sb的判断呢 - 朴素算法不必多说 - 稍微高级一点的算法，可以使用树上差分，每个节点开两个`bitset` - 最快的算法，可以用一下在树上差分的同时，使用一个**几乎绝对正确**的判断（**概率近似**） - ![最优算法](https://gitee.com/rizzohou/olympiad-in-informatics/raw/master/Images/%E7%BD%91%E7%BB%9C%E6%94%BB%E9%98%B2%E6%9C%80%E4%BC%98%E7%AE%97%E6%B3%95.PNG) - 如何使用树上差分 - 树上差分不一定必须要使用"+/-1"的形式，还可以用“异或”来替代 - 因为异或两次同一个数，该数的影响就会消去 - 因为这道题必须要用树上差分，可以直接在用树上差分的同时求出桥 - 一个图的所有桥一定在其生成树上 - 且其生成树上一次都没有被非树边覆盖的边一定是一个桥 - 关于异或型树上差分和"+/-1"型的比较见后面的知识总结 ### 未标记的题目 1. [P1208 [USACO1.3]混合牛奶 Mixing Milk](https://www.luogu.com.cn/problem/P1208) 2. [P4995 跳跳！](https://www.luogu.com.cn/problem/P4995) 3. [P1678 烦恼的高考志愿](https://www.luogu.com.cn/problem/P1678) - 二分法 4. [P2678 [NOIP2015 提高组] 跳石头](https://www.luogu.com.cn/problem/P2678) - 二分法 5. [P2440 木材加工](https://www.luogu.com.cn/problem/P2440) - 二分法 6. [P3853 [TJOI2007]路标设置](https://www.luogu.com.cn/problem/P3853) - 二分法 7. [P1182 数列分段 Section II](https://www.luogu.com.cn/problem/P1182) 8. [P1036 [NOIP2002 普及组] 选数](https://www.luogu.com.cn/problem/P1036) - dfs 9. [P2036 [COCI2008-2009#2] PERKET](https://www.luogu.com.cn/problem/P2036) - dfs 10. [P1605 迷宫](https://www.luogu.com.cn/problem/P1605) - dfs 11. [P2404 自然数的拆分问题](https://www.luogu.com.cn/problem/P2404) - dfs 12. [P1540 [NOIP2010 提高组] 机器翻译](https://www.luogu.com.cn/problem/P1540) - ***queue*** 13. [P1305 新二叉树](https://www.luogu.com.cn/problem/P1305) - ***二叉树*** 14. [P1030 [NOIP2001 普及组] 求先序排列](https://www.luogu.com.cn/problem/P1030) - ***二叉树*** 15. [P1918 保龄球](https://www.luogu.com.cn/problem/P1918) - ***map*** 16. [P1621 集合](https://www.luogu.com.cn/problem/P1621) - ***并查集*** 17. [P3879 [TJOI2010] 阅读理解](https://www.luogu.com.cn/problem/P3879) - ***map***(`unordered_map`) 18. [P2814 家谱](https://www.luogu.com.cn/problem/P2814) - ***map***(`unordered_map`) 19. [P2661 [NOIP2015 提高组] 信息传递](https://www.luogu.com.cn/problem/P2661) - ***图*** 20. [P1330 封锁阳光大学](https://www.luogu.com.cn/problem/P1330) - ***图*** 21. [P1017 [NOIP2000 提高组] 进制转换](https://www.luogu.com.cn/problem/P1017) - ***进制转换*** - 涉及负进制 22. [P3913 车的攻击](https://www.luogu.com.cn/problem/P3913) - ***计数*** 23. [P1572 计算分数](https://www.luogu.com.cn/problem/P1572) - ***最大公约数*** 24. [P4057 [Code+#1]晨跑](https://www.luogu.com.cn/problem/P4057) - ***最大公约数*** 25. [#10005. 「一本通 1.1 练习 1」数列极差](https://loj.ac/p/10005) - ***贪心*** - [代码](https://gitee.com/rizzohou/olympiad-in-informatics/tree/master/Exercises/%2310005.%20%E3%80%8C%E4%B8%80%E6%9C%AC%E9%80%9A%201.1%20%E7%BB%83%E4%B9%A0%201%E3%80%8D%E6%95%B0%E5%88%97%E6%9E%81%E5%B7%AE) 26. [#10006. 「一本通 1.1 练习 2」数列分段](https://loj.ac/p/10006) - ***贪心*** 27. [#10007. 「一本通 1.1 练习 3」线段](https://loj.ac/p/10007) - ***贪心*** 28. [#10014. 「一本通 1.2 练习 1」数列分段 II](https://loj.ac/p/10014) - ***二分*** 29. [#10015. 「一本通 1.2 练习 2」扩散](https://loj.ac/p/10015) - ***二分***, ***bfs*** 30. [#10016. 「一本通 1.2 练习 3」灯泡](https://loj.ac/p/10016) - ***三分*** 31. [#10023. 「一本通 1.3 练习 2」平板涂色](https://loj.ac/p/10023) - ***dfs***, ***剪枝*** 32. [#10024. 「一本通 1.3 练习 3」质数方阵](https://loj.ac/p/10024) - ***dfs***, ***剪枝*** 33. [#10030. 「一本通 1.4 练习 2」Keyboarding](https://loj.ac/p/10030) - ***bfs*** 34. [#2653. 「POI2007」山峰和山谷 Ridges and Valleys](https://loj.ac/p/2653) - ***bfs*** 35. [#10036. 「一本通 2.1 练习 2」Seek the Name, Seek the Fame](https://loj.ac/p/10036) - ***字符串***, ***hash*** 36. [#10035. 「一本通 2.1 练习 1」Power Strings](https://loj.ac/p/10035) - ***字符串***, ***hash*** 37. [#2823. 「BalticOI 2014 Day 1」三个朋友](https://loj.ac/p/2823) - ***字符串***, ***hash*** 38. [#10038. 「一本通 2.1 练习 4」A Horrible Poem](https://loj.ac/p/10038) - ***字符串***, ***hash*** 39. [#2452. 「POI2010」反对称 Antisymmetry](https://loj.ac/p/2452) - ***哈希*** 40. [#10045. 「一本通 2.2 练习 1」Radio Transmission](https://loj.ac/p/10045) - ***kmp*** 41. [#10052. 「一本通 2.3 练习 1」Immediate Decodability](https://loj.ac/p/10052) - ***Trie*** - 这个其实可以注意一下在insert时就可以完成对答案的判断 42. [#10053. 「一本通 2.3 练习 2」L 语言](https://loj.ac/p/10053) - ***Trie***, ***dfs***, ***记忆化*** - 注意dfs时要**记忆化**，防止超时 - 注意`if`后的`{}`和**缩进** 43. [#10054. 「一本通 2.3 练习 3」Secret Message 秘密信息](https://loj.ac/p/10054) - ***Trie*** - 注意可能会有重复的密码 - 启示：当不能确定题目中的数据的某些特征时，**尽可能编写能解决最多种问题的代码**，保证结果正确； 44. [#10062. 「一本通 2.4 练习 5」病毒](https://loj.ac/p/10062) - ***Trie***, ***dfs*** 45. [#119. 单源最短路](https://loj.ac/p/119) - ***最短路*** - 最短路算法模版题 46. [#10098. 「一本通 3.6 例 1」分离的路径](https://loj.ac/p/10098) - ***点双联通分量*** - 注意在对思路正确但某些部分打错的代码调试时，要一行一行过，在大脑中推算 47. [#10099. 「一本通 3.6 例 2」矿场搭建](https://loj.ac/p/10099) - ***点双联通分量***, ***邻接表*** - `vector`存储时常数时间较大，用邻接表存储在数据量较大时能够优化速度 - `buffer overflow detected : terminated`这个错误信息可能是某些数组开小了 48. [#130. 树状数组 1 ：单点修改，区间查询](https://loj.ac/p/130) - ***树状数组*** - 当一个数组较大时，尽量将其开成全局变量，如果开成局部变量的话，程序仍会编译成功，但无法运行 - 当某个较大的数组是一个类的一个成员变量时，创建这个类的实例也要是全局的，但是可以在函数内修改它的属性 49. [#10119. 「一本通 4.2 例 1」数列区间最大值](https://loj.ac/p/10119) - ***RMQ***, ***ST*** 50. [#10121. 「一本通 4.2 例 3」与众不同](https://loj.ac/p/10121) - ***RMQ***, ***ST*** - 书上的例题 - [Solution](https://www.bilibili.com/read/cv10358521/) 51. [#130. 树状数组 1 ：单点修改，区间查询](https://loj.ac/p/130?locale=zh_CN) - ***线段树*** - 注意数组标号是**从0开始还是从1开始** 52. [#132. 树状数组 3 ：区间修改，区间查询](https://loj.ac/s/1868048) - ***线段树*** 53. [#10130. 「一本通 4.4 例 1」点的距离](https://loj.ac/p/10130) - ***LCA***, ***倍增*** - 这本是一道极简单的题，可我调试了一个小时 - 注意，这道题的`MAZ_LOG_DEPTH`虽然是17，但是开数组时要开成`f[VERTEX][MAX_LOG_DEPTH + 1]`，因为需要访问f[n][17] - 否则，不加一的话，修改`f[n][17]`时就会修改成`f[n + 1][0]`，而且调试时没有任何提示 - 还有一点要注意，树是一种无向图，边数要开成两倍的顶点数量 - 否则，提交时会奇怪地提示`MLE` 54. [#10138. 「一本通 4.5 例 1」树的统计](https://loj.ac/p/10138) - ***树链剖分***, ***线段树*** - `assignment of member 'SegmentTree::curSum' in read-only object`错误信息的可能原因： - 该成员函数声明为`const`，但过程中对某些成员变量进行了修改 - 线段树的数组的**开始下标应为1**（如果是0的话，0的左端点就成了0） - 注意求线段树上当前节点的子节点用左移`<<`符号 55. [#10143. 「一本通 4.6 例 1」营业额统计](https://loj.ac/p/10143) - ***平衡树***, ***Treap*** - ```cpp Node& leftNode(const int k) const { return node[node[k].left]; } ``` - 以上代码会报错，因为该成员函数是`const`类型，但是返回的引用不是`const`类型 56. [#10147. 「一本通 5.1 例 1」石子合并](https://loj.ac/p/10147) - ***区间dp*** - 用到了一个变环为链的小技巧：可以开一个二倍环大小的数组，用a[i][i + 环大小]表示环 57. [#10148. 「一本通 5.1 例 2」能量项链](https://loj.ac/p/10148) - ***区间dp*** - 变环为链的技巧同上一题 58. [P8865 [NOIP2022] 种花](https://www.luogu.com.cn/problem/P8865) - ***排列组合*** - 注意：**当一个测试点有多组数据时，在计算每组数据时，一定要注意状态重置** 59. [P9117 [春季测试 2023] 涂色游戏](https://www.luogu.com.cn/problem/P9117) - ***模拟*** 60. [#10153. 「一本通 5.2 例 1」二叉苹果树](https://loj.ac/p/10153) - ***树形dp*** - 当程序主体思路正确，答案却怎么也不对时，可以看一下数据的初始化和输入，以及函数的参数 61. [#3564. 「NOIP2021」报数](https://loj.ac/p/3564) - ***埃氏筛*** - 这题数据范围小于等于1e7，故可以用埃氏筛 - 但是这题数论好像做不了 - 有一个小技巧：在埃氏筛把判定问题处理的同时，也可以同时处理一个nxt数组（下一个满足条件的数） - 这样每一次查询就是O(1)的 62. [#10155. 「一本通 5.2 例 3」数字转换](https://loj.ac/p/10155) - ***树形dp***, ***树的最长链*** - 注意一个小技巧 - 算在1~n内的各个数的约数和时，我们可以枚举每个数，再求约数和 - 但是我们注意到，各个数的约数中有很多重复的 - 所以，可以从小到大枚举每个约数，再将1~n内所有是该约数的倍数的数的约数和加上该约数 - 这样可以大幅减少枚举次数 - 启示：**要主动思考，提问式思考，养成良好的思维习惯（当用到枚举时，可以先想有几种枚举方式，再选出最优的）** 63. [Balancing Act](http://poj.org/problem?id=1655) - ***树形dp***, ***树的重心*** 64. [#10156. 「一本通 5.2 例 4」战略游戏](https://loj.ac/p/10156) - ***树形dp***, ***树的最大独立集*** 65. [#10157. 「一本通 5.2 例 5」皇宫看守](https://loj.ac/p/10157) - ***树形dp*** - 注意：**题上并没有说1号节点一定是根节点**，且**该树为单向图**，需要**用根节点入度为0的性质来寻找根节点** - **双向树任何点都可以是根节点** 66. [#10165. 「一本通 5.3 例 3」Windy 数](https://loj.ac/p/10165) - ***数位dp***, ***记忆化搜索*** - 数位dp模板题，也可以用dfs记忆化解决 67. [#10170. 「一本通 5.4 例 1」国王](https://loj.ac/p/10170) - ***状态压缩***, ***dp*** - 注意：当算法正确，**但输入较大时结果却出现异常值时，可以考虑变量开小了** - 状态压缩dp模版题 68. [#10171. 「一本通 5.4 例 2」牧场的安排](https://loj.ac/p/10171) - ***状态压缩***, ***dp*** - 本题一行最多有12块土地，且草地的种植不能相邻，可以用**递推**的思想算出当12块地都可种时的方案数 - 设f\[x]表示有x块土地时的方案数，则f\[1] = 2, f\[2] = 3, f\[x] = f\[x - 1] + f\[x - 2] 69. [#10175. 「一本通 5.5 例 1」滑动窗口](https://loj.ac/p/10175) - ***单调队列优化***, ***dp*** 70. [#10176. 「一本通 5.5 例 2」最大连续和](https://loj.ac/p/10176) - ***单调队列优化***， ***dp*** - 注意：用前缀和f\[x] = f\[x - 1] + arr\[x]预处理数据后，想要求任意一段连续序列的和，会少掉原序列整个的和 - （因为下标从0开始） 71. [#10177. 「一本通 5.5 例 3」修剪草坪](https://loj.ac/p/10177) - ***dp***, ***单调队列优化*** 72. [4. 多重背包问题 I](https://www.acwing.com/problem/content/description/4/) - ***多重背包问题***, ***单调队列优化*** 73. [#10193. 「一本通 6.1 例 1」序列的第 k 个数](https://loj.ac/p/10193) - ***快速幂*** 74. [P9652 『GROI-R2』 紫水晶](https://www.luogu.com.cn/problem/P9652) - ***最大公约数***, ***最小公倍数*** - 这种题，只要求求出一个合理解，那么可以在纸上推一下有没有有**特殊性质**的、可以用通项公式求出的合理解 75. [3526. 素数](https://www.acwing.com/problem/content/3529/) - ***线性素数筛*** - 线性素数筛不能在总筛数个数变化时**断点续筛**, 因为每次筛时都只会筛自己范围内的 76. [#10213. 「一本通 6.4 例 5」Strange Way to Express Integers](https://loj.ac/p/10213) - ***同余方程组***, ***拓展欧几里得*** - 当某一个题有多组数据，且在数据逐个输入时即可判断是否有解，不要直接把当前组的数据直接`break`掉 - 这样会造成**输入输出混乱** 77. [#123. 最小生成树](https://loj.ac/p/123) - ***最小生成树***, ***MST*** - 模版题 78. [#10092. 「一本通 3.5 例 2」最大半连通子图](https://loj.ac/p/10092) - ***Tarjan***, ***缩点***, ***dp*** 79. [[CSP-S 2023] 密码锁【民间数据】](https://www.luogu.com.cn/problem/P9752) - ***交集*** 80. [#100. 矩阵乘法](https://loj.ac/p/100) - ***矩阵*** - 矩阵乘法纯计算模板题 81. [#10220. 「一本通 6.5 例 2」Fibonacci 第 n 项](#10220. 「一本通 6.5 例 2」Fibonacci 第 n 项) - ***矩阵优化常系数线性递推关系*** - 注意：类的static成员变量在类定义内部用`static`声明后，还需要在类定义外部在不用`static`的条件下重新声明 82. [呜](https://contest.xinyoudui.com/contest/157/problem/644) - ***乘法原理***, ***加法原理***, ***预处理*** 83. [NOIP001. 植物收集](https://www.actiku.com/p/NOIP001?tid=6550aa857d896604f1cf919c) - ***正难则反***, ***定长区间最值***, ***三分*** - 这道题从正面分析的话，发现要考虑的情况太多 - 那么可以从结果推过程 - 发现不管怎么样，最后一定是所有发育阶段都有且只有一个植物，故这样分析要考虑的因素会先少后多 - 同时，把题上的意思也反向转换一下：花费k能逆向轮换一次，消去i阶段的植物要花ai的钱，求将所有植物消去的最小代价 - 刚开始，我只想到花费最小的可以直接消去，但是轮换还要花费k，总代价不一定最少 - **因为要同时考虑两个因素：消去花费和轮换花费，故可以将其中一个变量固定住，去分析另一个** - 可以固定轮换次数，发现要使消去花费最小，就要选定长区间最小值 - 此时算法已经是O(n^2)的了，可以拿八十分 - 但是因为**随着轮换次数的增加，轮换花费会逐渐增大，但是消去花费会逐渐减小，故二者的和一般会存在一个单峰的极值点，可以用三分** - 那么算法就是O(n * log(n))的了，可以通过此题 84. [P5788 【模板】单调栈](https://www.luogu.com.cn/problem/P5788) - ***单调栈*** - 模板题 85. [Atlantis](http://poj.org/problem?id=1151) - ***线段树***, ***区间修改***, ***区间查询***, ***扫描线***, ***数据降维***, ***离散化*** 86. [A - Halloumi Boxes](https://codeforces.com/contest/1903/problem/A) - ***暴力***, ***冒泡排序*** 87. [C - Theofanis' Nightmare](https://codeforces.com/contest/1903/problem/C) - ***动态规划***, ***全局思想***, ***费用提前计算*** - 暴力的动态规划：O(n ^ 3) - 费用提前计算的动态规划：O(n ^ 2) - 在加上转移优化的动规：O(n) 88. [B - StORage room](https://codeforces.com/contest/1903/problem/B) - ***贪心***, ***构造*** 89. [A - Least Product](https://codeforces.com/contest/1917/problem/A) - ***贪心*** 90. [B - Erase First or Second Letter](https://codeforces.com/contest/1917/problem/B) - ***统计*** 91. [105. 七夕祭](https://www.acwing.com/problem/content/submission/107/) - ***贪心***, ***货仓选址*** - 《算法竞赛》上的例题 92. [#YDRS003A. 时暮的思眷 Le Souvenir avec le crepuscule](https://www.yundouxueyuan.com/p/YDRS003A) - ***贪心***, ***位运算*** - 因为**相应位的结果只与相应位的值有关**，且结果要求最大化，故可以**贪心地从高位到低位考虑** 93. [#YDRS003B. Fermat's Last Theorem](https://www.yundouxueyuan.com/p/YDRS003B) - ***数学*** ## 有用的链接 ### 知识类 1. [贪心算法（百度百科）](https://baike.baidu.com/item/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95/5411800?fr=aladdin) 2. [对素数筛的大幅改进](https://www.luogu.com.cn/blog/nopartyfoucaodong/solution-p3383) - 有用的结论：**大于等于5的质数一定和6的倍数相邻** 3. [map vs unordered_map in C++](https://www.geeksforgeeks.org/map-vs-unordered_map-c/) 4. [深度理解链式前向星](https://blog.csdn.net/ACdreamers/article/details/16902023) 5. [OI Wiki](https://oi-wiki.org/) - [Github](https://github.com/OI-wiki/OI-wiki) - [OI Wiki 状态页](https://status.oi-wiki.org/) - [国内阿里云镜像站](http://oi-wiki.com/) - 注意是`http`协议 6. [一文读懂欧拉函数](https://mp.weixin.qq.com/s?__biz=MzI4NTY3OTU3MA==&mid=2247483929&idx=1&sn=2c4b0d6a50eca1712619f58fc496cb1b&chksm=ebe9c8a4dc9e41b2da54c55bf01cb72d8c2b7ffe651dc50c81403e3ebd0727fba6a5acddb285&scene=27) 7. [多种快读，快写](https://www.cnblogs.com/lingyunvoid/p/15204568.html) 8. [中缀表达式转后缀表达式](https://blog.csdn.net/qq_43290883/article/details/125633103) 9. [次小生成树的求法](https://blog.csdn.net/qq_43290883/article/details/125633103) 10. [求第k大元素](https://blog.csdn.net/qq_37703292/article/details/119755453) 11. [负权环/负权回路相关问题](https://zhidao.baidu.com/question/29683625.html) 12. [在堆中修改元素](https://gitee.com/rizzohou/olympiad-in-informatics/raw/master/Images/%E5%9C%A8%E5%A0%86%E4%B8%AD%E4%BF%AE%E6%94%B9%E5%85%83%E7%B4%A0.jpg) 13. [SPFA algorithm](https://zhuanlan.zhihu.com/p/353019102) 14. [哈希查找的线性探测法](https://blog.csdn.net/m0_45901455/article/details/126148985?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169190948116800222852380%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=169190948116800222852380&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~baidu_landing_v2~default-2-126148985-null-null.142^v92^controlT0_1&utm_term=%E5%93%88%E5%B8%8C%E6%8E%A2%E6%9F%A5&spm=1018.2226.3001.4187) 15. [哈希模数的选取:31 131 1313 13131 131313 etc.](https://www.zhihu.com/question/20507188?from=profile_question_card) 16. [【BFS版本最短路汇总】【边权为1】【边权为0或1】](https://blog.csdn.net/bei2002315/article/details/126991405) 17. [c++入门必学库函数 next_permutation](https://blog.csdn.net/weixin_52115456/article/details/127626074) 18. [关于lower_bound( )和upper_bound( )的常见用法](https://blog.csdn.net/weixin_43967256/article/details/127462617) 19. [全面理解网络流中的最大流问题](https://blog.csdn.net/Nopoduct/article/details/123298182?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169198128116800225525108%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=169198128116800225525108&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-2-123298182-null-null.142^v92^chatgptT3_1&utm_term=%E7%BD%91%E7%BB%9C%E6%B5%81&spm=1018.2226.3001.4187) 20. [SPFA的两种优化方法——SLF和LLL](https://blog.csdn.net/zhouchangyu1221/article/details/90549195) 21. [用拓扑排序的顺序来求DAG单源最短路径](https://blog.csdn.net/u011728372/article/details/22266349) 22. [逗号表达式](https://baike.baidu.com/item/%E9%80%97%E5%8F%B7%E8%A1%A8%E8%BE%BE%E5%BC%8F/4496335) 23. [c++ fill函数](https://blog.csdn.net/liu16659/article/details/87152348) 24. [【C++】cout、printf 语句输出下运算结果保留n位小数的方法](https://blog.csdn.net/weixin_37706349/article/details/118019242) 25. [告别动态规划，连刷40道动规算法题，我总结了动规的套路](https://blog.csdn.net/hollis_chuang/article/details/103045322) 26. [离散化](https://blog.csdn.net/qq947467490/article/details/130590278) 27. [std::tie详解](https://blog.csdn.net/janeqi1987/article/details/102500340?ops_request_misc=&request_id=&biz_id=102&utm_term=std::tie&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-102500340.nonecase&spm=1018.2226.3001.4187) 28. [种类并查集](https://zhuanlan.zhihu.com/p/97813717) 29. [【并查集】并查集详解及两种优化方法（路径压缩与按秩合并）](https://blog.csdn.net/Qiuker_jl/article/details/109708771?ops_request_misc=&request_id=&biz_id=102&utm_term=%E5%B9%B6%E6%9F%A5%E9%9B%86%E7%9A%84%E6%8C%89%E7%A7%A9%E5%90%88%E5%B9%B6&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-109708771.142^v93^chatsearchT3_2&spm=1018.2226.3001.4187) 30. [【图论】【基本概念】](https://blog.csdn.net/default012/article/details/121425431) 31. [有重边不能去时，Dijkstra和prim的异同,去重边，记录最短路径条数(prim, dijkstra, spfa的相关问题)](https://blog.csdn.net/qq_51070956/article/details/123445775?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169227363816800184116393%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=169227363816800184116393&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-2-123445775-null-null.142^v93^chatsearchT3_2&utm_term=prim%E9%87%8D%E8%BE%B9%E5%A4%84%E7%90%86&spm=1018.2226.3001.4187) 32. [UVA 10462 kruskal处理次小生成树中重边问题(还有prim处理重边)](https://blog.csdn.net/qq_43580151/article/details/99168454?ops_request_misc=&request_id=&biz_id=102&utm_term=%E9%87%8D%E8%BE%B9%E5%A4%84%E7%90%86&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-99168454.142^v93^chatsearchT3_2&spm=1018.2226.3001.4187) 33. [递归转化为非递归](https://blog.csdn.net/SYGODNICE/article/details/105782583?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169231937216800180661688%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=169231937216800180661688&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-2-105782583-null-null.142^v93^chatsearchT3_2&utm_term=%E6%8A%8A%E9%80%92%E5%BD%92%E7%A8%8B%E5%BA%8F%E6%94%B9%E6%88%90%E9%9D%9E%E9%80%92%E5%BD%92&spm=1018.2226.3001.4187) 34. [LCA算法以及原理详解](https://blog.csdn.net/qq_37957064/article/details/111560301?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169232425916800215094319%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=169232425916800215094319&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-111560301-null-null.142^v93^chatsearchT3_2&utm_term=lca%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187) 35. [【图论·算法】树的直径&重心概念与求解](https://blog.csdn.net/Ronaldo7_ZYB/article/details/87181534?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169234337916800227412465%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=169234337916800227412465&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-87181534-null-null.142^v93^chatsearchT3_2&utm_term=%E6%A0%91%E7%9A%84%E7%9B%B4%E5%BE%84%E5%92%8C%E9%87%8D%E5%BF%83&spm=1018.2226.3001.4187) 36. [st表维护区间最大公约数（板子）](https://blog.csdn.net/qq_45719639/article/details/118658729) 37. [树状数组一维及二维区间修改区间查询](https://www.cnblogs.com/RabbitHu/p/BIT.html) 38. [分块（算法思想&&基本操作&&例题代码）](https://blog.csdn.net/CSDN_LIUCHENGYU/article/details/117374239?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169252250116800184151990%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=169252250116800184151990&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-117374239-null-null.142^v93^chatsearchT3_2&utm_term=%E5%88%86%E5%9D%97&spm=1018.2226.3001.4187) 39. [树上差分算法（在链接文章的后半部分）](https://www.luogu.com.cn/blog/RPdreamer/ci-fen-and-shu-shang-ci-fen) 40. [prim算法的堆优化](https://blog.csdn.net/weixin_45962388/article/details/113729740) 41. [C++元组(tuple)类型](https://blog.csdn.net/qq_42759112/article/details/125252105?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169259375316777224424284%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=169259375316777224424284&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-125252105-null-null.142^v93^chatsearchT3_2&utm_term=c%2B%2B%20tuple&spm=1018.2226.3001.4187) 42. [dfs求树的重心](https://blog.csdn.net/Ratina/article/details/95967532?ops_request_misc=&request_id=&biz_id=102&utm_term=dfs%E6%B1%82%E6%A0%91%E7%9A%84%E9%87%8D%E5%BF%83&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-1-95967532.142^v93^chatsearchT3_1&spm=1018.2226.3001.4187) 43. [C++：友元（看这一篇就够了）](https://blog.csdn.net/weixin_46098577/article/details/116596183?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169303657016800192247774%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=169303657016800192247774&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-116596183-null-null.142^v93^chatsearchT3_1&utm_term=%E5%8F%8B%E5%85%83%E5%87%BD%E6%95%B0&spm=1018.2226.3001.4187) 44. [C++中rand()函数的用法](https://blog.csdn.net/Kallou/article/details/123554991?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169305077716800211571400%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=169305077716800211571400&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-1-123554991-null-null.142^v93^chatsearchT3_1&utm_term=c%2B%2B%20rand%28%29&spm=1018.2226.3001.4187) 45. [数的重心详解](https://blog.csdn.net/m0_50966319/article/details/126764424?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522169338953216800182756632%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=169338953216800182756632&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-126764424-null-null.142^v93^chatsearchT3_2&utm_term=%E6%A0%91%E7%9A%84%E9%87%8D%E5%BF%83&spm=1018.2226.3001.4187) 46. [数组的复制](https://blog.csdn.net/qq_36955294/article/details/110948936) 47. [CSP-S初赛基础知识整理](https://blog.csdn.net/qq_49458360/article/details/126879300) 48. [背包问题----分组背包(超详细讲解)](https://blog.csdn.net/TheWayForDream/article/details/116567088) 49. [多重背包及多重背包的优化](https://blog.csdn.net/windfriendc/article/details/123892024?ops_request_misc=&request_id=&biz_id=102&utm_term=%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-1-123892024.nonecase&spm=1018.2226.3001.4187) 50. [多重背包问题——单调队列优化](https://blog.csdn.net/weixin_72060925/article/details/128714489) 51. [【远古】详解__int128](https://www.cnblogs.com/FReQuenter5156/p/int128-post.html) 52. [`memmove`函数](https://cplusplus.com/reference/cstring/memmove/) 53. [算法学习笔记(20): 二维偏序](https://zhuanlan.zhihu.com/p/112504092) 54. [启发式搜索](https://blog.csdn.net/Mr_SCX/article/details/104156542) 55. [【C++】匿名函数详解](https://blog.csdn.net/weixin_43717839/article/details/127673897) 56. [c++STL各个容器使用介绍(有heap)](https://blog.csdn.net/qq_48176859/article/details/123840181) 57. [2-SAT问题](https://blog.csdn.net/KaiserWilheim/article/details/125656137) 58. [二分图（概念、相关算法和题目应用）(全面整理)](https://blog.csdn.net/weixin_51797626/article/details/122129473) 59. [二分图](https://www.cnblogs.com/YLTFY1998/p/11326578.html) 60. [`bitset`知识整理+例题整理](https://blog.csdn.net/Code92007/article/details/105467263) 61. [单调栈(C/C++)](https://blog.csdn.net/m0_73096566/article/details/129232233) 62. [Bitset优化](http://oi-wiki.com/lang/csl/bitset/) 63. [关于线段树的数组到底是开2N还是4N / 线段树的两种建树方式](https://zhuanlan.zhihu.com/p/65943900?utm_id=0) 64. [random库](https://blog.csdn.net/CSDNwei/article/details/113865349) 65. [实用 STL —— rope 学习笔记](https://www.luogu.com/article/lxkd0nsa) 66. [黑科技：数组两倍空间线段树，实现方便](https://www.cnblogs.com/chy-2003/p/11815396.html) ### 其他 1. [NOI竞赛大纲（原版）.pdf](https://gitee.com/rizzohou/olympiad-in-informatics/raw/master/Documents/NOI%E7%AB%9E%E8%B5%9B%E5%A4%A7%E7%BA%B2%EF%BC%88%E5%8E%9F%E7%89%88%EF%BC%89.pdf) 2. [NOI竞赛大纲.pdf](https://gitee.com/rizzohou/olympiad-in-informatics/raw/master/Documents/NOI%E7%AB%9E%E8%B5%9B%E5%A4%A7%E7%BA%B2.pdf) 3. [NOI竞赛大纲 (IReader).pdf](https://gitee.com/rizzohou/olympiad-in-informatics/raw/master/Documents/NOI%E7%AB%9E%E8%B5%9B%E5%A4%A7%E7%BA%B2%20(IReader).pdf) 4. [【信息学奥赛一本通】题解目录](https://javaforall.cn/129962.html) 5. [值得收藏的5个C++网站](https://zhuanlan.zhihu.com/p/122471938) 6. [信息学奥赛一本通(提高篇)测试数据](https://pan.baidu.com/s/1q6PAFI9RMLq3XOAl-pPOpA) ## 代码模板 [链接](https://gitee.com/rizzohou/olympiad-in-informatics/tree/master/Reusable%20Code%20Snipppets) ## A FEW TIPS 1. `map >`第一个`>`之后要有空格；否则，则编译器可能认为是*右移*运算符 2. 负环与负回路等价 3. 树状数组只能处理下标以1开始的数组，若下标以0开始，则lowbit(0) = 0, 会陷入死循环 4. `memset(arr, 0xcf, sizeof arr)`会把数组初始化为-INF, `memset(arr, 0x3f, sizeof arr)`会把数组初始化为INF 5. `max`, `min`, `abs`等函数就在`iostream`中 6. 用递推预处理数组值时，要注意**赋初值** 7. `%`运算符处理正数时结果是非负数，处理负数时结果是非正数，用`(x % b + b) % b`处理结果一定是非负数 8. 当某一个题有多组数据，且在数据逐个输入时即可判断是否有解，不要直接把当前组的数据直接`break`掉，这样会造成**输入输出混乱** 9. 序列a\[1...n]的最小公倍数lcm(1, n) = lcm(1, n - 1) / gcd(lcm(1, n - 1), a\[n]) \* a\[n], 不满足II a\[1...n] = lcm * gcd 10. `for (char c : "ABC")`，c依次等于'A', 'B', 'C', **'\\0'**（空格） 11. stl中的vector, list, deque, set, map支持清空操作，stack, queue, priority_queue不支持，但是可以一个一个pop或用空值swap 12. `sort`自己传比较函数时，注意比较函数要用**<**、**>**号，**不能用≤或≥号** 13. 因为特定类型的数据范围有限，故**先除再乘**相较于先乘再除**不易溢出** 14. 取模运算**过程中每一步都要取模**，**以防溢出** 15. `unordered_map`与`map`**不在同一个头文件内** 16. 类的static成员变量在类定义内部用`static`声明后，还需要在类定义外部在不用`static`的条件下重新声明 17. `llu`代表`unsigned long long`，`lld`代表`long long int`, `ld`代表`long int`（和`int`没区别）,`Lf`代表`long double` 18. `memmove`在`cstring`内，`sort`在`algorithm`内 19. 即使定义了`typedef long long ll`，也不能用`sizeof ll`，应用`sizeof (long long)` 20. *Trie*的根节点为1，tot初始值为1，而非0 21. `size_t`在64位系统下是`unsigned long int`，在32位系统下为`unsigned int` 22. `rand()`和`srand()`在`cstdlib`中，`time()`在`ctime`中（通常用法为`time(NULL)`） 23. 注意**边界值** 24. 用于处理`long double`的函数都要在一般的函数名后加上`l`，e.g. `sqrtl` 25. 以下代码会输出"B" 26. `(l + r) >> 1`不会取到r，`(l + r + 1) >> 1`不会取到l 27. `x >> 1`是除2后向下取整，`x / 2`是除2后向零取整 ``` if (1) if (false) printf("A"); else printf("B"); ``` 28. `%*d`表示忽略一个数字, e.g.`scanf("%*d%d", &var)` 29. 注意swap的使用：比如，当从子结点向父亲节点进行状态转移时，如果可以的话，可以将其他子结点的状态先向其中一个状态最多/大的子结点转移，再将此子结点的状态与父节点的进行`swap` ## 思维方式 - 先要学会写暴力算法 - 尝试**不同的突破口**调整算法 - **正向思维，逆向思维**（**正难则反**） - 例如，正向计算代价时可以**反向计算贡献** - **整体思想，局部计算** - 多因素问题注意**控制变量来逐步分析** - 找到算法缺点，利用**所有题上能提供的信息**结合数据结构进行优化 - **缕清思路**后开始写代码 ## 对算法思想的理解 ### 思想 #### 单调性 ##### 单调队列优化 - 基本思想 - 要先**探究问题本身的性质** - 用**数学的技巧**在纸上进行推演 - **寻找可以变化中的不变量** - 探索**预处理**的方式 - 尽可能将**信息利用最大化** 1. 定长区间这个信息 2. 重叠区间的最值可以转移 - 适用范围：当在问题的某个范围内，序列值不变，且要不断的找**固定区间长度**的下的**最值**，可以考虑单调队列优化 - 基本操作 - 插入：从队尾插入，若会影响单调性，直到找到插入后不会破坏单调性的位置为止 - 获取最值：访问队首元素 - 与线段树和RMQ的关系：因为比线段树和RMQ**多利用了一个信息**（定长区间），故算法更快 - 时间复杂度：O(n) - 经典应用 1. 在动态规划中的应用 - 适用范围：和**定长连续子区间的最值问题**有关 - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/monotonicQueueOptimizationInDP.cpp) 2. 优化多重背包 - [多重背包问题——单调队列优化](https://blog.csdn.net/weixin_72060925/article/details/128714489) - 优化的推导思路讲得特别好 - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/monotonicQueueOptimizationForMultipleKnapsackProblems.cpp) - 注意 - 程序全局只需要用一个队列数组，需要重用时，只需重置左右指针即可（`lp = 0, rp = -1`） - 单调队列指针的初始值也不固定，主要是看该单调队列是否有初始项，若有1个初始项，则使`lp = 0, rp = 0`即可 - 还有就是判断单调队列是否“非空”的条件也不固定，如果该单调队列单调性的维护至少需要用到2个位置，则为`rp > lp`，而非`rp >= lp` - 如果某个单调队列的队头不一定是最优值时，可以仅仅维护单调性，用**（二分）查找**的方式查找最优解 ##### 二分与三分 ###### 二分 - 用于只具有一个单调性的问题求解 - [二分查找模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/binary_search.cpp) - 还有二分答案，是将一个最值问题转换为一个具有单调性的判定问题 - 还有，可以用导函数代替三分 - 整数集合上的二分 - `(l + r) >> 1`不会取到r，`(l + r + 1) >> 1`不会取到l - 实数域上的二分 - 一般需要保留k位小数时则取`eps = 1e-(k + 2)` - 还可以采用固定循环次数的方法设置精度 ###### 三分 - 用于具有**严格**单峰性的问题求解（双单调性） - [三分答案模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/trisection.cpp) - 还有三分查找（用的较少） ##### 单调栈 - 概念：单调栈顾名思义，就是栈内的元素是单调的 - 用途：给定一个序列,指定一个序列中的元素,求解该元素左侧/右侧第一个比自身小/大的元素 - 为什么能将单调性与栈结合来解决这个问题 - 栈具有FIFO的性质，如果对栈中的元素设置单调性限制，比如从顶到底为单调递增 - 那么也就是说在加入每一个元素时，之前递减的元素对我们没有价值 - 恰好，如果求解元素右侧第一个比自身大的元素，递减的元素对我们没有价值 - 那么就可以从右往左依次将所有元素都加入栈中，同时维护单调性，就可在O(n)下求解这个问题 - 其他类型的问题类似 - 同样，单调栈也可以用于求前/后缀递增/减序列 - 传统算法求后缀递增/减序列时，需要从后往前扫描，得到的序列的逆序列即为所求 - 但是用单调栈求解时，应从前往后扫描，得到的序列即为所求 - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/monotonicStack.cpp) - 详见[链接](https://blog.csdn.net/m0_73096566/article/details/129232233) #### 费用提前计算 - 基本思想：**全局思想**，**信息利用最大化** - 整体思路 - dp状态转移通常与题目上给出的处理项数（总递推次数）无关，这就丧失了一个可用信息 - 而**费用提前计算的思想充分利用了总处理项数的这个信息**，它从一个更为**全局**的角度简化了状态转移 - 即如果把最后结果的计算过程列成一个式子时，可以发现有部分**在一个或多个有规律的区间内累加，而这个规律本质上与某个解的特殊性质无关** - 那么可以在状态转移/设计时，**直接在某个区间的最开始把那部分对整个区间的贡献直接算上** - 例题：[#10184. 「一本通 5.6 例 1」任务安排 1](https://loj.ac/p/10184) #### 斜率优化 - 基本思想：**代数思想**，**线性规划**，**信息利用最大化**，**及时排除无用决策** - 主要用途：快速选择最优决策 - 整体思路 - 当得到一个不定dp转移方程时(有`max`或`min`等)，可以把`max`或`min`去掉，把转移方程看做一个方程f(i, j) = 0 - 尝试探索这个方程本身的性质，可以把与j有关的多个项（或者多个项看成一个整体）分别看做是因变量、自变量 - （因为这样在坐标系中能确定一部分元素的位置），探索状态转移（求最值）本身的几何意义 - 一般也会用到单调队列优化，直接选出最优决策 - 如果无法用单调队列直接选出最优决策，也可以用二分查找 - [用单调队列选择最优决策模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/slopeOptimizationForDP.cpp) - 时间复杂度：单次寻找最优决策O(1) - [用单调队列和二分查找选择最优决策模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/slopeOptimizationAndBinarySearchForDP.cpp) - 时间复杂度：单次寻找最优决策O(log2(n)) #### 贪心 - 特点：贪心选择（当前最佳、且对未来的决策最有利的选择），最优子结构（全局最优解包含局部最优解） - 经典应用 - 选择不相交区间问题 - 贪心选择：选择符合条件的区间中右端点最近的，**减少对未来决策的影响** - 贪心策略：按照右端点递增的顺序依次考虑 - 变式：动态选**互为子集关系**的区间 - 动态贪心策略：每次加入一个连续段，若没有相交，就直接加入。若已经加入了这个连续段的子集，那么我们一定不会加入这个连续段。如果加入了这个连续段的超集，我们直接将超集的那一段给删除，加入这一段。 - 用途：可以用`set`动态维护当前有的区间，然后逐步加入当前新产生的区间 - 区间选点问题 - 贪心选择：选每个区间的右端点 - 贪心策略：按区间右端点从小到大排序，然后依次考虑选择 - 区间覆盖问题 - 贪心选择：每次选择包含（剩余）待覆盖区间左端点且右端点最大的区间 - 贪心策略：按区间左端点从小到大排序，然后依次考虑贪心选择 - 流水作业调度问题 - 直观策略：让两台机器的空闲时间最短 - 一旦开始加工A机器就会一刻不停地工作 - 而在完成第一个任务时，B机器一定会等A机器完成 - 在完成最后一个任务时，A机器由于工作全部完成，故A机器一定会等B机器完成 - 贪心策略：*Johnson算法* - 设N1为a<\b的作业集合，N2为a>=b的作业集合，将N1按a非降序排序，N2中的作业按照b非升序排序 - 则N1接N2构成最优顺序 - 带限期和罚款的单位时间任务调度 - 贪心策略 - 把任务按w从大到小排序，依次考虑 - 安排任务时，应使该任务既在限期之内，又尽量靠后（**减少对未来决策的影响**） - 如果已排满，则放弃该任务 #### 二进制拆分 / 倍增 - 问题 - 为什么能用二进制拆分思想更好地解决某些问题？ - 因为任意的数都可以被拆分为O(logn)个二进制数位，逐个数位考虑问题的复杂度为O(log2(n) * f(n))（f(n)为考虑一次的复杂度） - 为什么必须是二进制拆分，而不能是三进制（或N进制）拆分？ - 因为2这个数字很特殊，它可以表示一个事物最基本的状态：有/无，由此可以延伸到表示任意一种状态（且满足条件的数字中2最小） - 并且，它在状态表示中的fundamental作用使其的代码实现也很简单，只需要一个`if`语句就可以等价替换 - 总结一下：①基础性作用 ②代码实现简单 - 此思想处理问题时有什么局限性？ - 该问题需要具备**无后向性**和**子问题独立性** - 即拆分的**各数位的解相互独立**，且**构成问题的整体解** - 具体内容 - 一般形式：arr\[i]\[j]表示位置i的2^j的某个属性 - 一般预处理方式：arr\[i]\[j] = arr\[arr\[i]\[j - 1]]\[j - 1]（原理：2 ^ j = 2 ^ (j - 1) + 2 ^ (j - 1)） - 如何得到位置i之后j个位置的某种属性 - 由二进制高数位到二进制低数位依次枚举，枚举O(log2(j))次，再将枚举过程中各二进制数位的属性整合后可得到 - 一般用途：逐数位试出某个数（路程，答案，etc.）的二进制排列 - 具体应用：倍增求LCA #### 空间换时间 ##### 离线 + 在线 - 含义：**离线处理数据（预处理），在线处理询问** - 备注：**主要强调离线的作用**，但是在线算法也很重要 - 如果问题完全在线处理，时间复杂度为O(f(q, n))；那么如果预处理一部分数据，时间复杂度为O(g(n) + h(q, n)) - 一般如果g(n)与h(q, n)很相似的话，实际程序运行效果较好 - 例如倍增算法可以将O(q \* n)优化成O(n * log2(n) + q \* log2(n))（基本上是 n -> log2(n) + log2(n)） - 具体应用：倍增求LCA，线段树，ST算法（RMQ问题），树状数组，KMP算法，Trie，AC自动机，字符串Hash ##### 记忆化 ##### 其他应用 - 哈希表，etc. #### 降维思想 ##### 控制变量法 - 常用于多因素问题的分析 ##### 数据降维 - e.g. 扫描线思想（将多维数据中的一维或多维当做一个整体用这些维度扫描整体数据） - [扫描线模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/scanningLine.cpp) #### 递归 - 两种类型：分治型和dfs型 ##### 分治 / 分治型递归 ##### dfs型递归 #### 随机 - 随机数据特点一：程序运行时间不会太慢 - 故可将原数据新添一个随机生成的属性，再写相应的代码来处理 - 随机数据特点二：数据碰撞、冲突的概率小 - 故可用随机值进行概率近似 - 其他应用：Treap, etc. #### 构造思想 ### 算法 #### 基本算法 ##### 搜索 ###### 深度优先搜索（*dfs*） - 对问题状态空间的深度优先遍历 - 搜索过程的基本形态：搜索树 - 不撞南墙不回头 - 可改进的地方 - 在无效解上耗时过多，时间复杂度高 - 重复搜索 - 优化途径 - 优化搜索顺序 - 可以先搜索出一个具有较好性质的搜索解 - 再按照一个合理且高效的搜索顺序搜索 - 剪枝 - 基本原则：正确性（剪枝正确），准确性（尽可能多地剪去无效枝条），高效性（提高剪枝判断本身的时间效率） - 常用技巧 - 排除等效冗余（一种类型的搜索枝条只搜索一次） - 可行性剪枝（提前判断该搜索枝条得到的解是否可行） - 最优性剪枝（与当前最优解比较） - 推导剪枝条件的技巧：放缩，etc. - 记忆化 ###### 广度优先搜索（*bfs*） - 对问题状态空间的广度优先遍历 - 一般可直接用于边权均为1的图的最短路求解，如果边权还有0，则可用*双端队列bfs* - 可改进的地方 - 太多无用状态，高内存 - 判重速度有待提高 - 优化途径 - Hash判重：Hash表的常见构造方法 - 状态压缩 - 直接取余 - 平方取中 - 乘积取整 - key \* A的结果取小数部分再乘以哈希表的大小，向下取整，i.e. floor(key * A mod 1 \* SIZE) - A最好是无理数，(sqrt(5) - 1) / 2是一个实际效果很好的数 - 双向bfs - 选择结点个数较少的那个方向先拓展 ###### 迭代加深搜索（*iddfs*） - 迭代加深搜索就是控制了搜索深度的dfs,总体来看像一个bfs - 这样将深搜和广搜结合起来，且通过剪枝灵活地控制宽度与深度， - 很好的解决了dfs时间复杂度高和bfs队列高内存的弊端，提高了搜索的效率。 - 标志性结构 ```cpp while (!dfs(maxDepth)) maxDepth++; ``` ##### 哈希表（*hashmap*） - 构造哈希函数，用链表存储哈希冲突/向后寻址 - 思想：**空间换时间** - stl: `map`（O(log2(n))，有序，红黑树）, `unordered_map`（O(1)，无序，哈希表） ##### 前缀和 & 差分 ###### 前缀和 ###### 差分 - 思想：**维护指令的累积影响** - 一维差分 - 高维差分 - 树上差分 - 详见[树上差分算法（在链接文章的后半部分）](https://www.luogu.com.cn/blog/RPdreamer/ci-fen-and-shu-shang-ci-fen) - +/-1 的形式 - 优势 - 可以统计出每个点或边被覆盖的次数 - 也能顺便求桥 - 缺点 - 实现较为复杂：需要用到LCA - 不能统计出覆盖两个点或边的非树边集是否相同 - 异或的形式 - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/differenceOnTree(XOR).cpp) - 优势 - 实现简单：只需要对覆盖的链的两个端点修改 - 也能顺便求桥 - 能统计出覆盖两个点或边的非树边集是否相同 - 详见[#NOIP004. 网络攻防](https://marsoj.xiemaedu.com/p/NOIP004?tid=6550aa857d896604f1cf919c) - 缺点 - 不能统计出每个点或边被覆盖的次数 ##### 动态规划（*DP*） - 思想：**记忆化**，**分治** - 基本思路 1. 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题 2. 经分解得到的子问题往往不是互相独立的，有些子问题被重复计算多次 3. 如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法（备忘录法） ![图解](https://gitee.com/rizzohou/olympiad-in-informatics/raw/master/Images/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E9%97%AE%E9%A2%98%E5%88%86%E8%A7%A3%E5%9B%BE%E8%A7%A3.png) - 使用动态规划来求解的问题需要具备的基本要素包括 1. 重复子问题 - 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质 - 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果 - 通常不同的子问题个数随问题的大小呈多项式增长，用动态规划算法只需要多项式时间，从而获得较高的解题效率 2. 最优子结构 - 一个问题的最优解包含着其子问题的最优解，这种性质称为最优子结构性质 - 分析问题的最优子结构性质 1. 假设由问题的最优解导出的子问题的解不是最优的 2. 设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾 - 利用问题的最优子结构性质 - 以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解 - 最优子结构是一个问题能用动态规划算法求解的前提 - 动态规划算法与分治算法的异同点 1. 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题 2. 分治算法经分解得到的子问题往往是独立的 3. 动态规划算法经分解得到的子问题往往不是独立的，有些子问题被重复计算多次 - 动态规划求解的基本步骤 1. 找出最优解的性质，并刻划其结构特征 2. 递归地定义最优值 3. **设置初始值/边界值** 4. 计算最优值 - 自底向上 - 递归 5. 根据计算最优值时得到的信息，构造最优解 ###### 区间类动态规划 - 特点：能将问题分解成两两合并的形式，一般以区间长度为阶段划分依据 - 求解：整个问题的最优值通过不断枚举合并点来得到 - 时间复杂度：一般为O(n ^ 3) - 常用技巧：变环为链, etc. - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/intervalDP.cpp) ###### 树形动态规划 - 特点：在树上进行动态规划 - 技巧：**次优解思想** - 注意：优化次优解时不光可以从之前的最优解转移，还可以从当前的遍历的非最优解转移 - 经典应用 - 树的重心 - 时间复杂度：O(n) - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/findTheCGOfATree.cpp) - 拓展：[树的重心的定义及性质](https://oi-wiki.org/graph/tree-centroid/) - 树的最长路径 / 最远点对 / 直径 - 时间复杂度：O(n) - 技巧：**次优解思想** - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/findTheLongestChainOfATree.cpp) - 其他求法：从任意点出发，dfs/bfs找最远点，再以最远点为源点找最远点（利用的树的直径的性质） - 树的中心 - 时间复杂度：O(n) - 技巧：**次优解思想** - 概念：一棵带边权的树，其中心到树中其他节点的最远距离最近 - 如何想到的 1. 先考虑定义，那么需要求以每个节点为端点的最长链长度 2. 再分类，此最长链要么过子节点，要么过父节点 3. 过子节点的好求，过父节点的需要用求直径的DP方法预处理出d1, d2，因为不能绕回来，所以还需要分别记录它们过的子节点 4. 然后从根节点到子节点更新即可 - 拓展技巧 - [二次扫描与换根法](https://www.cnblogs.com/zaza-zt/p/15269701.html) ###### 数位动态规划 - 整体思想：**逐位确定** - 一般流程 - 状态设计：f\[i]\[S]\[0/1]表示 - 填完了前i位 - 数字当前的状态为S - 前i位和动规边界的大小关系为0（小于）或1（等于）的数字个数 - 之所以要设计这个状态，是因为需要判断当前位的边界是动规边界当前位置的数字还是9 - 递推/记忆化搜索 - 时间复杂度：因为是逐位确定，故为log级别 - [递推模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/digitDP.cpp) - [记忆化搜索](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/digitDP(dfs).cpp) - 常用技巧：**区间减法** ###### 状态压缩类动态规划 - 核心思想：**状态压缩** - 利用计算机二进制表示和运算的优势，利用一个二进制数表示一种状态 - 问题特点 1. 问题规模的某一维或几维非常小 2. 具备动态规划问题的两个基本性质：最优性原理和无后向性 - 基本操作：位操作 - 时间复杂度：2^n 级别的算法，但问题规模较小 - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/stateCompressionDP.cpp) #### 字符串算法 ##### 字符串Hash - 内容 - 假设字符串S = c1c2...cm, hash(S, k) = (c1b^(k - 1) + c2b^(k - 2) + ... + ckb^0) mod h - h和b尽量互质 - 则对于任意子串S'，hash(S') = hash(S, k + n) - hash(S, k) * b^n - 复杂度：预处理O(n)，询问O(1) - 思想：**离线 + 在线** - 可改进的地方 - 可能会出现哈希冲突 - 优化 - 用孪生素数双哈希(e.g. 1e9 + 7和1e9 + 9) ##### KMP - 思想：**离线 + 在线** - 适用问题：给定一个B串和一群不同的A串，问B串是那些A串的子串 - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/kmp.cpp) - 时间复杂度：预处理O(m)，询问O(n) - 过程 - 求pattern数组（预处理） - 判断（询问） ##### Trie（字典树） - 思想：**离线 + 在线** - 适用问题：多个模式串B，一个待确认的全匹配串A，问A串是否是B串其中一个（跟**查字典**很像） - 时间复杂度：预处理O(∑m)，询问O(n) - [模版](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/Trie.cpp) - 过程：看模板就挺好懂的 - 注意 - 根节点为1，每次加入的节点编号应为`++tot + 1`，或者直接将`tot`设置为1，那么每次的编号就为`++tot` ##### AC自动机 - 思想：**离线 + 在线** - 适用问题：多个模式串B，一个待处理串A，问有多少个B在A中出现 - 本质：**在Trie树上进行KMP算法** - 时间复杂度：预处理O(∑m)，询问O(n) - [模版](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/ACTrie.cpp) - 过程 - 读入模式串，建立Trie树 - 这次需要有0号结点，将ch\[0]\[0...Z - 1] 全部设置为1（技巧①） - 预处理nxt数组 - 设nxt\[1] = 0（技巧①） - 按照bfs序遍历求nxt（代码中用到了技巧②） - 还有就是一本通第一版树上的`while (v > 0 && !ch\[v]\[i]) v = nxt\[v]`是多余的 - 因为**转移提前计算**了 - 预处理nxt数组用到的技巧 - ①运用**辅助结点** - ②**转移提前计算** #### 图论 ##### 最小生成树 - 一个图的生成树的定义：略 - 树的属性的几个难点 - 任意两点之间**只有一条简单路径** - **任意删除一条边后不连通** - 最小生成树：边劝和最小的生成树 - **最小边原则**：图中权值最小的边（如果唯一的话）一定在最小生成树上（可用反证法来证明） - **唯一性定理**：对于一个图，如果图中的边劝值都不相同，则最小生成树唯一，反之不然 - **连通块定理**：如果去掉所有权值大于w的边后，最小生成树被分割成k个连通支，则原图也被分割成k个连通块 - 切分定理：略 ###### *Prim* - 思想：**贪心** - 基本步骤：选取一个点作为基点，以此点按 **与已拓展的点集距离最短（贪心）** 的原则初步纳点 - 常用优化：用优先队列优化选点过程 - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/MSTPrim.cpp) ###### *Kruskal* - 思想：**贪心** - 基本步骤 1. 按边权值由小到大快排 2. 由小到大依次选边，使图中无环 3. 直到生成树中包含n - 1条边 - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/MSTKruskal.cpp) ##### 最短路 - 其他技巧：可以通过**分层思想**将复杂问题转换为最短路问题 ###### *Dijkstra*：单源最短路 - 前提：图中**无负权边** - 思想：与*Prim*思想类似，**贪心** - 过程：从起点v0每次都新拓展一个到源点距离最短的点，再以这个点为中间点，更新源点到其他所有点的距离 - 正确性：由于所有边劝均为正，故不会存在一个距离更短但没被拓展过的点 - 时间复杂度：O(n^2)，堆优化后降为O((n + m) * log2(m)) - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/dijkstra.cpp) ###### *Floyd*：多源最短路 - 前提：图不能有负环 - 思想：**动态规划** - 状态设计：d\[i]\[j]\[k]表示**路径中间只允许经过结点1...k的情况下，i到j的最短路距离** - 边界条件：d\[i]\[j]\[0] = map\[i]\[j] - 状态转移：**分为路径中间经过k和不经过k两种情况** - 因为**转移过程中k是递增的**，实际实现只需要用**二维数组** - 求解最小环 - 考虑算法的过程 - 当外层循环刚开始时，d\[i]\[j]保存着“经过编号不超过k-1的结点，从i到j的最短路的长度” - 因此min\{**d**\[i]\[j] + **map**\[j]\[k] + **map**\[k]\[i]}(**1 <= i < j < k**)就是满足一下两个条件的最小环长度 1. 由编号不超过k的结点组成（i.e. **最大结点为k的最小环**） 2. 经过结点k - 对于1...n范围内的k都进行上式计算，取最小值，即可得到整个图的最小环 - 在该算法中，由于我们对于每个k只考虑了编号不超过k的结点构成的最小环，没有考虑编号大于k的结点 - 由**对称性**可知，这样做不会影响结果 - 时间复杂度：O(n^3) - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/floyd.cpp) ###### *SPFA* / 队列优化的*Bellman-Ford*算法：单源最短（长）路 - 前提：图不能有负环 - 核心：**松弛操作使距离满足三角不等式** - 优化思路：**减少冗余扫描** - 如何判负环：每次对j进行松弛操作时如果松弛成功，则对j入队的次数进行检查，如果大于等于n，说明出现负环 - 代码实现需注意的问题 1. 建立**FIFO**的队列来保存待优化的结点 2. 每个结点可能会**入队、出队多次**，故： 1. 入队检查vst是否等于false，入队后vst = true 2. 出队后vst = false 3. 如果图是DAG的话，用**拓扑序**松弛，不需要重复遍历 - 时间复杂度：稀疏图O(km)，稠密图或构造的网格图退化为O(nm) - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/spfa.cpp) - 优化 - *SPFA*的深度优先实现及其优化 - [基本模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/spfaDfsOriginal.cpp) - 可改进的地方：因为不断盲目迭代而耗费了太多时间 - 优化 1. 在第一次dfs时得到一个较优解再进行完整的dfs，实际效果较好的是对每个结点只更新一条边后退出 2. 迭代加深搜索 - 经过比较发现bfs的优势主要体现在**某个点出队前可能再次被更新而得到更优的解** - 而dfs往往用一个次解进行层次很深的迭代，**一个次解会导致O(n)的更新** - 故用迭代加深搜索，两种不错的深度限制方法 1. 1, 2, 4, 8, 16... 2. 20, 30, 40, 50, 60, 70... - [初始解优化、iddfs优化后的模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/spfaIddfs.cpp) - 快速查找正负环 - 优化思路书上的很好，但太多了，在一本通P141 - 142 - 效果最好的是普通的dfs版的spfa，注意找环时d\[]应全部赋值为0 - 注意**排除冗余状态** - 其他应用：**差分约束系统**（[模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/differentialConstraintSystem.cpp)） ##### 强连通分量 - 应用 1. 缩点 - 如果将有向图中的强连通分量都缩成一个点(**缩点**)，则原图会形成一个**DAG** - 小结论：在DAG中，要使图中每个结点可以相互到达，那么需要添加的边数为min{出度，入度} - [Tarjan缩点模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/tarjanForShrinkingPoints.cpp) 2. [2-SAT问题](https://blog.csdn.net/KaiserWilheim/article/details/125656137) ###### *Kosaraju* - 基本思路：正向dfs+**反向图**反向dfs - 过程 1. 对原有图进行dfs，同时记录**访问完**（而非开始访问的顺序）的顺序 - 注意：**由于原图不一定连通，故所有点都要尝试作为起点** 2. 选择**最后访问完的节点为起点**，对**反向图**进行**dfs**，删除能够遍历到的点，这些点构成一个强联通分量 3. 如果还有顶点没有删除，继续第二步，否则算法结束 - 时间复杂度：O(n + m) - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/kosaraju.cpp) ###### *Tarjan* - 基本思路 - 因为**一个强联通分量<=>一个环或多个重叠的环** - 故**当前递归栈中的被其后的点（某个孙子）访问的最早（i.e.递归栈中满足条件的点最靠上）的点与其之后的（i.e.递归栈中它之下）的所有点构成一个强联通分量** - 过程太复杂，代码模板中有相应标注 - 时间复杂度：O(n + m) - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/tarjan.cpp) ##### 割点和桥 - 注意：以下内容的讨论范围均为**无向连通图** - 概念 - 点连通度：最小割点集合中的顶点数 - 边连通度：最小割边集合中的边数 - 点双连通、边双连通 - 割点和桥 - 当点连通度为1时，有割点 - 当边连通度为1时，有桥 - 注意 1. 一个图可能有多个割点、割边 2. 有割点的图不一定有割边 3. 两个割点之间的边不一定是割边 4. 割边的两个端点一定是割点 - 点双连通和边双连通都可以简称为双连通，但并不等价 - 双连通分量：极大双连通子图 - 点双连通分量又叫做块 - 注意 1. 边双连通分量一定是点双连通分量 2. 点双连通分量不一定是边双连通分量 ###### *Tarjan* - 判断割点 - 一个顶点u是割点，当且仅当满足以下两个条件之一 1. u为树根（i.e. tarjan最开始遍历的顶点v0），且u有多于一个子树 2. u不为树根，且存在子节点，使得dfn(u) **≤** low(v) - [判断割点模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/tarjanForFindingCutVertexes.cpp) - 判断桥 - 一条**无向边**(u, v)是桥，当且仅当其为树枝边（dfs搜索树上的边，非指向某个祖先的边i.e.后向边），且dfn(u) **<** low(v) - 注意 - 如果**有重边**，则因为每个边只遍历一次，而**每个点可能会多次遍历** - 那么需要**对遍历的边判重**：添加一个from函数参数或from数组记录 - [判断桥模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/tarjanForFindingCutEdges.cpp) - 判断双联通分量 - 基本思路：建**递归栈**，在发现割点或边后，标记并退栈（类似判断强连通分量） - 注意（具体见代码实现） 1. 求点双连通分量时，割点可划分到多个分量内（故判断分量的代码在枚举边的过程中） 2. 求边双连通分量时，需要判断**桥的端点**，**而非桥** 3. 且一个桥只可以判断出一个（或者说两个，但是实际上按照dfs序可直接搜出来一个）分量（故判断分量的代码在所有边枚举完后） - [判断点双连通分量模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/tarjanForFindingVertexDoubleConnectedComponents.cpp) - [判断边双连通分量模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/tarjanForFindingEdgeDoubleConnectedComponents.cpp) ##### 欧拉回路 - “一笔画”问题：经过每条**边**一次并仅一次 - 概念 - 欧拉回路 - 欧拉路径 - 欧拉图：存在欧拉回路 - 半欧拉图：存在欧拉路径但不存在欧拉回路 - 有向图的基图：忽略所有边的方向 - 判定 - 判断欧拉图 - 无向图G为欧拉图，当且仅当G为连通图且所有顶点的度为偶数 - 有向图G为欧拉图，当且仅当基图连通，且所有顶点的入度等于出度 - 判断半欧拉图 - 无向图G为半欧拉图，当且仅当G为连通图且除过两个顶点的度为奇数外，其他所有顶点的度为偶数 - 有向图G为半欧拉图，当且仅当基图连通，且存在顶点u的入度比出度大1，v的入度比出度小1，其他所有顶点的入度等于出度 - 辅助性质 - 将欧拉图的一个简单回路的所有边删去，新图的每一个极大连通子图都有一条欧拉回路 - 一个图的两个没有公共边、但至少有一个公共顶点的简单回路可以合并成一个新的简单回路 - 求欧拉回路 - 需要优化的地方 - 栈层数太多O(m) -> 自建栈 - 枚举找到一个点还未访问的边太慢 -> 访问完一个点后修改head数组 - 时间复杂度：O(n + m) - 过程：见模板 - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/eulerCircuit.cpp) ##### LCA - LCA：least common ancestors 最近公共祖先 - 可以用**倍增**思想来求 - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/LCA(binaryLifting).cpp) - 相关结论 - 在边权相同的树中，到达某三个节点X，Y，Z的距离之和最小的节点V - X Y Z中两两配对求LCA，得到的三个LCA其中至少两个相同 - 与其他的不相同的那个LCA即为节点V ##### 2-SAT - 2-CNF：每个子句仅包含两个文字的合取范式。例如 ( a ∨ ¬ b ) ∧ ( b ∨ c ) ∧ ( c ∨ ¬ f ) ∨ ( ¬ d ∨ e ) - 2-SAT：也叫2-CNF-SAT - 基本思想：一个命题和其反命题不能同时成立 - 在图论中，即为不在同一个强连通分量中 - 基本过程 1. 读入一组条件 a | b - 加边 反a -> b - 加边 反b -> a 2. tarjan求强连通分量 3. 判断是否存在解 - 即是否有一个命题和他的反命题处在同一个强连通分量中 4. 若存在，则构造出一组解 - 对于每一个变量，应选择拓扑序较大的变量 - e.g. 若图中有路径 true -> false, 应选择false - tarjan求出的co数组其实是逆拓扑序 - 若\[1, n]表示false, \[n + 1, 2 * n]表示true，则应用`co[i] > co[i + n]`作为i变量的解 - 详细过程：[link](https://blog.csdn.net/qaqwqaqwq/article/details/126124806) - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/2-sat.cpp) ##### 树的dfs序、欧拉序 - “序”的作用：将一个**树形结构映射到线性结构**，然后可以通过其他数据结构维护树上信息 - dfs序 - 按照dfs访问的顺序对一棵树上的节点进行编号 - 优点：每一棵子树的节点是连续的，可以方便的对一棵子树进行修改 - 备注：一般也可以等价成懒标记 - 欧拉序 - 无论是访问还是回溯，都将当前节点记录下来，形成一个长度为2n - 1的序列 - 特点：在欧拉序中 - 任意两个结点编号a, b之间的序列是a到b的一种路径 - 可能绕路，e.g. a -> c -> a -> b - 应用 - 求序列中两个结点编号之间的结点之中深度最小的结点等价于求LCA - 用O(n)的时间将原问题等价转化为RMQ问题 #### 数据结构 ##### 并查集（*Disjoint Set*） - 擅长维护的关系：具有传递性的关系，比如 - 一张无向图中节点之间的联通性 - 相等关系 - 食物链关系 - 一个数组中位置的占用情况 - 比如，可以维护从每个位置i开始向前数第一个空闲的位置，该关系具有传递性 - 例题：[145. 超市](https://www.acwing.com/problem/content/147/) - 优化方式：路径压缩和按秩和并 - 任意一个都可以优化到O(logn)，同时使用可以优化到O(a(n))，几乎为常数 - 基本模板：略 - 实现时的注意事项 - merge操作之前要注意判断它们是否已经在同一个集合 - 即使这个操作在基本的模板中用处不大,但是在更高级的形式中需要用到,这是a good programming practice - 进阶类型 - 边带权的并查集 - 例题：[238. 银河英雄传说](https://www.acwing.com/problem/content/240/) - 适用题目背景 - 在某些问题中，传递关系可能不止一种 - 并且这些关系可以互相导出 - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/disjointSetWithEdgeWeights.cpp) - 拓展域的并查集 - e.g. 维护食物链关系 - 能用拓展域的一般都能用边带权，e.g. 《算法竞赛进阶指南》的例题Party Game ##### 树状数组（*Binary Indexed Tree*） - 思想：**离线 + 在线**，**二进制拆分** - 使用范围 1. 单点修改，区间询问 2. 区间修改，单点询问（差分） - 思路 - 数组sum\[i]维护\[i - lowbit(i), i]区间信息 - 注意 - 下标不能为0（因为lowbit(0) == 0） - 初始化方法 - 简便方法 - 时间复杂度：O(nlogn) - 思路：一个一个将原始数据加入 - 高效方法 - 时间复杂度：O(n) - 这个是上限，实际上列出式子计算的话还要比这小 - 计算思路：BIT中的每个边只遍历了一次 - 思路：从小到大依次考虑每个节点x，借助lowbit运算扫描它的子结点并求和 - [一维模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/binaryIndexedTree.cpp) - [二维模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/binaryIndexedTree2D.cpp) - 树状数组与逆序对 - 经常还要用到离散化的技巧，要排序，因此实际上运行速度慢于归并排序求逆序对 - 拓展应用 - 区间增加，单点查询 - 用差分即可 - 区间增加，区间查询 - 思路 - 先用差分后的数组推一下区间查询的表达式 - 用b\[i]表示差分后的数组，设查询区间1~x的和，得到以下表达式：sum(i = 1, x, sum(j = 1, i, b\[j])) - 再**对表达式的各个变量进行分离** - 得到原式等于(x + 1) * sum(i = 1, x, b\[i]) - sum(i = 1, x, i * b\[i]) - 两个部分都可以分别用树状数组维护 - 时间复杂度：O(logn) - 与倍增结合 - 原理：树状数组的数组c\[i]恰好维护了，区间长度为2的次幂的一些信息，可以直接结合倍增来解决某些问题 - 效果：如果用二分，则一般为O(log^2(n))，若改为倍增，则为O(logn) ##### RMQ问题：ST算法 - 思想：**离线 + 在线**，**倍增** - 使用范围：区间值不变，多次询问最值（区间特征值） - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/st(RMQ).cpp) ##### 线段树 - 思想：**离线 + 在线**, **二进制拆分**, **分治** - 时间复杂度：建树O(n)，操作O(logn) - 分类 1. 单点修改，区间询问 - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/segmentTree(original).cpp) - 注意 1. 开4倍数组大小 - [关于线段树的数组到底是开2N还是4N / 线段树的两种建树方式](https://zhuanlan.zhihu.com/p/65943900?utm_id=0) 2. 区间查询时，因为直接划分原区间难以实现，故可以从整个区间搜起，遇到原区间的子集再计算贡献（**正难则反**） 3. 每次修改完要有一个push_up操作（用子节点更新父节点） 2. 区间修改，单点询问 - 对每个节点添加一个addsum，单点询问时从叶子节点加到根节点 3. 区间修改，区间询问 - 注意：如果区间修改，对一整个区间询问的话，只需要在“区间修改，单点询问”的基础上加一个push_up操作 - **延迟**标记 - 怎么想到的 - 如果在区间修改时，直接将所有子节点的sum值更新，这样的复杂度无法接受 - 因为，我们需要**额外的更新操作** - 但是，可以在**本来就要遍历子节点时，再更新标记** - 因为查询时本来就要遍历子节点，故可在此过程中标记下传 - **延迟**思想是设计算法和解决问题的一个重要思路 - 过程 - 区间更新时，修改addsum，并更新节点的sum值 - 需要用到某个节点时，再将当前节点的addsum值下传，更新两个节点的addsum与sum值 - 时间复杂度：操作O(logn) - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/segmentTree(lazyPropagation).cpp) - 标记永久化 - 怎么想到的 - 因为查询时要从上往下查询，故子节点对祖先的贡献需要提前计算 - 过程 - 不下传addsum标记，而在询问过程中计算每个遇到的节点对当前询问的影响 - 子节点的影响需要在修改操作时就计算好 - 实际上sum表示这个区间内除过此区间add值之外其他值的和 - 需要注意的是区间的add值可能有一部分在祖先节点上，这在递归时候累加即可 - 备注：这种方法局限性较大 - 对线段树维护的信息和标记的性质都有特殊要求 - 仅在二维线段树和可持久化线段树难以下传标记的情况下有所应用 - 时间复杂度：建树O(logn) - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/segmentTree(persistentDataStructure).cpp) - 其他技巧 - 对端点进行离散化 - 当区间修改时，端点一定在某一个点集之内，那么可以对该点集进行离散化，以降低空间开销 - 注意 - 离散化后，要开的空间应\*8（i.e. << 3），而不是*4 - 离散化后，区间可能会共用端点，可以用一闭一开区间解决 - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/segmentTree(discretized).cpp) - [扫描线](#扫描线) - 动态开点与线段树合并 - 动态开点 - 优点：可以降低空间复杂度 - 一段维护值域\[1, n]的动态开点的线段树在经历m次单点操作后，节点的数量规模为O(mlogn) - 背景 - 在计数问题中，线段树常用于维护值域范围（一段权值范围），这样的线段树也称为权值线段树 - 为了降低空间复杂度，我们在最开始时只建一个根节点，之后需要用到其他节点时再动态开点 - 模板：暂略，可参考《算法竞赛进阶指南》P222 - 线段树合并 - 备注：目前看到的版本是在动态开点的背景之下 - 时间复杂度：O(mlogn) - 模板：暂略，可参考《算法竞赛进阶指南》P223 ##### 扫描线 - 思想：**数据降维** - 将多维数据中的一维或多维当做一个整体用这些维度扫描整体数据 - [扫描线模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/scanningLine.cpp) ##### 分块 Chunking - 思想：**[空间换时间](#空间换时间)**, **大段维护，局部朴素**, **预处理** - 基本思路 - 通过**适当的划分** - 不一定必须是sqrt(N)块 - 在确定分多少块时，可以先设分T块 - 然后根据一定的算法，计算出预处理和所有询问总的时间复杂度 - 然后求T为多少时，取到时间复杂度的最小值 - 通常情况下，直接让预处理的时间复杂度与所有询问加起来的时间复杂度相等即可 - 可以参考《算法竞赛进阶指南》P228 - **预处理**一部分信息并保存下来 - 用**空间换取时间**，达到时空**平衡** - 比较 |数据类型|优势|劣势| |:-:|:-:|:-:| |树状数组|效率高，代码短|不易拓展，不太直观| |线段树|效率较高，拓展性好|代码较长，直观性一般| |分块|通用，直观|效率偏低，码长一般| - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/chunking.cpp) - 拓展：莫队算法 - 这是分块算法的另一种重要形式：**对“询问”进行分块** - 一种可能的针对\[l, r]的询问形式的分块方法 - 先将所有询问\[l, r]读入 - 把这些询问按照左端点排序，然后分成sqrt(N)块 - 在每个块内部再按照右端点排序 - 分析复杂度 - 这样以来，相邻两个询问的左端点变化在sqrt(N)内，右端点平均变化sqrt(N) - 如果我们**以上一次的询问的回答为基础**，那么每次只需要花费O(sqrt(N))的时间来处理多出或减出的部分 - 时间复杂度：O(Nsqrt(N)) - 例题：[251. 小Z的袜子](https://www.acwing.com/problem/content/253/) - 解析在《算法竞赛进阶指南》P230 ##### 点分治 - 基本思想：在树上对**路径**根据是否经过某个**点**进行**分治**计算 - 算法过程： 1. 选取当前连通支的**重心作为根节点** - 因为这样问题的规模在每次分治后就至少缩小一半 2. 从当前根节点出发预处理 3. 计算**过根节点的路径**对答案的贡献 4. 删除根节点，对每棵子树递归执行1~4步 - 时间复杂度 - 设每一层的所有递归过程的合计时间复杂度为O(f(n)) - 递归O(logn)层 - 总时间复杂度为O(f(n) * logn) - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/divesionBasedOnVertex.cpp) ##### 离线分治算法 - 相关概念 - 在线算法：依次处理每个操作和询问 - 离线算法：预先知道整个操作序列，再批量回答所有询问 - 静态问题：只含查询操作，或一切查询在一切修改之后 - 动态问题：非静态问题 ###### 基于时间的分治算法（CDQ分治算法） - 基于时间顺序对序列进行分治 - 基本思想：对于操作序列中的每个“查询”，计算其结果等价于**计算“初始数据”以及“之前的所有修改”对该查询造成的影响** - 基本过程 - 定义`solve(l, r)`为：对于任意在时间顺序\[l, r]内的“查询”操作k，计算1~k-1操作中的“修改”对它造成的影响 - 具体计算方法如下: 1. 设mid=(l + r) >> 1，递归计算solve(l, mid) 2. 递归计算solve(mid + 1, r) 3. 计算l~mid项操作中的所有“修改”对第mid+1~r项操作中所有“查询”造成的影响 - 效果：把一个动态问题划分为O(M)个静态问题，原始问题中的每个查询是由O(logM)个静态问题的结果共同组成的 - 这个算法能够简化问题的关键之处：该算法能够**对“时间”进行分治**，让转化后的静态问题不必考虑“修改”和“查询”的时间顺序，**使按照其他信息成为可能**，**降低了数据结构需要控制的限制条件的维度** - 时间复杂度：如果我们能够在仅与r - l有关的时间复杂度内解决`solve(l, r)`的第三部分，那么整个分治算法解决动态问题的时间复杂度就仅比解决同类静态问题乘了个O(logM) - [官方模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/CDQ(officialVersion).cpp) ###### 基于值域的整体分治算法 - 基于值域的整体分治算法 - **基于值域（答案域）**对整个操作序列进行分治 - 使操作序列在**保持时间顺序**的基础上 - 能够**同值域一起划分为独立的子问题** - 如何分析算法 - 先假设每次询问的值（属于答案域）都一样，得到一个较快的算法A - 然后再根据答案域对操作进行分治，在分治的每个独立子问题内使用A即可 - [官方模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/globalDivideAndConquerBasedOnRange.cpp) ##### 平衡树 Treap - 思想：**离线 + 在线**, **分治**, **随机** - 基本思路 - 因为普通的二叉查找树遇到有序数据时会退化成O(n)（变成一条链），而对随机数据表现较好 - 并且对于一组相同的数据，二叉查找树的形态可以有多种 - 故考虑用**随机思想**，是二叉查找树的形态趋于均衡 - 因为有多种形态，故可以对每个节点再添加一个随机的属性 - Treap中添加的是优先级，并使优先级满足小根堆的性质 - 关键操作：左旋zag，右旋zig - 时间复杂度：建树和操作都是θ(log2(n))（期望） - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/Treap.cpp) #### 数学部分 ##### 快速幂 - 是**分治**思想的一个体现 - function fastExponentiation(base, exponent): - if exponent % 2 == 0: - tmp = fastExponentiation(base, exponent / 2) - return tmp \* tmp - if exponent % 2 == 1: - tmp = fastExponentiation(base, exponent / 2) - return tmp \* tmp \* base - 时间复杂度：O(log2(n)) - [递归的模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/fastExponentiation.cpp) - [非递归模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/fastExponentiation(non-recursive).cpp) - 用到了**二进制拆分思想** ##### 质数 ###### 素数筛 - 整体思想：**考虑当前决策对未来决策的贡献** - 基本思想：质数的倍数一定不是质数 - 经典的埃氏筛法：时间复杂度O(n * log2(log2(n))) - 进阶的线性筛法 - 分析埃氏筛法可改进的地方 - 同一个数可能会被筛多次：e.g. 12 = 2 \* 2 \* 3 - 考虑改进方法 - 能否使每个合数只被自己的最小因子筛掉 - 具体实现 - 因为每个合数都可以被分解为自己的最小因子与一个小于该合数的数的乘积 - 故在筛一个数n时，可以将已经筛出的、比该数的最小因子e要小的质数x与该数n的乘积y标记，并记录该数y的最小因子为之前的那个质数x - 还要注意标记的数要在所有要筛的数的范围之内 - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/primeLinearSieve.cpp) - 想要筛出\[L, R]范围内的素数，只需要把\[2, sqrt(R) + 1]范围内的质数筛出，然后用埃氏筛筛\[L, R]即可 ###### 质因数分解 - 过程 - 扫描由小到大2 ~ sqrt(N)的每个数d（此时等价于质数） - 若d能整除N，则从N中除掉所有质因子d，若最后剩下的数不等于1，则它一定是一个质数 - 因为一个数最多只有一个大于sqrt(N)的质因子 - 时间复杂度：O(sqrt(n)) - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/primeFactorization.cpp) ##### 约数 ###### 求N的正约数集合——试除法 - 时间复杂度：O(sqrt(n)) - 推论：一个整数的约数个数上界为2 * sqrt(N) - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/findThePositiveDivisorsOfN(%E8%AF%95%E9%99%A4%E6%B3%95).cpp) ###### 求1 ~ N每个数的正约数集合——倍数法 - 时间复杂度：O(n * log2(N)) - 推论：1 ~ N每个数的约数个数的总和大约为N * log2(N) - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/findThePositiveDivisorsOfN(%E5%80%8D%E6%95%B0%E6%B3%95).cpp) ###### 最大公约数与最小公倍数 - 性质 - a * b = gcd(a, b) \* lcm(a, b) - 其他见一本通P382 - 最小公倍数求法 - 一般求法：欧几里得算法 - 时间复杂度：O(log2(a + b)) - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/gcd.cpp) - 高精求法：二进制算法 - 原因：因为高精度除法（取模）不易实现，需要高精度运算时，可以考虑二进制算法 - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/gcd(BigInteger).cpp) ##### 同余问题 - 基本定义和定理、同余的性质：见一本通P393 ###### 拓展欧几里得算法 - 时间复杂度：O(log2(a + b)) - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/extendedGCD.cpp) - 应用：求解不定方程 ax + by = c - 见一本通P394 ###### 线性同余方程 - 求法：拓展欧几里得 - 见一本通P396 - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/linearCongruenceEquation.cpp) ###### 乘法逆元 - 求法：费马小定理，欧拉定理，拓展欧几里得 - 用途：化简分式同余式 - 详见一本通P397 ###### 中国剩余定理 - 核心思想：**构造思想** - 用途：求解模数互质的线性同余方程组 - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/chineseRemaiderTheorem.cpp) - 详见一本通P399 ###### 拓展欧几里得解同余方程组 - 核心思想：**数学归纳法** - 用途：求解一般的线性同余方程组 - 详见一本通P402 ###### 高次同余方程 - 核心思想：**分块**，**BSGS** - [模板](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/solveHigherOrderCongruenceEquation.cpp) - 详见一本通P403 ##### 矩阵乘法 - 详见一本通P411，这里只作理解上的补充 - k阶常系数线性递推关系 - 矩阵、方阵、和单位矩阵 - 单位矩阵在矩阵乘法中起着特殊的作用，如同数的乘法中的1，通常用In或En表示n阶单位矩阵 - 矩阵加减法 - 矩阵乘法 - 满足结合律、不满足交换律 - 方阵乘幂 - 可以用快速幂的思想来求方阵乘幂 - 应用 1. 很容易将有用的状态存在一个矩阵中 2. 通过状态矩阵与转移矩阵相乘可以快速得到一次DP的值 - 这个状态转移方程必须要是一次的递推式 3. 求矩阵相乘可以先用快速幂算后面转移矩阵，再用初始矩阵乘上后面的转移矩阵得到结果 - 时间复杂度：O(log2(n)) ##### 容斥原理 - 用途：多个集合求并集大小 - 表述 - 符号+ - + -循环 - 求交集的集合个数从1到n递增 #### 经典问题 ##### 均分纸牌 - 算法：***贪心*** - 具体过程 - 从左到右一次考虑每个人 - 计算当前人的纸牌数ci与最终均分的目标纸牌数t之间的差的绝对值d，将d加或减到下一个人的纸牌数上 - 因为有平均值，可以考虑将每个人的纸牌数减去平均值，且此操作不影响最终结果 - 记减去平均值的纸牌数的前缀和为si，则结果就是对si的绝对值求和 ##### 货舱选址 - 选中间位置（中位数） - 如何想到的：可以从一个次优解左右移动得出最优解 #### 其他技巧 ##### 离散化 - 内容：离散化是一种将连续数据映射到离散值的过程，它通常应用于与区间查询有关的问题的优化 - 具体过程 - 在离散化过程中，我们将一组实数转换为一组整数，使得原始数据的**顺序和区间关系得以保留**。 - 具体地说，我们将原始数据排序，然后为每个不同的值分配一个整数。 - 这个整数是该值**在排序后出现的位置**，即离散化后的数值。 - [详细解读](https://blog.csdn.net/qq947467490/article/details/130590278) - [模版](https://gitee.com/rizzohou/olympiad-in-informatics/blob/master/Reusable%20Code%20Snipppets/discretize.cpp) ##### `bitset`优化 - 复杂度：O(n / w)，w为计算机位数（32 / 64） - 详见[链接](http://oi-wiki.com/lang/csl/bitset/) ## 其他总结 ### 图论 #### 判环的技巧 - 如果图中所有点的出度都不为0，则图中一定有环，且每个点都在环上 - 并查集 - 拓扑排序：遍历到的点的数量如果小于总点数，则一定有环（因为在环上的点的入度不可能变成0） - dfs_spfa ### 数论 #### 比较好用的几个质数 - 1e4 + 7 - 1e4 + 9 - 9e4 + 1 - 9e4 + 7 - 9e4 + 11 - 1e5 + 3 - 1e5 + 19 - 1e6 + 3 - 1e6 + 33 - 1e9 + 7 - 1e9 + 9 ### 调试代码 - 添加输出语句 - dbg debug - 对拍 - 自动数据生成器 ### 测试总结 #### CSP-S2023 1. 做题策略 - **每道题**一定要**有分** - 先通读一遍题，安排好写题顺序 - 安排写题顺序**首要原则是确定能拿的分数大小** - **次要原则是思路难易** 2. 针对各题 1. 密码锁 - 这道题放的水有点多，作为CSP-S的T1未免太过简单，这道题做的较快，但打乱了后面的做题节奏 - 用时：30min - 分数：100 - 启示：考场上要保持自己做题的心态 2. 消消乐 - 这道题刚看到时的思路是区间动规，只能拿部分分，考场上直接去做下一题了，下一题做的时间过长，中途返回来把区间动规写了 - 用时：40min - 分数：35左右 - 启示：考场上应该以**得分为主**，先把区间动规写了，说不定在考试过程中就会涌现出一些优化方法 3. 结构体 - 考场上 - 这道题刚看到时有点轻敌了，觉得是大模拟，写的过程中才发现很复杂，最后还差一点没有完成，但是一分没有 - 这道题在考场上**没注意到有提示**，在考场上写了两个小时还差一个操作 - 下考场之后，按照提示的思路用了大约1h30min编写完后AC - 用时：1h30min以上 - 分数：0 - 启示 1. 一定要注意**题目最后有没有提示** 2. 考场上要**把一定能拿到的、且容易拿到的分拿到** 4. 种树 - 这道题最后就没有动 - 用时：0 - 分数：0 #### NOIp 2023 1. 词典 - 这道题数据放水有点多，实际数据可以出到1e6，可是只出到了3e3，有的较为暴力的思路也能拿到满分 - 我刚开始想到了一个O(n logn)的思路，需要用到排序，但是，想要用`sort`和自定义的cmp排序，cmp的性质一定要好 - 否则，会出现排完序后，序列不符合cmp的情况