也许是 card 最全部分分(?)
2026-11-14 18:10:16
发布于:江西
题意:
局游戏,对于每一轮游戏,做如下操作:
牌从第 张开始打出( 是轮数 )
打出一张点数为 的牌时:
若桌面上没有点数为 的牌,就将这张牌放在最右端
没有,就收走桌面上点数为 的牌及其右侧的所有牌,再把这张牌放在最右端
求:在所有 轮游戏中,有多少局结束时桌面上留有点数为 的牌
1.
不会枚举,模拟?
不要紧,只要看懂题了就行,情况最多只有 (实际少于这个),可以手算
时间复杂度:
2.
这时,需要一些模拟了
维护一个数组,每轮游戏开始时清空
对于每次打出的牌,首先,遍历数组,看看在不在里面,然后按题意模拟
时间复杂度:
3.
沿用 的方法,但需要加快模拟
使用一个栈和一个 数组
一个数出栈,入栈时,在 里标记
这样就能 判断在不在栈里
对于一轮游戏,一个数最多入栈出栈 次
所以 轮只有 的时间复杂度
时间复杂度:
4.特殊性质 A 且
A mean: 数组不降
观察一下,当 数组不降时,唯一有可能在栈里面的只有栈顶
这样就能 判断在不在栈里
沿用 的时间复杂度分析,可得时间复杂度为
5.
首先,对所有的游戏,首尾总是会被保留
接下来,你可以发现,当 时,只保留首尾
why?
首先,首尾不相同时,最多,也只有 1 2
首尾相同时,中间的 都会被 消掉(或相反)
所以,只需要统计每个数的出现次数,然后把 的出现次数设为 即可
6.特殊性质 B
B mean: 数组只有 个位置是与下一位不同的
可以注意到一个结论:当 时,第 轮和第 轮游戏保留的数字完全一样
简单模拟一下,在第 轮时,第 步, 被消,只剩 ,这确实和第 轮第 步一样
把一样的压缩一下,就最多有 个数
沿用 的方法,时间复杂度为
7.
特殊性质 B 给了我们一些启发,假如是 a b a 或者 a b c a 那种呢?
其实,也是一样的
不管中间怎么消,假如以 开头,且 ,那么 和 最终结果一样
那么,我们就可以只统计最后一个的值,看起来是 不能过的
但是这没事,我们再思考思考,假如 已经是最后一个,那么 这个位置是不会被以 开始的消掉的,依然可以去到以 的最后一个为结尾
这样,时间复杂度就有
8.特殊性质 A
A mean: 数组不降
观察一下,这时候,每一个数都不会没有,因为能消掉 的只有
所以你可以倒序处理,这时时间复杂度为
真想不到非正解做法了
全部评论 2
我只拼出72
1周前 来自 浙江
0%%%你J一定380+了吧
1周前 来自 上海
0并没有()
1周前 来自 江西
0PPP
1周前 来自 江西
0P在哪
1周前 来自 上海
0








有帮助,赞一个