2019年藍橋杯省賽個人題解

• • • 平方和
    • 數列求值
    • 最大降雨量
    • 完全二叉樹的權值
    • 外賣店優先級
    • 修改數組
    • 糖果

平方和

小明對數位中含有 2、0、1、9 的數字很感興趣，在 1 到 40 中這樣的數包

括 1、2、9、10 至 32、39 和 40，共 28 個，他們的和是 574，平方和是 14362。

注意，平方和是指将每個數分别平方後求和。

請問，在 1 到 2019 中，所有這樣的數的平方和是多少？

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ll sum = 0;
    int j,t,f;
    for(int i=1;i<=2019;++i){
        f=0;j=i;
        while(j){
            t = (j%10);
            if(t==2||t==0||t==1||t==9){
                f=1;break;
            }
            j/=10;
        }
        if(f)sum += i*i;
    }
    printf("%lld\n",sum);//2658417853
}
           

數列求值

給定數列 1, 1, 1, 3, 5, 9, 17, …，從第 4 項開始，每項都是前 3 項的和。求

第 20190324 項的最後 4 位數字。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e4;

int main(){
    int f[4]={1,1,1};
    for(int i=4;i<=20190324;++i){
        f[3]=(f[0]+f[1]+f[2])%MOD;
        if(i%3==1)f[0]=f[3];
        else if(i%3==2)f[1]=f[3];
        else f[2]=f[3];
    }
    printf("%d\n",f[3]);//4659
}
           

最大降雨量

由于沙之國長年幹旱，法師小明準備施展自己的一個神秘法術來求雨。

這個法術需要用到他手中的 49 張法術符，上面分别寫着 1 至 49 這 49 個

數字。法術一共持續 7 周，每天小明都要使用一張法術符，法術符不能重複使

用。

每周，小明施展法術産生的能量為這周 7 張法術符上數字的中位數。法術

施展完 7 周後，求雨将獲得成功，降雨量為 7 周能量的中位數。

由于幹旱太久，小明希望這次求雨的降雨量盡可能大，請大最大值是多少？

49-16+1=34

完全二叉樹的權值

給定一棵包含 N 個節點的完全二叉樹,哪個深度的節點權值之和最大？如果有多個深度的權值和同為最大，請你輸出其中最小的深度。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+1;
int a[N],n;

int main(){
     scanf("%d",&n);
     for(int i=0;i<n;++i)scanf("%d",&a[i]);
     int j=0,t=1,i,deep=1,level=1;
     ll maxv=-(1LL<<60),sum;
     while(j<n){
         sum = 0;
         for(i=j;i<n&&i-j<t;++i){
             sum+=a[i];
         }
         if(maxv<sum){
            maxv=sum;
            deep=level;
         }
         j = i;
         level++;
         t<<=1;
         //printf("%d %d %d\n",sum,j,t);
     }
     printf("%d\n",deep);
}
           

外賣店優先級

“飽了麼”外賣系統中維護着 N 家外賣店，編号 1 ∼ N。每家外賣店都有

一個優先級，初始時 (0 時刻) 優先級都為 0。

每經過 1 個時間機關，如果外賣店沒有訂單，則優先級會減少 1，最低減

到 0；而如果外賣店有訂單，則優先級不減反加，每有一單優先級加 2。

如果某家外賣店某時刻優先級大于 5，則會被系統加入優先緩存中；如果

優先級小于等于 3，則會被清除出優先緩存。

給定 T 時刻以内的 M 條訂單資訊，請你計算 T 時刻時有多少外賣店在優

先緩存中。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;//最大數組長度

vector<int> order[N];//外賣商店id的訂單

int main(){
    int n,m,t;//商店數，訂單數，時間
    scanf("%d%d%d",&n,&m,&t);
    int ts,td,pre,a,size;//訂單時間，訂單id,上次預定時間，優先數,數組長度
    int ans=0;//結果
    for(int i=0;i<m;++i){
        scanf("%d%d",&ts,&td);
        order[td].push_back(ts);
    }
    for(int i=1;i<=n;++i){
        pre=a=0;
        sort(order[i].begin(),order[i].end());
        size  = order[i].size();
        for(int j=0;j<size;++j){
            ts = order[i][j];
            if(ts>pre+1)a = max(a-(ts-pre-1),0);//訂單時間未連續
            a+=2;
            pre = ts;
        } 
        a =   max(a-(t-pre),0);//在t訂了不要扣，未訂需要扣，是以不需要-1
        if(a>5||(a==5&&pre!=t)||(a==4&&pre<t-1))ans++; /*
        (1) 優先數>5符合
        （2） 優先數=5，要符合必須是下降得到的，則在t時刻沒有訂單
        （3） 優先數=4 需要連續下降2次
        */
    }
    printf("%d\n",ans);
    
}
           

修改數組

給定一個長度為 N 的數組 A = [A1, A2, · · · AN]，數組中有可能有重複出現

的整數。

現在小明要按以下方法将其修改為沒有重複整數的數組。小明會依次修改

A2, A3, · · · , AN。

當修改 Ai 時，小明會檢查 Ai 是否在 A1 ∼ Aii 1 中出現過。如果出現過，則

小明會給 Ai 加上 1 ；如果新的 Ai 仍在之前出現過，小明會持續給 Ai 加 1 ，直

到 Ai 沒有在 A1 ∼ Aii 1 中出現過。

當 AN 也經過上述修改之後，顯然 A 數組中就沒有重複的整數了。

現在給定初始的 A 數組，請你計算出最終的 A 數組。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;//最大數組長度
int f[N]={0};

int find(int x){
    return f[x]==0?x:f[x]=find(f[x]);
}

int main(){
    int n,d;
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%d",&d)
        d = find(d);//尋找連續區間的最大值+1
        f[d]=d+1;
        printf("%d ",d);
    }
    printf("\n");
    //for(int i=1;i<=n;++i)printf("%d ",f[i]);
}
           

糖果

糖果店的老闆一共有 M 種口味的糖果出售。為了友善描述，我們将 M 種

口味編号 1 ∼ M。

小明希望能品嘗到所有口味的糖果。遺憾的是老闆并不單獨出售糖果，而

是 K 顆一包整包出售。

幸好糖果包裝上注明了其中 K 顆糖果的口味，是以小明可以在買之前就知

道每包内的糖果口味。

給定 N 包糖果，請你計算小明最少買幾包，就可以品嘗到所有口味的糖

果。