__CYJian__

题解

/ 注册

全部文章 / 题解（共4篇）

牛客等级之题N1（8.3场）题解

基础期望练习题。考虑设表示第 ***作后剩余黑球期望个数。令，，根据期望的线性性，则有：因为每次操作的时候，有的概率加入一个黑球，加上第轮期望剩下个黑球，则现在期望剩下个黑球。然后考虑扔掉一个球后，每个黑球都有的概率被留下，所以期望剩下个黑球。得到递推式之后，...

期望数学

2020-08-04

3 773

牛客挑战赛 40 C 题题解

简单题。考虑到有个性质：若我们已经知道串、长啥样，就可以用这样的方式计算最小交换次数：，考虑令等于的长度为的前缀中的出现次数减去的长度为的前缀中的出现次数，则跨过这个位置的交换一定至少有步。将所有位置的最小交换次数加起来，则可得到将变成的最小交...

模拟 dp

2020-05-15

2 710

牛客挑战赛 40 E 题题解

yysy，这题连都不要，为啥要开啊，故意放暴力过？？？这里是个非常弱智的做法：随便钦定一个点为根之后，考虑将一条边的边权放在儿子节点上。首先树剖，然后考虑修改的点权，可以先只修改其重儿子以及其到父亲的边的边权。然后考虑用带修主席树（树套树）维护一下区间内边权出现次数。再然后...

DS

2020-05-15

5 1043

牛客练习赛63 E 题题解

写这份题解之前，还没看见有人写这个题的题解，那么我就来写个吧。不排除我眼瞎的可能性首先，我们钦定串为最短的，满足，再钦定为。如果，则答案一定为。毕竟不可能出现在比它还短的串中。那么，不难发现，对于，都能用和的若干次拼接表示。然后再经过分析，不难发现，由于，...

KMP 矩阵加速斐波那契

2020-05-09

8 1081