ACM新生赛部分题解

2021级的ACM新生赛已经完结了，我就自己做出来的八道题整理一下题解，因为其他是真的不会。

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

一、我们是冠军

7 日星期 777 的凌晨，777777777777 公里外的冰岛，英雄联盟 S11rm S11S11全球总决赛。来自 LPLLPLLPL 的中国战队 EDGrm EDGEDG 和卫冕冠军、韩国战队 DKrm DKDK 鏖战 555 局，最终 EDGrm EDGEDG 战队强势逆转，以总比分 3−23-23−2 的成绩，获得 202120212021 年英雄联盟全球总决赛冠军！

数年的卧薪尝胆，在这一刻终于得到了回报，EDG终于登上了荣耀的巅峰。当EDG战队的队员捧起英雄联盟S11总决赛召唤师奖杯的那一刻，相信不少年轻人开始放声嘶吼。中国LPL赛区战队EDG以3：2战胜韩国LCK赛区战队DK，获得2021年英雄联盟全球总决赛冠军，为LPL中国赛区夺得第三个召唤师奖杯。朋友圈刷屏微博话题突破30亿这一刻是荣耀的，我们是世界冠军。朋友圈里边每个小朋友都在庆贺，没有关注的小朋友却是一脸疑问。
“这个EDG是什么？怎么朋友圈里边全是EDG？”毫无疑问，7日的这一天是属于EDG的。
比赛刚刚结束，中央电视台新闻中心官方微博@央视新闻 凌晨1时许就发布了喜讯“英雄联盟S11总决赛，中国LPL赛区战队@EDG电子竞技俱乐部 以3：2战胜韩国LCK赛区战队DK，获得2021年英雄联盟全球总决赛冠军！恭喜！”微博相关话题#EDG夺冠#的阅读量达到了27亿，讨论350.7万条，网友毫不吝啬的送上祝福：“我们是冠军！”
赛前EDG并不被看好为什么EDG夺冠，小伙伴们这么兴奋，其实赛前，EDG并不被看好。
让我们来回顾下EDG总决赛的对手韩国DK战队。DK战队实力强劲，是S10世界冠军，此前连续拿下了LCK赛区春、夏季冠军，在世界赛的小组、八强赛中均未尝一败，教练是有着三冠教练的Kkoma。这样的实力加上经验丰富的教练，毫无疑问DK战队是夺冠大热门。
而反观EDG战队，是首进四强、创造决赛纪录。他们一路走来是相当的坎坷，八强赛面对RNG，打满了五局才分出胜负，四强赛对阵GEN亦是如此。他们在赛场上没有表现出绝对的统治力，而DK战队有着决赛的经验，而且实力又那么强劲，难怪赛前不被看好。逆风翻盘夺回荣耀。这场比赛对于两支队伍来说，都是将要创造历史的比赛。DK如能取胜，将成为史上第二支二连冠队伍，而EDG如果能击败DK，不仅是LPL的S赛第三冠，并且还是首支在世界赛中击败两支LCK队伍并成功夺冠的队伍。比赛开始，EDG先下一城，随后被DK连胜两局。在关键的第四局中，EDG在团战中连续追击击杀大龙，以2：2追平比分，将决赛拉至第五局。第五局，EDG战队发挥出色，不仅扛住了所有压力，更是逆风翻盘，为中国夺得了本次S11冠军。这是中国第三次取得英雄联盟全球总决赛冠军。未来可期 亚运会期待你们的表现据11月5日杭州亚组委消息，明年的杭州亚运会，包括英雄联盟在内的多个电竞项目，将成为亚运会正式竞赛项目，这也是电竞首次作为亚运会正式竞赛项目，项目所获得的奖牌将记入国家奖牌榜。相信这些队员在未来会给我们带来更多的荣耀。

输入描述:

输入一行 仅包含小写字母 的字符串 s. (1 ≤ |s|≤ 10^4)

输出描述:

仅一行，统计字符串 s 中字符串 "edgnb" 出现的次数。

代码：

#include <bits/stdc++.h>
using namespace std;
char s[100100];
int main()
{
    int count = 0;
    scanf("%s",s);
    for(int i = 0;i < strlen(s);i ++ )
    {
        if(s[i]=='e'&&s[i+1]=='d'&&s[i+2]=='g'&&s[i+3]=='n'&&s[i+4]=='b') 
        {
            
            count++;
        }
    }
    printf("%d",count);
    return 0;
}

怎么说呢，这个题比赛的时候我没有做出来，原因是字符串的长度开的不够大，我感觉是他的题目不够严谨，他的题目上说字符串 s. (1 ≤ |s|≤ 10^4)，但实际情况是我开始开了1e4 + 10，一直没有通过，我就以为是其他的问题，导致第一题都没有做出来，主要想法就是暴力搜索?，最后补充一句：EDG牛逼！！！

二、大的要来啦！！

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

给定一个长度为 n 的、仅由 1∼91 sim 91∼9 组成的字符串，你可多次执行下面的操作：
 

1. 交换两相邻字符。
2. 删除一个字符。

问，你能获得的最大字符串是多少 ？我们按照数字的比较规则定义「最大」，如: 11>2、233>211。

输入描述:

输入有两行，第一行包含一个整数 n ，表示接下来输入一个长度为 n. (1 ≤ n ≤ 10^3) 的字符串。

第二行，输入一个仅含有 1∼9 的字符串。

输出描述:

一行，表示你执行操作后能得到的最大字符串。

#include <bits/stdc++.h>
using namespace std;

int str[10],t;
int main()
{
    
    int n;
    scanf("%dn",&n);
    while(n -- )
    {
        scanf("%1d",&t),++str[t];
    } // 记录每个相同的数字出现的次数
    for(int i = 9;i > 0;--i)
    {
        while(str[i] -- )    printf("%d",i);
    } // 对原数组按降序输出
    return 0;
}

 话说，这个题比赛的时候我还是用插入排序做的，怎么说呢，做的很麻烦，这串代码是别人的，方法很简洁，思路也很清晰，只能说我和大佬还有很大差距，主要想法嘛，就是将字符串的每个字符都看成是数组的下标，统计相应下标出现的次数，然后按照降序的方法输出每个数组下标的个数即可?。

三、关于我转生变成史莱姆遇见米莉亚这档事……

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

背景：萌王米莉亚总是喜欢问新晋魔王史莱姆.利姆露一些奇怪的问题。
比如，现在有一个只有黑白颜色的 n×2 的网格，其中第一排的前 a 个格子和第二排的前 b 个格子全为白色剩余格子全为黑色。现要把 x 个 2×1 的白色骨牌，和 y 个 2×1 的黑色骨牌全部放入对应颜色的网格区域，不能有重叠。若可以输出 "YES" ，否则输出 "NO" (不含引号)

输入描述:

第一行输入 t，表示有t组数据 (1≤t≤3×10^3)对于每组数据分别输入 n,a,b，随后换行 x,y，含义如题意。

输出描述:

对于每组数据在一行输出 YES 或者 NO

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    scanf("%d",&t);
    while(t -- )
    {
        int n,a,b,x,y;
        scanf("%d%d%d%d%d",&n,&a,&b,&x,&y);
        int i = min(a,b) + (fabs(a - b) / 2); // 计算白色的最多能放多少
        int j = min(n - a,n - b) + (fabs(a - b) / 2); // 计算黑色的最多能放多少
        if(x <= i && y <= j)    printf("YESn");
        else    printf("NOn");
    }
    return 0;
}

怎么说呢，这个题啊，我当时的想法有一点错误，当时以为骨牌只能竖着摆（受了例题的影响,哭成小猪头[???])，主要想法就是找到白色骨牌竖着能放多少个（找到两行中白色格子数a,b中最小的  [min(a,b)]），再看横着能放多少个（两行中白格子数a,b大的减去小的再除以2  [fabs(a - b) / 2]，之后分别与x,y进行比较，如果x,y都较小即可输出"YES"，反之则输出"NO"。

四、啊bnmcaupws的我

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

智乃酱最喜欢的字符串 "swpuacmnb" 的顺序打乱了！！！现在的他非常苦恼。为了使智乃酱重新开心，我想了下面一种方法：

• 每次交换任意两个字符位置。

问最小操作多少次才能得到 "swpuacmnb" ?

输入描述:

仅一行长度为 9 的字符串，数据保证是 "swpuacmnb" 乱序得到的结果。

输出描述:

最少要操作多少步才能得到 "swpuacmnb"。

#include <bits/stdc++.h>
using namespace std;

int main (void)
{
    int cnt = 0;
    string s, a = "swpuacmnb";
    cin >> s;
    for ( int i = 0; i < 9;i ++ ) // 遍历数组找到不在相应位置上的字符进行交换，记录交换次数
    {
        if ( s[i] != a[i] )
        {
            for (int j = i + 1; j < 9;j ++ )
            {
                if ( s[j] == a[i] )
                {
                    swap ( s[i], s[j] );
                    cnt++;
                }
            }
        }
    }
    cout << cnt;
    return 0;
}

emmmmm，这个题嘛，我比赛的时候不会做，这是看了我们团队一文学长的代码敲出来的，这个方法比DFS爆搜要好理解很多?，想法就是遍历字符串，找到不在原位上的字符，然后再找到该字符本应所在位置的下标，将下标所指的字符与该字符互换，并将次数加一，遍历完成后，字符串变为正常顺序，输出交换次数即可。

五、并不很傻瓜的计算器

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

C++ 和 Java 中都有异常报告机制，代码化的讲：

try {
// do work
} catch (Error) {
// handle error
}

异常最大的意义就是告警程序员程序运行时会出现的问题，以便于更好地解决问题。如果程序在运行时出现了**不可以执行的语句**，将会抛出异常。本题要求你模拟这个过程。

涛涛设计了一个仅针对整形数据 xxx 的计算器，需要实现下面四种功能：

1. + val，执行后 x += val
2. - val，执行后 x -= val
3. * val，执行后 x *= val，数据保证乘后的结果不会超过 int 范围。
4. / val，执行后 x /= val（整除）

分析上面的过程中可能出现的问题，如果出现除零异常，报告之，格式如下：

Divide by zero exception

否则，输出执行了这一步之后的 xxx 。

输入描述:

第一行输入两个整数 x,q，表示需要运算的对象以及需要运算的次数。
下面 q 行，每行包含一个字符与一个整数，格式形如 + 1, * 2 。

输出描述:

输出共包含 q 行。
如果该行发生除零异常，输出 “Divide by zero exception”
否则，输出运算后的 x 。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x,q;
    scanf("%lld%d",&x,&q);
    while(q -- )
    {
        char c;
        int val,flag = 1;
        scanf(" %c%d",&c,&val);
        if(c == '+')    x += val;
        if(c == '-')    x -= val;
        if(c == '*')    x *= val;
        if(c == '/')
        {
            if(val == 0)
            {
                printf("Divide by zero exceptionn");
                flag = 0;
            }
            else    x /= val;
        }
        if(flag)    printf("%dn",x);
    }
    return 0;
}

嘶~~，对于这个题完全是自己脑瘫，比赛时忘了编写分母不为零时的操作，以至于结果都是错的，最nt的是一直没检查出来。对于这个题，想法就是进行q次操作，每次对x执行相应的操作，最后输出x即可（我是废物?）。

六、3 SCORE!

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

球和篮筐是篮球比赛中必不可少的设备——带有篮筐的扁平矩形篮板。我们用侧视图来描述，忽略厚度，篮板被认为是平行于y轴的一段，篮筐被认为是平行于x轴的一段。篮筐的右端与篮板相连。

为了简化模型，我们将篮球视为一个质点。只考虑重力，如果不考虑篮筐和篮板，篮球的运动轨迹就是a<0a<0a<0的抛物线 y = ax^2 + bx + c。但篮球很有可能撞到篮板，导致轨迹发生变化。我们将篮球与篮板（包括端点）之间的碰撞视为完全弹性碰撞，这意味着篮球在 x 轴上的速度将反转，而在 y 轴上的速度将保持不变。我们在这个问题中忽略了球场地板。

如果篮球从上到下穿过篮筐（不包括端点），我们才认为是一个进球。一旦篮球触及篮筐的任一端点，即击中篮筐，篮球将被弹开而无法进球。另外，根据规则，篮球不能从下往上穿过篮筐，否则属于违例，不能计入球门。

智乃酱现在知道了 a、b、c 的值以及篮板和篮筐的位置。她想知道如果篮球从x=−10^50 开始并沿 x 轴的正方向移动，是否可以进球。

输入描述:

输入包含 8 个整数，分别是 a,b,c,x0,x1,y0,y1,y2​，分别表示 ax^2 + bx + c 的 (a,b,c)，随后五个数分别确定了 篮筐的位置 (x0,y0)，(x1,y0) 以及篮板的位置 (x1,y1)，(x1,y2) 。 其中x0 < x1，y1 < y0 < y2。

所有数的绝对值都不会超过 10 ^ 4。

输出描述:

输出一行，如果球能够进入，输出 "YES" (不包含引号)， 否则输出 "NO" (不包含引号)。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a,b,c,x0,x1,y0,y1,y2;
    cin >> a >> b >> c >> x0 >> x1 >> y0 >> y1 >> y2;
    if(a*x0*x0 + b*x0 + c > y0 && a*x1*x1 + b*x1 + c < y0 || a*x0*x0 + b*(-x0) + c < y0 && a*x1*x1 + b*x1 + c > y0) // 判断条件
    {
        printf("YES");
    }
    else
    {
        printf("NO");
    }
        return 0;
}

怎么说呢，这个题啊，思路真的很简单，但我比赛的时候看了一眼题感觉文字太多，认为会很难就没有看，该打???，想法也很简单，就是判断一元二次函数根的区间，其次要注意的是篮球反弹时可以看成篮球穿过篮板进入篮板另一侧的篮筐，对答案无影响，但是会简单一点?。

七、智乃酱的数组

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

智乃酱现在有一个长度为 nnn 的数组 {A} ，一个整数 k ，现在要从 A 数组中选出一些元素Ab1,Ab2,Ab3,⋯ ,Abm  (1 ≤ b1 < b2 < ⋯ < bm ≤ n)，满足 ∀1 ≤ i < j ≤ m,  ∣Abi – Abj∣ ≥ k。智乃酱想下考你，能选出的元素个数的最大值 m 是多少？

输入描述:

第一行两个整数 n，k (1 ≤ n ≤ 10^3,0 ≤ k ≤ 10^9)
第二行 n 个整数 A1,A2,A3,⋯ ,An (1≤Ai≤10^9)

输出描述:

输出你能选出的元素个数的最

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,k,count = 1;
    cin >> n >> k;
    int a[n];
    for(int i = 0;i < n;i ++ )   scanf("%d",&a[i]);
    sort(a,a+n); // 对数组升序排序
    int j = a[0];
    for(int i = 1;i < n;i ++ ) // 找出符合题意的数
    {
    	if(a[i] - j >= k)	count ++,j = a[i];
    	
	}
    
    printf("%d",count);
    return 0;
}

emmmmmm，思路就是先对数组进行升序排序，然后将数组中最小的记为一个标志，然后遍历数组，找出第一个与标志数字相差大于等于k的数字，重置标记为当前数字，计数加一，遍历完成，输出计数即可。

八、牛与马的故事

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

草原上有 n 头牛马，ta 们从左到右排成一排，第 i 个牛马的高度为 hi​，由于 《我们不一样》 ，所以不同牛马的高度一定不同。众所周知， tt 从小骑马上学，他想把这排牛马按照高度从低到高的顺序，从左到右依次排好。但是 tt 不想用普通的排序方式，他想到了一种新的排序方法。他希望将这一排牛马从左到右切分成 K 段连续的 K 组牛马，仅对这 K 组牛马序列的内部进行一次从小到大的排序，就可以使得整排牛马从低到高排好。聪明的 tt 轻松的解决了这个问题，但是他留下了一个问题给大家：K 的最大值是多少？即最多可以分为多少个连续的组 ？

输入描述:

输入包含两行，第一行包含一个整数 n ，表示 n 位牛马。
第二行包含 n 个整数，hi​ 表示第 i 条牛马的身高，以空格隔开。

输出描述:

一个整数，表示你的答案。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int main()
{
    long long a[N],b[N],s = 0,t = 0;
    int n,count = 0;
    cin >> n;
    for(int i = 0;i < n;i ++ )
    {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b,b + n); // 排序
    for(int i = 0;i < n;i ++ ) // 通过前缀和来判断可以分为几段
    {
        s += a[i];
        t += b[i];
        if(s == t)    count ++;
    }
    printf("%d",count);
    return 0;
}

唔~~~，这个题怎么说也是自己想复杂了，思路就是建立两个数组，同时存储相同的数据，对其中的一组进行排序，然后通过前缀和来判断可分为几段，就是每次当两个数组的前缀和相等时，计数加一，最后输出计数即可。

怎么说呢，我会的八道题都整理完了，感觉这八道题不是很难，但是不知道为什么当时不会做，可能事后做出来都觉得不难，总之，一切借口都是狡辩，只有不断提升自己的能力才是硬道理，之前发过说说引用了狂铁的半句话：“迄今所有的人生都大写着失败。”今天想把后半句一起说出来：“迄今所有的人生都大写着失败，但不妨碍我继续向前。”差不多就到这里了，以后有时间再写???。