2021.09.13模拟赛

忳郁邑余侘傺兮，吾独穷困乎此时也

2021.09.13模拟赛

A. 古代龙人的谜题

古代龙人的谜题

能发现成立当且仅当两个最靠左右的 $1$ 在 $1$ 中标号的奇偶性相同

考虑一个点作为右端点的时候，它可以选取自己左右的连续的 $0$ 中的位置，或者选取之前的奇偶性相同的 $1$ 的左边的连续 $0$

就可以 $O(n)$ 统计了

code

B. 石头剪刀布

石头剪刀布

考虑如果最终的结果确定了，所有的比赛过程也就确定了，所以只需要知道最后是谁赢了就能递归建出来序列

因为不太好判断所以可以把三种可能枚举一遍，字典序最小看一下左右子树谁小谁在前面就行

$O(n2^n)$

code

C. 投票

投票

感性理解下每次取两个人投票肯定是要让他们两个投乘不投的概率最大化，所以肯定是选一个能选的最大的和最小的

理性理解下可以考虑如果选了 $m$ 个人，当前选了 $x$ ，那么最后的概率是 $\sum c_ip_x+c'_{i}(1-p_x)$，这是个一次函数，一定要 $p_x$ 最大/最小的时候取到最大值

$c_i$ 没法求，但是不重要，都试试就行

求出来 $i$ 个前后缀 $j$ 个人支持的概率拼起来即可

$O(n^2)$

code

D. 小学组

小学组

确实是小学组，暴力即可