0%

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 架了起来。有兴趣的同学不妨订阅一下嘛。(目测没谁有兴趣……)