Day24h

分类

2019 Multi-University Training(2) 2019牛客暑期多校训练营(1) CF(37) Record My Feelings(5) 动态规划(23) 图论(4) 字符串(3) 数学(20) 数据结构(8) 未归档(5) 模板(23)

/ 注册

全部文章（共131篇）

Roadblocks

Roadblocks 该题的难点在于求次短路，而次短路的求法与最短路基本一致，更新的方式就是当当前权重比最短路大且比次短路小的时候就更新它，如果它比最短路小，那么就把它和最短路交换一下关键代码： //d1[i]是从起点到达i的当前最短路 //d2[i]是从起点到达i的当前次短路 i...

次短路

2020-01-18

0 558

路径还原

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

2020-01-18

0 451

string的插入和删除

string的插入和删除参考：string插入和删除插入（字符串和字符）： string& insert(int pos, const char* s); //插入字符串 string& insert(int pos, const string& s...

字符串

2020-01-18

0 496

string中find()和substr()的用法

string中find()和substr()的用法查找从指定位置开始的 string s="123453"; cout<<s.find('3')<<endl; cout<<s.find('3',2); 输出： 2 2 当找不到的时候，...

字符串

2020-01-17

0 613

Bellman-Ford

Bellman-Ford BF算法求的是单源最短路问题，即每一个点到起点s的最短距离。算法的思想在于\(d[i]=min(d[i],d[j]+e(j,i))\) d[i]表示点i到s的最短距离，对d[i]不断进行更新，知道不能更新为止，复杂度为\(O(nm)\) 代码： const in...

Bellman-Ford 最短路

2020-01-17

0 452

Elections

C. Elections 证明自己赢的时候获得的票数与贿赂所需的最小代价的函数是一个凸函数：从自己赢的票数等于 n 的时候往小推，每一次减去一个最大的代价，但是要保证在该情况下能赢刚开始是单调递增的，但是随着自己的票数越来越少以及某些人的票数越来越多，我们想要自己赢的票数再少一点，那...

三分

2020-01-17

0 508

食物链

食物链因为不知道要输入的 x ，是属于A，B，C，哪个位置上的，所以把空间开了三倍，每一种状态都保存一下如果 x 与 y 同类，那么judge(x,y)为true。如果 x 吃 y 那么，judge(x,y+n)为true 这个题卡的点在于，poj会卡cin，所以应...

并查集

2020-01-15

0 515

next_permutation(begin,end)

next_permutation(begin,end) 当排列还存在下一种（以字典序排列）排法时，返回true，否则返回false 返回true的同时，把数组变成字典序中的下一种排法。测试代码： // Created by CAD on 2020/1/15. #include <bi...

排列

2020-01-15

0 430

并查集（防退化）

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

并查集

2020-01-15

0 376

Two Arrays

C. Two Arrays \(dp[i][j]\)表示有\(j\)个数每个数的范围为\(1～i\)时的非递减排列种数，因为 n 和 m 的数据范围也不大，用记忆化搜索很快可以得出每一个值。再来看满足条件时的\((a,b)\)，\(a\)为非递减序列，\(b\)为非递增序列，所以\(b...

记忆化搜索容斥原理 dp

2020-01-15

0 431