當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

UVA - 12174 Shuffle （预处理+滑动窗口）

發布時間：2024/10/8 编程问答 24 如意码农

生活随笔收集整理的這篇文章主要介紹了 UVA - 12174 Shuffle （预处理+滑动窗口）小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

題意：已知歌單中的歌曲數目s，和部分的播放歷史，問下一首可能播放的歌曲種數。

分析：

1、按照歌單數目s，將播放歷史劃分為幾部分。

2、將播放歷史的n首歌曲之前加上s首歌曲，之后加上s首歌曲，為防止標號重復，分別將其標號為100001 + i和200001 + i。

3、枚舉這個新的序列中的每首歌，以s首為區間，區間開頭為i，結尾為s + i - 1，若該區間里的數字不唯一，則不可能以該區間為標準劃分，排除i%s這一劃分可能。

4、判斷區間里歌曲唯一的方法，記錄每首歌出現次數，進入區間則加1，離開區間則減1，若區間長為s，里面每首歌都出現過1次，則此時sum一定為0，區間內是一種可行的播放順序。

5、為排除之前s首和之后s首對歌曲唯一性判斷的影響，只要初始化成之前的歌曲出現次數-1后不為1，之后的歌曲出現次數+1后不為2即可。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define lowbit(x) (x & (-x))

const double eps = 1e-8;

inline int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 1e9 + 7;

const double pi = acos(-1.0);

const int MAXN = 300000 + 10;

const int MAXT = 10000 + 10;

using namespace std;

int a[MAXN];

map<int, int> mp;

bool ans[MAXN];

int s, n;

int solve(){

    int sum = 0;

    for(int i = 1; i < n + s; ++i){

        int et = s + i - 1;

        if(--mp[a[i - 1]] == 1) --sum;

        if(++mp[a[et]] == 2) ++sum;

        if(sum != 0) ans[i % s] = false;

    }

    int cnt = 0;

    for(int i = 0; i < s; ++i){

        if(ans[i]){

            ++cnt;

        }

    }

    return cnt;

}

int main(){

    int T;

    scanf("%d", &T);

    while(T--){

        mp.clear();

        memset(a, 0, sizeof a);

        memset(ans, true, sizeof ans);

        scanf("%d%d", &s, &n);

        for(int i = 0; i < s; ++i){

            a[i] = 100001 + i;

            ++mp[a[i]];

        }

        for(int i = 0; i < n; ++i){

            scanf("%d", &a[i + s]);

        }

        for(int i = 0; i < s; ++i){

            a[s + n + i] = 200001 + i;

        }

        printf("%d\n", solve());

    }

    return 0;

}

總結

以上是生活随笔為你收集整理的UVA - 12174 Shuffle （预处理+滑动窗口）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。