这场前期不错,后期打爆了
#### A - Chat Group
场1A。
用 $2^n-\sum_{i=0}^{k-1}C_{n}^i$ 即可。
#### B - Scapegoat
场1A。
化式子得到要求的就是 $\sum_{i=1}^n\frac{x_i^2}{k_i}$ 的最小值,其中 $\sum_{i=1}^nk_i=m$ 。
那么维护一个堆,按照 $\frac{x_i^2}{k_i}-\frac{x_i^2}{k_i+1}$ 从大到小排序即可。
效率: $O(m\log n)$ 。
#### C - Traffic Light
场1A。阅读理解题。
其实就是 $s_i$ 的总和加上最大的红灯时间。
#### D - Mr. Panda and Geometric Sequence
场1A。
发现第二项最大 $10^5$ ,而且这样的好数不多,可以枚举第二项预处理。
$\text{sort}$ 后二分就好了。
#### E - Snakebird
场未A,没看。
#### F - Good Number
场未A,没想出来。
#### G - Image Recognition
场未A,场后A。
建立 $\text{trie}$ 树,如果选择一列也就意味着选择了一层的边,那我们可以删掉两边中有没有子树的边,因为选择那些边是无意义的。然后发现剩下的边是必选的。
因此找出相邻两个点的 $\text{lca}$ 所在的层,用桶维护即可。
不能倍增求 $\text{lca}$ 不然会爆空间,于是我写的树链剖分。
#### H - Mr. Panda and Birthday Song
场未A,场后A。
$\text{dislike}$ 就是全填辅音或元音看可不可以。
$\text{like}$ 就可以考虑 $\text{dp}$ : $f_{i,0/1}$ 表示这一位填元音/辅音,且最小的连续长度为多少。
转移就只要考虑上一位能不能填辅音/元音,如果能的话就是 $1$ ,不然就是上一个 $\text{dp}$ 值 $+1$ 。
#### I - PLAYERUNKNOWN'S BATTLEGROUNDS
场未A,没看。
#### J - Straight Master
场1A。
差分后贪心的放在后面的 $3/4/5$ 个位即可。
#### K - Downgrade
场A(-2)。
fjj写的,没看题。应该很简单。
#### L - SOS
场A(-1)。
就是一方要营造出 $\text{SXXS}$ 并且把另一方逼近这个状态就可。
发现 $<7$ 的先后手都可以互相拉扯为平局,而 $\ge 7$ 的奇数,先手一定可以营造出这个局面,而偶数的话不一定,因为先手可以先在中间下 $\text{O}$ 来破坏后手的局面,但如果 $\ge 16$ 的话就无法破坏了,因此是后手赢。
#### M - World Cup
场1A。fjj写的,水题。