2019年蓝桥杯省赛个人题解

今天药忘吃喽~ 2023-07-12 08:50 41阅读 0赞

### 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 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖  
> 果。