题意：
你在听音乐播放器，它采用随机播放形式。随机播放的原理时先随机产生一个1~n的排列，然后就按这个排列顺序播放歌曲。播放完这序列的所有歌曲以后，再次随机生成一个1～n的排列，再继续播放。
现在给你一个播放历史记录，这个历史记录是不完整的，以为它是开始记录时，已经有些歌曲播放过了而没有记录到。
现在给你一段从某个时刻开始的播放音乐的历史记录，以及播放器里一共有多少首歌。
问历史记录中第一首歌可能是某个随机列表中的第几首，总共有多少种可能？
思路：
滑动窗口，依次遍历，检查每个数能否作为循环的开始。
1 #include<iostream> 2 #include<cstring> 3 #include<set> 4 using namespace std; 5 6 const int N = 1e5 + 5; 7 8 int s, n, a[N], vis[N]; 9 bool flag[N]; 10 int ans; 11 12 void init() { 13 cin >> s >> n; 14 int num = 0; 15 for (int i = 0; i < n; i++) { 16 cin >> a[i]; 17 if (i < s) { //对前面的s个进行分析 18 if (vis[a[i]]) num++; //统计前s个中重复的数字 19 vis[a[i]]++; 20 } 21 } 22 23 for (int i = 0; i < n; i++) { 24 //如果num=0，说明前s个中没有重复的数字，那么第一个数字可以作为循环的开始 25 if (num == 0) flag[i] = true; 26 27 //窗口开始滑动 28 if (vis[a[i]] == 2) num--; //如果此时最左边的数为重复了的数，num需要减1 29 vis[a[i]]--; 30 31 int k = i + s; //新数字进入滑动窗口 32 if (k >= n) continue; 33 if (vis[a[k]]) num++; //如果已经出现过 34 vis[a[k]]++; 35 } 36 } 37 38 bool judge(int x) { 39 for (int i = x; i < n; i += s) 40 if (!flag[i]) return false; 41 return true; 42 } 43 44 void solve() { 45 memset(vis, 0, sizeof(vis)); 46 47 ans = 0; 48 for (int i = 0; i < s; i++) { 49 if (judge(i)) ans++; 50 if (i >= n) continue; 51 //从左往右依次遍历，如果当前a[i]前面已经出现过，那么前面必须会有开头，此时必须结束循环 52 if (vis[a[i]]) break; 53 vis[a[i]]++; 54 } 55 } 56 57 int main() { 58 //freopen("D:\\txt.txt", "r", stdin); 59 int t; 60 cin >> t; 61 while (t--) { 62 memset(flag, 0, sizeof(flag)); 63 memset(vis, 0, sizeof(vis)); 64 init(); 65 solve(); 66 cout << ans << endl; 67 } 68 return 0; 69 }
本来我是这样写的，结果不行，超时了。
1 #include<iostream> 2 #include<cstring> 3 #include<set> 4 using namespace std; 5 6 const int maxn = 100000 + 5; 7 int a[maxn]; 8 int vis[maxn],flag[maxn]; 9 10 int s, n, ans; 11 12 bool judge(int x) 13 { 14 for (int i = x; i < n; i += s) 15 if (!flag[i]) return false; 16 return true; 17 } 18 19 int main() { 20 //freopen("D:\\txt.txt", "r", stdin); 21 int t; 22 cin >> t; 23 while (t--) 24 { 25 memset(flag, 0, sizeof(flag)); 26 cin >> s >> n; 27 for (int i = 0; i < n; i++) 28 { 29 cin >> a[i]; 30 } 31 for (int i = 0; i < n; i++) 32 { 33 int ok = 0; 34 memset(vis, 0, sizeof(vis)); 35 for (int j = i; j < i + s && j < n; j++) 36 { 37 if (vis[a[j]]) break; 38 vis[a[j]] = 1; 39 if (j == i + s - 1 || j==n-1) ok = 1; 40 } 41 if (ok) flag[i] = 1; 42 } 43 ans = 0; 44 memset(vis, 0, sizeof(vis)); 45 for (int i = 0; i < s; i++) 46 { 47 if (judge(i)) ans++; 48 if (i >= n) continue; 49 if (vis[a[i]]) break; 50 vis[a[i]] = 1; 51 } 52 cout << ans << endl; 53 } 54 return 0; 55 }
原文：http://www.cnblogs.com/zyb993963526/p/6357707.html