路径还原 例如在求解最短路等等问题时，只需用一个pre[]数组在更新我们要求的数据时，记录一下前驱顶点即可

string的插入和删除 参考：string插入和删除 插入（字符串和字符）： string& insert(int pos, const char* s); //插入字符串 string& insert(int pos, const string& str); //插入字符串 string& insert(int pos, int n, char c); //在指定位置插入n个字符c string s="12345"; s.insert(2,"000"); cout<...

string中find()和substr()的用法 查找从指定位置开始的 string s="123453"; cout<<s.find('3')<<endl; cout<<s.find('3',2); 输出： 2 2 当找不到的时候，函数会返回一个s.npos 找第一个目标字符串的位置和最后一个的位置（不是全匹配）： string s="123453"; cout<<s.find_first_of("34")<<endl; cout<<s.find_...

Bellman-Ford BF算法求的是单源最短路问题，即每一个点到起点s的最短距离。 算法的思想在于\(d[i]=min(d[i],d[j]+e(j,i))\) d[i]表示点i到s的最短距离，对d[i]不断进行更新，知道不能更新为止，复杂度为\(O(nm)\) 代码： const int maxn=1e5; struct edge{ int u,v,w; }e[maxn]; int d[maxn];//每个点到s的最短距离 int n,m; void BF(int s) { for(int i=1;i<=n;++i) d[i]=inf; d[s]=0...

C. Elections 证明自己赢的时候获得的票数与贿赂所需的最小代价的函数是一个凸函数： 从自己赢的票数等于 n 的时候往小推，每一次减去一个最大的代价，但是要保证在该情况下能赢 刚开始是单调递增的，但是随着自己的票数越来越少以及某些人的票数越来越多，我们想要自己赢的票数再少一点，那么就应该从票数多的人手上拿票（a）回来，再把自己手上的票（b）（要发给少的人）发出去，因为 a 比 b 先出来，所以 a>b ，所以这个时候自己需要付的钱开始增多了。 因此得证，这是一个凸函数。 代码： // Created by CAD on 2020/1/13. #includ...

食物链 因为不知道要输入的 x ，是属于A，B，C，哪个位置上的，所以把空间开了三倍，每一种状态都保存一下 如果 x 与 y 同类，那么judge(x,y)为true。 如果 x 吃 y 那么，judge(x,y+n)为true 这个题卡的点在于，poj会卡cin，所以应该用scanf()进行读入 代码： // Created by CAD on 2020/1/15. #include <cstdio> using namespace std; const int maxn=5e4+5; int f[3*maxn]; inline int fi...

next_permutation(begin,end) 当排列还存在下一种（以字典序排列）排法时，返回true，否则返回false 返回true的同时，把数组变成字典序中的下一种排法。 测试代码： // Created by CAD on 2020/1/15. #include <bits/stdc++.h> #include <ext/rope> using namespace std; int main() { int a[4]={1,2,3}; do{ for(int i=0;i<=2;++i) ...

并查集（防退化） 防退化的关键操作在于，记录每一个点的高度，合并的时候，将高度较小的点并到高度较大的点上去。 同时还有一个优化技巧就是路径压缩，它会改变树的高度，但是为了方便起见，也不修改 high 的值 合并操作： x=find(x),y=find(y); if(x!=y) { if(high[x]<high[y]) f[x]=y; else{ f[y]=x; if(high[x]==high[y]) high[x]++; } }

C. Two Arrays \(dp[i][j]\)表示有\(j\)个数每个数的范围为\(1～i\)时的非递减排列种数，因为 n 和 m 的数据范围也不大，用记忆化搜索很快可以得出每一个值。 再来看满足条件时的\((a,b)\)，\(a\)为非递减序列，\(b\)为非递增序列，所以\(b\)的最后一个数大于等于\(a\)的最后一个数是充要条件，因此我们只需要遍历\(a\)最后一个数即可得出答案，例如当\(a\)的最后一个数为3的时候，这部分的答案就应该是\((dp[3][m]-dp[2][m])*dp[n-3+1]\)，括号里是\(a\)的种数（利用容斥原理），括号外是\(b\)，...

取整 共包括三个函数，都在<math.h>头文件下 向下取整 floor() 向上取整 ceil() 四舍五入 round() 这些函数很显然只对小数有用，而当要运算两个整型数之间的除法时，要乘一个 1.0，以此来进行浮点数运算。

背包问题 当范围很小的背包问题是很容易解决的，而当范围很大\((例如：1\le n\le 100,1\le w_i\le10^7,1\le v_i\le 100,1\le W\le 10^9)\)时，就应该换一种 dp 的表示方式，这样才能够降低其复杂度。 \(dp[i+1][j]\)表示前 i 个物品中挑选出价值总和为 j 时总重量的最小值 \(\begin{cases}dp[0][0]=0\\dp[0][j]=INF\\dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i]) \end{cases}\) 代码： fill(dp[...

完全背包问题 \(\begin{cases}dp[0][j]=0\\dp[i+1][j]=max(dp[i][j-k*w[i]]+k*v[i]) \end{cases}\) 代码： int n,W; cin >> n >> W; for(int i=0;i<n;++i) for(int j=0;j<=W;++j) for(int k=0;k*w[i]<=j;++k) dp[i+1][j]=max(dp[i+1][j],dp[i][j-k*w[i]]+k*v[i]); int ans=...

最长公共子序列 注：子序列是可以不连续的。 递推公式： \(dp[i+1][j+1]=\begin{cases}dp[i][j]+1&(s_{i+1}=t_{j+1})\\max(dp[i][j+1],dp[i+1][j])&(其 他)\end{cases}\) 代码： // Created by CAD on 2020/1/14. #include <bits/stdc++.h> using namespace std; const int maxn=1e3+5; int dp[maxn][maxn]; int main() { ...

C. Petya and Exam 重要的事情说三遍！认真读题！认真读题！认真读题！ 思维要开阔一点，不要被局限住了。 因为 t 很大，所以我们不能遍历 t，但是 n 只有1e5，所以我们可以遍历每道题的截止时间。然后在其多余的时间内尽可能多的做后面还没有做过的简单题，做完了再做难题。 对于这组数据的解释是： input： 6 17 2 6 0 0 1 0 0 1 7 6 3 7 10 12 output： 1 在前面两分钟内写出两道简单题之后马上离开考场即可，不必做到截止时间最早的那道题。 代码： // Created by CAD o...