JOI Open 2019 三级跳 考虑 $a,b$，注意到如果存在 $a < i < b$ 且 $A_i \ge A_a$，$A_i \ge A_b$，则选择 $a,i$ 或者 $i,b$ 一定比 $a,b$ 不劣。 因此理论上可能成为答案的 $a,b$ 只有 $\mathcal O...

AtCoder Grand Contest 039 Connection and Disconnection 分类讨论贪心。 const int N = 107; int n, c, k, t, a, b; char s[N]; int main() { rds(s, n), rd(k); for (int l = 1, r = 1; l <...

AtCoder Grand Contest 038 01 Matrix 简单构造题。 const int N = 1e3 + 7; int n, m, a, b; int main() { rd(n, m), rd(a, b); for (int i = 1; i <= n; i++) { for (int j = 1; j ...

小小的知识点，大大的坑。 容斥原理 设集合 $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$ 个，要求对...