Contest Info

practice link

Solutions

A. Pavel and barbecue

签到题。

B. Travel Card

签到题。

C. Nikita and stack

题目大意：有 \(m\) 次询问，每次给出在 \(t_{i}\) 的时间，进行了一次入栈或出栈的操作，求按时间顺序进行当前的所有操作后栈顶元素。如果出栈时栈为空，则不进行操作。如果栈为空，输出 \(-1\)。

题解：为了避免讨论各种栈空的情况，我们首先在所有询问的时间之前进行 \(m+1\) 次入栈 \(-1\) 的操作。如果将入栈看做 \(+1\)，出栈看做 \(-1\)，并求后缀和，可以看出当前栈顶元素的操作时间是右起第一个后缀和为正的时间。用线段树维护即可。

D. Bacterial Melee

题目大意：给你一个字符串，每次操作可以将相邻两个字符中的一个变成另一个。问最终能形成多少个不同的字符串。

题解：这题挺有意思的。串 \(s\) 能操作变为 \(t\)，当且仅当 \(s\) 和 \(t\) 分别将连续的相同字符缩成一个后，\(t\) 是 \(s\) 的子序列。由于每次操作都满足该性质，因此必要性是显然的。而对于充分性也不难想到一种操作方法。

如果我们能求出 \(s\) “压缩”后长度为 \(i\) 的子序列有多少个，设为 \(f(i)\)，那么这些序列能够产生的 \(t\) 就有 \(f(i){n-1\choose i-1}\) 个。这个计数就是经典的本质不同子序列，只不过附加了不能有连续的相同字符这一条件。

时间复杂度 \(\mathcal{O}(n^{2}+n\Sigma)\)。

E. Byteland coins

题目大意：有 \(n\) 种硬币，第 \(i\) 种硬币的价值是第 \(i-1\) 种硬币价值的 \(a_{i}\) 倍，保证同样价值的硬币不超过 \(k=20\) 种。每种硬币有 \(b_{i}\) 个，保证 \(\sum b_{i}\le3\times10^{5}\)。问有多少种方法组合出 \(m\le10^{10000}\) 的价值。

题解：简单背包。设第 \(i\) 种硬币的价值为 \(p_{i}\)。设 \(dp[i][j]\) 表示前 \(i\) 种物品，组合出的价值除以 \(p_{i}\) 向下取整为 \(j\) 的方案数。这里我们向下取了个整，看似可以表示 \(p_{i}\) 种不同的价值，但是由于后一种硬币的价值是前一种硬币的价值的倍数，因此 \(i+1\) 后的硬币不可能组出模 \(p_{i}\) 不余 \(0\) 的价值，从而 \(m\mod p_{i}\) 的价值必须由前 \(i\) 种硬币组出，即当前价值和 \(m\) 模 \(p_{i}\) 同余，价值也就唯一确定了。

转移时用前缀和优化，可以 \(\mathcal{O}(1)\) 转移。如果 \(p_{i}=p_{i+1}\)，那么直接按背包转移就好。如果 \(p_{i}<p_{i+1}\)，那么要把余数非法的状态删去，并将状态除以 \(a_{i+1}\)，再进行转移。

时间复杂度 \(\mathcal{O}(k\sum b_{i}+\frac{\log^{2}m}{\text{BIT}})\)。

F. Long number

简单编译、数论，用递归下降分析法，配合数位 \(dp\) 和降幂即可。这题纯粹是难写恶心人，没有什么新意，就是把几个算法拼凑了一下而已。