CSPS2 考前复习

对着 OIWIKI 复习一遍。

C++

到考场在 dev 添加 -std=c++14 -O2。

读入优化

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = x * 10 + (c & 15), c = getchar();
	return f ? -x : x;
}

如果前面有负号，隔着一段是数字的话这个板子会出错。

对拍

遇到那种能看出来很容易挂分的题，或是时间充裕一定要对拍！！！

while(true) {
	// make data
    system("t1 < in > out1");
    system("t2 < in > out2");
    if (system("fc a.out b.out /W")) {
		system("pause"); exit(0);
    }
}

STL

枚举全排列

for (int i = 1; i <= n; i ++) a[i] = i;
do {

} while (next_permutation(a + 1, a + n + 1));

字符串

string 转 char[] ：成员函数 c_str()

char[] 转 string：重载了 = 运算符

重载运算符

int operator+(const node &b) const {
}

Lambda

Lambda 写全局似乎会莫名 CE。

尽量少用。

二分

int l = 0, r = INF;
while (l <= r) {
	int mid = l + r >> 1;
    check(mid) ? res = mid, l = mid - 1 : r = mid + 1;
}
// res 就是答案

lower_bound 大于等于。

upper_bound大于。

背包

01 完全多重 现推。

二维费用就开两维的状态。

混合判断一下物品类型用各自的转移。

分组对组做 01，要先枚举组再枚举背包大小再枚举 组内物品。

方案数记录转移就行。

枚举二进制子集

for (int j = i; j; j = (j - 1) & i) {
}

DDP

乘变加，加变 max。

概率期望

• 期望等于值乘概率
• 期望的线性性质

四边形不等式

相交大于包含。

分治，类似莫队。

字符串

字符串下标从 1 开始。

for (int i = 2, j = 0; i <= n; i ++) {
	while (j && s[j + 1] != s[i]) j = nex[i];
    if (s[j + 1] == s[i]) j ++; nex[i] = j;
}

如果真的遇到了 Z 函数马拉车直接二分哈希。有时间的话尽量写双哈希。

快速幂

先把底数取个模。

exgcd

int Exgcd(int a, int b, int &x, int &y) {
  if (!b) { x = 1; y = 0; return a;  }
  int d = Exgcd(b, a % b, x, y);
  int t = x; x = y; y = t - (a / b) * y;
  return d;
}

数论分块

for (int l = 1, r = 0; l <= n; l = r + 1) {
	r = n / (n / l);
}

欧拉函数

for (int i = 2; i < N; i ++) {
	if (!vis[i]) phi[i] = i - 1;
    for (j is prime) {
        if (i % j == 0) {
            phi[i * j] = phi[i] * j;
		} else {
            phi[i * j] = phi[i] * (j - 1);
		}
	}
}

$$n = \sum_{d \mid n} \varphi(d)=n$$

求单个欧拉函数

$$\varphi(n) = n \times \prod _{i=1}^s \frac{p_i-1}{p_i}$$

扩欧

gcd 不是 1 并且大于 $\varphi$ 就模完加 $\varphi$。

---

数论其余部分暂时放一下罢。

卡特兰数

$$\binom{2n}{n}-\binom{2n}{n-1}$$

反射原理。

线性基

void add(int x) {
	for (int i = 32; i >= 0; i --) {
		if (!(x >> i & 1)) continue;
        if (a[x]) x ^= a[x];
        else { a[x] = x; break; }
    }
}

图论

非严格次小生成树

在最小生成树的路径上找最大值替换。

严格次小生成树

倍增时维护最大值和严格次大值。

瓶颈生成树

边权最大值最小的生成树。

最小生成树一定是瓶颈生成树。但不必要。

Kruskal 重构树

原图两点路径最大边权的最小值 = 重构树上 LCA 的点权。

Prim

每次选距离当前树点最近的点加入生成树。

使用堆优化复杂度 $$O((n+m)\log n)$$。

dij

void dij() {
    memset(vis, 0, sizeof vis);
	memset(dis, 0x3f, sizeof dis);
    priority_queue<pii> p;
    p.emplace(0, 1), vis[1] = 1, dis[1] = 0;
    while (!p.empty()) {
        int x = p.top().second; p.pop();
        if (vis[x]) continue; vis[x] = 1;
        for (auto [y, v] : e[x]) {
            if (dis[x] + v < dis[y]) {
				dis[y] = dis[x] + v;
                p.emplace(-dis[y], y);
            }
		}
	}
}

$$O(m\log m)$$

spfa

void spfa() {
    memset(vis, 0, sizeof vis);
	memset(dis, 0x3f, sizeof dis);
    queue<int> p;
    p.push_back(1), vis[1] = 1, dis[1] = 0;
    while (!p.empty()) {
        int x = p.top(); p.pop(); vis[x] = 0;
        for (auto [y, v] : e[x]) {
            if (dis[x] + v < dis[y]) {
				dis[y] = dis[x] + v;
                if (!vis[y]) p.push_back(y), vis[y] = 1;
            }
		}
	}
}

差分约束

形如 $x_i-x_j\le c_k$，找到一组解。

结论：$i$ 向 $j$ 连权值 $c_k$ 有向边，然后建一个源点向所有点权值 $0$ 的连边，若有负环则无解，否则最短路是一组解。

2-SAT

拆点，对于逻辑关系连有向边表示选了这个另一个必须选，缩点若和自己在一起就无解；否则判断拓扑序，真的拓扑序大就取真。

树上问题连通性网络流先放下。

---

计算几何

旋转坐标系

$$u = \cos \alpha \times x -\sin\alpha\times y$$

$$v = \sin \alpha \times x +\cos\alpha\times y$$

距离

• 曼哈顿->切比雪夫 $(x + y, x - y)$
• 切比雪夫->曼哈顿 $(\frac{x+y}{2},\frac{x-y}{2})$

树的直径

• 两次 dfs 求直径要求边权正
• 树形dp
• 动态树的直径：a 到 b 的距离等于 dep[a] + dep[b] - 2 * dep[LCA(a, b)]，用欧拉序转换成区间最值。
• 子树内直径：线段树 [L,R] 直径可由 [L,mid] 和 (mid,r] 的直径端点拼接而成。

树的重心

• 所有点到重心的距离和最小
• 树的重心子树大小不大于 n/2
• 树的重心子树最大值最小