0%

Codeforces-157

又跪了。rank 37 去了。

solution

A

找到第一个 0 删掉即可。

如果全部都是 1 肿么办呢?随便删个都可以啊。

B

首先肯定是要数位 dp 预处理的。这个还好做吧,一遍 dfs ,枚举这一位上是啥就可以了。

接下来可以直接搜,也可以跑一遍背包。限制很强的嘛,搜不会 T 的。

叫你写搜不写 dp,写挂了吧?写挂了吧?

我居然脑残地没有算组合数。都说了要 先组合再排列 的啊,你肿么就忘了啊?

C

先排序。然后枚举 LCM 是多少,枚举 LCM 的因数,可以利用 lower_bound 快速知道有多种选择的元素有多少个。再去去重就好了。

D

不会做。T_T

后来 orz 了 jzp 的神代码,差不多看懂了。

p(w,x,y) 表示 w 次操作后, x 这个位置的数比 y 这个位置的数大的概率。每次交换 st ,就先令 p(w+1,s,t) = p(w+1,t,s) = 0.5 ,然后枚举其余每个位置 i ,令 p(w+1,i,s) = p(w+1,i,t) = 0.5(p(w,i,s) + p(w,i,t)) ,令 p(w+1,s,i) = p(w+1,t,i) = 0.5(p(w,s,i) + p(w,t,i)) 。然后 p 大部分是相同的,直接滚动更新就可以了。

E

这个脑残的每个点的链表直接转化为到根的路径嘛。

考虑 dfs 整棵树。和当前节点有共同数的点必定是若干棵子树上的,用 dfs 序维护。那么要维护 2 个操作:

  1. 添加/删除一条线段
  2. 求所有线段的总覆盖长度

这是一个很经典的线段树练手题。标记都不要下放的。

situation

看完 A 觉得水翻了,秒之。

B 一看要写数位 dp ,但感觉不难写,于是写去了。写了半天发现过不了 = = ,这样例真是精心手构啊。

感觉不能在一棵树上吊死啊,于是写 C 去。发现 C 好好写的,过掉。

然后看 E 有这么多人过,还是可写的啊,于是把 E 写掉。

这时还差 8min ,想把 B 过掉,但就是过不了,找不出哪里错了 T_T 。和主席二分发现超过 50 就要跪。

于是到最后调试发现 44 就会挂,原因是我没有考虑人与人之间的组合,每次要先选择若干个人,再令这若干人的幸运数码个数为多少,再算排列的,结果没有乘选择这若干个人的方案数了。

感觉 dp 就不会犯这种 SB 错误了嘛。

由于初始 rating 低,所以 rating 还是微涨到 2343(+19) 。

others

qmd 小号 sandytea AK 虐场。

xhm 和 xlk 半开黑,lydshy 大开黑。看 lydshy B 的 code 你就知道了。两人每道题提交时间相差不超过 5min。

主席脑残 E 没想出来。

cwx 的 rating 居然没变化!

liouzhou_101zcwwzdjn (我真心怀疑这个 ID 是随手打的) 两人 C 都 FST 了,目测溢出了。

化悲痛为食欲!慢慢啃板栗中。