一次多好的进前五的机会啊，居然被浪费了。

最近 FST 特别多，这状态怎么搞腾讯的比赛咯。

最后 #39 不算很坏的结果，但起码 E FST 了很桑心。

Solution

A

先把整个序列用 ab 染好，最后 $k - 2$ 个从 c 开始赋。

当然，搜索也是可以的。

B

可以发现前 $k$ 个与后 $n - k$ 个是无关的。由于 $k$ 特别小，直接搜索 $2 - k$ 个值即可。复杂度 $O(k^k)$ 。

C

不妨考虑 $p_n$ 应该是多少。令 $x$ 表示最小的不小于 $n$ 的能表示成 $2^k - 1$ 的形式的数，则 $p_n$ 的最优解显然就是 $x ^ k$ 。继续考虑下去，可以发现对于 $[x^n, n]$ 内的每个数我们都可以找到唯一的对应关系。剩下的数递归就好。

D

不妨设为有根树。考虑枚举 $a$ 到 $b$ 这条路径的 LCA $t$。我们要从 $t$ 的子树中选出两个点，使得它们的 LCA 是 $t$ 。这样的方案数是有 ${size_t \choose 2} - \sum_{x \textrm{is a child}} {size_x \choose 2}$ 。 $t$ 的子树外我们任取两个点即可，方案数为 ${n - size_t \choose 2}$ 。考虑到如果两条路径分布在不同的子树，这种情况我们会计算两遍，所以我们还要把这种情况剪掉。然后就没了。

E

一个显然的数位 dp 。我们预处理两个值 $f_i, g_i$ ，分别表示所有的 $i$ 位幸运数相邻两个的积的和以及所有 $i$ 位幸运数相邻两个的和的和。于是我们有如下递推式：

$$f_{i + 1} = 2 f_i + 65 * 100^i * (2^i - 1) + 11 * 10^i * g_i + (\frac{10^i - 1}{9} * 7 + 4 * 10^i) * (\frac{10^i - 1}{9} * 4 + 7 * 10^i)$$ $$g_{i + 1} = 2 g_i + 22 * 10^i * (2^i - 1) + 11 * \frac{10^{i + 1} - 1}{9}$$

$f$ 的递推式可以这么想：任意三个数 $x, y, A$ ，我们有

$$(x + A)(y + A) = A^2 + (x + y)A + xy$$

那么当从 $f_i$ 递推到 $f_{i + 1}$ 时，我们需要加上 $2^i - 1$ 个 $A^2$ ， $g_i$ 乘上 $A$ ，以及 $f_i$ 。 $A$ 有两种取值，一种是 $4 * 10^i$ ，一种是 $7 * 10^i$ 。最后再考虑一下多出来的一个积即可。

$g$ 的类似。

求出 $f$ 和 $g$ 后，剩下的就简单了。从前往后扫，每遇到一个 7 就计算对答案的贡献。

situation

今天真心不顺。

先是卡 A 卡了 12 min 。我想写贪心，但是各种怕特判，于是决定写搜。但是搜的一个地方忘记特判导致挂了……

看了 B 后觉得蛮简单的，写完后 A 掉。

看 C 。感觉这个题应该蛮简单的，但是没灵感，遂决定放到一边去。

看了 D 后第一想法是点分治。后面一项分什么治啊，直接 dfs 不就好了吗。我分了好几种情况，交了后发现 WA 了。怒决定写拍。发现拍比正解还难写啊。写完后发现我少考虑了几种情况。经过情况的合并后发现就两种情况嘛。和暴力拍了 20 以内的无误后交了。

然后转过去看 C 。第一想法是一位一位的来，然后就突然想到配对了。 $2^i$ 显然是和 $2^i - 1$ 配对嘛。按照这个思路下去就想到了那个构造，于是就好了。

现在大概还剩 50min 。发现 E 有人过我就去看了一下 E 。看完后瞬间就有想法了，于是推了一下公式后发现是可做的，怒写数位 dp 。写着写着发现只有 10+ min 了，我还没开始调试呢。最后在 1：58 的时候交了一个上去，过了 pretest ，对不对只能听天由命了。

结果 AE FST 了。如果任意一个都没 FST 的话应该可以红的。幸亏过了 D 。不然后果不堪设想呢。

最后 #39 被 liouzhou_101 怒踩。按照这 FST 率下去我真就只能专业算法三十年了。要搞 ACM 的话就找一个代码能力强的吧。

others

wjmsbmr 直接 #1 ，好强大……（现在 wjmsbmr 已经超过我大号了）

liouzhou_101 #38 。

只要 E FST 的人都没有好下场。

感觉第一题蛮好 cha 的。只可惜我没时间了。

感觉今天的 ABC 是主流吧。 squarefk、vfleaking、flydutchman、秋锅都是前三题，只不过速度差异有点大。

大叔只过了前两题，顺利跌回 div2 。

nonsense

今天腾讯打电话过来说进了区域赛了，到时候可以去免费深圳玩玩～