0%

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

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