2019级第二次月赛暨软件计科联合新生赛补题赛总结
2019级第二次月赛暨软件计科联合新生赛补题赛
帮助kiki
kuku送给kiki一串宝石，kiki发现每次可以从宝石序列中取出正好是相同类型的三个连续的宝石，在拿走三颗宝石之后，原始序列的左右两部分将自动按原始顺序合并为一个序列。
聪明的kuku当然知道这一点并且提前知道合并的次数和宝石最终的样子。
可爱的kiki很想知道自己最多需要合并几次才能得到最终的宝石序列，但是又不敢问kuku，所以这个问题只能交给同样聪明的你来解决。 Input
只有一行字符串s(1≤∣s∣≤105)s(1≤∣s∣≤105 )，表示宝石序列，其中相同的字母视为相同的类型。（仅包含大写字母）
Output
一行包含一个整数n和一个字符串m用空格隔开，表示kiki最多需要合并n次会得到最终的宝石序列m。（如果合并之后的宝石序列大小为0，kiki会很伤心，这个时候你需要输出qwq）。
思路如下
第一种思路：我们可以用最粗暴的方法来解决，我就通过 for循环不断的遍历所给的字符串一旦发现有三个连续相同的字母我们就直接删掉，然手再从头遍历 字符串，如果再找到三个连续的就在删除，这样循环往复，就就能得到结果
第二种方案就是：我们可以通过 栈 来解决这个问题，通过栈先进后出的特点，我所给的字符串一个接着一个的放进 栈 里，一旦栈里的元素超过3个 我们就可以判断 栈 顶部的三个元素是否相同如果相同，我们就把这个顶部3个字符串取出来，如果不相同，我们
题解如下
方法一：
#includereturn 0;
} 方法二：
#includekuku吃糖果
Description
众所周知kuku喜欢吃糖果，但是kuku吃糖果也是有原则的，他不会连续吃相同的糖果。kuku第一次吃了一个
A这种糖果，那么他第二次就不会再吃
A这种糖果了，但是他第三次可以继续吃
A这种糖果（连续的两次吃的糖果种类不能相同），现在告诉你
kuku手中的糖果种类以及每种糖果的个数，他是否能把他的糖果数吃完？如果能吃完就输出 “Yes”,否则输出“No"(输出不用把双引号输出)
Inputt(1≤t≤5)t(1≤t≤5)组输入，对于每组输入 第一行输入一个正整数n（1≤n≤106）n（1≤n≤106 ）表示kuku拥有的糖果种类接下来一行输入n个数，第i个数a i表示第i类糖果的个数(1≤ai≤1061≤a i≤106)。
Output
如果kuku能吃完糖果输出Yes,否则输出No。
Sample Input 1
2
3
4 1 1
5
5 4 3 2 1
Sample Output 1
No
Yes
思路如下：
我们这里可以用插空法，来完成，首先我们要确保最多那种糖的数量a 颗小于剩余糖的数量
只有这才可以确保 数量最多的那种糖 能够完全被隔开，这样相当于，两次不吃同样的糖，
然后我们再把剩余的糖 插入到 a-1个空中，当查到做最后一个位置后，继续从头开始查，这样就能是所有同种糖不相临
#####题解如下：
#includekuku会读数
Description
卖火柴的lly火柴卖完了([斜眼笑])，现在kuku有一个时钟使用标准的7段LCD显示屏显示所有数字，外加两个小段显示"："，并以24小时格式显示所有时间。
问题很简单，你只需要读数就行了。
Input
输入的第一行包含一个整数
t(1≤t≤200)
t(1≤t≤200)，表示测试用例的数量。
在每个测试用例中，时钟屏幕都有一个7×21ASCII7×21ASCII图像。
所有数字段均由两个字符表示，每个冒号段均由一个字符表示。字符"X"“X"表示分段，而”.""."则表示其他任何内容。
有关详细信息，请参见样本输入。
Output
对于每个测试用例，以HH：MM格式打印一行包含字符串T，其中T（00：00≤T≤23：59）T（00：00≤T≤23：59）表示时钟上显示的时间。
Sample Input 1
2
.XX...XX.....XX...XX.
X..X....X......X.X..X
X..X....X.X....X.X..X
......XX.....XX...XX.
X..X.X....X....X.X..X
X..X.X.........X.X..X
.XX...XX.....XX...XX.......XX.....XX...XX.
...X....X......X.X..X
...X....X.X....X.X..X
......XX.....XX...XX.
...X.X....X....X....X
...X.X.........X....X
......XX.....XX...XX.
Sample Output 1
02:38
12:39
思路如下：
这题我们要抓住 图案上表示的数字的特征，一种思路是，我们抓住每个数字是由7个 横竖的小节（三横四竖） 组成（有的每个数字需要几横，几竖 是不同的），我们可以统计对应每一横的有无，去判断是那个数字。
题解如下
#includekuku的电话号码
一个电话号码有11位数字，且必须以8为开头（可能跟平常号码的不一样ヽ(。>Д<)o゜）像8********* (*为一个0~9的数字) 是一个电话号码
现在给你一个n，代表数字的个数（11<=n<=10000），接下来个给你n个数字（n个数字连在一起，你可以把她当做一个长度为n的字符串）你希望使用他们来制作尽可能多的电话号码，每个数字最多使用一次，电话号码可以相同。
求这些数字最多构成的电话号码个数
输入描述:
多组输入（不多于1000组）
每组数据输入一个整数n（11<=n<=2000）
接下来给出n个数字
输出描述:
每组数据输出这些数字最多构成的电话号码个数
样例输入:
11
00000000008
样例输出:
1
思路如下：
这一题最难的是理解题意，这道题让求的不是 组成的电话号种类，而是要求可以组成的电话号 个数（一定要区分种类 和 个数 之间的差别），组成的电话个数就与 字符串中8的数量有关，也与字符串的长度有关。
题解如下：
#includekuku的无敌序列
Description
kuku现在有一个由1到n组成的无序数列，他将数列中每一个位置变为一个三元组，例如数列1,2,3,4,5将可以变成3个三元组（1,2,3），（2,3,4），（3,4,5），三元组中的数的位置可以改变如（1,2,3）等价于（3,2,1）或（2,3,1）等。。。。。。。。
现给出你n−2个三元组，求出满足的原数列，如有多种情况，输出最小字典序的那种。
Input
第一行给定一个n(3≤n≤10)
接下来将有n−2行的输入，每行一个三元组。
Output
输出字典序最小的原数列。（用空格隔开）
Sample Input 1
5
4 3 2
2 3 5
4 1 2
Sample Output 1
1 4 2 3 5
Sample Input 2
3
3 2 1
Sample Output 2
1 2 3
思路如下：
这题想着过程很复杂，但是题上给的 n 的取值范围很小，那我们就用最暴力的方法dfs，去把每种组合方案都 尝试一下，直到找出我们先要的答案。
题解如下：
#includekuku的生命线
Description
kuku有一个程序猿重要的属性-生命值，缩写为HP。
一般来说，HP的不同值分为4类：
若HP为（4n+1）形式，则为A类，即除以4，余数为1；
B类：HP为（4n+3），即除以4，余数为3；
C类：HP为（4n+2），即除以4，余数为2；
D类如果HP是4n的形式，即除以4，余数为0。
上述n可以是任意整数。
这4个类别从高到低依次为A>B>C>D，即A类最高，D类最低。
kuku可以提高角色的生命值。现在她希望你最多增加她的生命值2（也就是说，增加0，1或2）。她应该增加多少她的生命值，使它有可能是最高的类别？
Input
唯一一行包含一个整数x（30≤x≤100)x（30≤x≤100)当前的HP值。
Output
打印一个整数a（0≤a≤2）a（0≤a≤2）和一个大写字母b（b∈A，B，C，D）
b（b∈A，B，C，D），表示最好的方法是将她的生命值增加a，然后类别变为b。
请注意，输出字符区分大小写。
题解如下：
#includekuku的冠军梦想
思路如下：
用sort函数解决，可以通过sort对结构体的排序、或者sort 对string 字符串的排序
题解如下：
#include幸运的字符串
Description
如果字符串包含的所有字母连续（相邻），并且每个字母恰好出现一次，则该字符串称为幸运的字符串。
例如，以下字符串是幸运的：“ fced”，“ xyz”，“ r”和“ dabcef”。
以下字符串不是可爱的：“ az”，“ aa”，“ bad”和“ babc”。
请注意，字母“ a”和“ z”不相邻。
现在你需要判断给定的字符串是否是可爱的字符串，是即输出：Lucky，否则输出：Unlucky
Input
第一行包含整数n（1≤n≤100），表示要处理的字符串数。接下来的n行包含字符串，每行一个字符串。每个字符串仅包含小写字母，长度在1到100之间（含1和100）。
Output
打印
n行，每输入一个字符串一行。打印一个字符串：
Lucky或者Unlucky作为答案。
Sample Input 1
8
fced
xyz
r
dabcef
az
aa
bad
babc
Sample Output 1
Lucky
Lucky
Lucky
Lucky
Unlucky
Unlucky
Unlucky
Unlucky
思路如下：
这题我们直接用sort（）函数输入的各个字符串中的各个字符排序，对字符排完序号后，我们要判断是否连续、且不出现重复的字符，我们通过后一个字符减前一个字符 看差值是否都为1，如果符合题意就是Lucky，否则为Unlucky
题解如下：
#includekuku的排列组合
Description
kuku有一个题目，题目很简单就是求组合数
C( nm )
思路如下：
这题一看数据范围就应该明白，直接先求n的阶乘是不可行的，因为20多的阶乘， 用long long 也已经爆了，当然我们也不能用大数 乘法与 大数除法，因为这样太复杂了，需要非常复杂的代码，这个时候我们可以考虑 先化简 n！/m！ 为（m+1）*（m+2）…*n; 在考虑将这个化简后的多项式，用for循环来表示求这个式子的值，在求这个式子的值的时候，可以除
（n-m）！中的分式子的值（达到提前除防止数据超过数据范围）
思路如下：
#include定西
Description
这么多年你一个人一直在走
方向和天气的节奏会让你忧愁
你说你遇见了一大堆奇怪的人
他们看上去好像都比你开心
——李志《定西》
0.jpg
这首歌的吉他节奏总感觉是在致敬《加州旅馆》，前奏又像葫芦娃里面在蛇精洞似的配乐。kuku 一个人走了很多年，发现自己走进了一个无限迷宫。
所谓无限迷宫是指，由一个 N×M 的迷宫单元经过无限平铺得到的迷宫，即将无数份迷宫单元平铺在一个二维平面上。不妨假定 kuku当前位置为起点处。
那么问题来了，kuku能不能一直走下去呢？当然，走过的路是不能再走的。
Input
第一行两个整数 N,M (1≤N, M≤2000)，用来描述迷宫单元的尺寸。
接下来是一个 N×M 的字符矩阵，用来描述这个迷宫，每个字符一定属于以下三种：
- 字符
'.'代表这个点是空地。 - 字符
'S'代表这个点是起点。 - 字符
'#'代表这个点是墙，不可以走。
Output
输出一行一个字符串“Yes”或“No”（不包括引号），“Yes”表示 KuKu 可以逃到无限远的地方，“No”表示不可以。
Sample Input 1
3 3
#.#
#.#
#S#
Sample Output 1
Yes
Sample Input 2
5 5
#.#.#
..#.S
#####
..#..
#.#.#
No
思路如下：
这一题刚读完，让人完全没头脑，首先我们应该明白 什么样的情况可以无限走下去（本质原因：就是要我们求能否从起点到达另一个起点！），因此我们可以考虑只要从一块地图(x,y)出发，越过边界到第二块地图上，走在第一块图上的 所有点中，只要能够在第二块图上 找到在第一块图中出现的点一个对应点,只要有一个对应点，表明我们就可以到达第一块地图中的出发点(x,y)的在第二块图中的对应点，通过这样的转化 也可以的无限走下去了 . （叙述不严谨 为了严谨 可以把 “第二块图”改写成“其它地图”）
题解如下：
#include本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！