ARC102F Revenge of BBuBBBlesort! 题意 给定一个 $1 \sim n$ 的排列 $p$。 每次操作可以选择一个满足 $p_{i-1} > p_i > p_{i+1}$ 的 $i$，将 $p_{i-1}$ 和 $p_{i+1}$ 交换。 问能否将 $p$ 变成 $1,2,3,\c...

ARC092F Two Faced Edges 题意 给定一张 $n$ 个点 $m$ 条边无重边无自环的有向图。 求每条边反向后整张图的强连通分量个数有没有变化。 $n \le 10^3$，$m \le 2 \times 10^5$。 题解 直接上结论： 对...

ARC101F Robots and Exits 题意 数轴上有 $n$ 个 A 类点 $A_i$，$m$ 个 B 类点 $B_j$，任意两点的坐标都是整数且互不相同。 每次操作可以让所有 A 类点同时向左或者向右移动一个单位。 如果在某个时刻 $A_...

ARC103D Robot Arms 题意 平面上有 $n$ 个整点 $(x_i, y_i)$。 要求构造出一个长度为 $m(\in [1,40])$ 的整数序列 $d(\in [1,10^{12}])$，满足 $d$ 可以生成所有整点。 称一个整数序列 $d_{1\dots m}$ 可...

ARC093E Bichrome Spanning Tree 题意 给定一张 $n$ 个点 $m$ 条边的无重边无自环的无向图，边有边权。 求给边染黑白两色，使得包含两种颜色的边的边权和最小的生成树的边权和恰好为 $X$ 的方案数。 $n \l...

ARC103F Distance Sums 题意 有一棵 $n$ 个点的树。 对于每个点 $i$，已知 $d_i$，表示 $\sum_{j=1}^n \operatorname{dist}(i,j)$。 所有 $d_i$ 两两互不相同。 构造出一棵符合要求的树，或者判断无解。 $...

JOI Final 2020 長いだけのネクタイ (Just Long Neckties) 显然 $a,b$ 排序后对应位置上的数相减最优，multiset 维护一下即可，时间复杂度 $\mathcal O(n \log n)$。 const int N = 2e5 + 7; int n, a[N],...

AtCoder Grand Contest 043 Range Flip Find Route 注意到，最后走的路线一定是黑白交替的。 每一次翻转颜色都一定是在进入黑色的时候，将后面一段黑色的路变成白色。 这与最短路很类似，由于边权只有 $0...

Codeforces Round #635 (Div. 1) Linova and Kingdom 设深度为 $d$，子树大小为 $s$，点 $i$ 对答案的贡献为 $d_i - s_i + 1$，从大到小贪心就好了。 const int N = 2e5 + 7; int n, k, d[N], s[N]; vi e[...

莫队算法是由莫涛提出的算法，可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。 普通莫队 设定块大小 $T$，将 $m$ 个询问 $[l,r]$ 离线下来...