注意
该博客是为了帮助同学学习,并非为了协助同学刷题,请读者保持自觉,请勿做CV工具人。另外为了节省篇幅,代码中不再写明#include
,如果遇到我没有声明的函数,那么就是某一个头文件中的函数,读者搜索“c
+ 函数名字”就能查到相关信息。
后面几道难题采用了C++
进行编写,题解中会给出网上的C
语言解法(如果找得到的话),特别简单的题只给出代码。本次题解的题干由探姬姐姐负责抄写,本人负责格式化和编写题解。
简单题
这次真的没骗你 —— 这道超级简单的题目没有任何输入。
你只需要在一行中输出事实:This is a simple problem.
就可以了。
输入样例:
无
输出样例:
This is a simple problem.
题解
1 |
|
A乘以B
看我没骗你吧 —— 这是一道你可以在10秒内完成的题:给定两个绝对值不超过100的整数A
和B
,输出A
乘以B
的值。
输入格式:
输入在第一行给出两个整数A
和B
(−100≤A
, B
≤100),数字间以空格分隔。
输出格式:
在一行中输出A
乘以B
的值。
输入样例:
-8 13
输出样例:
-104
题解
1 |
|
打折
去商场淘打折商品时,计算打折以后的价钱是件颇费脑子的事情。例如原价 ¥988,标明打 7 折,则折扣价应该是 ¥988 x 70% = ¥691.60
。本题就请你写个程序替客户计算折扣价。
输入格式:
输入在一行中给出商品的原价(不超过1万元的正整数)和折扣(为[1, 9]区间内的整数),其间以空格分隔。
输出格式:
在一行中输出商品的折扣价,保留小数点后 2 位。
输入样例:
988 7
结尾无空行
输出样例:
691.60
题解
1 |
|
后天
如果今天是星期三,后天就是星期五;如果今天是星期六,后天就是星期一。我们用数字 1 到 7 对应星期一到星期日。给定某一天,请你输出那天的“后天”是星期几。
输入格式:
输入第一行给出一个正整数D
(1 ≤ D
≤ 7),代表星期里的某一天。
输出格式:
在一行中输出D
天的后天是星期几。
输入样例:
3
输出样例:
5
题解
1 |
|
到底是不是太胖了
据说一个人的标准体重应该是其身高(单位:厘米)减去100
、再乘以0.9
所得到的公斤数。真实体重与标准体重误差在10%
以内都是完美身材(即 | 真实体重 − 标准体重 | < 标准体重×10%
)。已知市斤是公斤的两倍。现给定一群人的身高和实际体重,请你告诉他们是否太胖或太瘦了。
输入格式:
输入第一行给出一个正整数N
(≤ 20)。随后N
行,每行给出两个整数,分别是一个人的身高H
(120 < H
< 200;单位:厘米)和真实体重W
(50 < W
≤ 300;单位:市斤),其间以空格分隔。
输出格式:
为每个人输出一行结论:如果是完美身材,输出You are wan mei!
;如果太胖了,输出You are tai pang le!
;否则输出You are tai shou le!
。
输入样例:
3
169 136
150 81
178 155
输出样例:
You are wan mei!
You are tai shou le!
You are tai pang le!
题解
1 |
|
奇偶分家
给定N
个正整数,请统计奇数和偶数各有多少个?
输入格式:
输入第一行给出一个正整N
(≤1000);第2行给出N
个非负整数,以空格分隔。
输出格式:
在一行中先后输出奇数的个数、偶数的个数。中间以1个空格分隔。
输入样例:
9
88 74 101 26 15 0 34 22 77
输出样例:
3 6
题解
这道题我们就点一个点,就是奇偶的判断优化。首先我们明确一个点,就是计算机进行位运算的速度是快于四则及取模运算的。
类比十进制时我们可以通过数字的尾数来快速地判断是否能被 2 整除,我们可以得出当二进制位最低位为0
时表明这是一个偶数,为1
时为奇数。
我们可以通过位运算得到一个整数的最低为为什么值:n & 1
,如果最低位为0
则表达式的结果为0
,否则为1
。
所以我们可以通过(n & 1) == 0
(或n & 1
)来代替n % 2 == 0
,这样子可以获得更好的性能。
1 |
|
幸运彩票
彩票的号码有 6 位数字,若一张彩票的前 3 位上的数之和等于后 3 位上的数之和,则称这张彩票是幸运的。本题就请你判断给定的彩票是不是幸运的。
输入格式:
输入在第一行中给出一个正整数N
(≤ 100)。随后N
行,每行给出一张彩票的 6 位数字。
输出格式:
对每张彩票,如果它是幸运的,就在一行中输出 You are lucky!
;否则输出 Wish you good luck.
。
输入样例:
2
233008
123456
输出样例:
You are lucky!
Wish you good luck.
题解
这道题我们取了一个巧,通过%1d
来控制每次只读入一位数字,读取三次获取三个位上的数字,这样就不用像%d
一样先读进来再分割数字,也不用像%c
一样需要考虑换行符以及要减去'0'
。
1 |
|
大笨钟的心情
有网友问:未来还会有更多大笨钟题吗?笨钟回复说:看心情……
本题就请你替大笨钟写一个程序,根据心情自动输出回答。
输入格式:
输入在一行中给出 24 个 [0, 100] 区间内的整数,依次代表大笨钟在一天 24 小时中,每个小时的心情指数。
随后若干行,每行给出一个 [0, 23] 之间的整数,代表网友询问笨钟这个问题的时间点。当出现非法的时间点时,表示输入结束,这个非法输入不要处理。题目保证至少有 1 次询问。
输出格式:
对每一次提问,如果当时笨钟的心情指数大于 50,就在一行中输出 心情指数 Yes
,否则输出 心情指数 No
。
输入样例:
80 75 60 50 20 20 20 20 55 62 66 51 42 33 47 58 67 52 41 20 35 49 50 63
17
7
3
15
-1
输出样例:
52 Yes
20 No
50 No
58 Yes
题解
1 |
|
数组元素循环右移问题
一个数组A
中存有N
(> 0)个整数,在不允许使用另外数组的前提下,将每个整数循环向右移M
(>= 0)个位置,即将A
中的数据由(A0,A1⋯AN−1)变换为(AN−M⋯AN−1,A0,A1⋯AN−M−1)(最后M
个数循环移至最前面的M
个位置)。如果需要考虑程序移动数据的次数尽量少,要如何设计移动的方法?
输入格式:
每个输入包含一个测试用例,第 1 行输入N
(1 <= N
<= 100)和M
(>= 0);第 2 行输入N
个整数,之间用空格分隔。
输出格式:
在一行中输出循环右移M
位以后的整数序列,之间用空格分隔,序列结尾不能有多余空格。
输入样例:
6 2
1 2 3 4 5 6
输出样例:
5 6 1 2 3 4
题解
偷懒解法
这道题虽然题干要求平移数组,但是实际上完全没这个必要,我们只需要修改遍历数组时的起始位点就可以了。
1 |
|
标准解法
按照移动数组的解法来写的话没想到什么可以避免开新空间用来存数据的方法。开新空间存数据有两种,一种是新建一个独立的数组,另一种是在开需要操作的数组的时候空间多开出移动的位数所需的空间。
1 |
|
猜数字
一群人坐在一起,每人猜一个 100 以内的数,谁的数字最接近大家平均数的一半就赢。本题就要求你找出其中的赢家。
输入格式:
输入在第一行给出一个正整数N
(<= 104)。随后N
行,每行给出一个玩家的名字(由不超过8个英文字母组成的字符串)和其猜的正整数(<= 100)。
输出格式:
在一行中顺序输出:大家平均数的一半(只输出整数部分)、赢家的名字,其间以空格分隔。题目保证赢家是唯一的。
输入样例:
7
Bob 35
Amy 28
James 98
Alice 11
Jack 45
Smith 33
Chris 62
输出样例:
22 Amy
题解
1 |
|
天梯赛的善良
天梯赛是个善良的比赛。善良的命题组希望将题目难度控制在一个范围内,使得每个参赛的学生都有能做出来的题目,并且最厉害的学生也要非常努力才有可能得到高分。
于是命题组首先将编程能力划分成了 106 个等级(太疯狂了,这是假的),然后调查了每个参赛学生的编程能力。现在请你写个程序找出所有参赛学生的最小和最大能力值,给命题组作为出题的参考。
输入格式:
输入在第一行中给出一个正整数 N
(<= 2×104),即参赛学生的总数。随后一行给出 N
个不超过 106 的正整数,是参赛学生的能力值。
输出格式:
第一行输出所有参赛学生的最小能力值,以及具有这个能力值的学生人数。第二行输出所有参赛学生的最大能力值,以及具有这个能力值的学生人数。同行数字间以 1 个空格分隔,行首尾不得有多余空格。
输入样例:
10
86 75 233 888 666 75 886 888 75 666
输出样例:
75 3 888 2
题解
1 |
|
凯撒密码
为了防止信息被别人轻易窃取,需要把电码明文通过加密方式变换成为密文。输入一个以回车符为结束标志的字符串(少于 80 个字符),再输入一个整数offset
,用凯撒密码将其加密后输出。恺撒密码是一种简单的替换加密技术,将明文中的所有字母都在字母表上偏移offset
位后被替换成密文,当offset
大于零时,表示向后偏移;当offset
小于零时,表示向前偏移。
输入格式:
输入第一行给出一个以回车结束的非空字符串(少于 80 个字符);第二行输入一个整数offset
。
输出格式:
输出加密后的结果字符串。
输入样例1:
Hello Hangzhou 2
输出样例1:
Jgnnq Jcpibjqw
输入样例2:
a=x+y -1
输出样例2:
z=w+x
题解
这段代码中我们说一下isalpha(out) && (islower(out) == true) == low
。
首先,isalpha
是用来判断字符偏移完后还是不是字母,如果偏移后不是字母说明其一定超出了范围,需要减26
。但是如果在字母范围内并不一定代表其没有超出范围,观察ASCII编码的排列可以知道,大写字母是排在小写字母前面的,且Z
和a
的间距小于26
,我们完全有可能会把一个小写字母偏移成一个大写的,也有可能把一个大写字母偏移为小写的。
所以必须处理这种情况,这就是后面的代码处理的内容。至于为什么多出来一个==
,是因为islower
这一类函数返回值不是严格的0
为假、1
为真,以至于islower
返回的两个真直接==
判断可能会不相等,通过==
就可以把值转化为标准的0 1
表达。
1 |
|
简单计算器
本题要求你为初学数据结构的小伙伴设计一款简单的利用堆栈执行的计算器。如上图所示,计算器由两个堆栈组成,一个堆栈 S1 存放数字,另一个堆栈 S2 存放运算符。计算器的最下方有一个等号键,每次按下这个键,计算器就执行以下操作:
- 从 S1 中弹出两个数字,顺序为 n1 和 n2;
- 从 S2 中弹出一个运算符 op;
- 执行计算 n2 op n1;
- 将得到的结果压回 S1。
直到两个堆栈都为空时,计算结束,最后的结果将显示在屏幕上。
输入格式:
输入首先在第一行给出正整数N
(1 <N
<= 103),为 S1 中数字的个数。
第二行给出N
个绝对值不超过 100 的整数;第三行给出N − 1
个运算符 —— 这里仅考虑+
、-
、*
、/
这四种运算。一行中的数字和符号都以空格分隔。
输出格式:
将输入的数字和运算符按给定顺序分别压入堆栈 S1 和 S2,将执行计算的最后结果输出。注意所有的计算都只取结果的整数部分。题目保证计算的中间和最后结果的绝对值都不超过 109。
如果执行除法时出现分母为零的非法操作,则在一行中输出:ERROR: X/0
,其中 X
是当时的分子。然后结束程序。
输入样例 1:
5 40 5 8 3 2
/ * - +
输出样例 1:
2
输入样例 2:
5 2 5 8 4 4 * / - +
输出样例 2:
ERROR: 5/0
题解
我们放一个图表来演示计算过程:
1 |
|
分而治之
分而治之,各个击破是兵家常用的策略之一。在战争中,我们希望首先攻下敌方的部分城市,使其剩余的城市变成孤立无援,然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序,判断每个方案的可行性。
输入格式:
输入在第一行给出两个正整数N
和M
(均不超过 10_000),分别为敌方城市个数(于是默认城市从 1 到N
编号)和连接两城市的通路条数。随后M
行,每行给出一条通路所连接的两个城市的编号,其间以一个空格分隔。在城市信息之后给出参谋部的系列方案,即一个正整数K
(<= 100)和随后的K
行方案,每行按以下格式给出:
Np v[1] v[2] ... v[Np]
其中Np
是该方案中计划攻下的城市数量,后面的系列v[i]
是计划攻下的城市编号。
输出格式:
对每一套方案,如果可行就输出YES
,否则输出NO
。
输入样例:
10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 10
2 4
5
4 10 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2
输出样例:
NO
YES
YES
NO
NO
题解
这道题我们求解时使邻接表存储图的信息,邻接表这里就不讲了,可以自行查看网络上的资源。
首先我们要清除一个点,即孤立无援是什么?其实孤立无援就是要保证所有点都没有与之相连的点。接下来自然是根据题目要求输入并存储图的数据,这是非常简单的一步。接着就是这道题的重点,输入并处理方案
数据。
这里我们有两个选择,第一种是每次处理数据前先把图复制一遍,然后直接在复制后的数据上进行计算,最终得出答案,这样就不会影响下一次计算,但是这个方法有一个明显的缺陷,就是在数据规模比较大的时候很容易内存超限或者时间超限。
所以我们选择第二种选择,即使用一个数组(或者vector
)存储方案,数组中实际存储的是指定节点被移除的连接的数目。这样子的话在处理完数据后遍历数组,判断其值是否大于等于图中的连接数量,就可以判断是否所有节点的连接数量都为0
。
1 |
|
符号配对
请编写程序检查C语言源程序中下列符号是否配对:/*
与*/
、(
与)
、[
与]
、{
与}
。
输入格式:
输入为一个 C 语言源程序。当读到某一行中只有一个句点.
和一个回车的时候,标志着输入结束。程序中需要检查配对的符号不超过100个。
输出格式:
首先,如果所有符号配对正确,则在第一行中输出YES
,否则输出NO
。然后在第二行中指出第一个不配对的符号:如果缺少左符号,则输出?-右符号
;如果缺少右符号,则输出左符号-?
。
输入样例1:
void test()
{
int i, A[10];
for (i=0; i<10; i++) { /*/
A[i] = i;
}
.
输出样例1:
NO
/*-?
输入样例2:
void test()
{
int i, A[10];
for (i=0; i<10; i++) /**/
A[i] = i;
}]
.
输出样例2:
NO
?-]
输入样例3:
void test()
{
int i
double A[10];
for (i=0; i<10; i++) /**/
A[i] = 0.1*i;
}
.
输出样例3:
YES
题解
1 |
|