本文共 1172 字，大约阅读时间需要 3 分钟。

题目大意：

给一个序列

X₁ = 1

X₂ = 2

X₃ = 3

X_i = (X_i-1 + X_i-2 + X_i-3) % M + 1         for i = 4 to N

求一段最短的连续子序列，使得这个子序列包含正整数【1，k】

思路：

扫描一遍即可，用一个队列记录下【1，k】区间内的数的位置，再用一个变量count维护【1，k】内不重复数的个数。当count等于k时说明当前序列已经满足了要求，而队列头的数的位置就是起始位置。

算法复杂度O（n）

代码：

/* * UVa 11536 - Smallest Sub-Array  * */#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long int64;typedef pair
         
          pii;const int INF = 0x3f3f3f3f;const int MAXN = 1000010;int n, m, k;int arr[MAXN];int cnt[MAXN];void init(){ arr[1] = 1; arr[2] = 2; arr[3] = 3; for(int i=4; i<=n; ++i) arr[i] = (arr[i-1]+arr[i-2]+arr[i-3])%m + 1; memset(cnt, 0, sizeof(cnt));}int main(){ int nCase, cas=1; scanf("%d", &nCase); while(nCase--){ scanf("%d%d%d", &n,&m,&k); init(); int minx = INF; int count=0; queue
          
           Q; for(int i=1; i<=n; ++i){ if(arr[i]>=1 && arr[i]<=k){ Q.push(i); if(cnt[arr[i]]++ == 0){ ++count; } while(count == k){ int tmp = i - Q.front() + 1; minx = min(tmp, minx); int val = arr[Q.front()]; if(--cnt[val]==0){ --count; } Q.pop(); } } } printf("Case %d: ", cas++); if(minx == INF) puts("sequence nai"); else printf("%d\n", minx); } return 0; }
          
         
        
       
      
     
    
   

转载地址：http://gszni.baihongyu.com/