线段树+lazy标记 线段树基于分治思想的二叉树,用于区间信息统计特点: 每个节点代表区间 唯一根节点,也就是全部区间 叶节点是长度为1的子区间,也就是所代表数组上的一个点 存线段树的结构体数组长度一般是 线段树所代表数组长度的4倍.12345const int maxn = 1e3;struct segmentTree { int l,r; int dat;} e[4 * 2019-07-17 算法
HDU_1875_prim HDU 1875 一开始把不符合条件的边删掉 判断是否能 生成最小生成树1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include <ios 2019-07-17 算法 prim
次小生成树原理+模板 原理: 枚举每一条不在最小生成树上的边作为最小生成树上的边,那么形成了一个环,将环上的最长的路(除了枚举的这一条边)去掉,更新这颗次小生成树的权值和, 最后与最小生成树的权值和比较.相同则说命存在. 其实如果次小生成树存在.在最小生成树中肯定存在一条边与图中不在最小生成树的边的权值相同. 通过枚举点来枚举每一条不在最小生成树上的边 pre[maxn]:记录每个点的上一个点 maxdis 2019-07-16 算法 次小生成树
POJ_3026_BFS+prim+建图 POJ 3026 题意:求出图中连接S和A在图中的最短距离。 样例的意思是S出发步数为0. 难点： 在读入时用map<pair<int,int>,int>将坐标上的每一个点按顺序从1离散出来. 通过bfs建图.一开始我以为单点bfs,后来才用多点bfs建图.能使所有点之间边都存在 prim求最短路. 题目数据读入有空格,也要读(首先就写读入数据)123456789 2019-07-16 算法 BFS+prim
POJ_1258_prim POJ 1258 水题,prim板子123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include <iostream>#include <string.h>#define INF 0x3f3f3f3fusing namespace std; 2019-07-16 算法 prim
POJ_1751_建图+kruskal POJ 1751 已经建好的边先用并查集指向在一起,然后kruskal 由于是特判,边的输出顺序无关1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include <i 2019-07-16 算法 kruskal
POJ_2349_建图+kruskal POJ 2349 题意:一个卫星频道等同于2个点之间可以任意通信, 处理点之后,建图,跑kruskal,然后将最短路的最大边都用卫星频道替代, 所以最大的D是最小生成树里面除掉卫星通信边之后的最大边12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535 2019-07-16 算法 kruskal
POJ_1789_建图+prime POj 1789 重点在建图,每个字符串是一个顶点,权值是字符串每个位置字符不同的个数, 每两个字符串之间的边权值相同,方向相反,所以不需要完全2层循环建图.12345for (int i=1; i<=n; i++) for (int j=i; j<=n; j++) { a[i][j] = a[j][i] = countnum(ch[i],ch[j]);// 2019-07-16 算法 prime
POJ_2421_kruskal POJ 2421 思路:最小生成树中有的边已经被选取,那么先标记加入到并查集中就行了, 然后继续求最小生成树123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include <iostream>#include < 2019-07-16 算法
shell_条件判断 sort -n:按数字排序,默认是按照字符串排序. -r:reverse反排序 -k a,b:排序的范围,第a到b列 -t ":":修改分隔符，例如:cp /etc/passwd /tmp/shsort -n -k 3,4 -t ":" student | awk 'BEGIN{FS=":"} 2019-07-15 Linux学习 shell