http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2531

看完題目後覺得好像有印象，原來是之前寫過類似的東西，叫作「核心字串」。

中心思想就是維護一個queue，只要是有用的數(1~K)，我就push此數，等到1~K的所有數字都至少出現一遍後，每加入一個有用的數，就去看如果把front的數字pop掉，queue裡面是不是還包含1~K，如果是，那就一直pop直到不能為止，這樣從頭到尾掃過去，途中記錄最小長度即可。這樣時間複雜度均攤下來就會是O(n)，因為一個數只會進入queue置多一次。

 

 

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;

const int MAX = 1000001;

int num[MAX] = {0, 1, 2, 3};

int main()
{
	int T, Case = 0;
	int N, M, K;
	
	
	
	scanf("%d", &T);
	while(T --)
	{
		scanf("%d %d %d", &N, &M, &K);
		
		for(int i = 4; i <= N; i ++)
			num[i] = (num[i-1] + num[i-2] + num[i-3]) % M + 1;
			
		int now, min_len = MAX, cnt = 0;
		int last_pos[101] = {};
		queue<int> Q;
		
		for(int i = 1; i <= N; i ++)
		{
			now = num[i];
			if(1 <= now && now <= K)
			{
				Q.push(i);
				
				if(last_pos[now] == 0) cnt ++;
				last_pos[now] = i;
				
				while(Q.front() != last_pos[num[Q.front()]])
					Q.pop();
					
				if(cnt == K)
					min_len = min(min_len, i-Q.front()+1);
				
			}
		}
		
		printf("Case %d: ", ++ Case);
		if(cnt == K)
		{
			printf("%d\n", min_len);
		}
		else
		{
			printf("sequence nai\n");
		}
		
	}


    return 0;
}