当前位置:首页 > 枚举 > 正文
SSOJ4390音乐
93+

题目大意:n首音乐,共听了m首,每一个阶段听n首,正常情况下,每阶段音乐各不相同,请问这m首音乐前面,可能听了多少首音乐?答案是0~n-1,请输出有多少个答案。

题目描述

LYK喜欢听音乐,总共有n首音乐,有m个时刻,每个时刻LYK会听其中一首音乐,第i个时刻会听第ai首音乐。它给自己定了一个规定,就是从听音乐开始,听的每连续n首音乐都是互不相同的。例如当n=3时,从听歌开始,123321就是一个合法的顺序(此时LYK听了两轮歌,分别是123和321,每一轮的歌都是互不相同的),而121323就是一个不合法的顺序(LYK也听了两轮歌,第一轮中121存在听了两次相同的歌)。我们现在只截取其中一个片段,也就是说并不知道LYK之前已经听了什么歌。因此121323也仍然可以是一个合法的顺序,因为LYK之前可能听过3,然后再听121323,此时LYK听了三轮歌,分别是312,132和3。
现在LYK将告诉你这m个时刻它听的是哪首歌。你需要求出LYK在听这m首歌之前可能听过的歌的不同方案总数(我们认为方案不同当且仅当之前听过的歌的数量不同)。LYK向你保证它之前听过的歌的数量是在0~n-1之间的。因此你输出的答案也应当是0~n中的某个整数(答案是0表示LYK记错了,没有一个合法的方案)。

输入

第一行两个数n,m。
第二行m个数表示ai。

输出

一个数表示答案。

样例输入

输入样例1
4 10
3 4 4 1 3 2 1 2 3 4
输出样例1
1
样例解释1:LYK之前一定只听过2首歌(12或者21),这样可以分成3部分分别是34,4132,1234,每一部分都没有出现相同的歌。对于其它情况均不满足条件。 

样例输出

输入样例2
6 6
6 5 4 3 2 1
输出样例2
6
样例解释2:LYK之前听过0~5首歌的任意几首都是有可能满足条件的。 

提示

对于50%的数据n,m<=1000。
对于100%的数据1<=n,m<=100000,1<=ai<=n。
其中均匀分布着n < m以及n>=m的情况。
提示:
LYK知道这个题目很长,但为了便于理解已经加了很多注释了……建议没看懂的同学们再重新看一遍…

解题思路

暴力枚举前面听了多少首音乐,然后判断连续的n个是否有重复即可。为了避免超时,可以预处理出每个音乐往右不重复听音乐的右边界,这样只需要判断每个阶段第一首音乐是否满足要求即可,如果第一首满足要求,第二是必然满足。除了第一阶段,其他阶段均需要满足不重复音乐数量达到n!

程序实现

SSOJ4390音乐:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter