ACGO首个AC作者的题解(我真的太棒了)(首个AC题解)
发表感言:
* 我草,满级入门题,我错了N次(战绩可查)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
正片开始了!
> 我呢,用的是VECTOR来解的题目,用链表更快,但我不会(应该是道模拟题目)
题目:
Nanae很喜欢和朋友玩游戏。虽然有时候看起来很无趣,今天Nanae发明一个新游戏叫LianLianKan。
这个游戏是在一个数字栈玩的,现在有一个数字栈,我们必须从顶部到底部连接和消除相同的一对元素。
你只能连接和消除与栈顶元素相同的元素,从栈里消除他们之后,所有的元素会下落。尽管这游戏好像非常有趣,但是事实上它真的非常无聊。
所以,为了证明我在Nanae的朋友里面是一个聪明人,Nanae加多了一条规则在游戏里面:对于每一个栈顶元素,它只能与距离小于6的相同的值元素连接和消除。在玩游戏之前,他想检查我是(题目后续我们也是不了解哈)
分析思路:
模拟一下,但我们不创建栈,因为栈无法便捷的删除元素,所以用vecotor,按顺序输入,在输入的过程中检查前6个是否有相同的,有则删除这个元素,如果全没有那么将这个数加入vector。
举个栗子:
* 就比如样例1,n = 2,数字为{1,1},那么先输入第一个数1,往前看6个数,但前面没有数字,不用管,直接加入vector,输入第二个数1,往前看6个数,首先检测到1,相等删除,然后就没有然后了,输入完成,判断是否为空,为空所以输出1
* 又比如样例2,n = 3,数字为{1,1,1},那么先输入第一个数1,往前看6个数,但前面没有数字,不用管,直接加入vector,输入第二个数1,往前看6个数,首先检测到1,相等删除,然后就没有然后了,输入第三个数1,但前面没有数字,不用管,直接加入vector,输入完成,判断是否为空,不为空所以输出0
那么,根据这种方法,就可以求解了,时间复杂度O(N2)O(N^2)O(N2)
答案如下:
不用开LONG LONG
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
动态数组(VECTOR)基本常用操作:
函数 栗子 效果 vector<数据类型> 动态数组名 vector<int> a 名定义名叫 a 的 整型 动态数组 动态数组名.push_back(x) a.push_back(1) 将1加入名叫a的动态数组中 动态数组名.erase(动态数组名.begin() + a) a.erase(a.begin() + 1) 删除a的动态数组的第一个元素 动态数组名.begin() a.begin() 获取名叫a的动态数组的第一个元素的索引 动态数组名.end() a.end() 获取名叫a的动态数组的最后一个元素之后的位置的索引 动态数组名.empty() a.empty()
检测名叫a的动态数组是否为空,为空返回true,不为空返回false 动态数组名.size() a.size() 获取名叫a的动态数组的元素个数(长度) 动态数组名.insert(动态数组名.begin() + a,b) a.insert(a.begin() + 1,2) 在名叫a的动态数组的索引1前插入2