算法：UVa 11536 - Smallest Sub-Array

算法：UVa 11536 - Smallest Sub-Array2014-03-17 csdn博客 shuangde800题目大意：

给一个序列

X1 = 1

X2 = 2

X3 = 3

Xi = （Xi-1 + Xi-2 + Xi-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<iostream>#include<cstdio>#include<cstring>#include<utility>#include<set>#include<queue>using namespace std;typedef long long int64;typedef pair<int,int>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<int>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
", minx）;}return 0; }