闲扯很有价值的一道题，其中的模型转化值得借鉴。 题面P1641 [SCOI2010]生成字符串 Solution我们将问题转化一下，我们将选中一个 $1$ 看做在网格图上向右上方走一步，选中一个 $0$ 看做是向右下方走一步。 最后我们要求的就是从 $(0,0)$ 走 $n+m$ 步，走到 $(n+ ...

闲扯感觉还是挺不错的一道题，在预处理上需要用到一些小技巧。 题面 小球碰撞 Solution考虑用期望的定义式来计算。 $E(L,R)=\sum_{i=1}^{inf}i\cdot P_i$ 。 其中 $P_i$ 表示跳 $i$ 步之后超过 $R$ 的概率。 很简单的，我们可以推出 $P_i=\f ...

闲扯这道题真妙啊~~ 题面495. Kids and Prizes Solution按照期望的概率，我们的答案是 $\sum_{i=1}^nP(i)\cdot i$ ，其中 $P(i)$ 表示选了其中 $i$ 个盒子的概率。 但是这样做很不好算，我们考虑换个思路。 根据期望的线性性，我们可以算出一个 ...

闲扯题解真的看不懂，还是毕老爷讲的好。 题面P4550 收集邮票 Solution我们设 $f_i$ 表示取到了 $i$ 种不同的邮票的期望步数。 我们考虑怎么从 $f_{i-1}$ 转移过来。 因为当前已经有了 $i-1$ 个，所以取到一个新的邮票的期望步数为 $\frac{n}{n-i+1}$ ...

闲扯这是一个基础的概率题，用到了一个很好用的结论，一定要记住。 题面P5081 Tweetuzki 爱取球 Solution我们有这样一个结论：如果一个事件有 $p$ 的概率成功，如果成功立即停止，否则一直重复，那么这个事件成功的期望次数是 $\frac{1}{p}$ 。 有了这个之后，我们即可轻松 ...

闲扯感觉很有意义的一道题，最主要的是关于 $S(n)$ 的计算方式，很值得借鉴。 题面2ω(n) Solution我们先看 $S(n)$ 怎么计算。 首先，我们有 $S(n)=\sum_{d|n}2^{\omega(d)}$ ，其中 $\omega(n)$ 。 我们如果直接按照这个来写，显然是对每一 ...

闲扯很巧妙的一道题，思路值得借鉴。 题面Weighted lattice paths Solution我们先考虑问题的弱化版： $n\leq 10^3,m\leq 10^3$ 。 考虑 $dp$ 。设 $dp_{i,j}$ 表示走到 $(i,j)$ 这个点，所有的 $G(P_{i,j},k)$ 的总 ...

闲扯好奇妙的一道计数题。 题面Nim Extreme Solution我们知道 $Nim$ 游戏的先手必胜策略是所有数的异或非 $0$ 。 但是我们要计算非 $0$ 的方案数显然很困难，我们考虑算出所有为 $0$ 的方案数，然后用总方案数减去 $0$ 的方案数来得到我们合法的方案数。 我们设 $dp ...

闲扯我太难了。。。 题面题面 $T1$Solution注意到这样一件事：重要度 $d_i$ 是前缀最小值，所以它一定是单调不升的。 所以最后的重要值经过离散化之后一定是类似于 $k,k,\cdots,k-1,\cdots,\cdots,2,1,\cdots,1$ 。 因为重要程度相等选择编号最小的一 ...

闲扯我太难了！！！ 题面题面 $T1$Solution我们考虑 $DP$ 。 设 $DP_{i,j}$ 表示 $(i-1,j-1)$ 都匹配成功，在 $(i,j)$ 处失配，其最短公共非子序列的长度， $dp_{0,0}$ 显然是 $0$ 。 考虑转移。 我们只在 $s_i=t_j$ 处转移。 假设 ...