Contest Info

date: 2018.10.xx

practice link

Solutions

A. Chat Group

签到题

B. Scapegoat

题目大意：

有\(n\le2\times10^5\)个物品，第\(i\)个物品的质量为\(a_i\)，对于每一个物品可以将其均分为若干份（也可以不分），使得物品总数变为\(m\le2\times10^5\)，最小化每份物品质量的方差。

题解：

平均质量是定值，考虑\(m-n\)次修改每次选方差变化最大的，用堆维护，\(O(n\log{n})\).

C. Traffic Light

题目大意：

在一条笔直的道路上，一个人要从起点出发到终点去，中间经过\(n\le1000\)个红绿灯。

已知这\(n+1\)段路每段需要的时间，以及这\(n\)个红绿灯的周期分别为\(A_i\)和\(B_i\)，即从一个位置的时间零点开始，第\(i\)个红绿灯会交替亮\(A_i\)秒的绿灯，\(B_i\)的红灯，且\(A_i+B_i\)对每个红绿灯都相同。

这个人可以在出发前给每个红绿灯设置一个\(OFF_i\)，将其周期错开\(OFF_i\)秒，问最坏情况下至少需要多少时间从起点到达终点。

题解：

通过设置\(OFF_i\)，将红灯结束时间对齐（考虑路程时间偏移），这样如果遇到了一个红灯，之后的红绿灯都不会被阻塞，最坏情况就是最长的红灯时间加路程时间。

D. Mr. Panda and Geometric Sequence

题目大意：

定义一个数字为好数当且仅当可以将其十进制表示划分成\(3\)段以上，每段是没有前导零的十进制数字，并从左到右形成一个公比大于\(1\)的等比数列。

求区间\([L,R]\)内好数的数量，\(0\le L\le R\le10^{15}\).

题解：

考虑合法的等比数列前三项，设其分别为\(rp^2,rpq,rq^2\)，其中\((p,q)=1\)且\(p<q\).

显然第二项不会超过\(10^5\)，否则这三项连起来一定超过\(10^{15}\)了，直接枚举，复杂度\(O(n\log^2{n})\).

合法的数字数量约等于\(O(n\log{n})\)，排序后二分回答询问即可。

G. Image Recognition

题目大意：

给出\(n\le2000\)个\(m\le4000\)维零一向量，保证任意两个向量至少一维不同，\(q\le2000\)次询问，每次给出一个大小为\(k\)的下标集合，要求给出少于\(k\)个维度使得可以分出每一个向量（即不存在两个向量给定的维度分量都相等）.

题解：

枚举维度将集合划分，递归地划分直到每个集合大小为\(1\)，并将划分过程建树，询问时将点按dfn排序，求出相邻两点的lca去重即可。

时间复杂度\(O(nm+\sum k\log{n})\).

H. Mr. Panda and Birthday Song

题目大意：

给出一个由小写字母和?组成的字符串，长度不超过\(10^6\)，问是否存在一种将?换成字母的方法，使得任意连续的元音字母少于\(x\)个，任意连续的辅音字母少于\(y\)个，同时问是否可以不满足这个条件。

题解：

不满足的就贪心全部换成元音字母或辅音字母判断一下，满足则用\(f[0/1][i]\)进行\(dp\)，计算第\(i\)位是否为辅音字母时在\(i​\)处至少由多少个连续的同为元音或辅音的数量即可。

J. Straight Master

签到题。

K. Downgrade

签到题。

L. SOS

题目大意：一个 \(1\times n\) 的格子，两个人每次往一格填入 S 或 O，填出 SOS 者胜。问胜负情况。

题解：\(n\) 为奇数时，先手可以填完中间格子后模仿后手的行动，因此先手不败。同理 \(n\) 为偶数时后手不败。

另外注意到能够制造出某个格子填 S 和 O 均负的 pattern 只有 S..S 一种，且制造出这种 pattern 并不影响剩余可填格子的奇偶性。也就是说，若 \(n\) 为奇数且出现了 S..S，那么先手必胜；若 \(n\) 为偶数且出现了 S..S，那么后手必胜。

当 \(n\ge7,2\nmid n\) 时，先手在中间放一个 S，随后在后手操作的对侧再放置一个 S 即可。

当 \(n\ge16,2\mid n\) 时，先手在某个地方放置一个东西后，后手在较宽的一侧的中间放置一个 S 即与上种情况类似。

\(n\) 更小时，暴搜可以证明都是平局。

M. World Cup

签到题。