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 题解
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 题解
ARC099F Eating Symbols Hard 题意 有一个长度为 $2 \times 10^9 + 1$ 的整数序列 $a_{-10^9 \dots 10^9}$,和一个整数 $p$,一开始均为 $0$。 对于一个仅包含 +->< 的字符串,按顺序依次执行每个字...
ARC089F ColoringBalls 题解
ARC089F ColoringBalls 题意 有 $n$ 个白色小球排成一排。 给定一个长度为 $k$ 的只包含红色和蓝色的染色操作序列。 按照染色操作序列的顺序,每次选择一段区间(可以为空),将区间内的小球全部染成当前...
ARC100F Colorful Sequences 题解
ARC100F Colorful Sequences 题意 给定 $n,k$ 和序列 $a_{1\dots m}$。 定义存在「长度为 $k$ 的连续子序列是一个连续段」的序列为 colorful 序列。 求所有长度为 $n$ 值域 $[1,k]$ 的 colorful 序列的所...
ARC095F Permutation Tree 题解
ARC095F Permutation Tree 题意 对于一个 $1\sim n$ 的排列 $p_{1\cdots n}$,可以通过如下方法生成一棵树: 对于 $i$,如果 $p_i \ne 1$,则找到一个最大的 $j$ 满足 $p_j < p_i$,在 $i,j$ 之间连...
ARC101E Ribbons on Tree 题解
ARC101E Ribbons on Tree 题意 给定一棵 $n$ 个点的树,保证 $n$ 为偶数。 将 $n$ 个点分成 $\frac n2$ 个无序点对。 对于每个点对,将树上两点之间的最短路径上的边染色。 问有多少种方案使得每条边都被...
Codeforces Round #637 (Div. 1) – Thanks, Ivan Belonogov! 题解
Codeforces Round #637 (Div. 1) - Thanks, Ivan Belonogov! Update:哈哈哈它 Unrated 了,爷的青春回来了。 Nastya and Strange Generator 垃圾题,模拟。 有病吧题面写这么长。 const int N = 1e5 +...
ARC091F Strange Nim 题解
ARC091F Strange Nim 题意 有 $n$ 堆石子,第 $i$ 堆有 $a_i$ 个石子和一个整数 $k_i$。 两个人轮流,每次选择一堆,从中要取出至少一个石子。 设选择了第 $i$ 堆,当前还剩下 $x$ 个石子,则可以从中取出...
ARC096E Everything on It 题解
ARC096E Everything on It 题意 有一个包含 $n$ 个元素的集合 $S$。 你要选择若干个互不相同的 $S$ 的子集,使得每个元素至少出现两次,求方案数。 $n \le 3 \times 10^3$,答案对 $M$ 取模。 题解 考...