【洛谷新手村解題報告四 】
- 過程函數與遞歸
- BOSS戰-入門綜合練習1
從遞歸的第三題開始了！
過程函數與遞歸
第三題 火柴棒等式[2,1]
這裡介紹最簡單的 便于了解的方法：
Sol 1 暴力枚舉
因為n最大24 我們計算所有的四位數需要的火柴棒數量預處理
計算的時候 每一位需要的火柴棒數量可以
int cnt[]={6,2,5,5,4,5,6,3,7,6};
最後計算的時候，枚舉A 和 B
如果 數字A B A+B 的火柴棒數量=n-4 就是一個解（因為加号和等号都是兩根）
Sol 2 打表
int f[25]={0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,8,9,6,9,29,39…………};
24根列完就OK了！
第四題 回文質數 Prime Palindromes[2,1]
寫一個程式來找出範圍[a,b] (5≤a<b≤100,000,000)( 一億)間的所有回文質數。
提示已經給了，先列舉回文數，再判斷是否為質數
這裡有個神奇的小東西：
除了11，所有的偶數位數的回文數都是非質數，都被11整除
那我們枚舉其他奇數位的回文數，再判斷是否是質數就可以了！
列舉長度為7的回文數：
for (int d1 = 1; d1 <= 9; d1+=2){ //偶數一定不是質數，最低(高)位一定是偶數
for (int d2 = 0; d2 <= 9; d2++){
for (int d3 = 0; d3 <= 9; d3++){
for(int d4=0;d4<=9;d4++){
pal = 1000000*d1 + 100000*d2 +10000*d3 + 1000*d4 +100*d3+ 10*d2 + d1;
if(pal<a || pal>b)continue; //判斷要在範圍内
if(ck(pal))printf("%lld\n",pal); //判斷質數
}
}
}
}
BOSS戰-入門綜合練習1
第一題 陶陶摘蘋果（更新版）[2,2]
又是一年秋季時，陶陶家的蘋果樹結了 n 個果子。陶陶又跑去摘蘋果，這次他有一個 a 公分的椅子。當他手夠不着時，他會站到椅子上再試試。
這次與 NOIp2005 普及組第一題不同的是：陶陶之前搬凳子，力氣隻剩下 s 了。當然，每次摘蘋果時都要用一定的力氣。陶陶想知道在s<0 之前最多能摘到多少個蘋果。
現在已知 n 個蘋果到達地上的高度 xi ，椅子的高度 a，陶陶手伸直的最大長度 b，陶陶所剩的力氣s，陶陶摘一個蘋果需要的力氣 yi，求陶陶最多能摘到多少個蘋果。
既然隻輸出最多摘多少個蘋果，那我們就貪心，每次摘需要花費力氣最小的蘋果，如果摘不到就下一個力氣次小的，依次類推
每個蘋果有高度和力氣兩個參數，我們使用簡便的
pair<int,int>P[MAX];
cmp()函數比較每個蘋果的力氣值，然後順序摘取
第二題 三連擊（更新版）[1,1]
之前的三連擊題目一樣，隻不過比例改成了自定義輸入，同之前的代碼
解題報告一，三連擊在裡面
第三題 哥德巴赫猜想（更新版）[2,2]
1742年6月7日哥德巴赫寫信給當時的大數學家歐拉，正式提出了以下的猜想：任何一個大于9的奇數都可以表示成3個質數之和。質數是指除了1和本身之外沒有其他約數的數，如2和11都是質數，而6不是質數，因為6除了約數1和6之外還有約數2和3。需要特别說明的是1不是質數。
因為範圍 9<n<20000 ，那麼我們需要先篩出這個範圍内所有的素數
用埃篩即可，原理：i是素數的話，i*k(正整數) 一定不是素數，則可以篩去
複雜度O(NlogN)
int shai(void){
int p=-1;
for(int i=2;i<MAX;++i){
if(num[i])continue; //記錄i有沒有被篩走
pri[++p]=i; //下一個質數是i
for(int j=i*2;j<MAX;j+=i) //k倍都篩掉
num[j]=1; //j篩走了
}
return p;
}
然後枚舉 質數 a b ，是否 n-a-b 也是質數即可
第四題 烤雞[3,3]
豬豬 Hanke 特别喜歡吃烤雞（本是同畜牲，相煎何太急！）Hanke 吃雞很特别，為什麼特别呢？因為他有 10種配料（芥末、孜然等），每種配料可以放 1 到 3 克，任意烤雞的美味程度為所有配料品質之和。
現在， Hanke 想要知道，如果給你一個美味程度 n ，請輸出這 10 種配料的所有搭配方案。
輸入
11
輸出
10
1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 2 1 1 1
1 1 1 1 1 2 1 1 1 1
1 1 1 1 2 1 1 1 1 1
1 1 1 2 1 1 1 1 1 1
1 1 2 1 1 1 1 1 1 1
1 2 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1
有一定難度的遞歸題目，答案還要求字典序升序輸出
首先我采用了狀态壓縮做法（每種調料使用1/2/3 三種狀态）3^10 也沒逾時間
試試就逝世
一通狂做，一看輸出傻眼了：（最後答案反轉了一下輸出的）
這咋就這麼奇怪呢？狀态壓縮是二進制方法實作的，二進制不保證字典序！
那就利用遞歸好好做吧
void pd(int pos,int now)
表示目前位置為pos ，用了調料now了
邊界1 ： 如果pos=10 表示處理完了 如果now！=n 表示用的不對，反之輸出
邊界2 優化： 如果目前位置和以後位置都放3都放不完調料了，跳出
邊界3 優化 ： 如果目前位置now>n 了，那表示再怎麼放都不對了，跳出
處理 ：這位放1 繼續遞歸 這位放2 繼續遞歸 這位放3 繼續遞歸
思路很好了解，那就貼代碼嗎（嗚嗚當時調了很久 我好菜）
void pd(int pos,int now){
if(pos==10){ //邊界1
if(now!=n)return;
ans++;
for(int i=1;i<=10;++i){
aa[ans][i]=cas[i]; //第ans種情況，先存起來
}
return ;
}
if(now>n)return ; //邊界3
if(10-pos + now > n || (10-pos)*3 + now <n)return ; //邊界2
cas[pos+1]=1; //這位放1 遞歸，下同理
pd(pos+1,now+1);
cas[pos+1]=2;
pd(pos+1,now+2);
cas[pos+1]=3;
pd(pos+1,now+3);
return ;
}
求個贊拉 寫了這麼多