第十二届蓝桥杯省赛第二场 C/C++ B组编程题与详解

青旅半醒 2024-04-22 22:01 68阅读 0赞

![701718904a934962b72237b8d2cde2bb.gif][]

> **文章目录**
> 
> 一、特殊年份
> 
> 1、1 题目描述
> 
> 1、2 题解关键思路与解答
> 
> 二、小平方
> 
> 2、1 题目描述
> 
> 2、2 题解关键思路与解答
> 
> 三、完全平方数
> 
> 3、1 题目描述
> 
> 3、2 题解关键思路与解答
> 
> 四、负载均衡
> 
> 4、1 题目描述
> 
> 4、2 题解关键思路与解答
> 
> 五、国际象棋
> 
> 5、1 题目描述
> 
> 5、2 题解关键思路与解答
> 
> --------------------
> 
> **?♂️ 作者：@Ggggggtm ?♂️**
> 
> **? 专栏：数据结构与算法 ?**
> 
> **? 标题：第十二届蓝桥杯省赛第二场 ?**
> 
> **❣️ 寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景 ❣️**
> 
> ![5e140be53a354e7c98d9dd38f0bed8a2.png][]

## 一、特殊年份 ##

### 1、1 题目描述 ###

> **题目来源：**第十二届[蓝桥杯][Link 1]省赛第二场
> 
> **题目难度：**简单
> 
> **题目描述：**今年是 2021 年，2021 这个数字非常特殊，它的千位和十位相等，个位比百位大 1，我们称满足这样条件的年份为特殊年份。输入 5 个年份，请计算这里面有多少个特殊年份。
> 
> **输入格式：**输入 5 行，每行一个 44 位十进制数（数值范围为 1000 至 9999），表示一个年份。
> 
> **输出格式：**输出一个整数，表示输入的 55 个年份中有多少个特殊年份。
> 
> **输入样例：**
> 
>     2019
>     2021
>     1920
>     2120
>     9899
> 
> **输出样例：**
> 
>     2
> 
> **样例解释：**2021 和 9899 是特殊年份，其它不是特殊年份。

### 1、2 题解关键思路与解答 ###

> 这道题的思路什么简单，我们只需要将年份的各个数字拿出来，看是否满足：它的千位和十位相等，个位比百位大 1 即可。我们直接看代码：

#include<bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        int cnt=0;
        
        int ret=0;
        for(int i=0;i<5;i++)
        {
            scanf("%d",&ret);
            int a=ret/1000,b=ret/100%10,c=ret%100/10,d=ret%10;
            
            if(a==c && d-b==1)
                cnt++;
        }
        
        cout<<cnt;
        return 0;
    }

## 二、小平方 ##

### 2、1 题目描述 ###

> **题目来源：**第十二届[蓝桥杯][Link 1]省赛第二场
> 
> **题目难度：**简单
> 
> **题目描述：**小蓝发现，对于一个正整数 n 和一个小于 n 的正整数 v，将 v 平方后对 n 取余可能小于 n 的一半，也可能大于等于 n 的一半。请问，在 1 到 n−1中，有多少个数平方后除以 n 的余数小于 n 的一半。
> 
> 例如，当 n=4时，1,2,3的平方除以 4 的余数都小于 4 的一半。
> 
> 又如，当 n=5时，1,4 的平方除以 5 的余数都是 1，小于 5 的一半。
> 
> 而 2,3 的平方除以 5 的余数都是 4，大于等于 5 的一半。
> 
> **输入格式：**
> 
> 输入一行包含一个整数 n。
> 
> **输出格式：**
> 
> 输出一个整数，表示满足条件的数的数量。
> 
> **数据范围：**
> 
> 1≤n≤10000
> 
> **输入样例：**
> 
>     5
> 
> 输出样例：
> 
>     2

### 2、2 题解关键思路与解答 ###

> 由于数据范围较小，所以我们直接暴力枚举即可。我们直接看代码：

#include<bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        int n;
        int cnt=0;
        cin>>n;
        for(int i=1;i<n;i++)
        {
            if((i*i)%n*2 < n)
                cnt++;
        }
        
        cout<<cnt;
        return 0;
    }

## 三、完全平方数 ##

### 3、1 题目描述 ###

> **题目来源：**第十二届[蓝桥杯][Link 1]省赛第二场
> 
> **题目难度：**简单
> 
> **题目描述:**一个整数 a 是一个完全平方数，是指它是某一个整数的平方，即存在一个整数 b，使得 a=b\*b。给定一个正整数 n，请找到最小的正整数 x，使得它们的乘积是一个完全平方数。
> 
> **输入格式:**
> 
> 输入一行包含一个正整数 n。
> 
> **输出格式:**
> 
> 输出找到的最小的正整数 x。
> 
> **数据范围:**
> 
> 对于 30% 的评测用例，1≤n≤1000，答案不超过 1000。  
> 对于 60% 的评测用例，1≤n≤1e8，答案不超过 1e8。  
> 对于所有评测用例，1≤n≤1e12，答案不超过 1e12。
> 
> **输入样例1：**
> 
>     12
> 
> **输出样例1：**
> 
>     3
> 
> **输入样例2：**
> 
>     15
> 
> **输出样例2：**
> 
>     15

### 3、2 题解关键思路与解答 ###

> 从题目中给出的数据范围可知，我们如果暴力去找最小的数，是不行的。这里就用到了质因数。如果一个数完全平方数，那么这个数的所有质因数的个数为偶数。根据这一特点，我们就判单题目中给出的数据，找出该数据的质因数个数为奇数的，然后相互乘起来就是我们所要的结果。我们结合代码一起理解一下。

#include<bits/stdc++.h>
    
    using namespace std;
    
    typedef long long LL;
    
    int main()
    {
        LL n;
        scanf("%lld",&n);
        
        LL res=1;
        for(LL i=2;i*i<=n;i++)
        {
            if(n%i==0)
            {
                int s=0;
                while(n%i==0)
                {
                    n/=i;
                    s++;
                }
                if(s%2)
                    res*=i;
            }
        }
        
        if(n>1)
            res*=n;
        
        cout<<res;
        return 0;
    }

## 四、负载均衡 ##

### 4、1 题目描述 ###

> **题目来源：**第十二届[蓝桥杯][Link 1]省赛第二场
> 
> **题目难度：**中等
> 
> **题目描述:**有 n 台计算机，第 i台计算机的运算能力为 vi。有一系列的任务被指派到各个计算机上，第 i 个任务在 ai 时刻分配，指定计算机编号为 bi，耗时为 ci 且算力消耗为 di。如果此任务成功分配，将立刻开始运行，期间持续占用 bi 号计算机 di 的算力，持续 ci 秒。对于每次任务分配，如果计算机剩余的运算能力不足则输出 −1，并取消这次分配，否则输出分配完这个任务后这台计算机的剩余运算能力。
> 
> **输入格式：**
> 
> 输入的第一行包含两个整数 n,m，分别表示计算机数目和要分配的任务数。
> 
> 第二行包含 n 个整数 v1,v2,⋅⋅⋅vn，分别表示每个计算机的运算能力。接下来 m 行每行 4 个 整数 ai,bi,ci,di，意义如上所述。数据保证 ai 严格递增，即 ai<ai+1。
> 
> **输出格式：**
> 
> 输出 m 行，每行包含一个数，对应每次任务分配的结果。
> 
> **数据范围：**
> 
> 对于 20% 的评测用例，n,m≤200。  
> 对于 40% 的评测用例，n,m≤2000。  
> 对于所有评测用例，1≤n,m≤200000，1≤ai,ci,di,vi≤1e9，1≤bi≤n。
> 
> **输入样例：**
> 
>     2 6
>     5 5
>     1 1 5 3
>     2 2 2 6
>     3 1 2 3
>     4 1 6 1
>     5 1 3 3
>     6 1 3 4
> 
> **输出样例：**
> 
>     2
>     -1
>     -1
>     1
>     -1
>     0
> 
> **样例解释：**
> 
> 时刻 1，第 1 个任务被分配到第 1 台计算机，耗时为 5，这个任务时刻 6 会结束，占用计算机 1 的算力 3。
> 
> 时刻 2，第 2 个任务需要的算力不足，所以分配失败了。
> 
> 时刻 3，第 1 个计算机仍然正在计算第 1 个任务，剩余算力不足 3，所以失败。
> 
> 时刻 4，第 1 个计算机仍然正在计算第 1 个任务，但剩余算力足够，分配后剩余算力 1。
> 
> 时刻 5，第 1 个计算机仍然正在计算第 1,4 个任务，剩余算力不足 4，失败。
> 
> 时刻 6，第 1 个计算机仍然正在计算第 4 个任务，剩余算力足够，且恰好用完。

### 4、2 题解关键思路与解答 ###

> 该题目输入的时刻是保证有序的。但是每个任务需要花费的时间是一段时间段，这似乎是一个很棘手的问题。我们看每个计算机是否能进行此任务，关键是要看该计算机的剩余的算力是否足够。我们发现每个计算机都是独立的，**我们需要去维护每个时刻的算力和运行的任务**。如果某个时刻前面的**任务已经结束**，我们**需要重新加回该任务所消耗的算力值**。我们可以考虑用一下**优先队列**来去维护计算机的算力和运行的任务。我们需要定义**pair来存储某个任务结束的时间点和所需算力值**。我们结合代码理解：

#include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    
    #define x first
    #define y second
    
    using namespace std;
    
    typedef pair<int,int> PII;  //first ：某个任务结束的时间点。 second ：该任务所需算力值 
    
    const int N=2e5+10;
    
    int n,m;
    int s[N]; //存储剩余的算力
    
    priority_queue<PII,vector<PII>,greater<PII>> q[N];  //小根堆。存储正在计算的任务
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",&s[i]);
        
        while(m--)
        {
            int a,b,c,d;
            scanf("%d%d%d%d",&a,&b,&c,&d);
            
            while(q[b].size() && q[b].top().x<=a)  //判断是否寂静有任务结束
            {
                s[b]+=q[b].top().y;
                q[b].pop();
            }
            
            if(s[b]<d)
                puts("-1");
            else
            {
                s[b]-=d;
                q[b].push({a+c,d});
                
                printf("%d\n",s[b]);
            }
        }
        return 0;
    }

## 五、国际象棋 ##

### 5、1 题目描述 ###

> **题目来源：**第十二届[蓝桥杯][Link 1]省赛第二场
> 
> **题目难度：**困难
> 
> **题目描述:** 众所周知，“八皇后” 问题是求解在国际象棋棋盘上摆放 88 个皇后，使得两两之间互不攻击的方案数。已经学习了很多算法的小蓝觉得 “八皇后” 问题太简单了，意犹未尽。作为一个国际象棋迷，他想研究在 N×M 的棋盘上，摆放 K 个马，使得两两之间互不攻击有多少种摆放方案。由于方案数可能很大，只需计算答案除以 1000000007 (即 1e9+7) 的余数。
> 
> 如下图所示，国际象棋中的马摆放在棋盘的方格内，走 “日” 字，位于 (x,y) 格的马（第 x 行第 y 列）可以攻击 (x+1,y+2)、(x+1,y−2)、(x−1,y+2)、(x−1,y−2)、(x+2,y+1)、(x+2,y−1)、(x−2,y+1) 和 (x−2,y−1) 共 8 个格子。
> 
> ![fac2a0611c1243998df959c7690a5528.png][]
> 
> **输入格式：**
> 
> 输入一行包含三个正整数 N,M,K，分别表示棋盘的行数、列数和马的个数。
> 
> **输出格式：**
> 
> 输出一个整数，表示摆放的方案数除以 1000000007 (即 1e9+7) 的余数。
> 
> **数据范围：**
> 
> 对于 5% 的评测用例，K=1；  
> 对于另外 10% 的评测用例，K=2；  
> 对于另外 10% 的评测用例，N=1；  
> 对于另外 20% 的评测用例，N,M≤6，K≤5；  
> 对于另外 25% 的评测用例，N≤3，M≤20，K≤12；  
> 对于所有评测用例，1≤N≤6，1≤M≤100，1≤K≤20。
> 
> **输入样例1：**
> 
>     1 2 1
> 
> **输出样例1：**
> 
>     2
> 
> **输入样例2：**
> 
>     4 4 3
> 
> **输出样例2：**
> 
>     276
> 
> **输入样例3：**
> 
>     3 20 12
> 
> **输出样例3：**
> 
>     914051446

### 5、2 题解关键思路与解答 ###

> 以下题解来自于Acwing。
> 
> 我们首先将问题化简一下，首先考虑一个n行m列的棋盘最多能有多少种摆放方式，能够不发生冲突。如果采用dfs的思想我们是一定会超时的，此时一看n是小于6的那么我们就可以采用状态压缩递推出方法数。然后我们此时一看他的限制条件，是一个日字型，与前面两列都是有关的，所以我们的状态至少要保持前面两列的状态。思考完这些我们便可以推算出全部的摆放方式，在来思考摆放的个数限制条件，我们可以在加一个维度来记录即可。我们结合代码一起理解：

#include<iostream>
    using namespace std;
    const int N=1<<6;
    const int M=110;
    const int T=30;
    const int mod=1e9+7;
    typedef long long ll;
    ll f[M][N][N][T];//f[i][a][b][t] i 代表前i列 a代表前前列，b代表前面一列的状态集合 t代表已经用过多少个棋子
    int lowit(int x){//计算当前列增加了多少个棋子
        int res=0;
        for(;x;x-=(x&-x))res++;
        return res;
    }
    int main(){
        int n,m,k;
        cin>>n>>m>>k;
        int maxn=1<<n;
        f[0][0][0][0]=1;//初始化
        for(int i=1;i<=m;i++)
            for(int a=0;a<maxn;a++)
                for(int b=0;b<maxn;b++)
                    if((a>>2)&b||a&(b>>2))continue;//判断前前列和前列有没有发生冲突剪枝
                    else
                        for(int c=0;c<maxn;c++){
                            if((c>>2)&b||c&(b>>2))continue;//判断前列和当前列有没有发生冲突
                            if((c>>1)&a||c&(a>>1))continue;//判断前前列和当前列有没有发生冲突
                            int t=lowit(c);
                            for(int tt=t;tt<=k;tt++)//背包计算个数
                                f[i][b][c][tt]=(f[i][b][c][tt]+f[i-1][a][b][tt-t])%mod;
                        }
        int res=0;
        for(int i=0;i<maxn;i++)//对前前列和前列不同的状态最终有多少个可以摆放的方案数
            for(int j=0;j<maxn;j++)
                res=(res+f[m][i][j][k])%mod;
        cout<<res;
    }

[701718904a934962b72237b8d2cde2bb.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/17fe25a39e314f8f87e2b3ff725fa6e3.gif
[5e140be53a354e7c98d9dd38f0bed8a2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/6535b14693b04a6d8154b7d6a10ddb95.png
[Link 1]: https://so.csdn.net/so/search?q=%E8%93%9D%E6%A1%A5%E6%9D%AF&spm=1001.2101.3001.7020
[fac2a0611c1243998df959c7690a5528.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/063a70da224246818a258208c4f96630.png