Codeforces Round #606 (Div. 1, based on Technocup 2020 Elimination Round 4) As Simple as One and Two 贪心:碰到 twone 删 o,碰到 two 删 w,碰到 one 删 n。 const int N = 1.5e5 + 7; const stri...
题解
CF578F Mirror Box 题解
CF578F Mirror Box 题意 在一个 $n \times m$ 的网格中,每个格子里都有一个呈 \ 或 / 状的镜子。 一个合法的网格需要满足从任意一个边界段垂直射进网格中,光线会从相邻的边界段射出,同时网格中的每一段...
CF516E Drazil and His Happy Friends 题解
CF516E Drazil and His Happy Friends 题意 有 $n$ 个男生 $m$ 个女生,编号分别为 $0 \sim n - 1$ 和 $0 \sim m - 1$。 有 $b$ 个男生和 $g$ 个女生是快乐的,其他人是不快乐的。 在第 $i$ 天,编号为 $i...
CF576E Painting Edges 题解
CF576E Painting Edges 题意 给定一张 $n$ 个点 $m$ 条边的无向图。 一共有 $k$ 种颜色,一开始,每条边都没有颜色。 定义合法状态为仅保留染成 $k$ 种颜色中的任何一种颜色的边,图都是一张二分图。 有 $...
CF547E Mike and Friends 题解
CF547E Mike and Friends 题意 给定 $n$ 个字符串 $s_{1 \dots n}$。 $q$ 次询问 $s_k$ 在 $s_{l \dots r}$ 中出现了多少次。 $n, \sum |s| \le 2 \times 10^5$,$q \le 5 \times 10^5$。 题解 首先对 ...
CF547D Mike and Fish 题解
CF547D Mike and Fish 题意 给定 $n$ 个整点。 你要给每个点染成红色或蓝色。 要求同一水平线或垂直线上两种颜色的数量最多相差 $1$。 $n,x_i, y_i \le 2 \times 10^5$。 题解 对于每个点,将横纵坐标...
CF575A Fibonotci 题解
CF575A Fibonotci 题意 $s_{0\dots +\infty}$ 是一个正整数序列。 给定 $s_{0 \dots n - 1}$,对于 $i \ge n$,有 $m$ 个 $i$ 给定 $s_i$,剩下的 $i$ 满足 $s_i = s_{i \bmod n}$。 $f_{0 \dots +\infty}...
CF559E Gerald and Path 题解
CF559E Gerald and Path 题意 有 $n$ 条线段。 每条线段给定其中一端的位置及长度。 求所有线段覆盖的最大长度。 $n \le 100$。 题解 首先对一端位置排序。 考虑 dp,设 $f_{i,j,p}$ 表示考虑前 $i$ ...
CF512D Fox And Travelling 题解
CF512D Fox And Travelling 题意 给定一张 $n$ 个点 $m$ 条边的无向图。 一个点只有当与它直接相连的点中最多只有一个点未被遍历过时才可被遍历。 询问对于每个 $k \in [0,n]$,遍历 $k$ 个点的方案数。 $...
CF576D Flights for Regular Customers 题解
CF576D Flights for Regular Customers 题意 给定一张 $n$ 个点 $m$ 条边的有向图。 一开始你在 $1$ 号节点,你要走到 $n$ 号节点去。 只有当你已经走过了至少 $d_i$ 条边时,你才能走第 $i$ 条边。 问最...