本文将会不定期更新~
代码模板
我的 OI 代码模版。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
#define fir first
#define sec second
#define ep emplace
#define eb emplace_back
#define lowbit(x) ((x) & (-(x)))
inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
return x * f;
}
int main() {
return 0;
}数据范围反推算法
一般 OI / ACM 或者笔试题的时间限制是 1 秒或 2 秒。
在这种情况下，C++ 代码中的操作次数控制在 $10^7 \sim 10^8$ 为最佳。
下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：
- $n \le 30$, 指数级别, Dfs + 剪枝，状态压缩 DP
- $n \le 100$ => $O(n^3)$，$O(n^4)$，Floyd，DP，高斯消元
- $n \le 1000$ => $O(n^2)$，$O(n^2 \log n)$，DP，二分，朴素版 Dijkstra、朴素版 Prim、Bellman-Ford
- $n \le 10000$ => $O(n * \sqrt n)$，块状链表、分块、莫队
- $n \le 100000$ => $O(n \log n)$ => 各种 Sort，线段树、树状数组、Set/Map、Heap、拓扑排序、Dijkstra + Heap、Prim + Heap、Kruskal、SPFA、求凸包、求半平面交、二分、CDQ 分治、整体二分、后缀数组、树链剖分、动态树
- $n \le 1000000$ => $O(n)$, 以及常数较小的 $O(n \log n)$ 算法 => 单调队列、 Hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 $O(n \log n)$ 的做法：sort、树状数组、heap、Dijkstra、SPFA
- $n \le 10000000$ => $O(n)$，双指针扫描、KMP、AC 自动机、线性筛素数
- $n \le 10^9$ => $O(\sqrt n)$，判断质数
- $n \le 10^{18}$ => $O(\log n)$，最大公约数，快速幂，数位 DP
- $n \le 10^{1000}$ => $O((\log n)^2)$，高精度加减乘除
- $n \le 10^{100000}$ => $O(\log k \times \log \log k)，k 表示位数$，高精度加减、FFT / NTT
本部分来自 yxc 的文章：《由数据范围反推算法复杂度以及算法内容》，有改动。
实用链接
着重推荐 https://cftracker.netlify.app/contests 和 https://kenkoooo.com/atcoder#/table！
| 简述 | 详情 |
|---|---|
| 在线查看汇编 | 甚至支持代码片段的汇编 |
| 模板 OJ | 专门为模板题提供评测的 OJ |
| 并查集的最优写法 | 对比八种并查集写法，给出在不同条件下的最优写法 |
| 大组合数取模 | 大组合数 \binom{n}{m} 对任意质数幂 p^e 取模在 \mathcal O (p e + e \log_p n) 次大数乘法内解决 |
| 用人话解析 C++ 语法 | 给出变量或数组或函数的定义或类型转换，翻译成英语以供理解 |
| AtCoder 数据 | 下载 AtCoder 每题的测试数据 |
| AtCoder 难度评分和 AC 统计 | 方便查询每题的难度系数，也可以指定用户名查看通过的题目，还有更多功能 |
| 分解质因数 | 只能说是一个很奇怪的分解质因数的网站 |
| Codeforces 插件 | 由于 Chrome 禁止未知来源的扩展程序，请在 Chrome 网上应用店中安装使用 |
| Codeforces 掉分预测 | 由于 Chrome 禁止未知来源的扩展程序，请在 Chrome 网上应用店中安装使用 |
| 比较两个文本之间的差异 | 看起来甚至支持图片和 PDF 的比较，这合理吗？ |
| GCC 编译选项推荐 | 预防各种 bug |
| Codeforces 刷题信息统计 | 由于 Chrome 禁止未知来源的扩展程序，请在 Chrome 网上应用店中安装使用 |
| 更好的 Codeforces 掉分预测 | 由于 Chrome 禁止未知来源的扩展程序，请在 Chrome 网上应用店中安装使用 |
| Codeforces AC 统计 | 指定用户名查看通过的题目，大大有利于刷题 |
| C++ 运行时错误查询 | 调题必备；须会英文（） |
转自 FYMS-OI(YAOJ) 《OI 实用链接》，有改动。
变量名
以下按字母序列出一些推荐使用的变量和函数名，仅供参考。
注 1：mat, matrix 矩阵（这样的写法表示的意思是，matrix 是 mat 的全写，推荐用 mat，不推荐用 matrix，直接用单词比较长，且容易和各种保留字冲突）
注 2：本文只适用于算法竞赛或编程初学者，不适合与工业界代码规范相比
add 加
anc, ancestor 祖先
ans, answer 答案
avg, average 平均值
adj, adjective 相邻
bel, belong 属于
best 最佳的
build 建立
block 障碍
buc, bucket 桶
ch, char 字符
check 判定
color 颜色
col 列
cmp, compare 比较
cnt, count 计数器
cur, current 当前量
deg, degree 度数
dep, depth 深度
del 删除（delete是保留字）
delta 增量
diff, difference 差别
dist, distance 距离
div, division 除法，部分
dp 动态规划
edge 边
extra 额外的
fa, father 父亲
factor 因子
fail 失败
flag 标志
flow 流
from 来自
get 得到
Hash 哈希表（hash是保留字）
heap 堆
in 入
ind, index 标号
inq 在队列里
inf, infinity 无穷大
init, initialize 初始化
insert 插入
inv, inverse 翻转，颠倒
last 最后一个
len, length 长度
lim, limit 极限
low, lower 下边的
lay, layer 层
mx 最大值
mn 最小值
max_dep 最大深度
min_dep 最小深度
mat, matrix 矩阵
mid, middle 中间量
mod 模
modify 修改
mp, map 映射
mst 最小生成树
mul, multiply 乘法
node 结点
num, number 数量
nxt 后继（next是保留字）
out 出
pa, pair 对子
pre, precursor 前驱
prime 质数
pos, position 位置
prod, product 乘积
put 放置
que, queue 队列
query 询问
rank 秩
res, result 结果
res, residual 剩余
row 行
scc 强连通分量
size 大小
split 分裂
start 开始
stk, stack 栈
str 字符串
suc, succeed 后继
sum 和
tim 时间（time是保留字）
tmp, temporary 临时量
tree 树
to 表目的
unite 联合
up, upper 上边的
update 更新
used 使用过的
val, value 值
vec, vector 向量
vis, visit 访问
zero 零
参考自 《算法竞赛编程变量命名指南》，有改动
快速读写（namespace）
namespace fastio {
const int SIZ = 55;
int que[SIZ], op, qr;
char ch;
template <class I>
void read(I &w) {
ch = getchar(), op = 1, w = 0;
while(!isdigit(ch)) { if (ch == '-') op = -1; ch = getchar(); }
while(isdigit(ch)) { w = w * 10 + ch - '0'; ch = getchar(); }
w *= op;
}
template<typename T, typename... Args>
void read(T& t, Args&... args) { read(t); read(args...); }
}