已注销

ACM模版篇

C++(4) CONTESTS(31) dfs && bfs(59) GitHub(1) Linux(4) OpenGL(2) PHP(5) Python(7) QT(3) Script(4) STL(24) 位运算(3) 其他(37) 动态规划(148) 区间(22) 图形打印(6) 图论(96) 字符串(39) 打表(13) 排序(31) 数学相关(153) 数据结构(73) 数论(101) 暴力解题(31) 机器学习(10) 栈(14) 树(51) 每周都有那么几天不想学习(2) 汇编(6) 知识点总结(17) 笔试试题(15) 网络流(7) 职场老油条(1) 计算几何(17) 贪心(62) 逐梦者(97) 郑州-大连(2) 问题残余(4) 骑行也是追梦(1)

/ 注册

全部文章 / ACM模版篇（共139篇）

最小覆盖问题

ACM模版最小路径覆盖最小路径覆盖O(n^3)路径覆盖:就是在图中找一些路经,使之覆盖了图中的所有顶点,且任何一个顶点有且只有一条路径与之关联。最小路径覆盖:就是找出最少的路径条数,使之成为P的一个路径覆盖。路径覆盖与二分图匹配的关系:最小路径覆盖=|P|-最大匹配数;其中最大匹配数...

2021-05-22

0 647

星期问题

ACM模版星期问题基姆拉尔森公式： W = (D + 2 * M + 3 * (M + 1) \ 5 + Y + Y \ 4 - Y \ 100 + Y \ 400) Mod 7 基姆拉尔森公式的计算结果是0，1，2，3，4，5，6 七种可能；结果的对应关系： 0：星期一...

2021-05-22

0 530

所有数位相加

ACM模版所有数位相加 /* * 所有数位相加 * dig(x) := x if 0 <= x <= 9 * dig(x) := dig(sum of digits of x) if x >= 10 */ 模...

2021-05-22

0 441

二分查找

ACM模版查找v /* * 在[l, h)范围内查找值v,返回下标 * 假设a数组已经按从小到大排序 * 失败返回-1 */ int bs(int a[], int l, int h, int v) { int m; while (l < h) { ...

2021-05-22

0 360

树状数组

ACM模版一维 /* * INIT: ar[]置为0; * CALL: add(i, v): 将i点的值加v; sum(i): 求[1, i]的和; */ #define typev int // type of res const int N = 1010; typev ar[N]; ...

2021-05-22

0 605

逆序数

ACM模版归并排序求逆序数 /* * 也可以用树状数组做 * a[0...n-1] cnt=0; call: MergeSort(0, n) */ const int N = 1010; int a[N]; int c[N]; int cnt = 0; void MergeSort...

2021-05-22

0 392

并查集

ACM模版并查集 /* * INIT: makeset(n); * CALL: findset(x); unin(x, y); */ const int N = 1010; struct lset { int p[N], rank[N], sz; void link(int ...

2021-05-22

0 354

快排

ACM模版快排 void ksort(int l, int h, int a[]) { if (h < l + 2) { return ; } int e = h, p = l; while (l < h) { ...

2021-05-22

0 325

机器工作调度

ACM模版机器工作调度 2台机器,n件任务,必须先在S1上做,再在S2上做. 任务之间先做后做任意.求最早的完工时间. 这是一个经典问题: 2台机器的情况下有多项式算法(Johnson算法),3台或以上的机器是NP-hard算法。 Johnson算法: (1)把作业按工序加工时间分成两...

2021-05-22

0 294

大数运算

ACM模版普通大数运算 const int MAXSIZE = 200; void Add(char *str1, char *str2, char *str3); void Minus(char *str1, char *str2, char *str3); void Mul(char *...

2021-05-22

0 439