https://vjudge.net/problem/UVA-12174 題意：
你在聽音樂播放器，它采用随機播放形式。随機播放的原理時先随機産生一個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 }