2020 蓝桥杯大学 B 组省赛模拟赛（一）

编程入门行业动态更新时间:2024-10-25 06:23:53

2020 蓝桥杯<a href=https://www.elefans.com/category/jswz/34/1770028.html style= 大学 B 组省赛模拟赛（一）"/>

2020 蓝桥杯大学 B 组省赛模拟赛（一）

A. 结果填空：有趣的数字

我们称一个数是质数，而且数位中出现了 5 的数字是有趣的。例如 5, 59, 457 都是有趣的，而 15, 7不是。求 1 到 100000中有趣的数的个数。
思路：比赛的时候能暴力就暴力吧，求1到100000的质数中包含5的个数，直接两个函数一个判断质数，一个判断5，时间复杂度太大，建议素数打表。

# include<iostream>
using namespace std;
typedef long long ll;
ll fun1(ll n)
{for(ll i=2;i*i<=n;i++)if(n%i==0)return 0;return 1;
}
ll fun2(ll n)
{while(n){int t=n%10;if(t==5)return 1;n/=10;}return 0;
}
int main()
{ll sum=0;for(int i=2;i<=100000;i++){if(fun1(i)&&fun2(i)){sum++;//cout<<i<<" ";}}cout<<sum<<endl;return 0;}

素数打表

 # include<iostream># include<cstring>#include<cstdio>using namespace std;# define N 100000int prime[N],n;void Prime(){for(int i=2;i*i<=N;i++){if(!prime[i])for(int j=i*i;j<=N;j+=i)prime[j]=1;}}int main(){int ans=0;memset(prime,0,sizeof(prime));Prime();for(int i=5;i<=100000;i++){if(!prime[i]){int t=i;while(t){int temp=t%10;if(temp==5){ans++;break;}t/=10;}}}cout<<ans<<endl;return 0;}

B. 结果填空：爬楼梯

蒜头君要爬楼梯。楼梯一共有 10 层台阶。因为腿长的限制，每次最多能上 4 层台阶。但是第 5,7 层楼梯坏掉了不能踩。求上楼梯的方案数。
思路：之前没有遇见过这种台阶问题，其实可以用递归，递推，动态规划，找规律都能解决
第5层台阶与前边的四层相关，去掉5,7层就行，怎么去掉呢？=0即可

# include<iostream>
using namespace std;
int fun(int n)
{if(n==1)return 1;if(n==2)return 2;if(n==3)return 4;if(n==4)return 8;if(n==5||n==7) return 0;return fun(n-1)+fun(n-2)+fun(n-3)+fun(n-4);
}  int main()
{int ans=fun(10);cout<<ans;return 0;
}

~~待更：~~ =============================================

C. 结果填空：七巧板

原题链接：传送门
思路：跟平面划分差不多，找规律，第一条直线将内部划分6个区域，以后以此类推：6 7 8 9 10，总的区域：7+6+7+8+9+10

#include<cstdio>
using namespace std;
int fun(int n)
{if(n==1)return 6;elsereturn fun(n-1)+1;
}
int main()
{int ans=7;for(int i=1;i<=5;i++)ans+=fun(i);printf("%d\n",ans);return 0;
}

小结：类推空三角形1+1+2+3+4+5= 16（f(n)=f(n-1)+1）

D. 结果填空：苹果

原题链接：传送门
思路：贪心

从左往右枚举每一个，先一次取3个苹果，再从后边两个加本身这个各取1个苹果（直到不能取为止）62
第一次取3个苹果，第二次取1 1 1个苹果（只取一次）60
与1相反59
所以答案62
1：

#include<cstdio>
using namespace std;
int main()
{   int a[30],ans=0;for(int i=0;i<30;i++)scanf("%d",&a[i]);for(int i=0;i<30;i++){ans+=a[i]/3;a[i]%=3;while(a[i]>0&&a[i+1]>0&&a[i+2]>0){ans++;a[i]--;a[i+1]--;a[i+2]--;}}   printf("%d",ans); return 0;
}

2：

#include<cstdio>
using namespace std;
int main()
{int a[30],ans=0;for(int i=0;i<30;i++)scanf("%d",&a[i]);for(int i=0;i<30;i++){ans+=a[i]/3;a[i]%=3;if(a[i]>0&&a[i+1]>0&&a[i+2]>0){ans++;a[i]--;a[i+1]--;a[i+2]--;}}printf("%d",ans);return 0;
}

3：

#include<cstdio>
using namespace std;
int main()
{int a[30],ans=0;for(int i=0;i<30;i++)scanf("%d",&a[i]);for(int i=0;i<30;i++){while(a[i]>0&&a[i+1]>0&&a[i+2]>0){ans++;a[i]--;a[i+1]--;a[i+2]--;}ans+=a[i]/3;a[i]%=3;}printf("%d",ans);return 0;
}

待更 ==============================================

F. 程序设计：寻找重复项

有一个数列 {an}，a0=1，ai+1 =(A*ai+ai mod B)mod C请你编程求出这个数列第一次出现重复的项的标号。如果答案超过 2000000 输出 “-1”（不加引号）
输入格式
第一行三个整数 A,B,C 。
输出格式
输出一行一个整数表示答案。
数据范围
对于 30% 的数据： 0 < A,B,C<= 10^5 ,
对于 100% 的数据： 0 < A,B,C <=10^9.
思路1：依次枚举ai+1,每次判断是否在之前出现过

# include<iostream>
# include<utility>
# include<vector>
# include<cmath>
# include<algorithm>
using namespace std;
typedef long long ll; 
vector<int>v;
ll a[1000001];
ll ans=0;
int main()
{ll i=0,A,B,C;cin>>A>>B>>C;a[0]=1;v.push_back(1);for(i=0;;i++){a[i+1]=(A*a[i]+a[i]%B)%C;//cout<<a[i+1];if(i+1>2000000){cout<<"-1"<<endl;break;}if(find(v.begin(),v.end(),a[i+1])==v.end()){v.push_back(a[i+1]);//ans++;}else{cout<<i+1<<endl;break;}}return 0;
}

这个用到的是不定长数组，结局悲凉，仅通过四组数据…（超时）
思路2：想到了用map来，从key到value的映射，key只能出现一次

# include<iostream>
# include<map>
#include<unordered_map> 
using namespace std;
typedef long long ll;
int main()
{unordered_map<ll,ll>node;ll A,B,C,a=1;cin>>A>>B>>C;node[1]=1;//以数组形式插入 for(int i=1;i<=2000000;i++){ll b=(A*a+a%B)%C;if(node[b]){cout<<i<<endl;return 0;}a=b;node[b]=1;}cout<<"-1"<<endl;return 0;
}

该方法能通过9组测试数据主要原因是超时了（map的key会排序，应该是浪费了时间）
用map会超时，可以用unordered_map来标记(正解,可AC)
思路3：既然map（映射的关系）key只允许出现一次，那么我们也可以用set来标记，其中有一个方法count就是来统计元素出现的次数（这个很少用到）count=0表示该元素在集合中没出现过=1出现过

# include<iostream>
# include<map>
#include<unordered_map> 
#include<set>
#include<unordered_set> 
using namespace std;
typedef long long ll;
int main()
{set<int>node;//将set换成unordered_set完美AC ll A,B,C,a=1;cin>>A>>B>>C;node.insert(1); for(int i=1;i<=2000000;i++){ll b=(A*a+a%B)%C;if(node.count(b)==1){cout<<i<<endl;return 0;}node.insert(b);a=b;  }cout<<"-1"<<endl;return 0;
}

感兴趣的可以试试，依然通过了9组数据（共10组），他和map一样内部是有序的，我们只需要将set换成unordered_set完美AC （这个内部时无序的）
H. 程序设计：字符串
有一个长度为 LL 的字符串，每个字符是大写字母。如果我们把 A 看做 0 ，B 看做 1 ，C 看做 2 … Z 看做 25，那么我们就得到了一个 26 进制的数字串。我们可以对这个字符串做一个操作：将两个位置的字母进行交换。这样得到了一个新的数字串。现在有一个十进制整数 M ，请判断是否可以通过做至多一次（可以不做）操作，使得得到的字符串是 M 的倍数。
输入格式
第一行一个只包含大写字母的字符串。
第二行一个整数 M 。
输出格式
如果初始串就可以，那么输出 “0 0”（不加引号）
如果通过一次操作可以，请输出交换的两个位置的标号（标号小的在前，从 1 开始）。如果有多解，输出字典序最小的。
如果做不到，那么输出 “-1 -1”（不加引号）
数据范围
字符串长度为 L 。
对于 30% 的数据：1<=L<=10,1<=M<=10.
对于 50% 的数据：除前面 30% 外， 1 <= L <=500, M = 5或25或26
对于 100% 的数据： 1≤L≤2,000,1≤M≤200,000
样例输入:
NETTLE
35
样例输出
1 2
样例解释
交换 N 和第一个 E 。
思路1：说实话，这个B组模拟出的题真是挺难的，各种坑，暴力方法就是每次枚举可能换的两个字母，并转换成10进制判断是否被整除，思路是对的。看结果…

#include<iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll ans=0;
ll fun(string s)
{ans=0;int len=s.size();for(int i=0,j=1;i<s.size();i++,j*=26){ans+=(int)(s[len-i-1]-'A')*j;}return ans;
}
int main(){string s,s2;ll m;cin>>s>>m;if(fun(s)%m==0){cout<<"0 0"<<endl;}else{int flag=1;char x;for(int i=0;i<s.size();i++){if(flag){for(int j=i+1;j<s.size();j++){s2=s;{x=s2[i];s2[i]=s2[j];s2[j]=x;if(fun(s2)%m==0){cout<<i+1<<" "<<j+1<<endl;flag=0;break;}}}}elsebreak;}if(flag==1)cout<<"-1"<<" "<<"-1"<<endl;}return 0;
}

仅通过了7组测试数据总共20
思路2：做一次26转10就行了，同时记录dist[i]为第i个字母的26的几次方，在枚举过程中，先减掉要交换字母的对应值，在加上交换后字母的对应值，取余判断就行

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2000+10;
ll ans=0,sum,mod,dist[N];
ll fun(string s)
{ans=0;//没看到要重置0 int len=s.size();for(int i=0,j=1;i<s.size();i++,j=(j*26)%mod){ans+=(s[len-i-1]-'A')*j;dist[len-i-1]=j;}return ans;
}
int main(){string s;cin>>s>>mod;sum=fun(s);if(sum%mod==0){printf("0 0\n");return 0;}for(int i=0;i<s.size();i++){for(int j=i+1;j<s.size();j++){ans=sum;ans=ans-(s[i]-'A')*dist[i]-(s[j]-'A')*dist[j];ans=ans+(s[i]-'A')*dist[j]+(s[j]-'A')*dist[i];ans=ans%mod;if(!ans){printf("%d %d\n",i+1,j+1);return 0;}}}printf("-1 -1\n");return 0;
}

待更 ===============================================
2020.1.29

J. 程序设计：迷宫

原题链接：传送门
思路：这道题我写了，只AC了6/10，不过还是想贴出来，以后自己再碰上了，回来看看是哪里错了。
坑太多了

传送多次：可能你走到下一步直接传送了n次（过程中可能遇到终点）如果遇到终点直接退出
传送成环：可能你传送一圈又回到了刚开始要被传送的地方（此时步数还是之前的）
传送过程是不计入步数的，只有在四周走的情况下计入步数

这些我都想了，可是还是没通过所有数据，呆了一下午也没改√，以后会了再来改吧

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int n,m,q,q1[100][4];
char map[1001][1001];
int vis[1001][1001];
char dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int x,y;
typedef struct map{int x,y;int step;
}node;
void bfs()
{queue<node>p;node head;head.x=1,head.y=1,head.step=0,vis[1][1]=1;p.push(head);while(!p.empty()){node head=p.front();p.pop();if(head.x==x&&head.y==y){printf("%d\n",head.step);return ;}node t;for(int i=0;i<4;i++){t.x=head.x+dir[i][0];t.y=head.y+dir[i][1];for(int j=0;j<q;j++)if(t.x>=1&&t.y>=1&&t.x<=n&&t.y<=m&&map[t.x][t.y]!='*'&&t.x==q1[j][0]&&t.y==q1[j][1]){    if(t.x==x&&t.y==y)//传送过程中遇到了终点 {printf("%d",head.step+1);return ;} t.x=q1[j][2];t.y=q1[j][3];}if(t.x>=1&&t.y>=1&&t.x<=n&&t.y<=m&&map[t.x][t.y]!='*'&&!vis[t.x][t.y]){ t.step=head.step+1;vis[t.x][t.y]=1;p.push(t);} }}printf("No solution\n");
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){getchar();for(int j=1;j<=m;j++)scanf("%c",&map[i][j]);}scanf("%d",&q);for(int i=0;i<q;i++)scanf("%d%d%d%d",&q1[i][0],&q1[i][1],&q1[i][2],&q1[i][3]);scanf("%d%d",&x,&y);memset(vis,0,sizeof(vis));bfs();return 0;}