lalalaterraria
lalalaterraria
全部文章
分类
题解(4)
归档
标签
去牛客网
登录
/
注册
lalalaterraria的博客
全部文章
(共4篇)
2020牛客暑期多校训练营(第六场)A African Sort
A African Sort题意: 给定排列 p,每次可以选一个下标集合等概率打乱包含的数并花费集合大小的代价,求给 p 排升序最优策略下最小代价的期望,对 998244353 取模 做法:一个permutation可以看成若干个环(i连p[i]),显然不存在大小不为1的环即为排序完成。那么对所有大...
2020-07-27
5
630
2020牛客暑期多校训练营(第五场)G Greetings Souvenir
G Greetings Souvenir 再更新一下,造了一些hack数据对拍,拿了三份代码对拍,给出几份hack数据输出彼此之间都有一致的数据也有不一致的,说明至少四支队伍可以hack掉三只队伍!!!! 61 2 1 2 56 5 2 1 2 3顶不住也给我顶:6空白:5吃顿好的:6Contest...
2020-07-25
5
814
牛客练习赛64 - 宝石装箱
这里给出一种容斥+多项式的做法 复杂度为是n^2/2 大家一般是容斥+背包啊,我觉得这里多项式也蛮好写的。 容斥应该不用多说了,设为第i个球合法的情况。套一套下面两个公式。 我们要求的是第二个公式的左半,用第一个公式带入第二个公式的右边第二项。 所得公式的右半边从左向右数第i项(不考虑符号),表...
2020-05-23
0
644
硬币游戏Ⅲ做题心得
研究了一天终于会写了,故在自己研究并ac后简略提供下解题思路。 官方题解中,"这样我们就转化为k堆独立的硬币问题"是最让我迷惑的地方,这里错了,应改为"转化成n堆独立的硬币问题"。IOI2009中国集训队论文 有一篇关于SG函数的论文中提出的翻硬币问题就是本题的背景。 翻硬币问题可以转化为若干0加一...
2020-05-11
3
648