20191102模拟-lq

lq的场

abc143F Distinct Numbers

题意:给出$n \le 3e5$个数,对于$\forall k \in [1,n]$,求出「每次选k个不同的数,能选多少次」

请先思考后再展开

经典问题

所以枚举每个答案,用不等式处理即可,为了快速计算和式可以先排个序,基排可以线性

code

AGC019F Yes or No

题意:有n+m次问题,其中n个的答案是YES而m个是NO,每次动态决策出一个答案(显然会选择剩下最多的那种),然后judge会给出这次的正确答案,问期望答对的问题数,$n,m \le 5e5$

请先思考后再展开

$dp_{i,j}=\frac{1}{i+j}*(j*dp_{i,j-1}+i*dp_{i-1,j}+max(i,j))$,求$dp_{n,m}$,假设$n \le m$

这个dp看起来就很像是一个带权路径计数,所以放到表格上面,每条路径的权值为经过的蓝色边数量,但注意在$i=j$的时候,我们给出的答案(走向哪个点)是不确定的,所以不设置蓝色边,而是额外给权值加上$\frac{1}{2}*经过的[i=j]点$

然后非常重要的是,这样画出来后,你发现所有路径都会恰经过m条蓝色边,所以$ans=m+\sum_{i=1}^n \frac{1}{2}*经过(i,i)的方案数$

code

CF840E In a Trap

这里

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/5865fdd5.html
转载请注明出处,谢谢!