目录
Contest Info
| 8/11 | O | O | O | - | - | O | O | - | O | O | O |
- O 在比赛中通过
- Ø 赛后通过
- ! 尝试了但是失败了
- - 没有尝试
Solutions
A A Prize No One Can Win
签到。
B Birthday Boy
题意：
给出\(n\)个生日，现在要找个日期，使得在它前面离它最近的生日和它相距的天数最大，如果有多个，输出和\(10-27\)相距天数最大的。
思路：
题意读清楚就可以了，枚举每一天。
C Cardboard Container
题意：
给出一个立方体的体积\(V\)，算表面积
思路：
枚举长宽高，长宽高是\(V\)的因子，枚举量不大。
D Driver Disagreement
题意：
给出\(n\)个点的图，每个点都有两条边，并且每个点有一个标记\(1\)或者\(0\)
现在两个人在同一点，但是他们不知道自己在哪一点，一个人觉得他们在\(A\)，另一个人觉得他们在\(B\)。
然后他们所在的位置是\(A\)或者\(B\)
现在需要设计一种路线，使得沿着路线走，如果从\(A\)出发走到一个点和从\(B\)出发走到一个点那个点的标记不一样，那么它们就知道谁对谁错了。
现在问最少的路线长度。
这个路线是每次选择往左走还是往右走，因为每个点有两条边
E Entirely Unsorted Sequences
题意：
有\(n\)个数，定义一个数是有序的当且仅当它左边的数都小于等于它，它右边的数都大于等于它。
现在问有多少种这些数的排列，使得所有数都不是有序的。
F Financial Planning
题意：
给出一些理财产品，对于每个理财产品，刚开始需要投入\(c_i\)的钱，之后每一天都会获得\(p_i\)的钱。
过了\(x\)天，一款理财产品带来的收益是\(xp_i - c_i\)。
现在问，如果选择理财产品，使得\(x\)天后的收益大于等于\(M\)
要满足\(x\)最小
思路：
二分\(x\)，那么每款理财产品的收益固定，贪心的取。
G Game Night
题意：
有一个长度为\(n\)的字符串环，里面只有'A', 'B', 'C'三种字符。
问最少要移动多少个字符，使得同类字符所在的位置的连续的。
思路：
枚举最终形态，那么如果一个位置最终形态对应的位置不是本身，那么这个字符要动。
维护三个前缀和\(O(1)\)算贡献。
H Harry the Hamster
题意：
有一张\(n\)个点\(m\)条边的有向图，每条边有边权，一个人在\(S\)点，它的左脑不想睡觉，它的右脑想睡觉。
两个脑袋轮流操作，每次操作在当前点选择一条出边往下走。
保证除了\(T\)点之外每个点都有出边，并且\(T\)没有出边。
问两个脑袋都最优操作，最终能否到\(T\)，能的话就输出到\(T\)的时间，不能的话就输出'infinity'
I In Case of an Invasion, Please. . .
题意：
给出一张\(n\)个点\(m\)条边的无向图，每个点有\(p_i\)个人，有\(s(1 \leq s \leq 10)\)个保护区。
每个保护区有一个容量\(c_i\)，保证\(\sum c_i \geq \sum p_i\).
现在所有人都要到保护区，令所有人到保护区的最大时间最小。
思路：
二分答案，那么对于每个点，我们可以知道在这个答案下，这个点上的人可以到达哪些保护区。
那么用一个\(s\)的二进制状态表示它的可达状态，发现最多只有\(2^s\)种状态。
将同种状态的点都缩起来，网络流判断是否流量等于\(\sum p_i\)即可。
J Janitor Troubles
题意：
给出四条边，问这四条边构成的四边形的最大面积
思路：
四边形是内接圆四边形时最大。
K Kingpin Escape
题意：
给出一棵树，有一个特殊点，现在可以额外加一些边，使得不管删去原树中的哪条边，每个点仍然可以到达特殊点