算法：UVa 12174 - Shuffle

算法：UVa 12174 - Shuffle2014-03-17 csdn博客 shuangde800【题目大意】

你在听音乐播放器，它采用随机播放形式。随机播放的原理时先随机产生一个 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
", ans）;}return 0;}

查看本栏目更多精彩内容：http://www.bianceng.cn/Programming/sjjg/