Terminus

原题链接 g[i][j] 用于快速判断 Si∼SjS_i \sim S_jSi​∼Sj​ 是不是回文串。 f[i] 表示前 i 个字符的分割方案数中的最小值。由于终点 i 固定，可以将分割方案划分成分割后字符串 S 最后一段为 1 ~ i、2 ~ i 一直到 i ~ i 这些类。所有方案取最小值就是 f[i] 的值。 1234567891011121314151617181920212223242526class Solution {public: int minCut(string s) { int n = s.size(); s = ' ' + s; vector<vector<bool>> g(n + 1, vector<bool>(n + 1, false)); vector<int> f(n + 1, 1e8); for(int j=1;j<=n;j++) { for(int ...

DP 问题分析方法 背包问题 给一些物品，每件物品的体积是 viv_ivi​，价值是 wiw_iwi​，有一个背包，体积是 V，问背包可以装下的物品的最大价值是多少？ 01 背包 每件物品最多只能用一次 状态转移方程： f(i,j)=max(f(i−1,j),f(i−1,j−vi)+wi)f(i,j) = max(f(i-1, j), f(i-1, j-v_i) + w_i)f(i,j)=max(f(i−1,j),f(i−1,j−vi​)+wi​) f(i,j)f(i, j)f(i,j) 表示在前 i 个物品中选择，且总体积不大于 j 的所有选法中的价值最大值。 01 背包问题 12345678910111213141516171819202122#include <iostream>using namespace std;const int N = 1010;int n, m;int w[N], v[N];int f[N][N];int main() { cin >> n >> m; for(int i=1;i< ...

容斥原理 可在离散数学（左孝凌）课本 p97 找到容斥原理的证明。容斥原理又叫包含排斥原理。 有三个集合时的公式如下： ∣S1∪S2∪S2∣=∣S1∣+∣S2∣+∣S3∣−∣S1∩S2∣−∣S1∩S3∣−∣S2∩S3∣+∣S1∩S2∩S3∣|S_1 \cup S_2 \cup S_2| = |S_1|+|S_2|+|S_3|-|S_1 \cap S_2|-|S_1 \cap S_3|-|S_2 \cap S_3|+|S_1 \cap S_2 \cap S_3|∣S1​∪S2​∪S2​∣=∣S1​∣+∣S2​∣+∣S3​∣−∣S1​∩S2​∣−∣S1​∩S3​∣−∣S2​∩S3​∣+∣S1​∩S2​∩S3​∣ 组合恒等式：Cn0+Cn1+Cn2+⋯+Cnn=2nC_n^0 + C_n^1 + C_n^2 + \dotsb + C_n^n = 2^nCn0​+Cn1​+Cn2​+⋯+Cnn​=2n 容斥原理公式中一共有 2n−12^n - 12n−1 项，所以使用容斥原理计算一组集合的并集中元素个数的时间复杂度为 O(2n)O(2^{n})O(2n)，n 为集合数量。 能被整除的数 枚 ...

高斯消元 可以在 O(n3)O(n^3)O(n3) 时间复杂度内 n 个未知数的求解多元线性方程组。 枚举每一列 找到绝对值最大的一行 将这行换到最上面 将该行第 1 个数变成 1 将下面所有行的当前列消成 0 将系数矩阵化成阶梯型，有三种情况 完美阶梯型，有唯一解 0 = 非零，无解 0 = 0，有无穷多个解 高斯消元解线性方程组 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include <iostream>#include <algorithm>#include <cmath>using namespace std;const int N = 110;const double eps = 1e-6;int n;double a[N][N];int gauss() { int c, r; // 枚举每一列 ...

原题链接 如果直接使用双指针，没有单调性，可以尝试先将原问题分成几个子集，子问题有单调性可以使用双指针。 12345678910111213141516171819202122232425262728293031class Solution {public: int K; unordered_map<char, int> cnt; void add(char c, int& x, int& y) { if(!cnt[c]) x++; cnt[c]++; if(cnt[c] == K) y++; } void del(char c, int& x, int& y) { if(cnt[c] == K) y--; cnt[c]--; if(!cnt[c]) x--; } int longestSubstring(string s, int _k) { ...

原题链接 模拟法做本题非常直观，这里给出一种只需一次遍历就能完成的方法。 在双指针的过程中，如果 i 和 j 指向的元素相同，那么翻转后也相同，只需要进行取反操作。如果 i 和 j 指向的元素不同，那么翻转再取反后就和当前状态一样，所以不用动。如果矩阵列数为奇数，中央元素需要取反一次。 12345678910111213141516171819class Solution {public: vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) { int n = A.size(); for(int i=0;i<n;i++) { int j=0, k = n-1; while(j<k) { if(A[i][j] == A[i][k]) { A[i][j] ^ ...

滑动窗口的题目有一个套路，可以通过在上一个窗口中维护的值计算出当前窗口中的值。一般需要用到累加和还有错位相减来推出递推公式。 本题中，记 fi=∑j=i−X+1ici⋅gif_i = \sum_{j=i-X+1}^{i} c_i \cdot g_ifi​=∑j=i−X+1i​ci​⋅gi​。其中 fif_ifi​ 表示当前窗口能够增加多少满意的顾客，cic_ici​ 表示第 i 分钟店内的顾客数，gig_igi​ 表示第 i 分钟老板是否生气。相乘的含义是如果老板在 i 分钟生气但忍住，就能增加 cic_ici​ 个顾客满意度。 那么 fi−1=∑j=i−Xi−1ci−1⋅gi−1f_{i-1} = \sum_{j=i-X}^{i-1} c_{i-1} \cdot g_{i-1}fi−1​=∑j=i−Xi−1​ci−1​⋅gi−1​ fi−fi−1=ci⋅gi−ci−X⋅gi−Xf_i - f_{i-1} = c_i \cdot g_i - c_{i-X} \cdot g_{i-X}fi​−fi−1​=ci​⋅gi​−ci−X​⋅gi−X​ fi=fi−1+ci⋅gi−ci−X⋅gi− ...

数论 质数 从 2 开始的整数定义的，小于等于 1 的数既不是质数也不是合数。 在大于 1 的整数中，如果只包含 1 和这个数本身两个约数，就被称为质数或者叫素数。 质数的判定 试除法 如果 d∣nd|nd∣n，那么 nd∣n\frac{ n }{ d }|ndn​∣n，只枚举每对约数中些较小那个的数，令 d≤ndd \le \frac{ n }{ d }d≤dn​，解得 d≤nd \le \sqrt{n}d≤n​。 从 2 一直枚举到 n\sqrt{n}n​，时间复杂度：O(n)O(\sqrt{n})O(n​) 12345678910bool is_prime(int n) { if(n<2) return false; // 为防止溢出建议写 i<=n/i for(int i=2;i<=n/i;i++) { if(n%i==0) { return false; } } return true;} 试除法判定质数 123456789101112131415161718 ...

最小生成树 最小生成树对应的图一般都是无向图 Prim 算法 朴素版 Prim 算法 时间复杂度：O(n2)O(n^{2})O(n2) 适合稠密图 Prim 算法求最小生成树 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include <iostream>#include <cstring>using namespace std;const int N = 510, INF = 0x3f3f3f3f;int g[N][N];// d[i] 表示节点 i 到生成树的最短距离int d[N];bool st[N];int n, m;int prim() { memset(d, 0x3f, sizeof d); int res = 0; // 有 n 个节点，循环 n 次 for(int i=0;i<n;i++) { int t = -1; // 找到不 ...

最短路 难点在建图，如何把问题抽象成一个图，转化成最短路问题。 单源最短路 所有边权都是正数 朴素 Dijkstra 算法 n 为节点数。 时间复杂度：O(n2)O(n^{2})O(n2) 适合稠密图。即 m 与 n2n^{2}n2 是一个级别的，图中边比较多。 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include <iostream>#include <cstring>using namespace std;const int N = 510;int g[N][N];int d[N];bool st[N];int n, m;int dijkstra() { d[1] = 0; // 有 n 个节点，一共需要做 n 次 for(int i=0;i<n;i++) { // 寻找未访问过的节点中，距离源点最近的点，t 存储的是找到的节点 int t = -1; for(int j=1 ...