UVA11572_Unique Snowflakes

超级经典的题目,扫描区间,滑动窗口

对这题目的最大感受就是,单独看这个题目,其实不难,但是很多我感觉挺难或者没做出来的题目,都是由这些若干个经典的算法组合而成的

滑动窗口便是一个典型的例子!!!!遇到过好几道用到滑动窗口的题目

而本题则赤裸裸的滑动窗口

题意:

输入一个长度为n的序列A,找一个尽可能长的子序列使他们之间无重复元素

思路:

第一步,自己暴力模拟

第二步,找规律,尝试着状态转移

第三步,修正,实现

首先不能重复,那么我们先假设区间[l, r] 无重复元素,那么加入一个元素a[r+1],会出现什么变化呢???

如果原来的区间没有a[r+1]那么新的区间仍然是一个无重复元素的区间,否则的话,移动左边界,一直到使他们没有重复

这题wa了几发,,原因是在循环的时候,边界判断错误

实现的话就用cnt[maxn]来记录区间里面的元素信息,右边界右移cnt[x]++,左边界则是cnt[x]--;

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<string>

#include<queue>

#include<cstdlib>

#include<algorithm>

#include<stack>

#include<map>

#include<queue>

#include<vector>

#include<set>

using namespace std;

const int maxn=1e6+5;

int A[maxn];

int main(){

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int n,t;

    cin>>t;

    while(t--){

        cin>>n;

        int r,l,ans;ans=l=r=0;

        for(int i=0;i<n;i++) cin>>A[i];

        set<int>s;

        while(r<n){

            while(r<n&&!s.count(A[r])) s.insert(A[r++]);

            ans=max(ans,r-l);

            s.erase(A[l++]);

        }

        cout<<ans<<endl;

    }

    return 0;

}

巴特西

UVA11572_Unique Snowflakes

最新文章

热门文章