竞赛讨论区 > 浙科第17届大学生程序设计竞赛 部分题解 B/C/I/K

浙科第17届大学生程序设计竞赛 部分题解 B/C/I/K

头像
nayix
编辑于 2020-09-14 23:52:20 APP内打开
赞 0 | 收藏 0 | 回复1 | 浏览365

B

题意就是让你求面积最大的连通块中其外围一周的长度(我将其定义为外周长)。我们将每个连通块染成不同的颜色,记下面积最大的连通块的颜色(题目保证不超过5)。对于一个连通块,要知道其外周长,我们不妨将其转换为求其外部的方块的内周长。复杂度o(5 * n * m),注意用bfs替代dfs来防止堆栈溢出即可(hulean成功hack标程,已加强数据并更新标程)。

AC代码

C

当T=1时你会获得相应数量翻倍卡,当T=2时代表你进行了一场游戏,这场游戏中你的得分为X(注意题目范围中X可能为负数)。对于每次询问,我们假设现在手中有A张翻倍卡,我们进行的游戏中有B场获得分数为正。则该次询问答案为进行的所有游戏获得分数和+获得分数前min(A, B)大的分数和。使用平衡数或者权值线段树维护即可。复杂度o(nlogn),题目数据较水,可能有些复杂度比较高的也能过。

AC代码

K

由于出题人每次都做不出状压,所以决定自己出一道状压。

题目给你N张卡片,M个奖励阶梯,求获得奖励最多的情况下能剩下多少钱。

考虑状压,对于某种选择,你选择第x张卡片和你选择第y张卡片的先后顺序只会影响你能不能选择或者你的余额多少,并不会影响你获得的奖励多少。所以只需要预处理出每种状态会获得的奖励再跑一遍状压即可。复杂度o(2^N + MlogM),其中MlogM是对奖励阶梯排序的复杂度。

AC代码

I

题目要求我们求 (1 * 数X所在堆中数的积) 是 (1 * 数Y所在堆中数的积)。显然当X或Y已经被删除时,这个S就是1。考虑对数,用浮点数加法来替代高精度乘法,然后再使用启发式合并就可以AC了(当然有条件的同学可以再考虑下左偏树)。

AC代码

1条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐