第十四届蓝桥杯刷题——day20

引言

    蓝桥杯C++研究生组（河北赛区）快要开赛了，接下来的两天围绕着往年真题开刷。要是能拿省二还能血赚，拿不了就当捐了吧。由于时间有限，这里的题目如果能够通过所有的测试用例，那就不再纠结了，至少能拿到一部分。

题目一：工作时长

【问题描述】
    小蓝手里有一份2022年度自己的上班打卡记录文件，文件包含若干条打卡记录，每条记录的格式均为“yyyy - MM - dd HH:mm:ss”，即按照年 - 月 - 日 时:分:秒的形式记录一个时间点（采用24小时进制）。由于某些原因，这份文件中的时间记录并不是按照打卡的时间顺序记录的，而是被打乱了。但我们保证小蓝每次上班和下班时都会正常打卡，而且正好打卡一次，其他时候不会打卡。每一对相邻的上 - 下班打卡之间的时间就是小蓝本次的工作时长，例如文件内容如下的话：

2022 - 01 - 01 12:00:05
2022 - 01 - 02 00:20:05
2022 - 01 - 01 07:58:02
2022 - 01 - 01 16:01:35

    表示文件中共包含了两段上下班记录，1) 2022 - 01 - 01 07:58:02 ～ 2022 - 01 - 01 12:00:05，工作时长为14523秒；2) 2022 - 01 - 01 16:01:35 ～ 2022 - 01 - 02 00:20:05，工作时长为29910秒；工作时长一共是14523 + 29910 = 44433秒。
    现在小蓝想知道在2022年度自己的工作时长一共是多少秒？
【 答案提交】
    这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
【解题思路】
    这题一看直接暴力，关键在于对时间的优化处理上，这里因为格式完全统一，可以不使用十五届中提到的istringstream流的形式输入，直接截取字符串，将每一个事件都转化成秒，最后再统计一次结果，最终得到的代码如下：

const int monthList[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
const int perDay=24*3600;
int convertTime(int month,int day,int hour,int minute,int second){int curDay=0;for(int i=1;i<month;++i){curDay+=monthList[i];}return (curDay+day)*perDay+hour*3600+minute*60+second;
}
int getWorkTime(){ifstream inFile("records.txt");string line;vector<int> arr;long long  year,month,day,hour,minute,second,result=0;while(getline(inFile,line)){year=stoi(line.substr(0,4));month=stoi(line.substr(5,2));day=stoi(line.substr(8,2));hour=stoi(line.substr(11,2));minute=stoi(line.substr(14,2));second=stoi(line.substr(17,2));arr.push_back(convertTime(month,day,hour,minute,second));}sort(arr.begin(),arr.end());for(int i=0,size=arr.size();i<size;i=i+2){result+=arr[i+1]-arr[i];}return result;
}

题目二：与或异或

【问题描述】
    小蓝有一张门电路的逻辑图，如下图所示：
    图中每个三角形代表着一种门电路，可能是与门、或门、异或门中的任何一种，它接受上一层中的两个圆形中的数据作为输入，产生一个输出值输出到下一级(如图中箭头所示)。图中圆形表示的是暂存的输出结果，取值只可能是0或1，为了便于表示我们用arr[i][j]表示第i(0 ≤ i ≤ 4)行第j(0 ≤ j ≤ i)个圆形的值。其中arr[0]=(In[0],In[1],In[2],In[3],In[4])表示的是输入数据，对于某个arr[i][j](i ≤ 0)，计算方式为arr[i][j]=arr[i - 1][j] op arr[i - 1][j + 1]，其中op表示的是将arr[i - 1][j]、arr[i - 1][j + 1]作为输入，将arr[i][j]作为输出的那个门电路，与门、或门、异或门分别对应于按位与&、按位或(|)、按位异或(^)运算符。

    现在已知输入为In[0]=1,In[1]=0,In[2]=1,In[3]=0,In[4]=1，小蓝想要使得最终的输出Out的值为1，请问一共有多少种不同的门电路组合方式？其中上图中显示的就是一种合法的方式。
【 答案提交】
    这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
【解题思路】
    同样的这题也可以考虑使用暴力方法，虽然一共有10个格子，但是每个格子只有3中可能情况。这题的关键在于如何去描述3^10这种排列组合方式。这里考察的就变成了计数原理：
（1）在数学里，若有多个独立的事件，每个事件都有若干种不同的发生方式，那么这些事件同时发生的总方式数就是每个事件发生方式数的乘积。在这个问题中，有 10 个数，每个数都能取 3 种不同的值，这 10 个数取值的行为是相互独立的。所以，所有可能的组合数就是 $3\times 3\times 3\times 3\times 3\times 3\times 3\times 3\times 3\times 3=3^{10}$ 种。
（2）代码里采用了类似数的进制表示的方法来生成所有组合。可以把每个数的 3 种取值看成是三进制数中的一位，这一位可以是 0、1 或者 2。这样一来，10 个数的组合就相当于一个 10 位的三进制数。给出一个简单例子：

    于是得到如下代码：

int getAnswer(int num1,int num2,int type) {if(type==0) {return num1&&num2;} else if(type==1) {return num1||num2;} else if(type==2) {return (num1==1&&num2==0)||(num1==0&&num2==1);}
}
bool isOkay(vector<int> data) {int k=0;vector<int> level1= {1,0,1,0,1};vector<int> level2= {0,0,0,0};vector<int> level3= {0,0,0};vector<int> level4= {0,0};for(int i=0; i<4; ++i) {level2[i]=getAnswer(level1[i],level1[i+1],data[k++]);}for(int i=0; i<3; ++i) {level3[i]=getAnswer(level2[i],level2[i+1],data[k++]);}for(int i=0; i<2; ++i) {level4[i]=getAnswer(level3[i],level3[i+1],data[k++]);}return getAnswer(level4[0],level4[1],data[k++]);
}
int getCount() {int result=0;for(int k=0; k<3*3*3*3*3*3*3*3*3*3; ++k) {int tmp=k;vector<int> data(10,0);for(int i=0; i<10; ++i) {data[i]=tmp%3;tmp=tmp/3;}cout<<endl;if(isOkay(data)) {result++;}}return result;
}

题目三：翻转

【问题描述】
    小蓝用黑白棋的n个棋子排成了一行，他在脑海里想象出了一个长度为n的01串T，他发现如果把黑棋当做1，白棋当做0，这一行棋子也是一个长度为n的01串S。
    小蓝决定，如果在S中发现一个棋子和它两边的棋子都不一样，就可以将其翻转变成另一个颜色。也就是说，如果S中存在子串101或者010，就可以选择将其分别变为111和000，这样的操作可以无限重复。
    小蓝想知道最少翻转多少次可以把S变成和T一模一样。
【输入格式】
    输入包含多组数据。
    输入的第一行包含一个正整数D表示数据组数。
    后面2D行每行包含一个01串，每两行为一组数据，第2i - 1行为第i组数据的Ti，第2i行为第i组数据的Si，Si和Ti长度均为ni。
【输出格式】
    对于每组数据，输出一行包含一个整数，表示答案，如果答案不存在请输出 -1。
【样例输入】

2
1000111
1010101
01000
11000

【样例输出】

2
-1

【评测用例规模与约定】
    对于20%的评测用例，1 ≤ ∑ni ≤ 10；
    对于所有评测用例，保证1 ≤ ∑ni ≤ 10^6，ni > 0。
【解题思路】
    这里考察的是贪心，我们根据题意可以知道字符串的第一个字符和最后一个字符都是不可能改变的。可以取其中一个字符串，比如这里取T字符串，从第二个字符开始遍历到倒数第二个字符，如果T字符串中字符不等于S字符串中的字符，那么这个字符一定需要考虑翻转，因此利用已知规则看是否能够支持翻转，如果可以翻转那么翻转并后移。
    如果不能够翻转，那么是否可能因为后续翻转引起前面可以翻转？下面我们论证如果当次不能够翻转，之后就再也不可能翻转了。给出例子：

1100111
1110101

    这里第三个字符当次不能够翻转，那么有没有一种可能第四个字符会先发生翻转，之后满足了第三个字符翻转的条件呢？这种情况不可能成立，因为第四个字符必须和第三个字符不同，第四个字符才能够翻转，如果第四个字符翻转成功，那么就和第三个字符一致，第三个字符就丢失了翻转条件，矛盾。
    因此可以直接使用贪心思想从左到右走一遍，如果不同尝试翻转，不能翻转直接就不可能相等。最终得到如下代码：

int minReverseCount(string str1,string str2) {int len1=str1.length(),len2=str2.length(),result=0;if(len1!=len2||str1[0]!=str2[0]||str1[len1-1]!=str2[len2-1]) {return -1;}for(int i=1; i<len2-1; ++i) {if(str2[i]!=str1[i]) {if(str2[i-1]!=str2[i]&&str2[i+1]!=str2[i]) {str2[i]=(str2[i]=='0'?'1':'0');result++;} else {return -1;}}}return result;
}

题目四：阶乘的和

【问题描述】
    给定 n 个数 Aᵢ，问能满足 m! 为 ∑(i = 1 到 n)(Aᵢ!) 的因数的最大的 m 是多少。其中 m! 表示 m 的阶乘，即 1 × 2 × 3 × ··· × m。
【输入格式】
    输入的第一行包含一个整数 n。
    第二行包含 n 个整数，分别表示 Aᵢ，相邻整数之间使用一个空格分隔。
【输出格式】
    输出一行包含一个整数表示答案。
【样例输入】

3
2 2 2

【样例输出】

3

【评测用例规模与约定】
    对于 40% 的评测用例，n ≤ 5000；
    对于所有评测用例，1 ≤ n ≤ 10⁵，1 ≤ Aᵢ ≤ 10⁹。
【解题思路】
    这里考察的是贪心和数学递推公式。我们可以发现，如果出现了三个2!，那么可以等效成一个3!，由此可以从小到大考虑给定的n个数中的可能融合情况，如果可以恰好满足了map[minNum]%(minNum+1)==0，说明较小的元素恰好可以向上完成一次融合，并且不剩余，是不是巨像《合成大西瓜》，最终没能合入的最小值一定就是想要目标值，因为整个数列是以求和的形式出现，于是得到如下代码：

int getMaxNum(vector<int> arr,int size) {unordered_map<int,int> map;int minNum=INT_MAX;for(int i=0; i<size; ++i) {map[arr[i]]++;minNum=min(minNum,arr[i]);}while(map[minNum]%(minNum+1)==0) {map[minNum+1]+=map[minNum]/(minNum+1);map[minNum]=map[minNum]/(minNum+1);minNum+=1;}return minNum;
}

题目五：公因数匹配

【问题描述】
    给定 n 个正整数 Aᵢ，请找出两个数 i, j 使得 i < j 且 Aᵢ 和 Aⱼ 存在大于 1 的公因数。
    如果存在多组 i, j，请输出 i 最小的那组。如果仍然存在多组 i, j，请输出 i 最小的所有方案中 j 最小的那组。
【输入格式】
    输入的第一行包含一个整数 n。
    第二行包含 n 个整数分别表示 A₁, A₂, …, Aₙ，相邻整数之间使用一个空格分隔。
【输出格式】
    输出一行包含两个整数分别表示题目要求的 i, j，用一个空格分隔。
【样例输入】

5
5 3 2 6 9

【样例输出】

2 4

【评测用例规模与约定】
    对于 40% 的评测用例，n ≤ 5000；
    对于所有评测用例，1 ≤ n ≤ 10⁵，1 ≤ Aᵢ ≤ 10⁶。
    这里应该采取点策略，本着拿分去，直接按照题目说明模拟这个检查过程，固定左侧数查右侧数，找两个有最大公因数大于1的两个数的位置。能够拿60%的分，血赚不亏。

bool hasCommonFator(int a,int b) {while(b!=0){int tmp=b;b=a%b;a=tmp;}return a>1;
}
void getMinIndex(vector<int> arr,int size) {for(int i=0; i<size; ++i) {for(int j=i+1; j<size; ++j) {if(hasCommonFator(arr[i],arr[j])) {cout<<(i+1)<<" "<<(j+1);return ;}}}
}

附录：源码gitee仓库

    考虑到有些算法需要模拟数据，如果全部放进来代码显得过长，不利于聚焦在算法的核心思路上。于是把所有的代码整理到了开源仓库上，如果想要看详细模拟数据，可在开源仓库自取：【凌空暗羽/剑指Offer-C++版手写代码】。

    我是【Jerry说前后端】，本系列精心挑选的算法题目均基于经典的《剑指 Offer（数据结构与算法面试题精讲）》。在如今竞争激烈的技术求职环境下，算法能力已成为前端开发岗位笔试考核的关键要点。通过深入钻研这一系列算法题，大家能够系统地积累算法知识和解题经验。每一道题目的分析与解答过程，都像是一把钥匙，为大家打开一扇通往高效编程思维的大门，帮助大家逐步提升自己在数据结构运用、算法设计与优化等方面的能力。
    无论是即将踏入职场的应届毕业生，还是想要进一步提升自身技术水平的在职开发者，掌握扎实的算法知识都是提升竞争力的有力武器。希望大家能跟随我的步伐，在这个系列中不断学习、不断进步，为即将到来的前端笔试做好充分准备，顺利拿下心仪的工作机会！快来订阅吧，让我们一起开启这段算法学习之旅！