indeed笔试第二场第四题

E[S]表示抓到集合S中的颜色球的期望。 E[empty] = 0 E[S] = \sigma_{i \in S} ((E[S - {i}] + 1) * P_i) + (E[S]+1)*P_S P_i表示取颜色为i的球的概率，P_S表示取集合S中颜色球的概率。 然后对上面的化简一下，发现就是一个状态压缩DP 按照状态压缩的方法求解就好了 复杂度为O(2^k)

非常感谢，我还有一个疑问： E[S] = \sigma_{i \in S} ((E[S - {i}] + 1) * P_i) + (E[S]+1)*P_S 是不是可以化简成：(1-P_S)*E[s] = \sigma_{i \in S} ((E[S - {i}] + 1) * P_i) + P_S 这个等式在s为全部状态时P_S是1，从而左边变成了0，而右边又不是0 ？ 【 在 leo0316 的大作中提到: 】 : E[S]表示抓到集合S中的颜色球的期望。 : E[empty] = 0 : E[S] = \sigma_{i \in S} ((E[S - {i}] + 1) * P_i) + (E[S]+1)*P_S : ...................

【 在 libenchao 的大作中提到: 】 : 非常感谢，我还有一个疑问： : E[S] = \sigma_{i \in S} ((E[S - {i}] + 1) * P_i) + (E[S]+1)*P_S : 是不是可以化简成：(1-P_S)*E[s] = \sigma_{i \in S} ((E[S - {i}] + 1) * P_i) + P_S : ................... 想了好长时间,发现思路想反了。 定义E[S]为收集到集合S中的颜色的球，期望还要取多少个球才能收集到全部的颜色。 根据定义E[\Omega] = 0,我们要求的是E[\emptyset] 根据期望的关系可以得到：E[S] = ( \sum_{i \notin S} (E[S \cup {i}] + 1)* P_i ) + (E[S] + 1)* P_S

太感谢了，这次终于懂了。膜拜~ 【 在 leo0316 的大作中提到: 】 : : 想了好长时间,发现思路想反了。 : 定义E[S]为收集到集合S中的颜色的球，期望还要取多少个球才能收集到全部的颜色。 : ...................

有没有聚聚说一下第三题怎么做的啊？状压DP?

暴力搜索即可。 【 在 chinadjh 的大作中提到: 】 : 有没有聚聚说一下第三题怎么做的啊？状压DP?

【 在 libenchao 的大作中提到: 】 : 暴力搜索即可。 : 哭。。我以为暴力过不了于是没做这一题，后面那个概率DP倒是做出来了

赞。 【 在 chinadjh 的大作中提到: 】 : 哭。。我以为暴力过不了于是没做这一题，后面那个概率DP倒是做出来了

【 在 libenchao 的大作中提到: 】 : 赞。 : 实话说第四题原来做过。。不过根据其他的大神反馈，好像4题AK的已收到电面通知，3题估计没戏[ema1]