AtCoder Beginner Contest 433 题解

A - Happy Birthday! 4

开局就绷不住了，晚上脑子有点不清醒直接暴力 check 到 \(10^7\) 没想到直接过了。代码。但是正解还是要推式子的，设 \(k\) 年后为答案，则有 \(X + k = Z(Y + k)\)，移项后得到 \(k = \dfrac{X - ZY}{Z - 1}\)，满足整除和 \(k \ge 0\) 即可。代码。

B - Nearest Taller

直接 \(O(n^2)\) 暴力，或者单调栈 \(O(n)\)，代码。

C - 1122 Substring 2

假设答案为 111222，直接枚举每个这样子串的最后一位，那么直接预处理出当前连续段的起始位置，那么 \(i\) 能作为答案当且仅当上一个连续段的长度大于当前的连续段，\(O(n)\) 解决。代码。

D - 183183

挠餐出题人又卡上常了。。差不多得了。先把倍数转化为模后余数为 \(0\)，首先考虑两个数 \(x, y\) 拼接后 \(\bmod \ m\) 的值，设 \(y\) 的位数为 \(k\)，那么 \(f(x, y) \bmod m = x\times10^k \bmod m+y \bmod m\)，枚举前者（或后者也行），再枚举 \(y\) 的位数，拿 map 记录一下就行，但是逆天出题人卡常，换用 gp_hash_table 就能过了。复杂度 \(O(n\lg V)\)。代码。

E - Max Matrix 2

思路很快就出了，但是代码很难写。首先把无解的情况判掉，当存在值在 \(X, Y\) 其中之一出现了两次及以上显然无解（因为填的是排列），然后考虑从后往前填数，因为这样的限制是最多的，假设当前填到数 \(v\)：

• 当存在 \(X_i = v, Y_j = v\) 时，直接把 \(v\) 填到 \(A_{i, j}\)。
• 当存在 \(X_i = v\) 时，任取一个 \(j\) 满足 \(Y_j > v\)，填到 \(A_{i, j}\)。
• 当存在 \(Y_j = v\) 时，任取一个 \(i\) 满足 \(X_i > v\)，填到 \(A_{i, j}\)。

因为我们从后往前填，所以能填数的地方会越来越多，因此只要满足上面的条件，就能随便填。实现方式很多。复杂度 \(O(nm)\)。

F - 1122 Subsequence 2

枚举前半串结尾，再枚举长度，得到一个组合数相关答案，写出来就是

\[ans=\sum_{i=1}^{n}\sum_{j = 1}^{\min(c_1,c_2)} \binom{c_1 - 1}{j - 1}\binom{c_2}{j} \]

其中 \(c_1\) 表示 \([1, i]\) 中 \(s_i\) 出现的次数，\(c_2\) 表示 \([i + 1, n]\) 中 \(s_i + 1\) 出现的次数。注意到这个东西可以稍微变一下之后范德蒙德卷积。

\[ans=\sum_{i=1}^{n}\sum_{j = 1}^{\min(c_1,c_2)} \binom{c_1 - 1}{j - 1}\binom{c_2}{c2-j}=\sum_{i=1}^{n}\binom{c_1+c_2-1}{c_2-1} \]

预处理阶乘和阶乘逆元即可 \(O(1)\) 查后面，复杂度 \(O(n)\)。代码。