当前位置：首页 > news >正文

UVa11572 Unique Snowflakes（尺取法）

news 来源：原创 2024/5/6 22:32:27

题目链接

在这里插入图片描述
1.题目大意：输入一个序列，找到一个最长的连续子序列，使得该子序列中没有相同的元素

2.此题是尺取法，但是稍微麻烦。关于尺取法，罗勇军老师的尺取专题写的非常详细，强烈建议学习。对于左右两个指针，首先固定左指针，使右指针不断向后，直到出现和当前序列不同的元素或者到达序列尾部，对于判断是否可以延伸，我们使用set判重。LRJ老师在书上关于正确性的解释有点不太好懂，我也想了很久，应该是如果当前序列有n个不同的数，第n+1个数是重复的，那么将左指针不断右移，并将它指向的数删除，直到删到了和第n+1个数相同的数，中间序列长度一直在变化，也就是相当于我们对前n个数的所有子序列的情况都判断了一次

3.除了使用set之外，使用数组last记录下标i的上一个“相同元素”下标，初始时如果数组从0下标开始，那么所有第一次出现的数都设置为-1（如果是1的话应该小于1的数都行），那么判断是否延伸就变成了它的上一个位置是否在区间内，使用hash_map更快

方法一

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
const int maxn=1e6+10;
int a[maxn];
set<int> s;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        s.clear();
        for(int i=1;i<=n;i++) cin>>a[i];
        int l=1,r=1,ans=1;
        while(r<=n){
            while(r<=n && !s.count(a[r])) s.insert(a[r++]);
            ans=max(ans,r-l);  //实际上这里取set的size也是正确的
            s.erase(a[l++]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

方法二

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int maxn=1e6+10;
unordered_map<int,int> mp;
int last[maxn];

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n,x;
    cin>>t;
    while(t--){
        cin>>n;
        mp.clear();
        for(int i=0;i<n;i++){
            cin>>x;
            if(!mp.count(x)) last[i]=-1;
            else last[i]=mp[x];
            mp[x]=i;
        }
        int l=0,r=0,ans=1;
        while(r<n){
            while(r<n && last[r]<l) r++;
            ans=max(ans,r-l);
            l++;
        }
        cout<<ans<<endl;
    }
    return 0;
}