UVa 12174 – Shuffle [滑动窗口]




You are listening to your music collection using the shuffle function to keep the music surprising. You assume that the shuffle algorithm of your music player makes a random permutation of the songs in the playlist and plays the songs in that order until all songs have been played. Then it reshuffles and starts playing the list again.

You have a history of the songs that have been played. However, your record of the history of played songs is not complete, as you started recording songs at a certain point in time and a number of songs might already have been played. From this history, you want to know at how many different points in the future the next reshuffle might occur.

A potential future reshuffle position is valid if it divides the recorded history into intervals of length s (the number of songs in the playlist) with the rst and last interval possibly containing less than s songs and no interval contains a specic song more than once.








#include <bits/stdc++.h>
using namespace std;

const int maxn = 400000;
int s, n, v[maxn], cnt[maxn], no[maxn];

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        memset(cnt, 0, sizeof(cnt));
        memset(no, 0, sizeof(no));
        scanf("%d%d", &s, &n);
        for(int i = 0; i < s; ++i) {
            v[i] = 110000 + i;
            v[i+s+n] = 220000 + i;
        for(int i = 0; i < n; ++i)
            scanf("%d", &v[i+s]);
        int multi = 0;
        for(int st = 1; st < s + n; ++st) {
            int ed = st + s - 1;
            if(--cnt[v[st-1]] == 1)
            if(++cnt[v[ed]] == 2)
                no[st%s] = true;
        int res = 0;
        for(int i = 0; i < s; ++i)
            if(!no[i]) ++res;
        printf("%d\n", res);
    return 0;