USACO 2019 December Contest Greedy Pie Eaters 区间 dp。 考虑最后放上去的区间,必有一个位置被新覆盖了。 枚举这个位置即可,时间复杂度 $\mathcal O(n^3)$。 const int N = 307; int n, m, a[N][N...
题解
Codeforces Round #641 (Div. 1) 题解
Codeforces Round #641 (Div. 1) Orac and LCM 每个质因子考虑一下即可。 namespace shai { const int N = 1e6 + 7; int p[N], v[N], phi[N], miu[N]; inline void init(int n) { v[...
JOI Open 2019 题解
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 题解
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 题解
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 ...
P4173 残缺的字符串 题解
P4173 残缺的字符串 带通配符的字符串匹配模板题。 两个长度为 $n$ 的字符串 $a, b$ 相等当且仅当 $\sum_{i=1}^n (a_i-b_i)^2 = 0$。 如果带有通配符,将通配符看成 $0$,则 $a,b$ 相等当且仅当 $\sum_{i=...
P6122 [Neerc2016]Mole Tunnels 题解
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) 题解
Codeforces Round #638 (Div. 2) Phoenix and Balance 由于最大的要比其它所有加起来还要大,因此一定是最大的那个带 $\frac n2 -1$ 个最小的。 int n; inline void solve() { rd(n); ll ans = 1...
ARC098F Donation 题解
ARC098F Donation 题意 给定一张 $n$ 个点 $m$ 条边的无向连通图,每个点有两个属性 $a_i,b_i$。 一开始你有 $w$ 元,你要从某个满足 $a_s \le w$ 的节点 $s$ 开始,每次进行下列两个操作中的一个: 选...
ARC097F Monochrome Cat 题解
ARC097F Monochrome Cat 题意 给定一棵 $n$ 个点的树,每个点要么是白色要么是黑色。 你可以从任何一个顶点出发,每秒执行下列操作中的一个: 走到一个相邻的节点,反转到达的节点颜色。 反转所在的节点...