牛客多校第五场

Gromah的题...

有些科技还是太为难老年人了...

C

题意

给定一个长为\(n\)的串，表示两个人打乒乓球，连续打\(n\)个球的结果

对于\(i\)，我们定义\(i\)赛制表示，双方中有一方得分超过\(i\)分，并且分差大于等于\(2\)时结果比赛的赛制

现在询问，对\(i = 1, 2, ..., n\)，在\(i\)赛制的情况下，Gromah赢了多少场

题解

还挺有意思的

一个显然的性质是，在\(i\)赛制下，比赛最多只有\(\lfloor \frac{n}{i} \rfloor\)场

.....然后考场上就短路了...

我们可以预处理出\(A\)赢了\(i\)个球的位置和\(B\)赢了\(i\)个球的位置，依次，我们可以判断他们是否进入了平局的阶段，如果进入了平局的阶段，说明之后的比赛应该是两者一赢一输，这个段也可以预处理出来

然后就完事了

E

吐槽

考场上写的脑子有点懵

C++的右移是坑爹的逻辑右移，对一个负数不断右移会得到一堆\(1\)，在利用\(\sim\)时被卡了记下...

G

吐槽

奇奇怪怪题

题意

给定\(a, b, \{p_i\}, \{q_i\}\)，定义\(c = \prod p_i^{q_i}\)，尝试找到\(x, y\)，使得\(x + y\)最小，并且\(lcm(a+x, b+y) = c\)

题解

队友的做法我没听...好像是极限数据\(2^{27}\)，但能卡卡的做法...（然后就WA了）

一个简单的想法是，枚举\(c\)的约数\(d_1\)，假设\(a + x = d_1\)，\(d_1\)也许会在若干质数上的次数没有卡到\(q_i\)，这就需要\(b+y\)去调整，也就是说相当于对于某个数\(M\)，\(b+y\)需要是\(M\)的倍数，而系数则应该是剩下卡到\(q_i\)的位置上质数次幂乘积的一个因子，难点在于如何寻找这个因子

利用折半搜索优化一下复杂度就能过了...