UVA - 11536 Smallest Sub-Array（尺取法）

题目：

思路：

读完题之后第一时间想到的是尺取法来做这个题，结果让自己写写崩了，还是练得少！！

到网上搜了一下学习了大佬的标记方法，用一个变量来判断是不是都已经出现，要比每次都判断一下快超多。

代码：

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define MAX 1e3

#define FRE() freopen("in.txt","r",stdin)

#define FRO() freopen("out.txt","w",stdout)

using namespace std;

typedef long long ll;

typedef pair<int, int> P;

const int maxn = ;

int a[maxn],vis[maxn];

int n,m,k;

void init(){

    memset(vis,,sizeof(vis));

    a[] = ,a[] = ,a[] = ;

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

        a[i] = (a[i-]+a[i-]+a[i-])%m+;

    }

}

int main(){

   // FRE();

    int kase=,T;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d%d",&n,&m,&k);

        init();

        if(k > m || k>n){

            printf("Case %d: sequence nai\n",++kase);

            continue;

        }

        int ans = ;

        int st=,en=,tot=;

        while(en <= n){

            int t = a[en++];

            vis[t]++;

            if(t<=k && vis[t]==) tot++;//标记区间个数get！！

            while(st<en && tot==k){

                ans = min(ans, en-st);

                t = a[st++];

                vis[t]--;

                if(t<=k && vis[t]==) tot--;//标记区间个数

            }

            //cout<<"en: "<<en<<"  st:  "<<st<<endl;

        }

        if(ans>n){

            printf("Case %d: sequence nai\n",++kase);

        }else{

            printf("Case %d: %d\n",++kase,ans);

        }

    }

    return ;

}