[iT铁人赛Day29]练习题(8)

时间过得真快，一转眼就来到做练习题的最後一天，明天要做最後总结
最後一天要来做练习题第八题
第八题要找的是子集合的个数
假设1到K然後找符合要求的子集合个数的总数
像是1到4，就要找包含{1,2,3,4}这4个数字的子集合
题目的序列是这个样子
{1,2,3,7,1,12,9,11,9,6,3,7,5,4,5,3,1,10,3,3}
然後我们要先找到包含{1,2,3,4}四个数字的序列
找到{1,2,3,7,1,12,9,11,9,6,3,7,5,4}这里，就包含了{1,2,3,4}
然後往後推{2,3,7,1,12,9,11,9,6,3,7,5,4,5}，把{1}删掉
整个序列还是包含{1,2,3,4}，以此类推，找出包含{1,2,3,4}
且符合设定的最短序列个数。
最後我们找到符合要求的最短序列个数为13个
第二笔资料要我们找包含{1,2,3,4,5,6,7,8}这8个数字的子集合
因为我们没有符合这些子集合的序列
所以第二笔资料显示"sequence nai"
最後，第八题的程序码如下：

import java.util.*;
class main{
	static int MAx=Integer.MAX_VALUE;
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		for(int j=1;j<=t;j++){
			int n=sc.nextInt(),m=sc.nextInt(),k=sc.nextInt();
			int[] x=new int[n+1];
			x[1]=1;
			x[2]=2;
			x[3]=3;
			for(int i=4;i<=n;i++){
				x[i]=(x[i-1]+x[i-2]+x[i-3])%m+1;
			}
			int[] y=new int[1000000];
			int sum=0,min=MAx;
			Queue<Integer> qu=new LinkedList<>();
			for(int i=1;i<=n;i++){
				qu.add(x[i]);
				if(++y[x[i]]==1&&x[i]<=k)
					sum++;
				if(sum>=k){
					while(qu.peek()>k || y[qu.peek()]>1){
						y[qu.peek()]--;
						qu.poll();
					}
					min=Math.min(qu.size(),min);
				}
			}
			System.out.println("Case "+j+": "+(min==MAx?"sequence nai":min));
		}
	}
}

执行结果如下

其实在写这篇文章的时候，时间有一点赶
因为我一开始先写CPE，用疯狂程设可以写
後来跑去写JAVA，JAVA写完，再回到疯狂程设
然後我的疯狂程设APP突然就打不开了，当时连网站都打不开
一时之间不知道该如何是好，之後才知道原来是版本的问题
过了这麽久需要更新也是正常的，更新一下就好了
那关於CPE的历届练习题就讲到这边了 谢谢大家