【11.23+11.24】Codeforces 刷题

D. Neko and Aki’s Prank

题意：

有一个由所有长为 $2\cdot n$ 的合法括号序列组成的 $\text{Trie}$ ，现在要求这棵树上最多的边集，符合边两两之间均没有共同节点。输出这个值模 $10^9+7$ 。

思路：构造最优解。

结论：对于一颗奇数层的二叉树，最大边集可以这样构造：找到所有的深度为偶数的节点（根深度为 $0$ ） ，然后指定他们连向父节点的边并添加到边集中，如果有冲突，只选择一个。这样构造出来的边集数量最大，而且数量刚好等于奇数深度的节点数量。 DP 计数即可。

这棵树刚好构成了一个拓扑图，拓扑图上 DP 计数。

AC代码：https://codeforces.com/contest/1152/submission/182214266

---

D. Field expansion

题意：

给出一个 $a\cdot b$ 的目标矩形和一个 $h\cdot w$ 的现有矩形以及 $n$ 个操作。每个操作有一个数 $a_i$ ，该可将现有矩形 $h$ 边乘上 $a_i$ ，或将 $w$ 边乘上 $a_i$ 。问至少进行几次操作，可以使得目标矩形能放入现有矩形中（可以旋转 $90$ 度）。若无解，请输出 $-1$

$a,b,h,w,n$ ( $1\le a,b,h,w,n\le 100000$ )

$2\le a_i\le 100000$

题解：CF799D Field expansion 题解

思路：首先，所需的 $a_i$ 不超过 $34$ 个。如果暴力枚举，将操作乘到 $h,w$ 其中一个，时间复杂度是 $2^{34}$ 。

有一种方法是 向下砍 而不是 向上乘 ，这样时间复杂度是 $2^{17}$ 。不会计算，很神奇。

AC代码：https://codeforces.com/contest/799/submission/182226507

---

构造题：

---

B. 3-Coloring

题意：略。

AC代码：https://codeforces.com/contest/1503/submission/182234386

---

E. Rock, Paper, Scissors

题意：

Alice 和 Bob 进行剪刀石头布的游戏，总共进行 $n(1\le n\le 10^9)$ 局。

Alice 出石头 $a_1$ 次，出剪刀 $a_2$ 次，出布 $a_3$ 次。

Bob 出石头 $b_1$ 次，出剪刀 $b_2$ 次，出布 $b_3$ 次。

问 Alice 最少赢多少次，最多赢多少次。

思路：最多赢多少次，取决于 $\min (a_1,b_2),\min (a_2,b_3),\min (a_3,b_1)$ 。

最少赢多少次，不仅取决于 Bob 赢了多少次，还有平局的次数。

方法一：三分套三分套三分（居然真的可以过）。定义 $x_1$ 表示 $b_1$ 赢 $a_2$ 的次数， $x_2,x_3$ 也同理。然后三次三分这三个变量即可。

方法二：见 题解 。

AC代码一：https://codeforces.com/contest/1426/submission/182246550

AC代码二：https://codeforces.com/contest/1426/submission/182247273

---

B1. Painting the Array I

题意：给定一个长度为 $n(1\le n\le 10^5)$ 的序列 $a$ ，你需要将这个序列拆分为两个子序列，使得子序列各自合并相邻相同元素之后的长度之和最大，输出最大值。

思路：贪心。详见 题解 。

AC代码：https://codeforces.com/contest/1479/submission/182305590

---

E. Breaking the Wall

题意：

现在有一个长度为 $n(2\le n\le 2\cdot 10^5)$正整数序列 $a$ , 你可以选择一个位置 $i$ ，进行一次操作：

• 将 $a_i$ 减去 $2$ ，将 $a_{i-1}$（如果存在）减去 $1$ ，将 $a_{i+1}$（如果存在）减去 $1$。

问至少要多少次操作可以使数列中至少出现两个非正整数。

思路：首先，两个非负整数只存在于三种情况。

1. 数列的最小值、次小值。
2. 数列相邻的两个元素。
3. 数列间隔为 1 的两个元素。

1 易计算，3 总结得到式子 $\lceil \frac{a+b}{2}\rceil$ 。

对于 2 ，定义两个元素操作次数为 $x,y$ ，得不等式 $2\cdot x+y\ge a,x+2\cdot y\ge b$ ，计算可得 $\min (x+y)=\frac{a+b}{3}$ ，$\text{int}(\min (x+y))=\lceil \frac{a+b}{3}\rceil$ 。但是当一个数大于另一个数的二倍时，这个式子不成立（容易发现是 $x$ 取到负数了），所以特判一下。

AC代码：https://codeforces.com/contest/1674/submission/182306159