ARC096E Everything on It 题意 有一个包含 $n$ 个元素的集合 $S$。 你要选择若干个互不相同的 $S$ 的子集，使得每个元素至少出现两次，求方案数。 $n \le 3 \times 10^3$，答案对 $M$ 取模。 题解 考...

ARC093F Dark Horse 题意 有 $2^n$ 个人，编号为 $1 \sim 2^n$，他们要进行一场比赛。 他们首先会排成一排形成一个排列，然后每一轮第 $2k-1$ 和第 $2k$ 个人对抗，留下胜利者，最终留下的人是冠军。 另有...

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...