基础
二分答案
int find1(int x) {
int l = 1, r = n;
while(l < r) {
int mid = (l + r) >> 1;
if(check(mid)) l = mid + 1;
else r = mid;
}
return l;
} // l：第一个不满足 check() 性质的数。
int find2(int x) {
int l = 1, r = n;
while(l < r){
int mid = (l + r + 1) >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
return l;
} // l：最后一个满足 check() 性质的数。
小数二分模板：
double l = MIN, r = MAX; //[MIN, MAX] 为解的取值范围。
while(r - l > 1e-9) {
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
快排
几乎不卡 STL::sort()，考场直接用就好。复杂度 \(O(n\log n)\)。
但是这道题卡快排就要分治写，复杂度 \(O(n)\)。代码：
void qsort(int l, int r, int x) { //求序列第 x 小的数。
if(l >= r) return;
int i = l - 1, j = r + 1, tmp = a[(l + r) >> 1];
while(i < j) {
do i++; while(a[i] < tmp);
do j--; while(a[j] > tmp);
if(i < j) swap(a[i], a[j]);
}
if (j >= x) qsort(l, j, x);
else qsort(j + 1, r, x);
}
归并排序
几乎不用，除了这道逆序对。
核心思想是分治，我写在 acwing 打卡里了。
int msort(int l, int r) {
if(l == r) return 0;
int mid = (l + r) >> 1;
int res = 0;
res += msort(l, mid); res += msort(mid + 1, r);
for (int i = l, j = mid + 1, k = l; k <= r; k++) {
if(j > r || (i <= mid && a[i] <= a[j])) t[k] = a[i++];
else {
res += mid - i + 1;
t[k] = a[j++];
}
}
for (int i = l; i <= r; i++) a[i] = t[i];
return res;
}
高精度
不想打，先咕。
离散化
每题实现不同，看这里罢。
前缀和与差分
较简单，写个 \(\text{LaTeX}\) 公式水一下。
\(\{s\}\) 表示 \(\{a\}\) 的前缀和数组，则
\[\sum^{r}_{l=1}{a_i} = s_r - s_{l- 1} \]差分则在原数组上打标记再跑前缀和即可。二维同理。
图论
建图
虽然不知道有什么必要写但还是写一下罢。
只贴链式前向星的因为其他的太简单了。
int nxt[M], to[M], idx, hd[N]; ll val[M];
void add(int a, int b, ll c) {
nxt[++idx] = hd[a], hd[a] = idx, to[idx] = b, val[idx] = c;
}
最短路
SPFA
bool vis[N]; ll dis[N]; // vis 表示在不在队列里
void spfa(int s) {
for (int i = 1; i <= n; i++) dis[i] = inf;
dis[s] = 0;
queue<int> q;
q.push(s);
vis[s] = 1;
while(q.size()) {
int u = q.front(); q.pop(); vis[u] = 0;
for (int i = hd[u]; i; i = nxt[i]) {
int v = to[i]; ll w = val[i];
if(dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if(!vis[v]) {q.push(v); vis[v] = 1;}
}
}
}
}
Dijkstra 堆优化
#define pir pair<int, int>
priority_queue<pir, vector<pir>, greater<pir> >q;
ll dis[N]; bool vis[N]; // vis表示当前点最短路是否已经确定
void dijkstra(int s) {
for (int i = 1; i <= n; i++) dis[i] = 1e18;
dis[s] = 0; q.push({0, s});
while(q.size()) {
auto t = q.top(); q.pop();
int disu = t.first, u = t.second;
if(vis[u]) continue; //这句话一定要写，防止一个点在队列出现多次导致 TLE。
//但是不会影响答案的正确性。
vis[u] = 1;
for (int i = hd[u]; i; i = nxt[i]) {
int v = to[i]; ll w = val[i];
if(dis[v] > disu + w) {
dis[v] = disu + w;
q.push({dis[v], v});
}
}
}
for (int i = 1; i <= n; i++) cout << dis[i] << ' ';
}
Floyd 求全源最短路
模板题：B3647 【模板】Floyd。
本质是 dp，可以直接用邻接矩阵来推。注意循环顺序：\(k \to i \to j\)。
有时间的话看看这题：灾后重建。
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if(g[i][k] + g[k][j] < g[i][j]) g[i][j] = g[i][k] + g[k][j];
最长路
模板题：P1807 最长路。
emm 直接把边权改成负数然后 SPFA 跑最短路就好了。代码贴了如贴。
负环
SPFA 判负环。模板题：P3385 【模板】负环。
bool spfa() {
for (int i = 1; i <= n; i++) dis[i] = 2e9; dis[1] = 0;
vis[1] = 1;
queue<int> q; q.push(1);
while(q.size()) {
int u = q.front(); q.pop();
vis[u] = 0;
for (int i = hd[u]; i; i = nxt[i]) {
int v = to[i];
if(dis[u] + val[i] < dis[v]) {
dis[v] = dis[u] + val[i];
dp[v] = dp[u] + 1; // dp 表示从起点到 v 点最短路的边数。
if(dp[v] > n - 1) return 1;
if(!vis[v]) q.push(v), vis[v] = 1;
}
}
}
return 0;
}
最小生成树
只记得 Krustal 了。本质是贪心选边，建图直接存边即可。模板题：P3366 【模板】最小生成树。
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
void krustal{
for (int i = 1; i <= m; i++)
{
int u = e[i].u, v = e[i].v, w = e[i].w;
int fu = find(u), fv = find(v);
if(fu == fv) continue;
fa[fu] = fv;
tot++; ans += w;
if(tot == n - 1) continue;
}
}
拓扑
模板题：B3644 【模板】拓扑排序 / 家谱树。
bool toposort() {
int s = 0;
for (int i = 1; i <= n; i++) if (!d[i]) s = i; // d 表示每个点的入度。
q[++tt] = s;
while(tt - hh + 1 >= 1) {
int t = q[hh++];
for (int i : a[t]) {
d[i]--;
if (d[i] == 0) q[++tt] = i;
}
}
return (tt == n);
}
SCC / 缩点
裸 Tarjan 求 SCC 模板题：B3609 [图论与代数结构 701] 强连通分量。
int dfn[N], low[N], vis[N], col[N]; // low 表示每个点可以遍历到的最小的时间戳，dfn 表示每个点的时间戳。
// vis 表示每个点在不在栈里面。
// col 表示每个点所在的强连通分量的编号。
vector<int> st; // 栈。
int dfncnt, colcnt;
void tarjan(int u)
{
if(!dfn[u]) dfn[u] = low[u] = ++dfncnt;
vis[u] = 1;
st.push_back(u); // 放入栈。
for (int i = hd[u]; i; i = nxt[i]) {
int v = to[i];
if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]); // 如果 v 没遍历过就求 v 然后更新。
else if (vis[v]) low[u] = min(low[u], low[v]); // 如果 v 遍历过了而且在栈中就直接更新。
// 否则 v 已经在某个强连通分量里面了，不用管。
}
if(dfn[u] == low[u]) { //u 是某个强连通分量的跟。
colcnt++;
while(st.back() != u) {
int v = st.back();
col[v] = colcnt;
vis[v] = 0;
st.pop_back();
}
col[u] = colcnt;
vis[u] = 0;
st.pop_back();
}
}
缩点模板题：P3387 【模板】缩点
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int N = 10010, M = 100010;
int n, m;
int nVal[N];
int hd[N], to[M], fr[M], nxt[M], idx;
int dfn[N], vis[N], low[N], dfncnt;
vector<int> st;
int col[N], colcnt, colVal[N];
void add(int u, int v) {
nxt[++idx] = hd[u], to[idx] = v, fr[idx] = u, hd[u] = idx;
}
void tarjan(int u) {
if(!dfn[u]) dfn[u] = low[u] = ++dfncnt;
st.push_back(u); vis[u] = 1;
for (int i = hd[u]; i; i = nxt[i]) {
int v = to[i];
if(!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if(vis[v]) low[u] = min(low[u], low[v]);
}
if(low[u] == dfn[u]) {
colcnt++;
while(st.back() != u) {
int v = st.back();
vis[v] = 0, col[v] = colcnt, colVal[colcnt] += nVal[v];
st.pop_back();
}
vis[u] = 0, col[u] = colcnt, colVal[colcnt] += nVal[u];
st.pop_back();
}
}
int in[N], dis[N];
int ans;
void toposort() {
queue<int> q;
for (int i = 1; i <= n; i++) if(!in[i]) q.push(i);
while(!q.empty()) {
int u = q.front(); q.pop();
dis[u] += colVal[u];
ans = max(ans, dis[u]);
for (int i = hd[u]; i; i = nxt[i]) {
int v = to[i];
in[v]--; if(!in[v]) q.push(v);
dis[v] = max(dis[v], dis[u]);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> nVal[i];
for (int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
add(u, v);
}
for (int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i);
for (int i = 1; i <= n; i++) hd[i] = 0;
idx = 0;
for (int i = 1; i <= m; i++) {
int u = fr[i], v = to[i];
if(col[u] == col[v]) continue;
add(col[u], col[v]); in[col[v]] ++;
}
n = colcnt;
toposort();
cout << ans;
return 0;
}
网络流
最小费用最大流
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
#define ll long long
#define inf (int)2e9
const int N = 5010, M = 10010;
int n, m, s, t, k;
namespace Graph {
int nxt[M], to[M], hd[N], idx;
ll val[M], cst[M];
void init() {
for (int i = 1; i <= n; i++) hd[i] = -1;
idx = 1;
}
void add(int u, int v, ll w, ll c) {
nxt[++idx] = hd[u], to[idx] = v, val[idx] = w, cst[idx] = c, hd[u] = idx;
}
}
using namespace Graph;
namespace Dinic {
bool vis[N]; ll dis[N];
int nhd[N];
ll minc = 0;
bool spfa(int sta = s) {
for (int i = 1; i <= n; i++) dis[i] = inf, nhd[i] = hd[i];
queue<int> q;
q.push(sta), vis[sta] = 1, dis[sta] = 0;
while(q.size()) {
int u = q.front(); q.pop(); vis[u] = 0;
for (int i = hd[u]; ~i; i = nxt[i]) {
int v = to[i]; ll w = val[i], c = cst[i];
if(dis[u] + c < dis[v] && w) {
dis[v] = dis[u] + c;
if(!vis[v]) vis[v] = 1, q.push(v);
}
}
}
return dis[t] != inf;
}
ll dfs(int u = s, ll flow = inf) {
if(u == t) return flow;
ll res = 0;
vis[u] = 1; //???
for (int i = nhd[u]; ~i && flow; i = nxt[i]) {
nhd[u] = i;
int v = to[i]; ll w = val[i];
if(!vis[v] && dis[v] == dis[u] + cst[i] && w) {
ll tmp = dfs(v, min(flow, w));
minc += tmp * cst[i];
res += tmp, flow -= tmp;
val[i] -= tmp, val[i ^ 1] += tmp;
}
}
vis[u] = 0;
return res;
}
}
int main() {
return 0;
}
数据结构
链表，栈，队列
直接用 STL，手写也可以。
几个要注意的点：
stack用vector。deque用list。
贴个手写：
AcWing 826. 单链表 - AcWing | AcWing 827. 双链表 - AcWing | AcWing 828. 模拟栈 - AcWing | AcWing 829. 模拟队列 - AcWing。
单调栈，单调队列
单调栈用于维护区间某个元素前比他小（大）的第一个元素，单调队列即滑动窗口。
咕。
平衡树
Splay
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
/*
1. 插入一个数 x。
2. 删除一个数 x（若有多个相同的数，应只删除一个）。
3. 定义 排名 为比当前数小的数的个数 +1。查询 x 的排名。
4. 查询数据结构中排名为 x 的数。
5. 求 x 的前驱（前驱定义为小于 x，且最大的数）。
6. 求 x 的后继（后继定义为大于 x，且最小的数）。
*/
namespace Splay {
int fa[N], son[N][2], sz[N], cnt[N], val[N];
int totNodes, ro;
#define ls(x) son[(x)][0]
#define rs(x) son[(x)][1]
//sz 是子树结点个数，cnt 是相同结点个数, val 是结点权值
void mke(int &x, int v) { x = ++totNodes, cnt[x]++, sz[x] = 1, val[x] = v; }
bool chkLs(int x) { // 检查是否为右儿子
return rs(fa[x]) == x;
}
void pushup(int x) { // 更新 val[x]
sz[x] = sz[ls(x)] + sz[rs(x)] + cnt[x];
}
void era(int x) { son[x][0] = son[x][1] = fa[x] = sz[x] = val[x] = cnt[x] = 0; } // 销毁一个结点
void rotate(int x) {
int y = fa[x], z = fa[fa[x]], wh = chkLs(x);
son[y][wh] = son[x][!wh]; if(son[x][!wh]) fa[son[x][!wh]] = y; // 记得判断有没有 !wh 儿子
son[x][!wh] = y; fa[y] = x;
fa[x] = z; if(z) son[z][y == son[z][1]] = x; // 将 x 接到 y 原来的位置，记得判断有没有 z
pushup(y), pushup(x);
}
void splay(int x) {
while(fa[x]) {
if(fa[fa[x]]) rotate(chkLs(x) == chkLs(fa[x]) ? fa[x] : x);
rotate(x);
}
ro = x;
}
void ins(int v) {
if(!ro) {
mke(ro, v);
return;
}
int u = ro, fu = 0;
while(1) {
if(val[u] == v) {
cnt[u]++;
pushup(u);
splay(u);
break;
}
fu = u, u = son[u][val[u] < v];
if(!u) {
mke(u, v);
fa[u] = fu;
son[fu][val[fu] < v] = u;
pushup(u); // 1
splay(u);
break;
}
}
}
int rnk(int v) {
int u = ro;
int res = 0;
while(1) {
if(val[u] > v) u = ls(u);
else {
res += sz[ls(u)];
if(val[u] == v) {
splay(u);
return res + 1;
}
res += cnt[u];
u = rs(u);
}
}
}
// int rnk1(int v, int x) { // 递归版本(写线段树写魔怔了自己手敲的)
// if(v < val[x]) return rnk1(v, ls(x));
// if (v > val[x]) return sz[ls(x)] + cnt[x] + rnk1(v, rs(x));
// splay(x);
// return 1;
// }
int kth(int k) {
int u = ro;
while(1) {
if(ls(u) && sz[ls(u)] >= k) u = ls(u);
else {
k -= sz[ls(u)] + cnt[u];
if(k <= 0) {
splay(u);
return val[u];
}
u = rs(u);
}
}
}
int pre() { // 查根的前驱
int u = ls(ro);
if(!u) return 0;
while(rs(u)) u = rs(u);
splay(u);
return val[u];
}
int nxt() { // 查后继
int u = rs(ro);
if(!u) return 0;
while(ls(u)) u = ls(u);
splay(u);
return val[u];
}
void del(int v) { // 删去一个值为 v 的
rnk(v); // 拉 v
if (cnt[ro] > 1) {
cnt[ro]--, pushup(ro);
} else if(!ls(ro) && !rs(ro)) {
era(ro);
ro = 0;
} else if(ls(ro) && !rs(ro)) {
ro = ls(ro);
era(fa[ro]), fa[ro] = 0;
} else if (!ls(ro) && rs(ro)) {
ro = rs(ro);
era(fa[ro]), fa[ro] = 0;
} else {
int tmp = ro, v = rs(ro); pre(); // 拉新根
era(tmp), fa[ro] = 0;
rs(ro) = v, fa[v] = ro;
pushup(ro);
}
}
}
int n;
using namespace Splay;
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
scanf("%d", &n);
while(n--){
int op, x; scanf("%d%d", &op, &x);
if(op == 1) ins(x);
else if (op == 2) del(x);
else if (op == 3) ins(x), printf("%d\n", rnk(x)), del(x);
else if (op == 4) printf("%d\n", kth(x));
else if (op == 5) ins(x), printf("%d\n", pre()), del(x);
else ins(x), printf("%d\n", nxt()), del(x);
}
// for (int i = 1; i <= totNodes; i++) printf("%d ", sz[i]);
return 0;
}
计算几何
最小圆覆盖
还没完全理解捏。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <random>
using namespace std;
#define db double
#define exp (db)1e-6
const int N = 1000010;
int n;
struct node {
db x, y;
} a[N], O;
double R;
db dis(node a, node b) { return sqrt((b.x-a.x) * (b.x-a.x) + (b.y-a.y) * (b.y-a.y)); }
bool inCir(node a) {
return dis(a, O) - R < exp;
}
void getCir(node a, node b, node c) {
O.x = ((b.x*b.x+b.y*b.y-a.x*a.x-a.y*a.y) * (c.y-a.y) - (c.x*c.x+c.y*c.y-a.x*a.x-a.y*a.y) * (b.y-a.y)) / (2 * (b.x-a.x) * (c.y-a.y) - 2 * (c.x-a.x) * (b.y-a.y));
O.y = ((b.x*b.x+b.y*b.y-a.x*a.x-a.y*a.y) * (c.x-a.x) - (c.x*c.x+c.y*c.y-a.x*a.x-a.y*a.y) * (b.x-a.x)) / (2 * (b.y-a.y) * (c.x-a.x) - 2 * (c.y-a.y) * (b.x-a.x));
R = dis(a, O);
}
mt19937 rng(time(0));
int ri(int l, int r) {
return rng() % (r - l + 1) + l;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lf%lf", &a[i].x, &a[i].y);
for (int i = 1; i <= n; i++) swap(a[i], a[ri(1, n)]);
O = a[1], R = 0;
for (int i = 1; i <= n; i++) {
if(!inCir(a[i])) {
O = a[i], R = 0;
for (int j = 1; j < i; j++) {
if(!inCir(a[j])) {
O = {(a[i].x+a[j].x)/2, (a[i].y+a[j].y)/2};
R = dis(a[i], a[j]) / 2;
for (int k = 1; k < j; k++) {
if(!inCir(a[k])) {
getCir(a[i], a[j], a[k]);
}
}
}
}
}
}
printf("%.2lf %.2lf %.2lf", O.x, O.y, R);
return 0;
}