Codeforces-156

刷小号。差一点就可以虐场了 T_T。

Solution

A

签到题。q 只需求个 min 就可以了，然后把 a 排序一路扫过去，能用就用。

B

dp 。先要转换一下思路，把答案分成若干份： ans = 前 1 个人能塞进去的概率 + 前 2 个人能塞进去的概率 + 前 3 个人能塞进去的概率 ……

然后就可以 dp 了。令 f[i, j, k] 表示前 i 个数中选了 j 个数，这 j 个数的和为 k 的方案数。然后枚举当前数选不选即可。

提供另一种思路：统计每个数字出现的次数，令这个数组为一个状态，每次枚举选哪个数。记忆化一下即可。

C

先把这个表打出来，统计每行的和，发现 m + 1 行的数的和为 2^g(m + 2) ，其中 g(x) 表示 x 的二进制表示中 1 的个数。然后就是一个简单的数位统计题了。

D

被卡常数了求破。

如果 t > maxb \|\| t > n ，那么显然可以直接输出 b 中不同数的个数。

这样就可以保证序列的长度不超过 nt 也就是 2 * 10^7 。然后暴力跑最长上升子序列即可。

注意时间复杂度的估计，不是 O(nt log nt) 的，而是 O(nt log ans) 的，而 ans < min(n, maxb) ，所以有一个 0.5 的常数。

我当时就是这么写的，但是这样是会 T 的。一个比较简单的剪枝是如果答案到达上限，那么就直接 break 掉。但是仍然会 T 。再加一个常数优化：对于位置 i ，这次二分的位置不会小于上次二分的位置，于是从上次二分的位置开始二分即可。加上这个常数优化就可以过了。

E

不会。挖坑

situation

首先看了 A 题，水之。

然后看完 B 第一反应不会做，第二反应是作业中的一道题，然后就有了这个 idea ，然后 dp 超好写的说。

接着看了 CDE 三个题，感觉都不太会。刷新一遍看到 C 有人出了，于是开 C 。

推了一下没推出啥结论，然后打表发现都是 2 的幂，瞬间想到二进制表示中 1 的个数，然后就有结论了。

写了好久过不了最大的样例，到最后才发现有个地方需要 + 1 我忘记了，浪费了好多时间 T_T 。

借助刚才想的思路，立马写 D 。然后写了个随机的 generator ，发现无压力，于是直接 submit 了。

YY 了一下 E ，暴力 dfs 发现所有合法的数并不多，但是没想到肿么处理。于是 cha 人去。结果一个人都没 cha 到。

然后发现 D FST 了。哭瞎。

后来优化了一下常数就过了。

现在 rank 是 20 ，如果 D 没挂，那么可以直接 rank 3 。第一次 CF 是 rank 1 ，第二次是 rank 2 ，第三次是 rank 3 该多好啊。T_T

others

liouzhou_101 D 题同样 FST ，TLE 11 比我还惨。

ryz 怒 cha 两人。

ryz 、XLk、shangjingbo、pty、hyy、ChnLich 一堆人中规中矩，过了 ABC 。

jzp、cwx、gsh、大叔只过了 AB 。

秋锅只过了 A 。

xiaodao 怒挂 B 。

nonsense

闲着无聊把 RSS 架了起来。有兴趣的同学不妨订阅一下嘛。（目测没谁有兴趣……）