小小的知识点，大大的坑。 容斥原理 设集合 $S_{1\dots n}$，有 $$ \left| \bigcup_{i=1}^n S_i \right| = \sum_{k=1}^n(-1)^{k+1}\sum_{1\le p_1 < p_2 < \cdots < p_k \le n} \left| \bigcap_{i...

P4173 残缺的字符串 带通配符的字符串匹配模板题。 两个长度为 $n$ 的字符串 $a, b$ 相等当且仅当 $\sum_{i=1}^n (a_i-b_i)^2 = 0$。 如果带有通配符，将通配符看成 $0$，则 $a,b$ 相等当且仅当 $\sum_{i=...

P6122 [Neerc2016]Mole Tunnels 大概是模拟费用流模板题。 考虑建出费用流的图： 对于每条树边 $(x,y)$，建边 $(x,y,+\infty,1),(y,x,+\infty,1)$。 对于每个点 $i$，建边 $(i, T, c_i, 0)$。 对于每只鼹...

Codeforces Round #638 (Div. 2) Phoenix and Balance 由于最大的要比其它所有加起来还要大，因此一定是最大的那个带 $\frac n2 -1$ 个最小的。 int n; inline void solve() { rd(n); ll ans = 1...

ARC098F Donation 题意 给定一张 $n$ 个点 $m$ 条边的无向连通图，每个点有两个属性 $a_i,b_i$。 一开始你有 $w$ 元，你要从某个满足 $a_s \le w$ 的节点 $s$ 开始，每次进行下列两个操作中的一个： 选...

ARC097F Monochrome Cat 题意 给定一棵 $n$ 个点的树，每个点要么是白色要么是黑色。 你可以从任何一个顶点出发，每秒执行下列操作中的一个： 走到一个相邻的节点，反转到达的节点颜色。 反转所在的节点...

ARC096F Sweet Alchemy 题意 有 $n$ 个物品，买一个第 $i$ 个物品需要花费 $m_i$ 元。 除了第一个物品外，第 $i$ 个物品有一个上级物品 $p_i(< i)$。 给定 $d$，设第 $i$ 个物品买了 $c_i$ 个，要求对...

JOI Final 2018 ストーブ (Stove) 用个堆维护差分后的序列，每次取最小的。 const int N = 1e5 + 7; int n, k, a[N], ans; int main() { rd(n, k), rda(a, n), ans = n; pq<int> q; fo...

JOI Final 2019 勇者ビ太郎 (Bitaro the Brave) 前缀和计数一下，时间复杂度 $\mathcal O(nm)$。 const int N = 3e3 + 7; int n, m, c[2][N][N]; char s[N][N]; ll ans; int main() { rd(n, m); ...

ARC099F Eating Symbols Hard 题意 有一个长度为 $2 \times 10^9 + 1$ 的整数序列 $a_{-10^9 \dots 10^9}$，和一个整数 $p$，一开始均为 $0$。 对于一个仅包含 +->< 的字符串，按顺序依次执行每个字...