- ACM Note No.12: DijkstraACM-ICPC
Dijkstra 算法可用于求解非负权图上的单源最短路径，在非负权图上对单个点跑一遍 Dijkstra 就可以知道该点到其他所有点的最短路径 Dijkstra 算法的核心思想是贪心： 如果 A -> C 的路程为 A -…
- ACM Note No.10: DSUACM-ICPC
并查集（DSU， Disjoint Set Union），顾名思义是一种能高效合并两个集合并查询某个数属于哪一个集合的数据结构，在处理连通分量（连通块）问题方面应用十分广泛 并查集实现的为一个森林，其核心思想有二： 将每…
- ACM Note No.13: FloydACM-ICPC
Floyd 算法可用于求解非负权图上的多源最短路径，在非负权图跑一遍 Floyd 就可以知道该所有点到其他所有点的最短路径 Floyd 算法的核心思想是动态规划： i节点到j节点的最短路径取决于 [i节点经过k节点到达j…
- ACM Note No.9: GraphACM-ICPC
图的存储方式有主要的两种：邻接表与邻接矩阵 邻接表：使用vector<vector<node>>存储，存储节点i的所有出边和权值 邻接矩阵：使用二维数组存储，mp[i][j] = w表示节点i到j有一条权值为w的边 给定…
- ACM Note No.11: MSTACM-ICPC
最小生成树（Minimum Spanning Tree，MST），是一个有权图删除若干边能得到的边权和最小的树 常见的求最小生成树的算法有 Prim 算法 和 Kruskal 算法 从小到大加入边，直到所有的点连通 由于…
- ACM Note No.6: DFSACM-ICPC
深度优先搜索（DFS）常常用于解决图的连通性问题，暴力枚举问题等等 DFS常常用递归实现： 从1∼n 这 n个整数中随机选出 m个，输出所有可能的选择方案。 #include <bits/stdc++.h> using…
- ACM Note No.8: ManacherACM-ICPC
马拉车算法可以用于解决最长回文子串的问题 当然也可以通过对下文的回文半径数组P求和，以获得回文子串的总数 #include <bits/stdc++.h> using namespace std; string manacher…
- ACM Note No.7: 数论ACM-ICPC
根据十进制的运算性质很容易能写出将十进制转换为数组倒序存储的方法 const int N = 1e4; int s[N + 10]; int toDex(int num){ int digit = 0; while (num…
