本文将会不定期更新~

代码模板

我的 OI 代码模版。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>

typedef long long ll;
typedef unsigned long long ull;

typedef std::pair<int, int> PII;
typedef std::pair<ll, ll> PLL;

#define x first
#define y second

const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {-1, 0, 1, 0};

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/contestshttps://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 平均值
bel, belong 属于
best 最佳的
build 建立
block 障碍
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 下边的
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...); }
}
最后修改:2022 年 12 月 02 日
赠人玫瑰,手有余香。您的赞赏是对我最大的支持!