sunrise__sunrise

题解

未归档(12) 读书笔记(1)

/ 注册

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

2021牛客暑期多校训练营5 K、King of Range 来自专栏

题目大意给你长度为的序列，并且有次查询，每次查询给出一个，询问在中有多少个区间的最大值减掉最小值严格大于。 Solution 考点：双指针+表考虑到区间不会修改，那么查找区间最值这个问题就用表维护就可以。然后再看最大值减掉最小值严格大于，如果在这个区间符合要求，那么是不是在这些右区间都是合法的...

ST表

2021-08-23

1 480

2021牛客暑期多校训练营5 G、Greater Integer, Better LCM 来自专栏

题目大意给你，你要让的前提下，最小的是什么，并且给出的是分解质因数的形式，。 Solution 考点：二进制枚举看到这个给的这么形式化，就要围绕这个去弄，而且幂次之和不超过，很明显的让我们去二进制枚举。那么我们就可以暴力的预处理出当前状态，可以的全部花费，那么要更新还有一个前提，就是之前的最...

二进制枚举

2021-08-23

1 570

2021牛客暑期多校训练营5 F、Finding Points 来自专栏

题目大意按逆时针给出凸包上的个点，你要在凸包里面找到一个点，让的最小值最大，然后输出这个最大的最小值。 Solution 考点：三分比较明显的容易发现如果我们固定，那么的相关函数一定是一个单峰函数。同理固定，那么的相关函数也一定是单峰函数。那么就直接用三分套三分就可以求解了，复杂度。 con...

三分

2021-08-23

0 478

2021牛客暑期多校训练营5 D、Double Strings 来自专栏

题目大意给你两个字符串，长度在级别，询问在两者的全部子序列中，长度相等，并且的数量有多少个？ Solution 考点：相同子序列数量如果直接考虑，因为子序列并不知道第几个位置不同，所以这个并不好处理，但是我们一定可以把这个的子序列分成段。第一段：子序列前个字符都相同。第二段：第三段：剩余长...

相同子序列个数

2021-08-23

0 496

2021牛客暑期多校训练营5 C、Cheating and Stealing 来自专栏

题目大意你和对手进行乒乓球比赛，你们原本进行了局比赛，代表你赢下了第局，代表你输掉了第局。现在我可以操控这个比赛规则，让游戏赛制变成在赢下球制，也就是我在赢下球后，如果和对手比分差值大于等于我就拿下一个小分，否则就是对手拿下一个小分，如果差值为或者那么接着进行下一局，那么我在球赛制下，进行完局比...

模拟

2021-08-23

0 660

2021牛客暑期多校训练营5 B、Boxes 来自专栏

题目大意你有个盒子，每个盒子内存在可能有黑球和白球中的一种，打开每个盒子都有一个代价，你还有一次询问裁判的机会，当然询问裁判代价为，你需要告诉裁判这个盒子每个盒子里面的球颜色，你需要花费的最小代价是多少？ Solution 考点：思维首先我们不询问裁判的话，我们就要把个盒子全部打开，代价为如果...

2021-08-21

2 563

2021牛客暑期多校训练营4 来自专栏

B、Sample Game 题目大意你有一个随机数生成器，他会随机生成到之间某个数，生成的概率为。现在分为大体步操作：随机生成一个。如果这个是已经生成的数中最大的，返回步骤一继续生成新的数，否则进入步骤三游戏结束，本局游戏的得分为生成序列的长度的平方。现在要你求出这局游戏的得分期...

2021暑假多校训练营

2021-08-20

0 880

2021牛客暑期多校训练营4 H、Convolution 来自专栏

题目大意题目重新定义了运算符：并且给出长度为的，以及常数，定义我们需要求解的异或和是多少？ Solution 参考题解我们优先就要转换这个符号的定义，不然这个题目就没办法下手了。从质因数幂次的关系转换到和他们对应之间的关系就更加容易处理这个关系式了。那么我们重新写出的定义式我们考虑...

2021-08-20

1 541

2021牛客暑期多校训练营4 G、Product 来自专栏

题目大意给出，你要构造的序列，对于其中一个序列来说他的贡献是，现在要你求出全部可能的序列贡献之和是多少？ Solution 考点：动态规划+容斥原理+组合数意义我们首先要推出下面这样的一个式子，可以看出这是个球分成组的可能方案数，那么总的方案数就是，即每个球都可能在每一组。好，我们回来看题...

组合数动态规划容斥原理

2021-08-20

0 658

2021牛客暑期多校训练营4 F、Just a joke 来自专栏

题目大意和两人在进行游戏，每轮游戏操作的玩家可以选择图中的一条边删去，或者找到图中的一棵树删去，最后无法进行操作的玩家就输掉了这局比赛，这张图是有个点条边的无向图。 Solution 我们分别考虑每个操作的势能函数（这个名词是讲题大佬直播的时候瞎编的）。删边：，是删掉的点数，是删掉的边数，任何时...

2021-08-20

0 656