ACM UVA 11536 Smallest Sub-Array

╰+哭是因爲堅強的太久メ 2022-06-11 03:37 103阅读 0赞

UVA 11536 Smallest Sub-Array

![20170729102151741][]

题目大意：输入N,M,K，按照规律%M得到数组长度为N的数组，问是否存在1-K的子序列（可以间隔其他数字，也可以乱序，例如12435），若存在输出最小长度。

思路：先按照规律把数组存下来。1，2,3的情况可以特殊考虑，然后开始遍历。先把位置都记录下来，当K个数字都出现过之后开始优化，把j向后移。

#include <stdio.h>
    #include <algorithm>
    #include <string.h>
    using namespace std; 
    int a[1000001],vis[1010];
    int main()
    {
    	int t,n,m,k,i,j,o=1,ans,s;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d%d%d",&n,&m,&k);
    		printf("Case %d: ",o++);
    		a[1]=1;a[2]=2;a[3]=3;
    		for(i=4;i<=n;i++)
    		a[i]=(a[i-1]+a[i-2]+a[i-3])%m+1;
    		if(k==1)
      		ans=1;  	 
        	else if(k==2)  
         	ans=2;  
         	else if(k==3)
         	ans=3;
         	else 
         	{
         		j=1;s=0;ans=1000002;
    			memset(vis,0,sizeof(vis)); 
    			for(i=1;i<=n;i++)
    			{
    				if(a[i]<=k)
    				{
    					if(!vis[a[i]])
    					s++;
    					vis[a[i]]++;
    					if(s==k)
    					{
    						while(j<=n&&(a[j]>k||vis[a[j]]>1))
    						{
    							if(a[j]<=k)
    							vis[a[j]]--;
    							j++;
    						}
    						ans=min(ans,i-j+1);
    					}
    				}
    			}
       		}   	 
    		if(ans!=1000002) 
    		printf("%d\n",ans);  
    		else  
    		printf("sequence nai\n");  
    	}
    }

[20170729102151741]: /images/20220611/5454813612e04628bb199339a678d5b1.png

发表评论取消回复

表情：

评论列表（有 0 条评论，103人围观）

还没有评论，来说两句吧...

相关阅读

相关环状序列(Circular Sequence,ACM/ICPC Seoul 2004,UVa1584)题解

文章目录题目描述输入输出原题（PDF）题目分析案例分析解题标程

浅浅的花香味﹌/ 2022年12月28日 04:24/ 0 赞/ 255 阅读

相关 uva 11997——K Smallest Sums

题意：给定k个含k个数的数列，然后每次从每个序列中取出一个相加，然后问所有的数中前k小的。思路：将每个表排序后然后插入优先队列中，依次是a\[0\]+b\[0\]

喜欢ヅ旅行/ 2022年08月21日 04:17/ 0 赞/ 20 阅读

相关 uva 11536——Smallest Sub-Array

题意：给定n个数，这n个数在m的范围之内。v\[i\]=(v\[i-1\]+v\[i-2\]+v\[i-3\])%m+1; 然后求一个最短连续子序列使得序列内包括1-k个数

淡淡的烟草味﹌/ 2022年08月09日 16:44/ 0 赞/ 94 阅读

相关 ACM UVA 11536 Smallest Sub-Array

UVA 11536 Smallest Sub-Array ![20170729102151741][] 题目大意：输入N,M,K，按照规律%M得到数组长度为N的数组，

╰+哭是因爲堅強的太久メ/ 2022年06月11日 03:37/ 0 赞/ 104 阅读

相关 Alignment of Code，ACM/ICPC NEERC 2010,UVa 1593

You are working in a team that writes Incredibly Customizable Programming Codewriter (IC

ゞ浴缸里的玫瑰/ 2022年06月09日 02:44/ 0 赞/ 218 阅读

相关铁轨（rails,ACM/ICPC CERC 1997,UVa 514）

今天学习算法：发现自己对栈很懵逼，看了一下程序，决定自己手动写一遍加深理解。有n节车厢从A方向驶入车站，按进站顺序编号1～n。现让这些火车按照某种特定的顺序进

超、凢脫俗/ 2022年05月19日 02:34/ 0 赞/ 188 阅读

相关数据库DATAbase， ACM/ICPC NEERC 2009, UVa1592 紫书例题

本题题意有点扯，看不懂先大概说一下思路把：设立字符串二维数组和int二维数组，还有一个《string，int》map1和《int，int》map2，，，通过数组转换（输

女爷i/ 2022年05月17日 00:47/ 0 赞/ 129 阅读

相关 Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has

╰半夏微凉°/ 2021年12月23日 23:39/ 0 赞/ 147 阅读

相关 Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has

曾经终败给现在/ 2021年12月17日 10:39/ 0 赞/ 141 阅读

相关 Uva11997 K Smallest Sums（优先队列）

题意：有一个k\k 的方阵，让你从当中每一行挑选一个数字相加最后能得到K^K次方的和，输出其中最小的k个。分析：《训练指南》P190，先对每一行排序然后两两归并，每

短命女/ 2021年12月11日 12:39/ 0 赞/ 232 阅读