首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
lalalaterraria
获赞
29
粉丝
0
关注
2
看过 TA
0
男
华南理工大学
2022
算法工程师
IP属地:未知
暂未填写个人简介
私信
关注
拉黑
举报
举报
确定要拉黑lalalaterraria吗?
发布(4)
刷题
lalalaterraria
2020-07-27 21:24
已编辑
算法工程师
2020牛客暑期多校训练营(第六场)A African Sort
A African Sort题意: 给定排列 p,每次可以选一个下标集合等概率打乱包含的数并花费集合大小的代价,求给 p 排升序最优策略下最小代价的期望,对 998244353 取模 做法:一个permutation可以看成若干个环(i连p[i]),显然不存在大小不为1的环即为排序完成。那么对所有大小不为1的环进行随机排序操作,记对大小为n的环进行操作至全部有序的期望花费为f(n)。 对于大小为n的环,随机打乱一共有n!种情况。可以发现,指定i个位置组成一个环,有C(n,i)*(i-1)!*(n-i)!种情况。C(n,i)为指定i个位置的方案数,(i-1)!为指定的i个位置能组成多少种不同的环...
0
点赞
评论
收藏
转发
lalalaterraria
2020-07-26 15:03
已编辑
算法工程师
2020牛客暑期多校训练营(第五场)G Greetings Souvenir
G Greetings Souvenir 再更新一下,造了一些hack数据对拍,拿了三份代码对拍,给出几份hack数据输出彼此之间都有一致的数据也有不一致的,说明至少四支队伍可以hack掉三只队伍!!!! 61 2 1 2 56 5 2 1 2 3顶不住也给我顶:6空白:5吃顿好的:6ContestinSurgery :段错误 66 4 5 2 13 1 6 2 5 4顶不住也给我顶:4空白:6吃顿好的:6ContestinSurgery :段错误 81 2 2 2 2 1 73 2 7 3 2 3 5 1顶不住也给我顶:6空白:6吃顿好的:8ContestinSurgery :段错误 网络流...
0
点赞
评论
收藏
转发
lalalaterraria
2020-05-23 12:20
已编辑
算法工程师
牛客练习赛64 - 宝石装箱
这里给出一种容斥+多项式的做法 复杂度为是n^2/2 大家一般是容斥+背包啊,我觉得这里多项式也蛮好写的。 容斥应该不用多说了,设为第i个球合法的情况。套一套下面两个公式。 我们要求的是第二个公式的左半,用第一个公式带入第二个公式的右边第二项。 所得公式的右半边从左向右数第i项(不考虑符号),表示n个球里面,任选i个不球,这i个球不合法,其他球任意(可合法也可不合法)的方案数。 其他球任意的方案数是种,那么剩下的i个球不合法的方案数是多少嘞。用下生成函数的方法来表示,第i个箱子有cnt[i]个候选的不合法球,可以选一个不合法球,生成函数表示就是(1+cnt[i]*x),全部n个箱子对应的生...
0
点赞
评论
收藏
转发
lalalaterraria
2020-05-11 19:36
已编辑
算法工程师
硬币游戏Ⅲ做题心得
研究了一天终于会写了,故在自己研究并ac后简略提供下解题思路。 官方题解中,"这样我们就转化为k堆独立的硬币问题"是最让我迷惑的地方,这里错了,应改为"转化成n堆独立的硬币问题"。IOI2009中国集训队论文 有一篇关于SG函数的论文中提出的翻硬币问题就是本题的背景。 翻硬币问题可以转化为若干0加一个1的串的子游戏,而这类题目属于Multi-SG问题,每次翻硬币等价于把一个子游戏又分为更多的子游戏,子游戏的sg函数为所有子子游戏的异或和。 比如样例1001001001,可以转化为四个子问题。1000100000010000000001所以只需要算出上述四个子问题的SG函数异或和是否为0即可 那...
0
点赞
评论
收藏
转发
1
工具箱
TA的圈子
暂未加入圈子
TA的圈子
TA的笔记
暂无笔记
TA的笔记
登录
0
天
已登录
0
天
连续登录
0
人
今日访客
牛客网
牛客企业服务