【比赛】第十四届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组(比赛过程记录,不是答案总结)
总结一下今天的蓝桥杯,唉,祈祷祈祷祈祷
第一次参加蓝桥杯,特发此文记录一下今天乱七八糟的做题状态。
试题 A: 日期统计(填空题)
【问题描述】
【思路】
【代码】
#include<bits/stdc++.h>
using namespace std;
int arr[105]{0};
int yuefen[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int yueshu=0;
int ans[13][32]{0};
int main()
{
for(int i=0;i<100;++i)
cin>>arr[i];
for(int i=0;i<100;++i)cout<<arr[i]<<' ';cout<<endl;
//long long sum=0;
for(int a=0;a<100;++a)
if(arr[a]==2)
for(int b=a+1;b<100;++b)
if(arr[b]==0)
for(int c=b+1;c<100;++c)
if(arr[c]==2)
for(int d=c+1;d<100;++d)
if(arr[d]==3)
{
for(int yue1=d+1;yue1<100;yue1++)
if(arr[yue1]<=1)
for(int yue2=yue1+1;yue2<=100;++yue2)
if(arr[yue1]==0||(arr[yue1]==1&&arr[yue2]<=2))
{
yueshu++;
int yue=arr[yue1]*10+arr[yue2];
for(int ri1=yue2+1;ri1<100;++ri1)
if(arr[ri1]<=3)
for(int ri2=ri1+1;ri2<100;++ri2)
{
int ri=arr[ri1]*10+arr[ri2];
//cout<<yue<<' '<<ri<<endl;
if(ri<=yuefen[yue]&&yue!=0&&ri!=0)ans[yue][ri]=1,cout<<yue<<' '<<ri<<endl;
}
}
}
long long sum=0;
for(int i=0;i<13;++i)
for(int j=0;j<32;++j)
if(ans[i][j])sum++;
cout<<sum;
return 0;
}
/*
5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2
7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1
0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3
*/
【答案】:235
试题 B: 01 串的熵
【思路】
一开始没有啥想法,甚至看这个定义都一头雾水,后面对着S=100这个解释才慢慢明白这个奇怪的式子每一位都要求一遍,后面全部加起来,而且这个通项和位置没有关系,那我们就直接上二分!这个时候我还没有看到“0”的个数比“1”的小,经过后面的计算才发现。就准备开始写了,有发现有点怪,不一定是单调的,得证明,才5分的题目也这么难?后面开摆了直接暴力算了👀。
【代码】
这里一开始代码二分没有考虑这个不一定是个单调的区间,吓死个人,后面疯狂调试发现了应该是一个对称的函数,关于x=(0+23333333)/2对称的函数。然后就是公式代入计算就好了👀
#include<bits/stdc++.h>
using namespace std;
int weishu=23333333;
bool check(int n)
{
int n0=n;
int n1=weishu-n0;
double zhanbi1=n1*1.0/weishu;
double zhanbi0=n0*1.0/weishu;
double ans=-n0*zhanbi0*std::log2(zhanbi0)-n1*zhanbi1*std::log2(zhanbi1);
if(abs(ans-11625907.5798)<0.0001)
printf("%.7f %d\n",ans,n);
//return true;
//cout<<ans<<endl;
return false;
}
int main()
{
/*int left=0,right=23333333;
while(left<right)
{
int mid=left+(right-left)/2;
if(check(mid))right=mid;
else left=mid+1;
}*/
for(int i=0;i<23333333;++i)
if(check(i))cout<<i<<endl;
//cout<<std::log2(8);
//check(1);
//check(1217805);
return 0;
}
/*
1217804
1217805
*/
【答案】:11027421
试题 C: 冶炼金属
【问题描述】
【输入格式】
【输出格式】
【样例输入】
【样例输出】
【思路】
前面做的有时间有点长了,这个时候就有点着急,这道题目我一看就觉得应该是找 A/B 然后确定最大最小值就好(因为样例第一第二行就直接算出来答案了)我也不知道自己想的,反正就直接写了,写完之后才发现不对啊,最后的一行 59/2=29 ,然后才重新回过头来看这道题,这代应该是说找出一个数 X 使得每一个 A/X 向下取整都能得到 B的值,也没啥好思路,直接二分法(又是二分?不对上一道题我没有用二分)。这里分别对左右边界进行二分求解就好了。
【代码】
这里我真的想给自己两巴掌,二分的是转换率V,然后限制条件那里的“if((b[i]+1)*(n)<a[i])return false;”我写成了:“if(b[i]*(n+1)<a[i])return false;”,完了debug半个小时,悲,好在后面看到了。
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
typedef long long LL;
LL a[N],b[N];
bool check(int n) //右边
{
for(int i=0;i<n;++i)
{
if(b[i]*n>a[i])return true;
if((b[i]+1)*n<a[i])return false;
if((b[i]+1)*n==a[i])return false;
//cout<<i<<' '<<a[i]<<' '<<b[i]<<endl;
}
return false;
}
bool check2(int n) //左边
{
for(int i=0;i<n;++i)
{
if(b[i]*n>a[i])return true;
if((b[i]+1)*(n)<a[i])return false;
if((b[i]+1)*(n)==a[i])return false;
}
return true;
}
int main()
{
//cout<<std::log2(1000000000);
int n;
cin>>n;
LL maxzhi,minzhi;
int l,r;
for(int i=0;i<n;++i)
{
cin>>a[i]>>b[i];
}
int left=0,right=(int)1e9;
while(left<right)
{
int mid=left+(right-left)/2;
if(check(mid))right=mid;
else left=mid+1;
}
maxzhi=left-1;
left=0,right=(int)1e9;
while(left<right)
{
int mid=left+(right-left)/2;
if(check2(mid))right=mid;
else left=mid+1;
}
minzhi=left;
cout<<minzhi<<" "<<maxzhi;
return 0;
}
/*
3
75 3
53 2
59 2
*/
【结果预测】
试题 D: 飞机降落
【题目描述】
【输入格式】
【输出格式】
【样例输入】
【样例输出】
【思路】
这道题我的想法是把到达时间和天上滞留时间加在一起作为一个整体,得到一个最晚起飞的时间,然后对每一个指标按顺序进行稳定排序,首先是最晚起飞时间,然后到到达时间、然后是降落时间,最后按顺序进行模拟,如果轮到一架飞机的降落时间超过它的对应最晚降落时间,那么就直接输出“NO”(区分大小写!),如果顺利模拟那就说明能够全部降落,输出“YES”。
【代码】
写太快了,最后五分钟发现没有稳定排序到达时间还有降落时间,希望能骗到一点分。
#include<bits/stdc++.h>
using namespace std;
const int N = 100;
typedef long long LL;
int t[N],d[N],l[N];
int main()
{
int k;
cin>>k;
while(k--)
{
int n;
cin>>n;
LL time=0;
bool biaoji=0;
for(int i=0;i<n;++i)
cin>>t[i]>>d[i]>>l[i];
for(int i=0;i<n;++i)
for(int j=0;j<n-i-1;++j)
{
if(t[j]+d[j]>t[j+1]+d[j+1])
{
swap(t[j],t[j+1]);
swap(d[j],d[j+1]);
swap(l[j],l[j+1]);
}
}
for(int i=0;i<n;++i)
{
if(time>t[i]+d[i])
{
biaoji=1;
cout<<"NO\n";
break;
}
time=max((int)time,t[i]);
time+=l[i];
}
if(biaoji)continue;
else cout<<"YES\n";
}
return 0;
}
/*
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
*/
【结果预测】
部分答案正确
试题 E: 接龙数列
【问题描述】
【输入格式】
【样例输入】
【样例输出】
【思路】
这道题目要求的是最少从中删除多少个数,而且没有询问我们是删除哪些数字,那就可以把问题转换为这个数列中最多有多少个接龙子序列,对于每一个数字我们也可以抽象成开头数字还有结尾数字,分别使用两个数组来存储就好,再来一个数组记录取到这一个整数最多能有多少个接力哦那个数列,然后从前往后一位一位枚举就好。
【代码】
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long LL;
int a[N],b[N],dp[N];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;++i)
{
int shuru;
cin>>shuru;
b[i]=shuru%10;
while(shuru>10)shuru/=10;
a[i]=shuru;
}
int maxzhi=0;
for(int i=0;i<n;++i)
{
dp[i]=1;
for(int j=0;j<i;++j)
{
if(b[j]==a[i])dp[i]=max(dp[i],dp[j]+1);
}
maxzhi=max(maxzhi,dp[i]);
}
cout<<n-maxzhi;
return 0;
}
/*
5
11 121 22 12 2023
*/
【结果预测】
超时了应该
试题 F: 岛屿个数
【问题描述】
【输入格式】
【输出格式】
【样例输入】
【样例输出】
3
【思路】
这道题应该是用bfs来做,但是只是浅浅一眼就润了,后面没有时间补了,悲,主要bfs不熟练,不太想花时间
试题 G: 子串简写
【问题描述】
【输入格式】
【输出格式】
【样例输入】
【样例输出】
【思路】
这道题直接暴力肯定是不太行的感觉,5×10^5 应该是会炸的,这里我把目标的字符抽离出来只简单记录好在原来的字符串中的位置,分别用两个数组来存储,然后对 a 的位置一个一个从前往后进行查找,我们的目标是找每一个 a 往后数 k-1 个位置之后有多少个 b 出现,所以简单while对比一下就好,由于我们已经把 a 还有 b 抽离出来存储位置,所以我们能够直接定位到 b 的位置的同时,也能够快速查询到后面还剩下多少个 b 。
【代码】
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long LL;
int a[N],b[N];
int main()
{
int k;
cin>>k;
string s;
char aa,bb;
cin>>s;
scanf(" %c %c",&aa,&bb);
//cout<<s;
//printf(" %c %c",aa,bb);
int len=s.size();
int zhizhena=0,zhizhenb=0;
for(int i=0;i<len;++i)
{
if(s[i]==aa)a[zhizhena++]=i;
if(s[i]==bb)b[zhizhenb++]=i;
}
LL sum=0;
for(int i=0;i<zhizhena;++i)
{
int weizhi=0;
while(b[weizhi]-a[i]<k-1&&weizhi<zhizhenb)weizhi++;
if(b[weizhi]-a[i]>=k-1)sum+=zhizhenb-weizhi;
}
cout<<sum;
return 0;
}
/*
4
abababdb a b
*/
【结果预测】
大部分能过
试题 H: 整数删除
【问题描述】
【输入格式】
【输出格式】
【样例输入】
【样例输出】
【思路】
一边查找一边删除,直接链表,但是忘记开long long
【代码】
这个忘记拷下来了👀
-后面两题不会了-
总结一下这一次的比赛,时间的安排上感觉有点急促,主要时间都花在一些奇怪问题的debug上面的了,早上好早就起来了,但是开始比赛的时候人还是不太清醒,看到第二题的时候吓到我了(因为没有用过 log2 这个函数,心里咯噔一下)后面在帮助文档上面找到了,然后就是第三题花的时间有点多,感觉一直没有进入状态,后面到了E题才慢慢进入状态。这一次比赛题目填空题偏难,隔壁 Java 的听说是一道求连续的阶乘和,从 1 加到202320232023好像是,求最后的 9 位,这不是一下子就又答案了嘛,为啥我们的题目这么多坑咧,大题整体上应该还行吧希望球球了,没有省一赏一个省二也行啊(不是)。
更多推荐
所有评论(0)