文章目录
一、特殊年份
1、1 题目描述
1、2 题解关键思路与解答
二、小平方
2、1 题目描述
2、2 题解关键思路与解答
三、完全平方数
3、1 题目描述
3、2 题解关键思路与解答
四、负载均衡
4、1 题目描述
4、2 题解关键思路与解答
五、国际象棋
5、1 题目描述
5、2 题解关键思路与解答
♂️作者:@Ggggggtm♂️
专栏:数据结构与算法
标题:第十二届蓝桥杯省赛第二场
❣️寄语:与其忙着诉苦,不如低头赶路,奋路前行,终将遇到一番好风景❣️
一、特殊年份
1、1 题目描述
题目来源:第十二届蓝桥杯省赛第二场
题目难度:简单
题目描述:今年是2021年,2021这个数字非常特殊,它的千位和十位相等,个位比百位大1,我们称满足这样条件的年份为特殊年份。输入5个年份,请计算这里面有多少个特殊年份。
输入格式:输入5行,每行一个44位十进制数(数值范围为1000 至9999),表示一个年份。
输出格式:输出一个整数,表示输入的55个年份中有多少个特殊年份。
输入样例:
20192021192021209899
输出样例:
2
样例解释:2021和9899是特殊年份,其它不是特殊年份。
1、2 题解关键思路与解答
这道题的思路什么简单,我们只需要将年份的各个数字拿出来,看是否满足:它的千位和十位相等,个位比百位大1 即可。我们直接看代码:
#includeusing 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 题目描述
题目来源:第十二届蓝桥杯省赛第二场
题目难度:简单
题目描述:小蓝发现,对于一个正整数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 题解关键思路与解答
由于数据范围较小,所以我们直接暴力枚举即可。我们直接看代码:
#includeusing 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 题目描述
题目来源:第十二届蓝桥杯省赛第二场
题目难度:简单
题目描述:一个整数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 题解关键思路与解答
从题目中给出的数据范围可知,我们如果暴力去找最小的数,是不行的。这里就用到了质因数。如果一个数完全平方数,那么这个数的所有质因数的个数为偶数。根据这一特点,我们就判单题目中给出的数据,找出该数据的质因数个数为奇数的,然后相互乘起来就是我们所要的结果。我们结合代码一起理解一下。
#includeusing namespace std;typedef long long LL;int main(){ LL n; scanf("%lld",&n); LL res=1; for(LL i=2;i*i1) res*=n; cout<<res; return 0;}
四、负载均衡
4、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
输出格式:
输出m行,每行包含一个数,对应每次任务分配的结果。
数据范围:
对于20% 的评测用例,n,m≤200。
对于40% 的评测用例,n,m≤2000。
对于所有评测用例,1≤n,m≤200000,1≤ai,ci,di,vi≤1e9,1≤bi≤n。输入样例:
2 65 51 1 5 32 2 2 63 1 2 34 1 6 15 1 3 36 1 3 4
输出样例:
2-1-11-10
样例解释:
时刻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#include#include#include#define x first#define y secondusing namespace std;typedef pair PII; //first :某个任务结束的时间点。 second :该任务所需算力值 const int N=2e5+10;int n,m;int s[N]; //存储剩余的算力priority_queue<PII,vector,greater> 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 题目描述
题目来源:第十二届蓝桥杯省赛第二场
题目难度:困难
题目描述:众所周知,“八皇后” 问题是求解在国际象棋棋盘上摆放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个格子。
输入格式:
输入一行包含三个正整数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的那么我们就可以采用状态压缩递推出方法数。然后我们此时一看他的限制条件,是一个日字型,与前面两列都是有关的,所以我们的状态至少要保持前面两列的状态。思考完这些我们便可以推算出全部的摆放方式,在来思考摆放的个数限制条件,我们可以在加一个维度来记录即可。我们结合代码一起理解:
#includeusing namespace std;const int N=1<>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>2)&b||a&(b>>2))continue;//判断前前列和前列有没有发生冲突剪枝 else for(int c=0;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;}