Sky390 的 OI 工具库

本文将会不定期更新~

代码模板

我的 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};

数据范围反推算法

一般 OI / ACM 或者笔试题的时间限制是 1 秒或 2 秒。在这种情况下，C++ 代码中的操作次数控制在 10^7 \sim 10^8 为最佳。

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

• n \le 30, 指数级别, Dfs + 剪枝，状态压缩 DP
• n \le 100 => O(n^3)，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！

转自 FYMS-OI(YAOJ) 《OI 实用链接》，有改动。