信A第十二周题解

目录

洛谷 P5728 【深基5.例5】旗鼓相当的对手

洛谷 P9231 [蓝桥杯 2023 省 A] 平方差

洛谷 P2626 斐波那契数列（升级版）

洛谷 P1104 生日

洛谷 P1162 填涂颜色

洛谷 P1037 [NOIP 2002 普及组] 产生数

洛谷 P5728 【深基5.例5】旗鼓相当的对手

题目描述

现有 N 名同学参加了期末考试，并且获得了每名同学的信息：语文、数学、英语成绩（均为不超过 150 的自然数）。如果某对学生 ⟨i,j⟩ 的每一科成绩的分差都不大于 5，且总分分差不大于 10，那么这对学生就是“旗鼓相当的对手”。现在想知道这些同学中，有几对“旗鼓相当的对手”？同样一个人可能会和其他好几名同学结对。

输入格式

第一行一个正整数 N。

接下来 N 行，每行三个整数，其中第 i 行表示第 i 名同学的语文、数学、英语成绩。最先读入的同学编号为 1。

输出格式

输出一个整数，表示“旗鼓相当的对手”的对数。

输入输出样例

输入 #1复制

3 90 90 90 85 95 90 80 100 91

输出 #1复制

2

说明/提示

数据保证，2≤N≤1000 且每科成绩为不超过 150 的自然数。

注意到本题N≤1000，故可直接采用双重循环暴力枚举。

先读入成绩并预计算总分，再通过两层循环遍历所有满足j>i的学生对，若条件全部满足则计数加一，最终输出计数结果即可。

#include<bits/stdc++.h>//万能头文件，几乎包含竞赛涉及到的所有函数 using namespace std; int main(){ int N,sum=0; //N为同学人数，sum为最后统计对数 cin>>N; //注意到N<=1000,最坏情况暴力出所有结果也仅有1000000 //所以直接使用双重for循环暴力枚举出所有可能即可 vector<int> chinese(N+1), math(N+1), english(N+1), total(N+1); //vector为STL中的动态数组，分别用于存储四个值 for(int i=1;i<=N;i++){ cin >> chinese[i] >> math[i] >> english[i]; total[i] = chinese[i] + math[i] + english[i];} for(int i = 1;i <=N;i++)for(int j = i + 1;j <=N;j++) if (abs(chinese[i] - chinese[j])<=5&&abs(math[i] - math[j])<=5 &&abs(english[i] - english[j])<=5&&abs(total[i] - total[j])<=10)sum++; //利用双重for循环列举出所有情况，再用if进行判断是否符合 cout<<sum; return 0; }

洛谷 P9231 [蓝桥杯 2023 省 A] 平方差

题目描述

给定 L,R，问 L≤x≤R 中有多少个数 x 满足存在整数 y,z 使得 x=y2−z2。

输入格式

输入一行包含两个整数 L,R，用一个空格分隔。

输出格式

输出一行包含一个整数满足题目给定条件的 x 的数量。

输入输出样例

输入 #1复制

1 5

输出 #1复制

4

说明/提示

【样例说明】

• 1=12−02
• 3=22−12
• 4=22−02
• 5=32−22

【评测用例规模与约定】

对于 40% 的评测用例，L,R≤5000；

对于所有评测用例，1≤L≤R≤109。

第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 C

利用平方差公式寻找规律进行奇偶性讨论即可

#include<bits/stdc++.h>//万能头文件 using namespace std; int main(){ int L,R,sum=0; cin>>L>>R; //简单推导一下x=y²-z²=(y-z)(y+z), //不难看出y-z与y+z的奇偶性相同 //当同为奇数时，只需要保证y-z为1 //此时如果改变y+z的值，y与z变化相同(y+z可每次+-2），即y+z可表示所有奇数 //所有同为奇数时的所有情况都符合 //当同为偶数时，即y与z的奇偶性相同，取(y-z)最小值即保证(y-z)为2 //同理y与z变化相同(y+z可每次+-2），即y+z可表示所有偶数 //但是由于同为偶数时前面(y-z)为2，即整体x的值为偶数的2倍即x为4的倍数 //综上所述满足要求的值为[L,R]间所有奇数与四的倍数的和 cout<<(R+1)/2-L/2+R/4-(L-1)/4; //(R+1)/2是区间[0,R]奇数的个数，L/2是区间[0,L-1]奇数的个数 //即(R+1)/2-L/2是区间[L,R]奇数的个数 //R/4是区间[0,R]四的倍数的个数，(L-1)/4是区间[0,L-1]四的倍数的个数 //即R/4-(L-1)/4是区间[L,R]四的倍数的个数 return 0; }

洛谷 P2626 斐波那契数列（升级版）

题目背景

大家都知道，斐波那契数列是满足如下性质的一个数列：

• f(1)=1
• f(2)=1
• f(n)=f(n−1)+f(n−2)（n>2 且 n 为整数）。

题目描述

请你求出第 n 个斐波那契数列的数 mod231 之后的值，并把它分解质因数。

输入格式

输入一个正整数 n。

输出格式

把第 n 个斐波那契数列的数分解质因数。

输入输出样例

输入 #1复制

5

输出 #1复制

5=5

输入 #2复制

6

输出 #2复制

8=2*2*2

说明/提示

n≤48

本题先求出第n位斐波那契数再进行质因数的寻找即可解出

#include<bits/stdc++.h>//万能头文件 using namespace std; int main(){ long long n,f1=1,f2=1,N; bool x=true; cin>>n; //易知要求f(n)，只需要知道f(n-1)和f(n-2) //我们可通过斐波那契数列的规则求出f(n-1)和f(n-2) for(long long i=3;i<n;i++){ if(i%2==0)f2+=f1; else f1+=f2;} //f1为奇数位需要的f(n-1)或f(n-2)，f2为偶数位需要的f(n-1)或f(n-2) //每次循环可以求出后一位所需要的值 //我们也可以直接循环到第n个斐波那契数列的数如果n为奇数则是f1反之则为f2 long long w=pow(2,31); //w为需要mod的值 N=(f1+f2)%w; //求出第N个数后根据题目要求进行mod cout<<N<<'='; for(long long i=2;i<=N;i++)while(N%i==0){ if(x){x=false; cout<<i;} else cout<<"*"<<i; N/=i;} //利用for循环进行遍历，while循环可以对同一个质因数进行多次分解 //注意每一次分解需要添加一个* return 0; }

洛谷 P1104 生日

题目描述

cjf 君想调查学校 OI 组每个同学的生日，并按照年龄从大到小的顺序排序。但 cjf 君最近作业很多，没有时间，所以请你帮她排序。

输入格式

输入共有 n+1 行，

第 1 行为 OI 组总人数 n；

第 2 行至第 n+1 行分别是每人的姓名 s、出生年 y、月 m、日 d。

输出格式

输出共有 n 行，即 n 个年龄从大到小同学的姓名（如果有两个同学年龄相同，输入靠后的同学先输出）。

输入输出样例

输入 #1复制

3 Yangchu 1992 4 23 Qiujingya 1993 10 13 Luowen 1991 8 1

输出 #1复制

Luowen Yangchu Qiujingya

说明/提示

数据保证，1<n<100，1≤∣s∣<20。保证年月日实际存在，且年份 ∈[1960,2020]。

看题目可以知道，因为涉及每个人的名字（string类型）、出生年月日还有排名（int类型）所以要用到结构体代表每个人的各种数据即

struct birthday{ string name; int year,month,day; int rank;};

由于要按照由大到小的排序方式，因为涉及结构体所以我们可以直接涉及一个排序比较方式即

bool compare(birthday& a,birthday&b){ if(a.year != b.year)return a.year<b.year; if(a.month != b.month)return a.month<b.month; if(a.day != b.day)return a.day<b.day; return a.rank>b.rank; }

排名比较方式有了之后就可以用sort进行排序即可得到最后的排名结果

最后代码如下

#include<bits/stdc++.h> using namespace std; struct birthday{ string name; int year,month,day; int rank;}; bool compare(birthday& a,birthday&b){ if(a.year != b.year)return a.year<b.year; if(a.month != b.month)return a.month<b.month; if(a.day != b.day)return a.day<b.day; return a.rank>b.rank; } int main(){ int n; cin>>n; vector<birthday>student(n+1); for(int i=1;i<=n;i++){ cin >>student[i].name>>student[i].year>>student[i].month>>student[i].day; student[i].rank=i;} sort(student.begin()+1,student.end(),compare); for(int i=1;i<=n;i++)cout<<student[i].name<<endl; return 0; }

洛谷 P1162 填涂颜色

题目描述

由数字 0 组成的方阵中，有一任意形状的由数字 1 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 2。例如：6×6 的方阵（n=6），涂色前和涂色后的方阵如下：

如果从某个 0 出发，只向上下左右 4 个方向移动且仅经过其他 0 的情况下，无法到达方阵的边界，就认为这个 0在闭合圈内。闭合圈不一定是环形的，可以是任意形状，但保证闭合圈内的 0 是连通的（两两之间可以相互到达）。

0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 1 0 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 2 2 1 1 1 2 2 2 1 1 2 2 1 2 1 1 1 1 1 1 1

输入格式

每组测试数据第一行一个整数 n(1≤n≤30)。

接下来 n 行，由 0 和 1 组成的 n×n 的方阵。

方阵内只有一个闭合圈，圈内至少有一个 0。

输出格式

已经填好数字 2 的完整方阵。

输入输出样例

输入 #1复制

6 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1

输出 #1复制

0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 2 2 1 1 1 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 1

说明/提示

对于 100% 的数据，1≤n≤30。

DFS做法：

题目让我们修改闭合圈内的数字，但是我们可以通过修改闭合圈外的数字来解决闭合圈内数字的问题。首先我们通过DFS寻找闭合圈外的0，并使其改为2，然后再通过a[i][j]=2-a[i][j]进行反转还原圈外的0同时保证圈数字1不变还能使圈内的数字变成要求的2

#include<bits/stdc++.h> using namespace std; int n; int a[32][32]; void dfs(int x,int y){ if(x<0||x>n+1||y<0||y>n+1||a[x][y]!=0)return; a[x][y]=2; dfs(x,y+1); dfs(x,y-1); dfs(x+1,y); dfs(x-1,y); } int main(){ cin>>n; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j]; dfs(0,0); for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=2-a[i][j]; for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cout<<a[i][j]<<' ';cout<<endl;} return 0; }

洛谷 P1037 [NOIP 2002 普及组] 产生数

题目描述

给出一个整数 n 和 k 个变换规则。

规则：

• 一位数可变换成另一个一位数。
• 规则的右部不能为零。

例如：n=234,k=2。有以下两个规则：

• 2⟶5。
• 3⟶6。

上面的整数 234 经过变换后可能产生出的整数为（包括原数）:

• 234。
• 534。
• 264。
• 564。

共 4 种不同的产生数。

现在给出一个整数 n 和 k 个规则。求出经过任意次的变换（0 次或多次），能产生出多少个不同整数。

仅要求输出个数。

输入格式

第一行两个整数 n,k，含义如题面所示。

接下来 k 行，每行两个整数 xi​,yi​，表示每条规则。

输出格式

共一行，输出能生成的数字个数。

输入输出样例

输入 #1复制

234 2 2 5 3 6

输出 #1复制

4

说明/提示

对于 100% 数据，满足 n<1030，k≤15。

【题目来源】

NOIP 2002 普及组第三题

看题可知，每一个数字可以有多种变换，然后我们通过观察变换规则可以看出规则具有传递性，由于不限制变换次数且每位数位置固定所以只用统计出每位数变换的可能再相乘即可，但是本体的数据超过long long范围所以我们需要使用到高精度或者_int128来进行统计

用rule[i][j]来表示从i到j的变换规则，用k,i,j的三层循环来推出其衍生的变换规则（注意利用rule[i][k]规则是否存在来进行截枝），最后用sum[i]统计每个数的变换可能次数。下面是通过高精度来对每一位进行相乘计算由于我这使用的是高精度所以最后要倒序输出

#include<bits/stdc++.h> using namespace std; int rule[10][10]; int sum[10]; int main() { string n; int k; cin>>n>>k; for(int i=0;i<10;i++)rule[i][i]=1; while(k--){ int x,y; cin>>x>>y; rule[x][y]=1;} for(int k=0;k<10;k++) for(int i=0;i<10;i++)if(rule[i][k]) for(int j=0;j<10;j++)if(rule[k][j]) rule[i][j]=1; for(int i=0;i<10;i++) for(int j=0;j<10;j++) sum[i]+=rule[i][j]; vector<int>ans; ans.push_back(1); for(char c:n){ int unm=c-'0'; int mul=sum[unm]; long long surplus=0; for(int i=0;i<ans.size();i++){ int new1=ans[i]*mul+surplus; ans[i]=new1%10; surplus=new1/10; } while(surplus>0){ ans.push_back(surplus%10); surplus/=10; } } for(int i=ans.size()-1;i>=0;i--)cout<<ans[i]; return 0; }