算法竞赛入门【码蹄集进阶塔335题】(MT3330-3335）
(文章目录)
前言
为什么突然想学算法了？
> 用较为“官方”的语言讲，是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 > 但从实际而言，是因为当下快到了考研和找工作的年纪(ಥ_ಥ)，无论走哪一条路，都不免需要一些相对丰富的算法知识，是故，便产生了一个暑假速成算法的计划，可能对于像我这种算法竞赛小白而言，几乎很难，但我仍然还是想尝试一下，毕竟，梦想还是要有的，万一实现了呢？～(￣▽￣～)~
为什么选择码蹄集作为刷题软件？
码蹄集，是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的，其依托全国各大名校计算机系和清华大学出版社等单位的强大资源，旨在为计算机学习爱好者提供全面和权威的计算机习题。
目录
1. MT2330 相似基因
（1）题目描述 基因片段由 四个字母组成。下面给定两个基因片段，请返回它们的相似度。
基因片段中每个字符前都有一个数字(不超过 )，表示该字符连续出现的次数，如，3A4T表示AAATTTT 。
相似表示在相同位置的字符相同。计算得出的相似度以分数的形式表示，无需化简。
保证扩充后两基因片段长度相同，且扩充后长度小于300,000 。
格式
输入格式: 两行字符串 .
输出格式: 一行字符串
样例1
输入格式: 3A4C 1A1C5G . 输出格式: 1/7
解析：
定义str1，str2，分别表示两段基因片段，直接将基因片段存入对应数组，而后展开进行比较即可
（2）参考代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
char ch;
static int str1[300005];
static int str2[300005];
int num = 0;
int end = 0;
int size;
int ans = 0;
while (ch = getchar())
{
if ((ch < 'A' || ch > 'Z') && (ch < '0' || ch > '9'))
{
size = end;
end = 0;
num = 0;
break;
}
if (ch >= 'A' && ch <= 'Z')
{
for (int i = end; i < end + num; i++)
{
str1[i] = ch - 'A';
}
end += num;
num = 0;
continue;
}
num = num * 10 + ch - '0';
}
while (ch = getchar())
{
if ((ch < 'A' || ch > 'Z') && (ch < '0' || ch > '9'))
break;
if (ch >= 'A' && ch <= 'Z')
{
for (int i = end; i < end + num; i++)
{
str2[i] = ch - 'A';
}
end += num;
num = 0;
continue;
}
num = num * 10 + ch - '0';
}
for (int i = 0; i < size; i++)
{
if (str1[i] == str2[i])
{
ans++;
}
}
printf("%d%c%d", ans, '/', size);
}
2. MT2331 序列01变
（1）题目描述 小码哥有一个长度为 的序列，仅包含0和1两种数字。 现在可爱的小码哥想让你进行若干次操作使得序列中任意两个相邻的数不相同。 每次操作你当且仅当可以选择当前序列中两个相邻位置且相同的数，并且可以将他们两个改变为任意的数
格式
输入格式: 第一行两个正整数n (1≤n ≤100000) 接下来一行一个字符串S，长度为n，包含且仅包含0和1两种字符 .
输出格式: 按题目要求输出一行一个整数，表示最小操作次数。
样例1
输入格式: 7 1100010 . 输出格式: 2
解析：
由题可得，修改0或1，使得相邻位置的数字不相同，只可能出现如下两种情况，即1010和0101，故只需对比s有多少不同，然后取二者间的最小值即可
（2）参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,result1=0,result2=0;
string s;
cin>>n>>s;
for(int i=0;i<s.size();i++){
if(i%2==0){
if(s[i]=='0') result1++;
else result2++;
}else{
if(s[i]=='1') result1++;
else result2++;
}
}
cout<<min(result1,result2);
return 0;
}
3. MT2332 分裂可乐
（1）题目描述 小码哥，小码弟，小码妹，小码姐和小码妹妹正在在卖“分裂可乐”的自动贩卖机那里排队。
队里第一个人（小码哥）会买一瓶分裂可乐，喝完以后他就会分裂成两个人并站到队尾。下一个人（小码弟）也会买一瓶分裂可乐，喝完后也会和刚才的小码哥一样分裂成两个人并站到队尾。这个过程可以一直持续下去（永动机）。举个例子，当小码妹喝下可乐（他之前的人也喝完了）后队列会变成这样：小码姐，小码妹妹，小码哥，小码哥，小码弟，小码弟，小码妹，小码妹。
请您编写一个程序来输出喝下第 罐分裂可乐的人。注意：一开始的队列总会是这样的：小码哥，小码弟，小码妹，小码姐，小码妹妹。第一个去买可乐的人总会是小码哥。
格式
输入格式: 输入包含一个整数n(1 ≤n ≤109) .
输出格式: 输出一行，一个字符串，代表喝下第n瓶分裂可乐的人的名字，只可能包含五种答案:分别是“xiaomage”, “xiaomadi”,"xiaomamei”, “xiaomajie", "xiaomameimei”。
样例1
输入格式: 1802 . 输出格式: xiaomamei
解析：
由题可得，每次分裂都会产生使其中一人变为两个，每遍历五次，下一个人想要喝到的次数就会乘2，是故只需要将n先除5，而后进行除2，直到为0，并记录被除2的次数，而后将其带入switch中进行逻辑左移-4，即可得出喝下第n瓶可乐的人的名字
（2）参考代码
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,tmp,countN = 0;
cin>>n;
for(tmp=n/5;(tmp>>1)!=0;countN++) tmp = tmp>>1;
switch((int)(((n+5)>> countN)-4)){
case 1:
cout<<"Sheldon"<<endl;
break;
case 2:
cout<<"Leonard"<<endl;
break;
case 3:
cout<<"Penny"<<endl;
break;
case 4:
cout<<"Rajesh"<<endl;
break;
case 5:
cout<<"Howard"<<endl;
break;
}
return 0;
}
4. MT2333 小码哥学多重集
（1）题目描述 小码哥今天新学了一个概念：多重集，一个多重集是指，可以包含重复的元素。由于小码哥天赋异禀，他刚学会就想出题考别人。
小码哥给出一个多重集 包含n个不同的非负整数。 他允许你对该多重集有k次操作：首先，他想知道这个集合中最大的数是什么。不过，他依然不满足，他还想知道这个集合中没有出现的最小的非负整数是什么。最后，他想把这两个数加起来除以 向上取整加到集合中。以上算一次操作。
现他要求算出k次操作后 中不同元素的个数。
格式
输入格式: 第一行一个正整数t表示测试组数(1<t≤100) 接下来每一组第一行两个整数n和k(1≤n ≤105,0 ≤k ≤109)，分别表示多重集S的初始大小和操作数 第二行输入S中的元素a(0≤ai≤109) .
输出格式: 每组数据一个正整数
样例1
输入格式: 7 10 7 1 7 4 6 8 0 2 5 3 9 2 7 0 1 2 5 0 1 6 7 4 5 3 0 2 1 10 9 9 7 1 4 6 0 8 13 5 2 8 3 3 0 7 4 5 1 6 2 1 3 0. 输出格式:
17 9 7 13 10 11 4
解析：
方案1：由题得，直接按题意，每次寻找最大值和最小未出现正整数，进行插入和计算即可，如代码1所示 . 方案2：由题得，一共会出现三种情况，分别为 (1) 原集合存1，k次操作后共有n+k次数 (2) 原集合不存1，且不存在最大数与1除以2再向上取整的数-> n+1次 (3) 原计划不存1，但存在最大数与1除以2再向上取整的数-> n次 是故只需将数据读入，进行判断，直接输出即可。
（2）参考代码
代码1：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
vector<int> arr; //用于存储输入的测试数据
double sum_num;
vector<int> arr1; //用于对输入的数据进行去重
vector<int> arr2; //用于存储结果
bool flag;
int t,a; //t表示要测试几组数 a用于暂存输入的测试数据，然后插入到数组arr中
ll k,n,num; //n表示一组数据中的个数，k表示对该组数据进行多少次测试
double min_num, max_num;
cin >> t;
for(int i=0;i<t;i++)
{
cin >> n >> k;
for(int j=0;j<n;j++)
{
cin >> a;
arr.insert(arr.end(),a);
}
//对数组进行去重和排序
//利用集合的特性对数组进行去重
set<int> s(arr.begin(),arr.end());
arr.assign(s.begin(),s.end());
//升序排序
sort(arr.begin(),arr.end());
//找出数组中的最大值
max_num = *max_element(arr.begin(),arr.end());
//判断数组是否以0开头且连续
for(int i=0;i<arr.size()-1;i++)
{
int com = arr[i+1]-arr[i];
if(com == 1 and arr[0]==0){
flag = 0;
}
else
{
flag = 1;
break;
}
}
if(flag)
{
for(int m=0;m<arr.size();m++)
{
if(arr[m]>m){
min_num = m;
break;
}
}
double sum_num = (max_num + min_num)/2.0;
sum_num = ceil(sum_num);
int b = sum_num;
arr.insert(arr.end(),b);
set<int> p(arr.begin(),arr.end());
arr1.assign(p.begin(),p.end());
if(arr1.size()>n)
{
num = n+1;
}
else{
num = n;
}
}
else
{
num = n+k;
}
arr2.insert(arr2.end(),num);
arr.clear();
num = 0;
}
for(int j=0;j<arr2.size();j++)
{
cout << arr2[j] << endl;
}
return 0;
}
代码2：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxN = 100001;
int a[maxN],t;
inline int cmp(int a,int b){
return a<b;
}
int main()
{
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
set<int> numSet;
for(int i=0;i<n;i++){
cin>>a[i];
numSet.insert(a[i]);
}
sort(a,a+n,cmp);
int maxNum = a[n-1],minNum=0;
if(a[1]>1) minNum=1;
else{
for(int i=0;i<n;i++){
if(numSet.count(a[i]+1)==0){
minNum = a[i]+1;
break;
}
}
}
if(minNum>maxNum) printf("%d\n",n+k);
else if(numSet.count(ceil(((double)minNum+maxNum)/2))==1) printf("%d\n",n);
else printf("%d\n",n+1);
}
return 0;
}
5. MT2334 滚动的小球
（1）题目描述 在一个长为Ⅳ的光滑平板上，有若干个光滑小球分布在平板的整数点上，比如0,1,2,. . .N，然后给定初始向左移动的小球几个，初始向右移动的小球R个，接下来给定向左移动的每个小球的初始位置和向右移动的每个小球的初始位置。保证小球的速度始终为每秒一个单位长度，当两个方向不同的小球相撞时，它们同时改变运动方向并继续运动（相撞瞬间完成，不消耗时间)。请求解最后一个小球从平板掉下来的时间。初始时刻t =0，即求解最后一个小球掉下去的t 的值。(如果端点处小球一开始就向木板外滚动，那么它的掉落时刻为t =0 )
格式
输入格式: 第一行三个整数N,L,R(1≤N≤104,1≤L＋R≤n ＋1) 第二行有L个整数left,(0 ≤lefti ≤n)，分别表示向左运行的小球的初始坐标。 第二行有R个整数right,(0 ≤right,≤n)，分别表示向右运行的小球的初始坐标。 .
输出格式:一个整数，即最后一个小球从平板掉下来的时间。
样例1
输入格式: 4 2 2 4 3 0 1 . 输出格式: 4
（2）参考代码
#include<bits/stdc++.h>
using namespace std;
int main( )
{
int n,l,r;
scanf("%d%d%d",&n,&l,&r);
int x;
int ans1 = -1,ans2 = n+1;
for(int i=1;i<=l;i++){
scanf("%d",&x);
ans1 = max(ans1,x);
}
for(int i=1;i<=r;i++){
scanf("%d",&x);
ans2 = min(ans2,x);
}
ans2 = n - ans2;
int ans;
if(l && !r){
ans = ans1;
}else if(r && !l){
ans = ans2;
}else{
ans = max(ans1,ans2);
}
cout<<ans<<endl;
return 0;
}
6. MT2335 上色
（1）题目描述 原棋盘为8行8列的白色棋盘，现在某些部分被污染成黑色，每次可将一行或一列染成白色，问至少需要多少次才能将棋盘恢复到初始状态。
格式
输入格式: 目标棋盘状态，W表示白，B表示黑 .
输出格式: 最少操作次数
样例1
输入格式: WWWWWWWW BBBBBBBB WWWWWWWW WWWWWWWW WWWWWWWW WWWWWWWW BBBBBBBB WWWWWWWW . 输出格式: 2
备注
题目保证一定可以通过题目中的操作完成染色任务
解析：
二进制状态压缩枚举，2的16次方种情况
（2）参考代码
#include<stdio.h>
int judge(int *row,int *col){
int i;
for(i=0;i<8;i++)
if(row[i]>0||col[i]>0)
return 1;
return 0;
}
int max_row(int *row){
int i;
int max=row[0];
int m_row=0;
for(i=1;i<8;i++)
if(row[i]>max){
max=row[i];
m_row=i;
}
return m_row;
}
int max_col(int *col){
int i;
int max=col[0];
int m_col=0;
for(i=1;i<8;i++)
if(col[i]>max){
max=col[i];
m_col=i;
}
return m_col;
}
int main(){
char a[8][8];
int i,j;
int row[8]={0},col[8]={0};
int max_r,max_c;
int res=0;
for(i=0;i<8;i++){
for(j=0;j<8;j++){
scanf("%c",&a[i][j]);
if(a[i][j]=='B'){
row[i]++;
col[j]++;
}
}
getchar();
}
while(judge(row,col)){
max_r=max_row(row);
//printf("%d\n",max_r);
max_c=max_col(col);
if(row[max_r]>=col[max_c]){
row[max_r]=0;
for(i=0;i<8;i++)
col[i]--;
res++;
}
else{
col[max_c]=0;
for(i=0;i<8;i++)
row[i]--;
res++;
}
}
printf("%d",res);
return 0;
}
结语
感谢大家一直以来的不断支持与鼓励，码题集题库中的新手村600题现已全部完结，之后会逐步跟进黄金，钻石，星耀，王者的题，尽请期待！！！ 同时，也希望这些题能帮助到大家，一起进步，祝愿每一个算法道路上的“苦行僧”们，都能够历经磨难，终成正果，既然选择了这条路，走到了这里，中途放弃，岂不是太过可惜？
愿你的结局，配得上你一路的颠沛流离。