Codeforces-177
一次多好的进前五的机会啊，居然被浪费了。
最近 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
今天腾讯打电话过来说进了区域赛了，到时候可以去免费深圳玩玩～