题目大意:
给一个序列
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\n", minx); } return 0; }
查看本栏目更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索int
, include
, 队列
, 位置
, 序列
一个
115372 36 6、www.kq36.cn 115、36115、115.126.36.43、,以便于您获取更多的相关知识。
时间: 2024-09-02 06:19:06