【题解】牛客OI周赛14-普及组

A题

数据范围 1(60pts): 随便设置的，不知道怎么才能只做到这一档分

数据范围 2(100pts): 开个桶，扫一遍字符串，记录一下每个字符出现没有过，没出现答案+1并标记即可，时间复杂度

B题

数据范围 1(30pts): 留给同学们乱搞以及部分细节错误的代码可以通过

数据范围 2(100pts): 对于每个数很容易想到取出他所有位上的分别是多少，然后枚举k，看能否满足条件，如果每一位的数的k次方和大于原数就停下，但需要考虑到所以数字都是1或0时可能会死循环，预处理一下0-9的k次方后，时间复杂度，可以二分k再优化一下复杂度

C题

数据范围 1(30pts): 每次换根dfs，求出对于每个点为根时的w，取min即可，复杂度

数据范围 2(100pts): 考虑任意选择一个点为根算出，对于两个相邻的点，我们令表示为根时，的子树大小，为为根时，的子树大小，那么显然在之间转移答案的变化为，故单次转移的复杂度为，总复杂度

D题

数据范围 1(20pts): 留给 暴力的同学

数据范围 2(100pts): 如果按照普通的思维定义 来表示讲完 件事的期望步数，会发现这个思路在这道题中不适用

因此我们尝试作出一些调整，即定义 为 **从一开始一直到第一次讲到第 件事**（注意不是讲完）的期望时间，我们容易得到

然后我们思考如何由 得到 的值。不难发现，我们的 是由下面几个部分构成的：

第一个部分是固定的部分

• 要想讲到第 件事，首先需要讲完前 件事，对期望时间的贡献是 。

第二个部分是由概率决定的部分

• 讲完第 件事后，有 的概率讲到下一件事。这种情况对期望就没有贡献了（有同学不理解这个地方为什么没有贡献，因为这种情况所整个需要的时间就是 ，已经被上面的部分算过啦）
• 另外有 的概率回到上一件事（ ），这种情况的贡献是 ，其中 代表从 “讲到第 件事” 一直到 “第一次讲到第 件事”的期望时间

显然， 也就相当于从“第一次开始讲i-1件事”到“第一次讲i+1件事”的期望时间。因为无论开始讲第 件事是不是你第一次讲到，都是对后面你讲到第 件事的期望时间没有影响的，简单来说就是没有后效性。按照定义可得 等于 。

于是我们有

最后我们整理以下公式，得到：

这下我们就可以 得出答案了。

最后要注意的是，由于我们求的 是第一次讲到第 件事的期望时间，所以最终我们的答案应该是 而不是 （因为是要把 件事讲完而不是刚好讲到第 件事）

（审题人不让出 的矩阵快速幂ww）

有的同学表示自己的算法正确，但是却没有得全分：原因主要是你的公式是由题解中公式演化出来的等价公式，但在计算时和标程由于计算方式不同出现了一定的误差。

例如：部分同学使用了一种双数组的做法，或没有化简递推公式。以上因素给这些公式正确但计算繁琐的同学造成了10-25分的失分，但对排名并未造成太大影响。这些失分的同学可以姑且把这次的失分看作因为算法不够优而造成的，因为你的代码或多或少在时间复杂度上都和std有着常数上的差距。