第1页 / 共143页
第2页 / 共143页
第3页 / 共143页
第4页 / 共143页
第5页 / 共143页
第6页 / 共143页
第7页 / 共143页
第8页 / 共143页
ACM程序设计竞赛模板完全版.pdf
ACM-ICPC 模板整理
HDU_Supportornot
2016 年 10 月 13 日
目录
1 动态规划
1.1 基于位运算的最长公共子序列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 决策单调且不要求在线时的糙快猛优化方法 . . . . . . . . . . . . . . . . . . . . .
1.3 悬线法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 插头 DP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 整数划分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 莫队算法
2.1 普通莫队算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 树上莫队算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 树上带修改莫队算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 二维莫队算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 数据结构
3.1 Hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 Hash 表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.2 字符串 Hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.3 矩阵 Hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 树状数组区间修改区间查询 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 K-D Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Link-Cut Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 Top Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6 Splay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6.1 普通 Splay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6.2 缩点 Splay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7 Treap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.8 替罪羊树实现动态标号 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.9 权值线段树中位数查询 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.10 线段树合并 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.11 树链剖分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
8
8
9
9
9
11
12
12
12
13
15
17
17
17
17
17
18
19
20
21
26
26
28
30
31
32
33
33
ACM-ICPC 模板整理
From Hangzhou Dianzi University
3.12 李超线段树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.13 ST 表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.14 左偏树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.15 带修改区间第 k 小 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.16 Segment Beats!
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.17 二维树状数组矩阵修改矩阵求和 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 树
4.1 动态维护树的带权重心 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 支持加边的树的重心的维护 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 虚树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4 曼哈顿最小生成树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 图
5.1 欧拉回路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 最短路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1 Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.2
SPFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.3 Astar 求 k 短路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Tarjan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.1 边双连通分量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.2 点双连通分量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.3 Dominator Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4 强连通分量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5 无负权图的最小环 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6
2-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.7 完美消除序列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.8 最大团 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.8.1 搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.8.2 随机贪心 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.8.3 独立集最大团计数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.9 最大独立集的随机算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.10 差分约束系统 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.11 点覆盖、独立集、最大团、路径覆盖 . . . . . . . . . . . . . . . . . . . . . . . . .
5.12 匈牙利算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.13 Hall 定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.14 网络流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.14.1 ISAP 求最大流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.14.2 上下界有源汇网络流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.14.3 费用流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
35
35
35
37
40
42
42
43
45
45
47
47
48
48
48
48
49
49
50
50
51
51
52
52
53
53
53
53
54
54
55
55
55
55
55
56
57
2
ACM-ICPC 模板整理
From Hangzhou Dianzi University
5.14.4 混合图欧拉回路判定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.14.5 线性规划转费用流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.15 最小树形图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.16 构造双连通图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.17 一般图最大匹配 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.18 图的绝对中心 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6 博弈论
6.1 SG 函数的计算方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Nim Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3 Bash Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.4 Nim-k Game
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.5 Anti-Nim Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.6 Staircase Nim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.7 Wythoff Game
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.8 树上删边游戏 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.9 无向图删边游戏 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.10 翻硬币游戏 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7 数学
7.1 Bell 数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2 扩展欧几里得算法解同余方程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3 同余方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4 线性基 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4.1 异或线性基 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4.2 实数线性基 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.5 原根、指标、离散对数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.5.1 求原根 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.5.2 扩展 Baby Step Giant Step . . . . . . . . . . . . . . . . . . . . . . . . . .
7.6 Catalan 数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.7 扩展 Cayley 公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.8 Jacobi’s Four Square Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.9 复数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.10 高斯消元 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.10.1 行列式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.10.2 Matrix-Tree 定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.11 康托展开 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.12 自适应 Simpson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.13 线性规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.14 调和级数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
58
58
59
59
60
62
62
62
62
62
62
62
62
63
63
63
64
64
64
65
65
65
65
66
66
66
67
67
67
67
68
68
68
68
69
69
70
3
ACM-ICPC 模板整理
From Hangzhou Dianzi University
7.15 曼哈顿距离的变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.16 拉格朗日乘数法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.17 线性递推逆元 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.18 组合数取模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.18.1 Lucas 定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.18.2 P 是质数的幂 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.19 超立方体相关 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.20 平面图欧拉公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.21 线性筛 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.22 数论函数变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.22.1 疯狂的前缀和 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.23 快速傅里叶变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.23.1 FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.23.2 NTT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.23.3 多项式求幂 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.23.4 拉格朗日反演 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.24 蔡勒公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.25 皮克定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.26 组合数 lcm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.27 区间 lcm 的维护 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.28 中国剩余定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.29 欧拉函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.30 快速沃尔什变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.31 幂和 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.32 斯特林数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.32.1 第一类斯特林数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.32.2 第二类斯特林数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.33 各种情况下小球放盒子的方案数 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.34 错排公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.35 Prufer 编码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.36 二项式反演 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.37 xk 的转化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.38 快速计算素数个数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.39 Best Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.40 法雷序列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.41 FFT 模任意质数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.42 拉格朗日四平方和定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.43 Pell 方程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.44 O(1) 求 GCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.45 拉格朗日插值法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
70
70
70
70
71
71
71
71
72
72
73
73
74
75
75
76
76
76
76
76
76
77
77
78
78
78
79
79
79
79
79
79
81
82
82
84
85
86
87
4
ACM-ICPC 模板整理
From Hangzhou Dianzi University
7.46 二次剩余 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8 字符串匹配
8.1 KMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.2 最小表示法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.3 AC 自动机 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.4 回文串 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.4.1 Manacher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.4.2 Palindromic Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.5 后缀数组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.6 后缀树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.7 后缀自动机 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.8 后缀自动机 - Claris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.9 后缀平衡树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.10 Basic Factor Dictionary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.11 可持久化 KMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.12 扩展 KMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.13 循环最长公共子序列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.14 生成 Lyndon Words
87
88
88
88
88
89
89
89
90
91
92
93
94
95
98
98
99
99
9 随机化
101
9.1 Pollard Rho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
9.2 最小圆覆盖 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
10 计算几何
103
10.1 半平面交 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
10.2 最小矩形覆盖 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
10.3 三维凸包 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
10.4 球缺 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
10.5 2D 计算几何模板大全 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
10.6 曼哈顿凸包 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
10.7 圆的面积并 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
10.8 平面图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
10.9 Descartes’ Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
10.10动态凸包 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
10.11四面体内切球公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
10.12长方体表面两点距离 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
10.133D 计算几何基本操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5
ACM-ICPC 模板整理
From Hangzhou Dianzi University
11 黑科技与杂项
122
11.1 开栈 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
11.1.1 32 位 Win 下 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
11.1.2 64 位 Linux 下：(对 main() 中的汇编语句做修改)
. . . . . . . . . . . . . 122
11.1.3 简化版本 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
11.2 I/O 优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
11.2.1 普通 I/O 优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
11.2.2 文艺 I/O 优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
11.2.3 二逼 I/O 优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
11.3 位运算及其运用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
11.3.1 枚举子集 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
11.3.2 求 1 的个数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
11.3.3 求前缀 0 的个数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
11.3.4 求后缀 0 的个数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
11.4 石子合并 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
11.5 最小乘积生成树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
11.6 特征多项式加速线性递推 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
11.7 三元环的枚举 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
11.8 所有区间 gcd 的预处理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
11.9 无向图最小割 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
11.10分割回文串 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
11.11高精度计算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
11.12高精度计算 - Claris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
11.13Rope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
11.13.1 示例 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
11.13.2 示例 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
11.14pb_ds 的红黑树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
12 Java
139
12.1 输入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
12.1.1 声明一个输入对象 cin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
12.1.2 输入一个 int 值 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
12.1.3 输入一个大数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
12.1.4 EOF 结束 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
12.2 输出 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
12.3 大数类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
12.3.1 赋值 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
12.3.2 比较 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
12.3.3 基本运算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
12.3.4 BigDecimal 的格式控制 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6
ACM-ICPC 模板整理
From Hangzhou Dianzi University
12.3.5 创建 BigDecimal 对象 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
12.3.6 对 bigNumber 的值乘以 1000，结果赋予 bigResult . . . . . . . . . . . . . 141
12.3.7 BigInteger 的进制转换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
12.4 小数四舍五入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
12.5 高精度小数 A+B，输出最简结果 . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
12.6 斐波那契数列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
12.7 两个高精度浮点数比较是否相等 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
12.8 高效的输入类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
12.9 输出外挂 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
7
ACM-ICPC 模板整理
From Hangzhou Dianzi University
1.1 基于位运算的最长公共子序列
1 动态规划
∑
是否存在，
输入两个串 S 和 T ，长度分别为 n1 和 n2，压 B 位，ap[i][j] 表示字符 i 在 S 串的第 j 位
j
k=0 row[i][k] 表示 T 串前 i 位与 S 串前 j 位的 LCS。时间复杂度 O( n1n2
B )。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include
typedef long long ll;
const int BIT=808,E=62;
int n1,n2,m,h,i,j,p,ans;char s[50000],t[50000];
struct Num{
ll x[BIT];
Num(){for(int i=0;i
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
