挂个 dotcpp 的 oj ,蓝桥杯的题都能来这里交
2023年第十四届蓝桥杯大赛软件类省赛C/C++大学A组真题 (dotcpp.com)
目录
试题 A: 幸运数(枚举)
思路:
代码:
试题 B: 有奖问答(搜索 / 线性dp)
试题 C: 平方差(数学 / 结论)
思路:
代码:
试题 D: 更小的数(区间dp)
思路:
代码:
试题 E: 颜色平衡树( 树形dp(60%) / 平衡树 )
试题 F: 买瓜(搜索剪枝)
思路:
代码:
试题 G: 网络稳定性(多源最短路(30%))
思路:
代码:
试题 H: 异或和之和(前缀和(60%))
思路:
代码:
试题 I: 像素放置(搜索剪枝)
思路:
代码:
试题 J: 翻转硬币(莫比乌斯函数)
试题 A: 幸运数(枚举)
本题总分:5 分
【问题描述】
共有多少个不同的幸运数字。
【答案提交】
答案为:4430091
思路:
数据范围10^8,直接全部枚举,判断是否幸运即可
代码:
#include<bits/stdc++.h>
using namespace std;
bool check(int x){
int tmp=x,len=0;
while(tmp){
len++;
tmp/=10;
}
if(len%2==1)return 0;
int t=len/2;
int ans1=0,ans2=0;
while(t--){
ans1+=x%10;
x/=10;
}
while(x){
ans2+=x%10;
x/=10;
}
return ans1==ans2;
}
int main(){
int ans=0;
for(int i=10;i<=100000000;i++){
if(check(i))ans++;
}
cout<<ans;
return 0;
}
试题 B: 有奖问答(搜索 / 线性dp)
本题总分:5 分
【问题描述】
有多少种?
【答案提交】
个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
试题 C: 平方差(数学 / 结论)
本题总分:10 分
【问题描述】
给定 L, R,问 L ≤ x ≤ R 中有多少个数 x 满足存在整数 y,z 使得 x = y^ 2 − z^ 2 。
【输入格式】
输入一行包含两个整数 L, R,用一个空格分隔。
【输出格式】
输出一行包含一个整数满足题目给定条件的 x 的数量。
【样例输入】
1 5
【样例输出】
4
【样例说明】
5 = 3^2 − 2 ^2 。
【评测用例规模与约定】 文章来源地址https://www.toymoban.com/news/detail-426342.html
思路:
找规律,发现所有的奇数都可以拆成 x/2 +1 和 x/2 的平方差
而所有的 4k+2 型的数不能拆成平方差, 4k 型的数可以拆成平方差
然后直接计算公式 前 R 个数 和 前 L-1 个数 即可
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f(ll x){
return x-x/4-(x%4>=2);
}
void solve(){
ll L,R;
cin>>L>>R;
cout<<f(R)-f(L-1);
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
试题 D: 更小的数(区间dp)
本题总分:10 分
【问题描述】
小蓝有一个长度均为 n 且仅由数字字符 0 ∼ 9 组成的字符串,下标从 0 到 n − 1,你可以将其视作是一个具有 n 位的十进制数字 num,小蓝可以从 num 中 选出一段连续的子串并将子串进行反转,最多反转一次。
小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字 numnew 满足条件 numnew < num, 请你帮他计算下一共有多少种不同的子串选择方案,只要两个子串在 num 中的 位置不完全相同我们就视作是不同的方案。
注意,我们允许前导零的存在,即数字的最高位可以是 0 ,这是合法的。
【输入格式】
从左至右下标依次为 0 ∼ n − 1。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
210102
【样例输出】
8
【样例说明】
一共有 8 种不同的方案:
8)所选择的子串下标为 3 ∼ 4 ,反转后的 numnew = 210012 < 210102 ;
【评测用例规模与约定】
思路:
非常标准的区间dp,bool数组记录这个区间能否翻转,如果左端大于右端,则可以翻转;如果两端一样则区间缩小两位,转移状态到小区间
状态转移方程:dp [ i ] [ i+k ] = dp [ i+1 ] [ i+k-1 ]
代码:
#include<bits/stdc++.h>
using namespace std;
void solve(){
string s;
cin>>s;
int n=s.length();
s=' '+s;
long long ans=0;
vector<vector<bool> >dp(n+1,vector<bool>(n+1,0));
for(int k=1;k<=n;k++){
for(int i=1;i+k<=n;i++){
if(s[i]>s[i+k]) dp[i][i+k]=1;
else if(s[i]<s[i+k]) dp[i][i+k]=0;
else dp[i][i+k]=dp[i+1][i+k-1];
ans+=dp[i][i+k];
}
}
cout<<ans;
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
试题 E: 颜色平衡树( 树形dp(60%) / 平衡树 )
本题总分:15 分
【问题描述】
平衡树。
求出这棵树中有多少个子树是颜色平衡树。
【输入格式】
的颜色和父亲结点编号。
据是一棵树。
输出一行包含一个整数表示答案。
【样例输入】
62 02 11 23 33 41 4
【样例输出】
4
【样例说明】
编号为 1, 3, 5, 6 的 4 个结点对应的子树为颜色平衡树。
【评测用例规模与约定】
试题 F: 买瓜(搜索剪枝)
本题总分:15 分
【问题描述】
请问小蓝至少要劈多少个瓜才能买到重量恰好为 m 的瓜。如果无论怎样小蓝都无法得到总重恰好为 m 的瓜,请输出 −1 。
【输入格式】
瓜的重量。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
3 101 3 13
【样例输出】
2
【评测用例规模与约定】
思路:
搜索剪枝,玄学复杂度,不知道能过多少,但60%应该有的
每个瓜有三种情况,全买,买一半,都不买,我们先把所有瓜排序再搜索,便于剪枝
剪枝策略:
1. 剩余的瓜全买也不足m
2. 当前的重量大于m
3. 当前的瓜数大于等于答案
4. 当前状态如果取到 和目前最优解一样的瓜数 也达不到m重量
代码:
先上课去了
试题 G: 网络稳定性(多源最短路(30%))
本题总分:20 分
【问题描述】
稳定性。如果两台设备之间不存在任何路径,请输出 −1 。
【输入格式】
性。
【输出格式】
输出 q 行,每行包含一个整数依次表示每个询问的答案。
【样例输入】
5 4 31 2 52 3 63 4 11 4 31 52 41 3
【样例输出】
-135
【评测用例规模与约定】
思路:
正解是nlogn的复杂度,暂时不会
考场直接Floyd算出任意两点间的稳定性,n^3拿30%跑路
代码:
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int dp[5005][5005];
void solve(){
memset(dp,-1,sizeof(dp));
cin>>n>>m>>q;
while(m--){
int u,v,x;
cin>>u>>v>>x;
dp[u][v]=max(dp[u][v],x); //选稳定性最大的一条路
dp[v][u]=max(dp[v][u],x);
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j&&j!=k&&i!=k){ //用 以K中转的路径 更新dp[i][j]
dp[i][j]=max(dp[i][j],min(dp[i][k],dp[k][j]));
}
}
}
}
while(q--){
int x,y;
cin>>x>>y;
cout<<dp[x][y]<<endl;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
试题 H: 异或和之和(前缀和(60%))
本题总分:20 分
【问题描述】
然后输出每组 L, R 得到的结果加起来的值。
【输入格式】
第二行包含 n 个整数 Ai ,相邻整数之间使用一个空格分隔。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
51 2 3 4 5
【样例输出】
39
【评测用例规模与约定】
思路:
异或其实和加法差不多,用前缀和O(N)预处理,n^2枚举 L和R 过60%跑路
减去之前异或过的数,相当于在异或一遍,两次异或 = 异或 0
ans(L,R) = pre [ R ] ^ pre [ L-1 ]
代码:
#include<bits/stdc++.h>
using namespace std;
long long a[100005],pre[100005];
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
pre[i]=pre[i-1]^a[i];
}
long long ans=0;
for(int L=1;L<=n;L++){
for(int R=L;R<=n;R++){
ans+=pre[R]^pre[L-1];
}
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
试题 I: 像素放置(搜索剪枝)
本题总分:25 分
【问题描述】
小蓝最近迷上了一款名为《像素放置》的游戏,游戏在一个 n × m 的网格棋盘上进行,棋盘含有 n 行,每行包含 m 个方格。
玩家的任务就是需要对这n × m 个方格进行像素填充,填充颜色只有黑色或白色两种。有些方格中会出现一个整数数字 x(0 ≤ x ≤ 9),这表示当前方格加上周围八个方向上相邻的方格(分别是上方、下方、左方、右方、左上方、右上方、左下方、右下方)共九个
玩家需要在满足所有数字约束下对网格进行像素填充,请你帮助小蓝来完成。题目保证所有数据都有解并且解是唯一的。
【输入格式】
接下来 n 行,每行包含 m 个字符,表示棋盘布局。字符可能是数字 0 ∼ 9,这表示网格上的数字;字符还有可能是下划线(ASCII 码为 95 ),表示一个不 带有数字的普通网格。
【输出格式】
输出 n 行,每行包含 m 个字符,表示答案。如果网格填充白色则用字符 0表示,如果网格填充黑色则用字符 1 表示。
【样例输入】
6 8_1__5_1_1_4__42_3__6__5____56____688___4_____6__
【样例输出】
000110000011110001000010111111110101111001111110
上图左是样例数据对应的棋盘布局,上图右是此局游戏的解。例如第 3 行第 1 列处的方格中有一个数字 3 ,它周围有且仅有 3 个格子被黑色填充,分别是第 3 行第 2 列、第 4 行第 1 列和第 4 行第 2 列的方格。
【评测用例规模与约定】
思路:
搜索剪枝,枚举所有的状态,然后根据给出的黑色个数来剪枝,因为样例的6*8秒出了,复杂度应该差不多(剪枝复杂度都是玄学)
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[15][15];
int n,m;
int ans[15][15];
bool flag=0;
int d[9][2]={-1,-1,-1,0,-1,1,0,-1,0,0,0,1,1,-1,1,0,1,1};
int cnt(int x,int y){
int res=0;
for(int i=0;i<9;i++){
int dx=x+d[i][0],dy=y+d[i][1];
res+=(ans[dx][dy]==1);
}
return res;
}
bool check(int x,int y){
for(int i=1;i<=x-2;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==-1)continue;
if(cnt(i,j)!=a[i][j]){
return 0;
}
}
}
if(x>=2)
for(int j=1;j<=y-2;j++){
if(a[x-1][j]==-1)continue;
if(cnt(x-1,j)!=a[x-1][j])return 0;
}
return 1;
}
bool check2(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==-1)continue;
if(cnt(i,j)!=a[i][j]){
return 0;
}
}
}
return 1;
}
void dfs(int x,int y){
if(flag)return;
if(x==n+1){
if(check2()==0)return;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<ans[i][j];
}
cout<<endl;
}
flag=1;
return;
}
if(check(x,y)==0)return;
if(y==m){
ans[x][y]=1;
dfs(x+1,1);
ans[x][y]=0;
dfs(x+1,1);
return;
}
ans[x][y]=1;
dfs(x,y+1);
ans[x][y]=0;
dfs(x,y+1);
return;
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char ch;
cin>>ch;
if(ch=='_')a[i][j]=-1;
else a[i][j]=ch-'0';
}
}
dfs(1,1);
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
/*
6 8
_1__5_1_
1_4__42_
3__6__5_
___56___
_688___4
_____6__
*/
试题 J: 翻转硬币(莫比乌斯函数)
本题总分:25 分
【问题描述】
求最少需要多少次操作可以让所有硬币都朝上。
【输入格式】
输入一行包含一个整数 n 。
【输出格式】
输出一行包含一个整数表示最少需要的操作次数。
【样例输入 1】
7
【样例输出 1】
6
【样例输入 2】
1131796
【样例输出 2】 文章来源:https://www.toymoban.com/news/detail-426342.html
688042
【评测用例规模与约定】
到了这里,关于2023第14届蓝桥杯C/C++A组省赛题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!