子序列 NYOJ （尺取法+队列+hash）（尺取法+离散化）

子序列

时间限制：3000 ms | 内存限制：65535 KB

难度：5

描述

给定一个序列，请你求出该序列的一个连续的子序列，使原串中出现的所有元素皆在该子序列中出现过至少1次。

如2 8 8 8 1 1，所求子串就是2 8 8 8 1。

输入

第一行输入一个整数T(0<T<=5)表示测试数据的组数
每组测试数据的第一行是一个整数N(1<=N<=1000000)，表示给定序列的长度。
随后的一行有N个正整数，表示给定的序列中的所有元素。
数据保证输入的整数都不会超出32位整数的范围。

输出

对于每组输入，输出包含该序列中所有元素的最短子序列的长度

样例输入

2

5

1 8 8 8 1

6

2 8 8 8 1 1

样例输出

2

5

来源

POJ月赛改编

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<sstream>

#include<algorithm>

#include<queue>

#include<deque>

#include<iomanip>

#include<vector>

#include<cmath>

#include<map>

#include<stack>

#include<set>

#include<fstream>

#include<memory>

#include<list>

#include<string>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

#define MAXN 1000044

#define INF 1000000009

#define eps 0.00000001

/*

利用队列从前到后遍历数组元素

当前元素未在之前出现过，更新ans为队列元素个数

当前元素在之前出现过

    如果当前队首元素在hash表中出现次数多于1次，pop

*/

int T, n, aim, a[MAXN],b[MAXN];

typedef struct Hashnode

{

    int data;

    int cnt;

    struct Hashnode* next;

}*List;

typedef struct Hashtb

{

    List* L;

}*HashTable;

HashTable Init()

{

    HashTable H = (HashTable)malloc(sizeof(Hashtb));

    H->L = (List*)malloc(sizeof(List)*MAXN);

    for (int i = ; i < MAXN; i++)

    {

        H->L[i] = (List)malloc(sizeof(Hashnode));

        H->L[i]->data = ;

        H->L[i]->cnt = ;

        H->L[i]->next = NULL;

    }

    return H;

}

int Hash(int x)

{

    return x%MAXN;

}

void clear(HashTable H)

{

    for (int i = ; i < MAXN; i++)

    {

        H->L[i]->data = ;

        H->L[i]->cnt = ;

        H->L[i]->next = NULL;

    }

}

List find(int x, HashTable H)

{

    List l = H->L[Hash(x)];

    List p = l->next;

    while (p != NULL&&p->data != x)

        p = p->next;

    return p;

}

int cnt(int x, HashTable H)

{

    List p = find(x, H);

    if (p == NULL)

        return -;

    else

    {

        if (p->cnt > )

        {

            p->cnt--;

            return p->cnt + ;

        }

        else

            return p->cnt;

    }

}

bool Insert(int x, HashTable H)

{

    List l = H->L[Hash(x)];

    List p = find(x, H);

    if (!p)

    {

        List tmp = (List)malloc(sizeof(Hashnode));

        tmp->data = x;

        tmp->cnt = ;

        tmp->next = l->next;

        l->next = tmp;

        return false;

    }

    else

    {

        p->cnt++;

        return true;

    }

}

int main()

{

    scanf("%d", &T);

    HashTable H = Init();

    while (T--)

    {

        clear(H);

        scanf("%d", &n);

        int ans = INF,tmp;

        queue<int> q;

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

        {

            scanf("%d", &tmp);

            if (!Insert(tmp,H))

            {

                q.push(tmp);

                ans = q.size();

            }

            else

            {

                q.push(tmp);

                while (!q.empty()&&cnt(q.front(),H) > )

                {

                    q.pop();

                }

                ans = min(ans,(int)q.size());

            }

        }

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

    }

    return ;

}

做法2 离散化+ 尺取

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<sstream>

#include<algorithm>

#include<queue>

#include<deque>

#include<iomanip>

#include<vector>

#include<cmath>

#include<map>

#include<stack>

#include<set>

#include<fstream>

#include<memory>

#include<list>

#include<string>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

#define MAXN 1000044

#define INF 1000000009

#define eps 0.00000001

int T, n;

int a[MAXN], b[MAXN], cnt[MAXN];

int bsearch(int l, int r, int aim)

{

    while (l <= r)

    {

        int mid = (l + r) / ;

        if (b[mid] == aim)

        {

            return mid;

        }

        else if (b[mid] < aim)

        {

            l = mid + ;

        }

        else

            r = mid - ;

    }

}

int main()

{

    scanf("%d", &T);

    while (T--)

    {

        scanf("%d", &n);

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

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

        memcpy(b, a, sizeof(a));

        memset(cnt, , sizeof(cnt));

        sort(b, b + n);

        int size = unique(b, b + n) - b;

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

        {

            a[i] = bsearch(, size, a[i]);

        }

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

        //    cout << a[i] << endl;

        int ans = n, l = , sum = ;

        cnt[a[]] = ;

        for (int r = ; r < n; r++)

        {

            while (sum == size)

            {

                cnt[a[l]]--;

                if (cnt[a[l]] == ) sum--;

                l++;

                ans = min(ans, r - l + );

            }

            if (cnt[a[r]] == ) sum++;

            cnt[a[r]]++;

        }

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

    }

    return ;

}

巴特西

子序列 NYOJ （尺取法+队列+hash）（尺取法+离散化）

子序列

最新文章

热门文章

巴特西

子序列 NYOJ （尺取法+队列+hash） （尺取法+离散化）

子序列

最新文章

热门文章

子序列 NYOJ （尺取法+队列+hash）（尺取法+离散化）