UVa 12174 - Shuffle

题目链接

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=513&page=show_problem&problem=3326

【题目大意】

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

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

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

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

【思路】

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

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

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

【代码】

/*
 *
 * UVa 12174 - Shuffle
 *
 */
#include<iostream>
#include<cstdio>
#include<cstring>
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<s && i<n && !cnt[arr[i]]; ++i){
        first[i+1] = true; 
        cnt[arr[i]] = 1;
    }
    if(i==n && i<s && first[i]){
        while(i++<s)
            first[i] = true;
    }

    memset(cnt, 0, sizeof(cnt));
    ok[n] = true;
    int count=0;

    for(int i=n-1; i>=0; --i){

        if(cnt[arr[i]]++ == 0){
            ++count;
        }

        if(count == s || n-i<s&&n-i==count){
            ok[i] = true;
        }

        if(i+s-1<n){
            if(--cnt[arr[i+s-1]] == 0){
                --count;
            }
        }
    }
}

bool check(int st){
    while(st < n){
        if(!ok[st]) return false;
        st += s; 
    }
    return true;
}

int main(){
    int nCase;
    scanf("%d", &nCase);
    while(nCase--){
       

        scanf("%d%d", &s, &n);

        for(int i=0; i<n; ++i)
            scanf("%d", &arr[i]);

        init();
        int ans = 0;
        for(int i=0; i<s; ++i)
            if(first[i] && check(i))
                ++ans;
        printf("%d\n", ans);

    }
    return 0;
}