题目链接
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=513&page=show_problem&problem=2619
题目大意:
给一个序列
X1= 1
X2= 2
X3= 3
Xi= (Xi-1+ Xi-2+ Xi-3) % M + 1 fori= 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;
}
分享到:
相关推荐
k-th-Smallest-element-in-an-array:第k个数组中的最小元素
关于有向图最小树形图的C代码,供大家参考。
这个源代码是一个最小生成树的算法实现,采用的visual c++6.0
将您的过程解决方案编码到lib/smallest_multiple.rb文件中。 将您的面向对象的解决方案编码到lib/oo_smallest_multiple.rb文件中。 运行learn直到所有RSpec测试通过。 来源 -- 在Learn.co上查看并开始免费学习编码。
将您的过程解决方案编码到lib/smallest_multiple.rb文件中。 将您的面向对象的解决方案编码到lib/oo_smallest_multiple.rb文件中。 运行learn直到所有RSpec测试通过。 来源 -- 在Learn.co上查看并开始免费学习编码。
将您的过程解决方案编码到lib/smallest_multiple.rb文件中。 将您的面向对象的解决方案编码到lib/oo_smallest_multiple.rb文件中。 运行learn直到所有RSpec测试通过。 来源 -- 在Learn.co上查看并开始免费学习编码。
将您的过程解决方案编码到lib/smallest_multiple.rb文件中。 将您的面向对象的解决方案编码到lib/oo_smallest_multiple.rb文件中。 运行learn直到所有RSpec测试通过。 来源 -- 在Learn.co上查看并开始免费学习编码。
欧拉公式求长期率的matlab代码最小倍数 构建一个函数,以找到最小的正数,该正数可以被从1...smallest_multiple.js的文件中完成。 使用以下命令npm test : npm test 总共有两个测试。 让他们通过! 来自欧拉计划问题5
将您的过程解决方案编码到lib/smallest_multiple.rb文件中。 将您的面向对象的解决方案编码到lib/oo_smallest_multiple.rb文件中。 运行learn直到所有RSpec测试通过。 来源 -- 在Learn.co上查看并开始免费学习编码。
将您的过程解决方案编码到lib/smallest_multiple.rb文件中。 将您的面向对象的解决方案编码到lib/oo_smallest_multiple.rb文件中。 运行learn直到所有RSpec测试通过。 来源 -- 在Learn.co上查看并开始免费学习编码。
将您的过程解决方案编码到lib/smallest_multiple.rb文件中。 将您的面向对象的解决方案编码到lib/oo_smallest_multiple.rb文件中。 运行learn直到所有RSpec测试通过。 来源 -- 在Learn.co上查看并开始免费学习编码。
将您的过程解决方案编码到lib/smallest_multiple.rb文件中。 将您的面向对象的解决方案编码到lib/oo_smallest_multiple.rb文件中。 运行learn直到所有RSpec测试通过。 来源 -- 在Learn.co上查看并开始免费学习编码。
将您的过程解决方案编码到lib/smallest_multiple.rb文件中。 将您的面向对象的解决方案编码到lib/oo_smallest_multiple.rb文件中。 运行learn直到所有RSpec测试通过。 来源 -- 在Learn.co上查看并开始免费学习编码。
自述文件描述Spring Boot最小项目Spring Boot最佳实践使用最简单的结构设定档档案结构|-- src|-- main|-- |-- com.spring.boot.example.{projectName}|-- |-- |-- {projectName}Application.java|-- |-- |-- config|...
代码:// find K-th Smallest Pair Distancepublic int smallestDistancePair(int[] nums
欧拉公式求长期率的matlab代码欧拉计划 ...将您的过程解决方案编码到lib/smallest_multiple.rb文件中。 将您的面向对象的解决方案编码到lib/oo_smallest_multiple.rb文件中。 运行learn直到所有RSpec测试通过。 来源 --
欧拉公式求长期率的matlab代码欧拉计划 ...将您的过程解决方案编码到lib/smallest_multiple.rb文件中。 将您的面向对象的解决方案编码到lib/oo_smallest_multiple.rb文件中。 运行learn直到所有RSpec测试通过。 来源 --
AT_code_festival_2017_qualb_f Largest Smallest Cyclic Shift 的 AC 代码
在服务器上存储例如JSON-Array 只需上传php文件 注意:完全没有安全性 警告 没有实现安全层。 此工具不应用于生产系统,并且不能替代基于框架和真实数据库的真实中间件系统。 入门 服务器 将整个项目( smallest_...
Android自定义dimens.xml,适应各种屏幕分辨率,300-450dp