2024牛客寒假算法基础集训营3部分题解

智乃与瞩目狸猫、幸运水母、月宫龙虾

来源：牛客网

Ubuntu是一个以桌面应用为主的Linux发行版操作系统，其名称来自非洲南部祖鲁语或豪萨语的"ubuntu"一词，意思是"人性"、"我的存在是因为大家的存在"，是非洲传统的一种价值观。

在ubuntu系统下，命令行执行

lsb_release -a

可以看到代号(Codename)，到目前为止，Ubuntu 发行版的每个代号都包含一个形容词和一个动物。例如：瞩目狸猫(Focal Fossa)、幸运水母(Jammy Jellyfish)、月宫龙虾(Lunar Lobster)，每个代号的两个单词首字母相同。

在不考虑单词词性的前提下，只要求两个单词的首字母忽略大小写相同时就认为它们可能是一组ubuntu代号，请你编写程序判断给定的两个单词是否可能是一个ubuntu代号。

输入描述:

第一行输入一个正整数T(1≤T≤105)T(1\leq T \leq 10^{5})T(1≤T≤105)，表示测试用例的组数。

对于每组测试用例，输入一行两个单词S,T(1≤∣S∣,∣T∣≤50)S,T(1 \leq |S|,|T|\leq 50)S,T(1≤∣S∣,∣T∣≤50)，单词仅包含大小写英文字母。

输出描述:

对于每组测试用例，如果它可能是一组ubuntu代号，则输出"Yes"，否则输出"No"。裁判程序将忽略大小写，你可以输出任意大小写的"Yes"和"No"。

示例1

输入

复制1 jammy jellyfish

1
jammy jellyfish

输出

复制Yes

Yes

示例2

输入

复制13 Artful Aardvark Bionic Beaver Cosmic Cuttlefish Disco Dingo Eoan Ermine Focal Fossa Groovy Gorilla Hirsute Hippo Impish Indri Jammy Jellyfish Kinetic Kudu Lunar Lobster Avada Kedavra

13
Artful Aardvark
Bionic Beaver
Cosmic Cuttlefish
Disco Dingo
Eoan Ermine
Focal Fossa
Groovy Gorilla
Hirsute Hippo
Impish Indri
Jammy Jellyfish
Kinetic Kudu
Lunar Lobster
Avada Kedavra

输出

复制Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;string s1,s2;
    cin>>t;
    getchar();
    while(t--){
        cin>>s1>>s2;
        if(s1[0]==s2[0]||s1[0]-32==s2[0]||s1[0]+32==s2[0])cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

智乃的数字手串

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

智乃有一个数字手串，数字手串上有NNN个数字，第NNN个数字与第111个数字相邻。智乃决定和清楚姐姐玩一个游戏。

两个人轮流从数字手串上进行取数和交换的操作，当且仅当某两个相邻数字的和为偶数时，可以拿走这两个相邻数字中的任意一个，取数后将剩下的数字按照它们之前的相对顺序重新紧凑排列并选择两个数字交换他们的值，例如一开始的数字环为[1,3,2,5,4,7][1,3,2,5,4,7][1,3,2,5,4,7]，取走数字333后，数字手串变为[1,2,5,4,7][1,2,5,4,7][1,2,5,4,7]，接下来还可以选择两个数字交换他们的值，例如交换111和222变为[2,1,5,4,7][2,1,5,4,7][2,1,5,4,7]。（玩家在交换这个环节也可以选择跳过不进行任何交换操作）。

若数字手串的尺寸为111，则玩家可以直接取走最后一个数字并获得游戏的胜利。

若玩家不能进行取数操作，则该玩家失败输掉游戏。

现在清楚姐姐先手取数，若两个人都采取最优策略，谁将获胜？

输入描述:

第一行输入一个正整数T(1≤T≤104)T(1\leq T \leq 10^{4})T(1≤T≤104)表示测试用例的组数

接下来对于每组测试用例，首行输入一个正整数N(1≤N≤26)N(1\leq N \leq 26)N(1≤N≤26)表示数字手串一开始的尺寸。

接下来一行输入NNN个整数ai(0≤ai≤109)a_i(0\leq a_i \leq 10^{9})ai(0≤ai≤109)表示数字的值。

输出描述:

如果两人都采取最优策略，在清楚姐姐先手的情况下清楚姐姐获胜，请输出"qcjj"，否则输出"zn"。

示例1

输入

复制1 5 1 1 2 2 2

1
5
1 1 2 2 2

输出

复制qcjj

qcjj

说明

清楚姐姐先手取走一个数字222，此时数字环变为[1,1,2,2][1,1,2,2][1,1,2,2]，接下来清楚姐姐交换一个111和一个222，数字环变为[1,2,1,2][1,2,1,2][1,2,1,2]。智乃无法取数而输掉游戏。

示例2

输入

复制2 2 1 1 2 1000000000 1000000000

2
2
1 1
2
1000000000 1000000000

输出

复制zn zn

zn
zn

说明

注意当只剩下一个珠子时，可以直接取下，由于对手无珠子可取从而获得胜利。

//这题想复杂了

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t,n,x;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<n;i++)cin>>x;
        if(n%2==1)cout<<"qcjj\n";
        else cout<<"zn\n";
    }
    return 0;                                                                                                                                                                                                                                                                             
}

chino's bubble sort and maximum subarray sum(easy version)

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

智乃最近学习了冒泡排序和最长子段和，所以她现在想把它们合并成一个新的算法。

众所周知，冒泡排序是一种通过交换相邻元素实现排序的算法，最长子段和是指从一个数组aaa中取出一段连续的非空数组区间[l,r][l,r][l,r]，最大化数组区间的和∑i=lrai\sum_{i=l}^{r}a_{i}∑i=lrai。

现在智乃有一个长度大小为NNN的数组，数组中元素的值有正有负。她想要先进行恰好KKK次相邻元素的交换操作，再求整个数组的最大子段和。她想要让最后求出的最大子段和尽可能的大，请你帮助智乃算出她最终可能的最大子段和有多大。

输入描述:

第一行输入两个正整数N,K(2≤N≤103,0≤K≤1)N,K(2\leq N \leq 10^3,0 \leq K \leq 1)N,K(2≤N≤103,0≤K≤1)表示数组的长度，交换的次数。

接下来一行NNN个整数，输入数组元素ai(−109≤ai≤109)a_i(-10^{9} \leq a_{i} \leq 10^{9})ai(−109≤ai≤109)表示数组元素的值。

输出描述:

仅一行一个整数，表示交换后能取到的非空最大子段和是多少。

示例1

输入

复制5 0 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000

5 0
-1000000000 -1000000000 -1000000000 -1000000000 -1000000000

输出

复制-1000000000

-1000000000

说明

注意“非空”

示例2

输入

复制5 1 5 4 -100 2 3

5 1
5 4 -100 2 3

输出

复制11

说明

交换"-100"和 "2"

备注:

注意已经通过一次的题目不再次计算罚时，你可以活用这一规则减少自己的罚时次数。

//冒泡排序+最大子段和，因为k为0或1，当k为0的时候，就是简单的求最大子段和；当k为1的时候，不是说进行一次冒泡排序的结果，而是进行一次相邻位置的数交换，为了得到最大子段和的最佳结果，就要比较n-1次交换后的结果。

#include<bits/stdc++.h>
using namespace std;
long long n,k,i,j,z,a[1005],y=-1e9;//long long定义，y取最小值
void solve(){
    for(z=1;z<=n;z++){//注意全局变量和局部变量，之前这里使用i一直不对
     long long x=0;
        for(j=z;j<=n;j++){
          x+=a[j];
          y=max(y,x); 
    }}
}
//最大子段和就是求n个数的组成的集合的子集和，
比如，这里有1，2，3三个数，可以组成1，2，3，1+2，2+3，1+3，1+2+3；
去比较上面6个子集和的最大值
int main(){
    cin>>n>>k;
    for(i=1;i<=n;i++)cin>>a[i];
    solve();
    if(k){
      for(i=1;i<n;i++){
        swap(a[i],a[i+1]);
        solve();
        swap(a[i],a[i+1]);//交换完成并求取子段和后初始化
      }}
    cout<<y;
    return 0;
}

智乃的比较函数(easy version)

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

在c++标准库中，存在一个叫做std::sort的函数，它可以默认按照升序的方式排序，或者按照一种给定的自定义方式排序。

新手在使用自定义比较函数进行sort时，经常会因为没有遵守sort传入比较函数的约定而导致代码崩溃。

具体来讲，使用sort时需要定义一个比较函数cmp(x,y)cmp(x,y)cmp(x,y)他表示比较在排序的过程中xxx的顺序是否严格小于yyy的顺序，如果xxx的顺序严格小于yyy的顺序，则cmp(x,y)=1cmp(x,y)=1cmp(x,y)=1，反之cmp(x,y)=0cmp(x,y)=0cmp(x,y)=0。

新手在编写cmpcmpcmp函数时的一个易错点是在xxx和yyy的值相等时令cmp(x,y)=1cmp(x,y)=1cmp(x,y)=1，例如降序排序时将x>yx>yx>y写成了x≥yx \geq yx≥y。

抛开c++语言的底层实现，这样其实已经产生了逻辑矛盾。因为当xxx和yyy的值相等时cmp(x,y)=cmp(y,x)=1cmp(x,y)=cmp(y,x)=1cmp(x,y)=cmp(y,x)=1，在调用约定中，它表示在排序中xxx的顺序严格小于yyy且yyy的顺序严格小于xxx，显然这里产生了逻辑矛盾。所以此时无论c++库函数执行出任何的结果都是可能的，一般来讲这将导致运行错误。

所以在编写cmp(x,y)cmp(x,y)cmp(x,y)时，一定要注意，当xxx和yyy的值相等时，应该令cmp(x,y)=cmp(y,x)=0cmp(x,y)=cmp(y,x)=0cmp(x,y)=cmp(y,x)=0，这表示通知排序函数，不能确定在排序中xxx的顺序严格小于yyy，同时也不能确定yyy的顺序严格小于xxx，当然，从逻辑上讲，这只有一种情况，就是x=yx=yx=y，并未产生任何逻辑矛盾。

现在有三个整形变量a1,a2,a3a_{1},a_{2},a_{3}a1,a2,a3（你可以认为这三个变量的值是int范围内任意的整数），告诉你NNN组cmp(ax,ay)cmp(a_x,a_y)cmp(ax,ay)的值，问是否产生了逻辑矛盾。

输入描述:

第一行输入一个正整数T(1≤T≤2×104)T(1\leq T \leq 2\times 10^{4})T(1≤T≤2×104)表示测试用例的组数。

对于每组测试用例，第一行输入一个正整数N(1≤N≤2)N(1\leq N \leq 2)N(1≤N≤2)表示约束条件的数目，接下来NNN行，每行输入三个整数x,y,z(x,y∈{1,2,3},z∈0,1)x,y,z(x,y\in \{1,2,3\},z\in {0,1})x,y,z(x,y∈{1,2,3},z∈0,1)表示第iii个约束关系为cmp(ax,ay)=zcmp(a_x,a_y)=zcmp(ax,ay)=z。

输出描述:

对于每组测试用例，若没有矛盾，则输出"Yes"，否则输出"No"，你可以输出任意大小写的"Yes"和"No"。

示例1

输入

复制1 2 1 2 1 2 1 1

输出

复制No

No

说明

两个变量a1<a2a_{1}<a_{2}a1<a2成立且a2<a1a_{2}<a_{1}a2<a1成立，矛盾

示例2

输入

复制1 2 1 2 1 1 2 1

输出

复制Yes

Yes

说明

注意输入的约束可能会重复，并不要求输入的约束条件能够完全将三者排序，仅要求不产生矛盾就输出"Yes"。

示例3

输入

复制3 1 1 1 0 1 1 1 1 2 1 2 0 1 2 1

输出

复制Yes No No

Yes
No
No

说明

注意输入的xxx和yyy可以相等

//这题是逻辑思维题，重点在于找矛盾

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t,n,x,y,z,a,b,c;
    cin>>t;
    while(t--){
        cin>>n;
        if(n==1){
            cin>>x>>y>>z;
            if(x==y&&z==1)cout<<"No\n";//题目给的矛盾
            else cout<<"Yes\n";
        }
        else{
            cin>>x>>y>>z;
            cin>>a>>b>>c;
            if((x==y&&z==1)||(a==b&&c==1))cout<<"No\n";//题目给的矛盾
            else if(a==x&&b==y&&z!=c)cout<<"No\n";//自身逻辑矛盾
            else if(a==y&&b==x&&c==z&&c==1)cout<<"No\n";//题目给的矛盾
            else cout<<"Yes\n";
        }
    }
    return 0;
}

智乃的36倍数(easy version)

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

本题有对应的normal version，区别仅在数据范围，保证easy version的测试用例集是normal version的真子集，通过困难版本的代码可直接通过简单版本。

智乃定义了一种运算fff，它表示将两个正整数按照字面值从左到右拼接。例如f(1,1)=11f(1,1)=11f(1,1)=11，f(114,514)=114514f(114,514)=114514f(114,514)=114514。

现在智乃有一个大小为NNN的正整数数组aaa，第iii个元素为aia_{i}ai，现在他从中想选出两个正整数进行前后拼接，使得它们拼接后是一个363636的倍数，问智乃有多少种可行的方案。

具体来讲，她想要知道有多少对有序数对i,j(i≠j)i,j(i\neq j)i,j(i=j)满足f(ai,aj)f(a_{i},a_{j})f(ai,aj)是一个363636的倍数。

输入描述:

第一行输入一个正整数N(1≤N≤1000)N(1\leq N \leq 1000)N(1≤N≤1000)数组的大小

接下来输入一行NNN个正整数ai(1≤ai≤10)a_{i}(1\leq a_{i}\leq 10)ai(1≤ai≤10)，表示aia_{i}ai的值。

输出描述:

输出一个非负整数，表示有多少对有序数对i,j(i≠j)i,j(i\neq j)i,j(i=j)满足f(ai,aj)f(a_{i},a_{j})f(ai,aj)是一个363636的倍数。

示例1

输入

复制7 1 2 3 4 5 6 7

7
1 2 3 4 5 6 7

输出

复制2

说明

分别为f(3,6)=36f(3,6)=36f(3,6)=36和f(7,2)=72f(7,2)=72f(7,2)=72

示例2

输入

复制4 3 3 3 6

4
3 3 3 6

输出

复制3

说明

f(1,4)=f(2,4)=f(3,4)=36f(1,4)=f(2,4)=f(3,4)=36f(1,4)=f(2,4)=f(3,4)=36

示例3

输入

复制1 10

1
10

输出

复制0

说明

注意当NNN为1时，凑不出一对。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,i,a[10005],j,x=0;
    cin>>n;
    for(i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    for(i=0;i<n;i++){
        for(j=n-1;j>=0;j--){
            int y=a[i]*10+a[j];
            if(i!=j&&y%36==0)x++;
        }
    }
    cout<<x;
    return 0;
}