本文共 883 字，大约阅读时间需要 2 分钟。

【题目大意】

你在听音乐播放器，它采用随机播放形式。随机播放的原理时先随机产生一个1~n的排列，然后就按这个排列顺序播放歌曲。播放完这序列的所有歌曲以后，再次随机生成一个1～n的排列，再继续播放。

现在给你一个播放历史记录，这个历史记录是不完整的，以为它是开始记录时，已经有些歌曲播放过了而没有记录到。

现在给你一段从某个时刻开始的播放音乐的历史记录，以及播放器里一共有多少首歌。

问历史记录中第一首歌可能是某个随机列表中的第几首，总共有多少种可能？

【思路】

先进行预处理，用一个bool数组ok记录，ok【i】表示以第i个位置开始的连续s个数是不是都不相同的。

然后一次枚举第一首歌是第x首，先检查前s-x首歌是不是都不相同，这个也可以先预处理判断。

之后从第x开始，判断x，x+s，x+2*s……是不是都满足条件即可。

 【代码】

/* * * UVa 12174 - Shuffle * */#include
   
    #include
    
     #include
     
      using namespace std;typedef long long int64;const int INF = 0x3f3f3f3f;const int MAXN = 100010;int s, n;int arr[MAXN];int cnt[MAXN];bool first[MAXN], ok[MAXN];// 预处理inline void init(){    memset(first, 0, sizeof(first));    memset(ok, 0, sizeof(ok));    memset(cnt, 0, sizeof(cnt));    first[0] = true;    int i;    for(i=0; i
      =0; --i){        if(cnt[arr[i]]++ == 0){            ++count;        }        if(count == s || n-i
     
    
   

转载地址：http://wpzni.baihongyu.com/