第一次参加蓝桥杯，特发此文记录一下今天乱七八糟的做题状态。

试题 A: 日期统计（填空题）

        

【问题描述】

小蓝现在有一个长度为 100 的数组，数组中的每个元素的值都在 0 到 9 的 范围之内。数组中的元素从左至右如下所示： 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 现在他想要从这个数组中寻找一些满足以下条件的子序列： 1. 子序列的长度为 8 ； 2. 这个子序列可以按照下标顺序组成一个 yyyymmdd 格式的日期，并且要求这个日期是 2023 年中的某一天的日期，例如 20230902 ， 231223。 yyyy 表示年份， mm 表示月份，dd 表示天数，当月份或者天数的长度只有一位时需要一个前导零补充。请你帮小蓝计算下按上述条件一共能找到多少个 不同 的 2023 年的日期。对于相同的日期你只需要统计一次即可。

【思路】

个人理解这道题目是从前往后确定8个不同的数字，组成一个合法的日期，询问最多能表示多少个日期。一开始简单写了一个代码计算一下满足的年份有多少种，后面发现满足年份是“2023”的只有170多种情况，直接暴力，一边选数字一边筛选掉不合格的省点时间（不然100^8也是有点吃吃不消），然后这道题目也要注意一下月份、日期是否合法就好。哦对了还有一点相同的日期只要统计一次?。

【代码】

没眼看了，糙得很。除了最后的答案是235（当时的答案）我还把月份还有日期也一起打出来了，虽然这样程序跑起来很慢，没有那么快见到结果，当时比赛的时候我这样做发现了我有日期为0的情况，差点就寄了?。

#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 27 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 10 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;}/*12178041217805*/

【答案】：11027421

 试题 C: 冶炼金属

【问题描述】

小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V ， V 是一个正整数，这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X ，当普通金属 O 的数目不足 V 时，无法继续冶炼。现在给出了 N 条冶炼记录，每条记录中包含两个整数 A 和 B，这表示本次投入了 A 个普通金属 O ，最终冶炼出了 B 个特殊金属 X。每条记录都是独立的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。根据这 N 条冶炼记录，请你推测出转换率 V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

【输入格式】

第一行一个整数 N ，表示冶炼记录的数目。 接下来输入 N 行，每行两个整数 A 、 B ，含义如题目所述。

【输出格式】

输出两个整数，分别表示 V 可能的最小值和最大值，中间用空格分开。

【样例输入】

3 75 3 53 2 59 2

【样例输出】

20 25

【思路】

前面做的有时间有点长了，这个时候就有点着急，这道题目我一看就觉得应该是找 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;}/*375 353 259 2*/

【结果预测】

上面估计是全错了，只有样例能过好像，悲

试题 D: 飞机降落

【题目描述】

N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 T i 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 D i 个单位时间，即它最早可以于 T i 时刻开始降落，最晚可以于 T i + D i 时刻开始降落。降落过程需要 Li个单位时间。一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。请你判断 N 架飞机是否可以全部安全降落。

【输入格式】

输入包含多组数据。第一行包含一个整数 T，代表测试数据的组数。对于每组数据，第一行包含一个整数 N。以下 N 行，每行包含三个整数： T i ， D i 和 L i 。

【输出格式】

对于每组数据，输出 YES 或者 NO ，代表是否可以全部安全降落。

【样例输入】

2 3 0 100 10 10 10 10 0 2 20 3 0 10 20 10 10 20 20 10 20

【样例输出】

YES NO

【思路】

这道题我的想法是把到达时间和天上滞留时间加在一起作为一个整体，得到一个最晚起飞的时间，然后对每一个指标按顺序进行稳定排序，首先是最晚起飞时间，然后到到达时间、然后是降落时间，最后按顺序进行模拟，如果轮到一架飞机的降落时间超过它的对应最晚降落时间，那么就直接输出“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;}/*230 100 1010 10 100 2 2030 10 2010 10 2020 10 20*/

【结果预测】

部分答案正确

试题 E: 接龙数列

【问题描述】

对于一个长度为 K 的整数数列： A 1 , A 2 , . . . , A K，我们称之为接龙数列当且仅当 A i 的首位数字恰好等于 A i − 1 的末位数字 (2 ≤ i ≤ K )。例如 12 , 23 , 35 , 56 , 61 , 11 是接龙数列； 12 , 23 , 34 , 56 不是接龙数列，因为 56的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。现在给定一个长度为 N 的数列 A 1 , A 2 , . . . , A N，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

【输入格式】

第一行包含一个整数 N 。 第二行包含 N 个整数 A 1 , A 2 , . . . , A N 。 【输出格式】 一个整数代表答案。

【样例输入】

5 11 121 22 12 2023

【样例输出】

1

【思路】

这道题目要求的是最少从中删除多少个数，而且没有询问我们是删除哪些数字，那就可以把问题转换为这个数列中最多有多少个接龙子序列，对于每一个数字我们也可以抽象成开头数字还有结尾数字，分别使用两个数组来存储就好，再来一个数组记录取到这一个整数最多能有多少个接力哦那个数列，然后从前往后一位一位枚举就好。

【代码】

#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;}/*511 121 22 12 2023*/

【结果预测】

超时了应该

试题 F: 岛屿个数

【问题描述】

小蓝得到了一副大小为 M × N 的格子地图，可以将其视作一个只包含字符‘0’ （代表海水）和 ‘1’（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上 / 下 / 左 / 右四个方向上相邻的 ‘1’ 相连接而形成。在岛屿 A 所占据的格子中，如果可以从中选出 k 个不同的格子，使得他们的坐标能够组成一个这样的排列： ( x 0 , y 0 ) , ( x 1 , y 1 ) , . . . , ( x k − 1 , y k − 1 )，其中( x ( i +1) % k , y ( i +1) % k ) 是由 ( x i , y i ) 通过上 / 下 / 左 / 右移动一次得来的 (0 ≤ i ≤ k − 1)，此时这 k 个格子就构成了一个 “ 环 ” 。如果另一个岛屿 B 所占据的格子全部位于这个 “ 环 ” 内部，此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若 B 是 A 的子岛屿， C 又是 B 的子岛屿，那 C 也是 A 的子岛屿。请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。

【输入格式】

第一行一个整数 T ，表示有 T 组测试数据。 接下来输入 T 组数据。对于每组数据，第一行包含两个用空格分隔的整数 M 、 N 表示地图大小；接下来输入 M 行，每行包含 N 个字符，字符只可能是 ‘0’ 或 ‘1’ 。

【输出格式】

对于每组数据，输出一行，包含一个整数表示答案。

【样例输入】

2 5 5 01111 11001 10101 10001 11111 5 6 111111 100001 010101 100001 111111

【样例输出】

1

3

【思路】

这道题应该是用bfs来做，但是只是浅浅一眼就润了，后面没有时间补了，悲，主要bfs不熟练，不太想花时间

试题 G: 子串简写

【问题描述】

程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 internation alization 简写成 i18n ， Kubernetes （注意连字符不是字符串的一部分）简写成 K8s , Lanqiao 简写成 L5o 等。在本题中，我们规定长度大于等于 K 的字符串都可以采用这种简写方法 （长度小于 K 的字符串不配使用这种简写）。给定一个字符串 S 和两个字符 c 1 和 c 2 ，请你计算 S 有多少个以 c 1 开头c 2 结尾的子串可以采用这种简写？

【输入格式】

第一行包含一个整数 K 。 第二行包含一个字符串 S 和两个字符 c 1 和 c 2 。

【输出格式】

一个整数代表答案。

【样例输入】

4 abababdb a b

【样例输出】

6

【思路】

这道题直接暴力肯定是不太行的感觉，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;}/*4abababdb a b*/

【结果预测】

大部分能过

试题 H: 整数删除

【问题描述】

给定一个长度为 N 的整数数列： A 1 , A 2 , . . . , A N。你要重复以下操作 K 次：每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。并把与它相邻的整数加上被删除的数值。输出 K 次操作后的序列。

【输入格式】

第一行包含两个整数 N 和 K 。 第二行包含 N 个整数， A 1 , A 2 , A 3 , . . . , A N 。

【输出格式】

输出 N − K 个整数，中间用一个空格隔开，代表 K 次操作后的序列。

【样例输入】

5 3 1 4 2 8 7

【样例输出】

17 7

【思路】

一边查找一边删除，直接链表，但是忘记开long long

【代码】

这个忘记拷下来了?

-后面两题不会了-

总结一下这一次的比赛，时间的安排上感觉有点急促，主要时间都花在一些奇怪问题的debug上面的了，早上好早就起来了，但是开始比赛的时候人还是不太清醒，看到第二题的时候吓到我了（因为没有用过 log2 这个函数，心里咯噔一下）后面在帮助文档上面找到了，然后就是第三题花的时间有点多，感觉一直没有进入状态，后面到了E题才慢慢进入状态。这一次比赛题目填空题偏难，隔壁 Java 的听说是一道求连续的阶乘和，从 1 加到202320232023好像是，求最后的 9 位，这不是一下子就又答案了嘛，为啥我们的题目这么多坑咧，大题整体上应该还行吧希望球球了，没有省一赏一个省二也行啊（不是）。