iT邦幫忙

2021 iThome 鐵人賽

DAY 29
0
自我挑戰組

JAVA簡易教學+CPE歷屆試題講解系列 第 29

[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));
		}
	}
}

執行結果如下
https://ithelp.ithome.com.tw/upload/images/20210929/20140567QIP75BI6TV.png
其實在寫這篇文章的時候,時間有一點趕
因為我一開始先寫CPE,用瘋狂程設可以寫
後來跑去寫JAVA,JAVA寫完,再回到瘋狂程設
然後我的瘋狂程設APP突然就打不開了,當時連網站都打不開
一時之間不知道該如何是好,之後才知道原來是版本的問題
過了這麼久需要更新也是正常的,更新一下就好了
那關於CPE的歷屆練習題就講到這邊了 謝謝大家


上一篇
[iT鐵人賽Day28]練習題(7)
下一篇
[iT鐵人賽Day30]鐵人賽最終回 心得分享
系列文
JAVA簡易教學+CPE歷屆試題講解30

尚未有邦友留言

立即登入留言