题意:
nnn 局游戏,对于每一轮游戏,做如下操作:
牌从第 iii 张开始打出( iii 是轮数 )
打出一张点数为 kkk 的牌时:
若桌面上没有点数为 kkk 的牌,就将这张牌放在最右端
没有,就收走桌面上点数为 kkk 的牌及其右侧的所有牌,再把这张牌放在最右端
求:在所有 nnn 轮游戏中,有多少局结束时桌面上留有点数为 iii 的牌
1.N≤5,M≤2N \LE 5,M \LE 2N≤5,M≤2
不会枚举,模拟?
不要紧,只要看懂题了就行,情况最多只有 353^535 (实际少于这个),可以手算
时间复杂度: O(1)O(1)O(1)
2.N≤500,M≤200N \LE 500,M \LE 200N≤500,M≤200
这时,需要一些模拟了
维护一个数组,每轮游戏开始时清空
对于每次打出的牌,首先,遍历数组,看看在不在里面,然后按题意模拟
时间复杂度: O(n2m)O(n ^ 2m)O(n2m)
3.N≤5000,M≤3000N \LE 5000,M \LE 3000N≤5000,M≤3000
沿用 2.2.2. 的方法,但需要加快模拟
使用一个栈和一个 visvisvis 数组
一个数出栈,入栈时,在 visvisvis 里标记
这样就能 O(1)O(1)O(1) 判断在不在栈里
对于一轮游戏,一个数最多入栈出栈 111 次
所以 111 轮只有 O(n)O(n)O(n) 的时间复杂度
时间复杂度:O(n2)O(n^2)O(n2)
4.特殊性质 A 且 N≤5000,M≤3000N \LE 5000,M \LE 3000N≤5000,M≤3000
A mean: 数组不降
观察一下,当 aaa 数组不降时,唯一有可能在栈里面的只有栈顶
这样就能 O(1)O(1)O(1) 判断在不在栈里
沿用 3.3.3. 的时间复杂度分析,可得时间复杂度为 O(n2)O(n^2)O(n2)
5.M≤2M \LE 2M≤2
首先,对所有的游戏,首尾总是会被保留
接下来,你可以发现,当 m≤2m \le 2m≤2 时,只保留首尾
why?
首先,首尾不相同时,最多,也只有 1 2
首尾相同时,中间的 222 都会被 111 消掉(或相反)
所以,只需要统计每个数的出现次数,然后把 ana_nan 的出现次数设为 nnn 即可
6.特殊性质 B
B mean: 数组只有 499949994999 个位置是与下一位不同的
可以注意到一个结论:当 ai=ai+1a_i = a_{i + 1}ai =ai+1 时,第 iii 轮和第 i+1i + 1i+1 轮游戏保留的数字完全一样
简单模拟一下,在第 iii 轮时,第 222 步, aia_iai 被消,只剩 ai+1a_{i + 1}ai+1 ,这确实和第 i+1i + 1i+1 轮第 111 步一样
把一样的压缩一下,就最多有 500050005000 个数
沿用 3.3.3. 的方法,时间复杂度为 O(50002)O(5000^2)O(50002)
7.N≤2×105,M≤3000N \LE 2 \TIMES 10^5,M \LE 3000N≤2×105,M≤3000
特殊性质 B 给了我们一些启发,假如是 a b a 或者 a b c a 那种呢?
其实,也是一样的
不管中间怎么消,假如以 iii 开头,且 ai=aja_i = a_jai =aj ,那么 iii 和 jjj 最终结果一样
那么,我们就可以只统计最后一个的值,看起来是 O(nm)O(nm)O(nm) 不能过的
但是这没事,我们再思考思考,假如 iii 已经是最后一个,那么 i+1i + 1i+1 这个位置是不会被以 aia_iai 开始的消掉的,依然可以去到以 ai+1a_{i + 1}ai+1 的最后一个为结尾
这样,时间复杂度就有 O(m2)O(m^2)O(m2)
8.特殊性质 A
A mean: 数组不降
观察一下,这时候,每一个数都不会没有,因为能消掉 aia_iai 的只有 ai+1a_{i + 1}ai+1
所以你可以倒序处理,这时时间复杂度为 O(n)O(n)O(n)
N≤2×105,M≤105N \LE 2 \TIMES 10^5,M \LE 10^5N≤2×105,M≤105
真想不到非正解做法了