Codeforces Round #461 (Div. 2) 题解
比赛地址：Dashboard – Codeforces Round #461 (Div. 2) – Codeforces，也可以在底下的赛题列表点进题目。
由于这场比赛我并不打算也没有时间重新把代码写一遍，这里仅提供思路。
赛题列表
#A 922A – Cloning Toys | 思维
#B 922B – Magic Forest | 暴力、枚举
#C 922C – Cave Painting | 数论、暴力
#D 922D – Robot Vacuum Cleaner | 贪心
#E 922E – Birds | DP
#F 922F – Divisibility | 数论、构造
922A Cloning Toys
题目描述
最开始你有1个原始玩具，有一个玩具复制机，有两种复制模式：①输入一个原始玩具（但不消耗）并额外输出一个原始玩具和一个复制玩具；②输入一个复制玩具（但不消耗）并额外输出两个复制玩具。现在想得到x个复制玩具和y个原始玩具，想知道是否可行。
数据范围：0 \leq x, y \leq 10^9
样例
样例1
输入：
6 3
输出：
Yes
说明：
2次①，2次②。
样例2
输入：
4 2
输出：
No
样例3
输入：
1000 1001
输出：
Yes
题解
易知，y-1就是①操作的次数，这个时候只要求出x-(y-1)就能知道需要②操作进行多少次，如果这个值是奇数，显然②操作是做不到的，这个时候需要输出No，其他时候输出Yes。
别忘了特殊情况！
首先，y=0绝对不可行。y=1的时候，x只能为0。以及必须满足x-(y-1)>0。
复杂度：O(1)
922B Magic Forest
题目描述
给定值n，求出满足以下条件的有序数对(a, b, c)数。
- 1 \leq a \leq b \leq c \leq n；
- a \bigoplus b \bigoplus c = 0，\bigoplus表示异或运算；
- 存在边长分别为a, b, c的三角形。
数据范围：1 \leq n \leq 2500
样例
样例1
输入：
6
输出：
1
说明：
只有一组(3, 5, 6)
样例2
输入：
10
输出：
2
题解
看到这个数据范围，就想可以枚举来做。
枚举i，j，求出i^j，然后判断答案合不合法，统计一下合法的数量。i可以从6开始枚举。
复杂度：O(n^2)
922C Cave Painting
题目描述
给定值n, k，判断是否符合条件：不存在有序实数对(i, j)，满足以下条件
- 1 \leq i < j \leq k
- n \mod i = n \mod j
数据范围：1 \leq n, k \leq 10^{18}
样例
样例1
输入：
4 4
输出：
No
说明：
4 \mod 1 = 4 \mod 4 = 0
样例2
输入：
5 3
输出：
Yes
题解
让我们从1开始探索n应当满足的条件，可以发现下列式子
\begin{matrix} n \equiv 0 \ (\mod 1) \\ n \equiv 1 \ (\mod 2) \\ n \equiv 2 \ (\mod 3) \\ \cdots \\ n \equiv k - 1 \ (\mod k) \end{matrix}
这个条件一列出来，经过冷静的分析，机制的你发现了n = {\rm lcm}\{1, 2, \cdots, k\} - 1。然后再冷静分析一波，算一下k的上限，发现n取到上限的时候k应该很小（43），借用一些辅助工具甚至可以把这个表打出来。
比较可取的做法是对于比较大的k直接输出No，k比较小的时候就用上面条件验证一下。
复杂度：取决于你设的k的上限
922D Robot Vacuum Cleaner
题目描述
给你n个只包含s和h的串，一个串的价值是其中的满足i\<j且i位置为s且j位置为h的(i, j)对数。求一种排序方式，使得这些串排完序拼接成的长串的价值最大。只需要输出最大价值。
数据范围：1 \leq n \leq 10^5
样例
样例1
输入：
4 ssh hs s hhhs
输出：
18
说明：
按照ssshhshhhs的顺序获得最大价值。
样例2
输入：
2 h s
输出：
1
题解
按照经验来说这种题往往都是贪心，而它确实是个贪心。依据：设s_i表示i串的s字符数，h_i表示i串的h字符数，保证\frac{s_i}{h_i}在排序中单调不增即可。
证明如下：
设想一个排序中有相邻的i, j两串，考察满足什么条件的时候交换它们的顺序答案会更优。我们发现它们内部对答案的贡献与它们的顺序无关，这个整体与排序中其他部分联合产生的贡献也与它们的顺序无关，这个时候只需要讨论它们之间产生的贡献。当s_i \cdot h_j > s_j \cdot h_i时排序不需要交换，整理就得到了s/h比较大的串应该在前面的结论。
复杂度：O(n \log n)（排序算法的复杂度）
922E Birds
题目描述
有n棵树，每棵树上有鸟巢，第i棵树的鸟巢里有ci只鸟，获得第i棵树的鸟每只花费costi能量，同时使能量上限增加B，每棵树可以自由选择获得0~ci只鸟。最开始的时候能量和能量上限都是W，从一棵树走向下一棵树的时候恢复X能量，但是拥有的能量不能超过当前能量的上限。求最后最多能获得多少鸟。
输入第一行n, W, B, X，第二行ci，第三行costi。
数据范围：1 \leq n \leq 10^3, 0 \leq W, B, X \leq 10^9, \sum_{i=1}^n c_i \leq 10^4, 0 \leq cost_i \leq 10^9
样例
样例1
输入：
2 12 0 4 3 4 4 2
输出：
6
说明：
第一棵树获得2只，第二棵获得4只。
样例2
输入：
4 1000 10 35 1 2 4 5 1000 500 250 200
输出：
5
说明：
从最后一棵树获得5只。
样例3
输入：
2 10 7 11 2 10 6 1
输出：
11
题解
发现当前剩余能量这个显然不能放进DP的维度里，于是可以考虑把这个当做DP值，把当前获得的鸟数量作为DP的一个维度，于是设计出DP的状态：dp[i][j]表示到第i课树，当前获得了j只鸟的剩余能量。
然后就可以推一下方程了
dp[i][j] = \max \{\min\{dp[i-1][j-k]+X, W+(j-k)*B\} - k*cost_i\}
然后我们发现它应该是一个O(n)的转移，枚举k即可。
复杂度：O(n^2)
922F Divisibility
题目描述
给定n，找到一个\{1, 2, \cdots, n\}的子集I，满足I中满足a, b都来自I，a\<b且a|b的有序实数对(a, b)的数量为k。
如果找不到，输出No，如果找得到，输出一种I。
数据范围：2 \leq n \leq 3 \times 10^5, 1 \leq k \leq \min (10^9, \frac{n(n-1)}{2})
样例
样例1
输入：
3 3
输出：
No
样例2
输入：
6 6
输出：
Yes 5 1 2 4 5 6
说明：
有序实数对是(1, 2)(1, 4)(1, 5)(1, 6)(2, 4)(2, 6)。
样例3
输入：
8 3
输出：
Yes 4 2 4 5 8
说明：
有序实数对是(2, 4)(2, 8)(4, 8)。
题解
首先说判定。当k比集合\{1, 2, \cdots, n\}产生的答案还大的时候，就不存在。这个集合产生的答案就是每个数字除了它本身和1以外的因子数，这个可以O(n \log n)预处理出来再前缀和得到。
接下来构造。首先找到一个前缀和不大于k的最大位置pos，我们要选出答案为k的集合，换句话就是说要在\{1, 2, \cdots, pos\}删元素删到答案为k，考虑从pos/2~pos这一段开始删，这一段的因子数本来就比较大，而且删除这些数并不会对比其他数对答案的贡献产生影响。删完以后把剩下的输出就行。
复杂度：O(n \log n+2n)
