藍橋杯 2021年 國賽 填空題 (帶寬,純質數,完全日期,最小權值)
2022-05-19 22:25 幻霞 閱讀(503) 評論(0) 收藏 舉報B.純質數 (5分)
如果一個正整數只有 1 和它本身兩個約數，則稱為一個質數（又稱素數）。
前幾個質數是： 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , ? ? ?
如果一個質數的所有十進制數位都是質數，我們稱它為純質數。例如：2,3,5,7,23,37 都是純質數，而 11 , 13 , 17 , 19 , 29 , 31不是純質數。當然 1 , 4 , 35 也不是純質數。
請問，在 1到 20210605 中，有多少個純質數？
#include<bits/stdc++.h> using namespace std; // 0,1,2,3,4,5,6,7,8,9 int f[20210606]={0,0,1,1,0,1,0,1,0,0}; bool isPWZ(int n){ while(n){ if(f[n%10]==0) return false; n/=10; } return true; } bool isZ(int n){ for(int i=2;i<=sqrt(n);i++) if(n%i==0) return false; return true; } int main(){ int sum=0; for(int i=2;i<=20210605;i++) if(isPWZ(i)) if(isZ(i)) sum++; cout<<sum<<endl; //1903 return 0; }
C.完全日期
如果一個日期中年月日的各位數字之和是完全平方數，則稱為一個完全日期。
例如： 2021年 6月 5日的各位數字之和為 2 + 0 + 2 + 1 + 6 + 5 = 16 而 16是一個完全平方數，它是 4的平方。所以 2021年 6月 5日是一個完全日期。
例如： 2021年 6月23日的各位數字之和為 2 + 0 + 2 + 1 + 6 + 2 + 3 = 16 ，是一個完全平方數。所以 2021年 6月 23日也是一個完全日期。
請問，從 2001年 1月 1 日到 2021 年 12月 31日中，一共有多少個完全日期？
#include<bits/stdc++.h> using namespace std; int M[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int getV(int n){ int ans=0; while(n){ ans+=n%10; n/=10; } return ans; } bool ok(int m){ double mq=sqrt(m); return mq-(int)mq<10e-6;//這里因為浮點精度問題所以存在一個極小的偏差,忽略這個偏差才能得到正確結果 } int main(){ int sum=0; int startYear=2001,startMonth=1,startDay=1; int endYear=2021,endMonth=12,endDay=31;//2+0+2+1+1+2+3+1=12不是完全平方 while(!(startYear==endYear &&startMonth==endMonth &&startDay==endDay)){ //備注:先在邏輯上正確,再斟酌過程上的簡化,簡化可能會帶來無法察覺的邏輯變化. int tmp= getV(startYear)+getV(startMonth)+getV(startDay); if(ok(tmp)){ sum++; } startDay++; if(startDay>M[startMonth]){ startMonth++; startDay=1; } if(startMonth>12){ startYear++; startMonth=1; M[2]=(startYear%400==0||startYear%4==0 && startYear%10!=0)?29:28; } } cout<<sum<<endl; return 0; }
對于一棵有根二叉樹 T，小藍定義這棵樹中結點的權值 W ( T )如下：
空子樹的權值為 0。
如果一個結點 v有左子樹 L, 右子樹 R，分別有 C ( L )和 C ( R ) 個結點，則 W ( v ) = 1 + 2 W ( L ) + 3 W ( R ) + ( C ( L ) ) *( C ( L ) ) *C ( R )
樹的權值定義為樹的根結點的權值。
小藍想知道，對于一棵有 2021個結點的二叉樹，樹的權值最小可能是多
少？
本題可以用dp做,參考背包問題可以得到 dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])這個遞推式
這里主要是dp[i][j][...]...=w這個多維數組的意義賦予比較難去思考,
本題我們抽出值為數量的關鍵主體:節點數,權值,總節點數(定量)
題目的目標是找到最小的權值,而權值和節點數能計算出新的權值,我們要求的是權值,所以數組的值的含義就能暫時確定為權值,數組必然有一維與節點數有關,我們不妨賦予第一維i以總節點數的意義
這樣dp就確定下來了
對dp的一些理解,可以略過
dp可以看作是對輸入不同的維度的數據確定一個唯一的答案的一個函數,通過不斷優化最后得到正確結果的過程.這個結果不是一下就出來的,
像是背包問題,在背包容積確定和物品個數和價值確定的情況下便能得到最優解,可能存在一樣的不過對于最值問題知道它即可,所以dp[i][j]的含義是選擇到第i個物品空間為j時的最優解,
為什么w(價值)和v(體積)不參與dp的一個維度呢?其實這和高數中的一個知識點有關.
如果你有幾個表達式,變量很多,但是你仔細理一理,發現可以去掉很多變量,最后簡化成只有兩個或三個變量,其實基本的思想是消元,背包問題中每一個i和它的w和v唯一對應,所以頂層簡化成i,但是光有物品清單無法得到結果,所以還需要背包容積作為第二個維度,即dp[i][j]表示為dp[物品個數][空間大小],而本題的輸入只有總節點數,所以總節點數便能確定最終值
繼續正題
dp[i] = min(dp[i], 1ll + 2ll * dp[j] + 3ll * dp[i - j - 1] + j * j * (i - j - 1));
知道總節點數,肯定還得知道左節點和右節點數,不妨設置左節點數為i,右節點數為j,對于根節點,x=i+j+1
然后我們得到遞推式dp[i+j+1]=min(dp[i+j+1],1+2*dp[i]+3*dp[j]+i*i*j);其實我們是按照總節點來去遞推的dp[i+j+1]不符合我們遍歷的要求,我們把i+j+1都換成x;
然后得到 dp[x]=min(dp[x],1+2*dp[x-j-1]+3*dp[j]+(x-j-1)*(x-j-1)*j)然后第一層從1到2021表示總節點數,第二層(有幾維就需要幾層循環)從0到2020表示右節點數j
#include <bits/stdc++.h> #define ll long long #define INF 0x3f3f3f3f3f3f3f3f using namespace std; ll dp[2022]; int main() { memset(dp, INF, sizeof(dp)); dp[0] = 0; for (ll x = 1; x <= 2021; x++) { for (ll j = 0; j < x; j++) { dp[x]=min(dp[x],1+2*dp[x-j-1]+3*dp[j]+(x-j-1)*(x-j-1)*j); } } cout<<dp[2021]<<endl; return 0; }
然后運行,得到2653631372
浙公網安備 33010602011771號