walkalone

题解

/ 注册

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

牛客多校第六场题解

C Delete Edges 题意：给定一个由个点组成的完全图，每次可以选择三个点，如果边均存在，则删去这三条边。求一种构造可以不断的进行这样的操作使得最后剩下来的边数不超过。解法：我们需要删掉的边总数至少为。一开始我们可以有一个朴素的想法：找一个点出来，剩下的点两两配对，这样构成三...

2021-08-11

2 755

牛客多校第五场题解

B Boxes 题意：有个盒子，每个盒子中装有黑球白球概率均为。打开第个盒子所需代价为。现在有一个机会，使用的代价知晓剩余盒子中黑球个数，问使用最优策略开盒子直到直到全部盒子装球颜色情况的期望最小代价。解法：显然询问盒子中有几个黑球这个策略一定只会用一次：第二次用的答案一定可以通过...

2021-08-11

0 579

牛客多校第四场题解

B Sample Game 题意：使用一个不等概率的随机数生成器，如果当前这一轮摇出来的数比之前摇出来的数都大或者等，游戏继续；否则终止游戏，其得分为轮数的平方。问得分的期望。解法：如果游戏不结束，那么我们生成出来的序列一定形如：，当然中间有些数可能不取。那么我们可以考虑构造一个多项式函数（...

2021-08-11

0 721

牛客多校第三场题解

B Black and white 题意：给定一个的全白方阵，每个小方格有一个点权，先要将其全部染黑，对于方格其染黑代价为。若对于某一个方格，存在另外一行一列满足均已被染色，则当前无条件染色。问最小全部染黑代价。解法：一个非常常见的方法是将点化边，边化点。对于每一横行和纵行，都认...

2021-08-11

0 609

牛客多校第二场题解

B Cannon 题意：有一个两行、无限长的棋盘，第一行有个炮，第二行有个炮，求依次发生次吃炮事件的方案总数。 Subtask 1：无限制。 Subtask 2：考虑两行的执行顺序。解法：考虑有个炮的情况。那么发生一次吃炮事件的方案数为，由此可以推出发生次吃炮事件的方案数为 ...

2021-08-11

1 681

牛客多校第一场题解

G Game of Swapping Numbers 题意：给定两个序列，可以对进行恰好次交换，最大化。解法：先简化该问题，若不计交换次数，即允许任意排列，最大答案为多少？考虑每一位上对答案的贡献。若，则，反之等于。可以注意到在这个操作中，与各添加了一个正负号。那么进而...

2021-08-11

0 575