题意：
你正在使用的音乐播放器有一个所谓的乱序功能，即随机打乱歌曲的播放顺序。
假设一共有s首歌，则一开始会给这s首歌随机排序，全部播放完毕后再重新随机排序、继续播放，依此类推。
注意，当s首歌播放完毕之前不会重新排序。这样，播放记录里的每s首歌都是1～s的一个排列。
给出一个长度为n（1≤s，n≤100000）的播放记录（不一定是从最开始记录的），你的任务是统计下次随机排序所发生的时间有多少种可能性。
例如，s=4，播放记录是3, 4, 4, 1, 3, 2, 1, 2, 3, 4，不难发现只有一种可能性：前两首是一个段的最后两首歌，后面是两个完整的段，因此答案是1；
当s=3时，播放记录1, 2, 1有两种可能：第一首是一个段，后两首是另一段；前两首是一段，最后一首是另一段。答案为2。
比较难的滑动窗口 还没彻底搞懂 细节多
LRJ
// UVa12174 Shuffle // Rujia Liu #include<iostream> #include<vector> using namespace std; const int maxn = 100000 + 5; int s, n, x[maxn*3], cnt[maxn], ok[maxn*2]; int main() { int T; cin >> T; while(T--) { cin >> s >> n; // add s "-1" to the left/right of orriginal sequence // so we don't have to worry about negative subscript or wrapping round fill(x, x+n+2*s, -1); for(int i = 0; i < n; i++) cin >> x[i+s]; int tot = 0; // how many different integers in current sliding window fill(cnt+1, cnt+s+1, 0); // cnt[i] is the number of occurrence of i in the current sliding window fill(ok, ok+n+s+1, 0); // ok[i] = 1 iff the i-th sliding window didn't have duplicate numbers // compute "ok" array for(int i = 0; i < n+s+1; i++) { if (tot == s) ok[i] = 1; // complete window if (i < s && tot == i) ok[i] = 1; // incomplete windows on the left side if (i > n && tot == n+s-i) ok[i] = 1; // incomplete windows on the right side // update cnt and tot for the next sliding window if (i == n+s) break; // no more sliding windows, so we stop here if (x[i] != -1 && --cnt[x[i]]==0) tot--; // remove the first one if (x[i+s] != -1 && cnt[x[i+s]]++==0) tot++; // add the next one } // check each possible answer int ans = 0; for(int i = 0; i < s; i++) { int valid = 1; for (int j = i; j < n+s+1; j += s) if(!ok[j]) valid = 0;; if(valid) ans++; } if(ans == n+1) ans = s; // special case cout << ans << " "; } return 0; }
#include<iostream> #include<cstring> #include<set> using namespace std; const int N = 1e5 + 5; int s, n, a[N], vis[N]; bool flag[N]; int ans; void init() { cin >> s >> n; int num = 0; for (int i = 0; i < n; i++) { cin >> a[i]; if (i < s) { //对前面的s个进行分析 if (vis[a[i]]) num++; //统计前s个中重复的数字 vis[a[i]]++; } } for (int i = 0; i < n; i++) { //如果num=0，说明前s个中没有重复的数字，那么第一个数字可以作为循环的开始 if (num == 0) flag[i] = true; //窗口开始滑动 if (vis[a[i]] == 2) num--; //如果此时最左边的数为重复了的数，num需要减1 vis[a[i]]--; int k = i + s; //新数字进入滑动窗口 if (k >= n) continue; if (vis[a[k]]) num++; //如果已经出现过 vis[a[k]]++; } } bool judge(int x) { for (int i = x; i < n; i += s) if (!flag[i]) return false; return true; } void solve() { memset(vis, 0, sizeof(vis)); ans = 0; for (int i = 0; i < s; i++) { if (judge(i)) ans++; if (i >= n) continue; //从左往右依次遍历，如果当前a[i]前面已经出现过，那么前面必须会有开头，此时必须结束循环 if (vis[a[i]]) break; vis[a[i]]++; } } int main() { //freopen("D:\txt.txt", "r", stdin); int t; cin >> t; while (t--) { memset(flag, 0, sizeof(flag)); memset(vis, 0, sizeof(vis)); init(); solve(); cout << ans << endl; } return 0; }