HNUCM 2018级《算法分析与设计》练习一题解

阳光穿透心脏的1/2处 2023-07-06 13:29 1阅读 0赞

# HNUCM 2018级《算法分析与设计》练习一题解 #

--------------------

## [A-无法重启的2020][A-_2020] ##

--------------------

**题意：**  
给定一个四位数，判断是否符合ABAB类型  
是输出Yes，否输出No

**题解：**  
需要注意的坑点是第一个数和第二个数不能相等，否则就是AAAA类型了

--------------------

## [B-XP的众数][B-XP] ##

--------------------

**题意：**  
多组输入，每组给定数组大小，后面紧跟着该数组的值，求该数组众数的个数

**题解：**  
1.如果会C++，直接用map，会发现非常水

2.但是不会也没关系，可以先对数组a\[\]排序，然后再进行遍历，可以再开一个数组b\[\]，用来存在遍历时每个数出现的次数，然后再对新数组遍历一次，找出出现最多的次数；然后通过遍历一一比较即可得出答案（当然也可以对数组b\[\]由大到小排序，然后再遍历遇到与前一个不等时，直接跳出循环）

--------------------

## [C-XP的电灯][C-XP] ##

--------------------

**题意：**  
k位同学，n盏灯，起初所有灯都是熄灭的；第i位同学会按一次i的倍数的灯（也就是说当熄灭时会打开，打开状态是会关闭）；求最终有多少盏灯是亮着的

**题解：**  
直接可以用数组模拟，两重循环即可解决，第一重循环对学生，第二重循环对灯

--------------------

## [D-饥饿的XP][D-_XP] ##

--------------------

**题意：**  
首先给出n，m；n表示xp的速度，m表示食物供给点的数量  
然后给出xp的位置（x，y）  
紧接着给出m个食物供给点的位置(xi，yi）

求到达最近食物点的时间

**题解：**  
1、需要注意的是：这题需要多组输入，题目的确没讲太清楚

2、然后就只要注意下防止精度丢失就可以了

--------------------

## [E-Yftc的字符串转换][E-Yftc] ##

--------------------

1、多组输入  
2、直接对每个字符串遍历一下，然后大写转小写；小写转大写即可

--------------------

## [F-进制转换：十进制转二进制][F-] ##

--------------------

**题意：**  
多组输入，给出一个10进制数，求它的二进制表示方法

**题解：**  
直接用数组存即可，当然防止暴内存，可以用字符数组存

除k取余即可

--------------------

## [G-圆柱的体积][G-] ##

--------------------

**题意：**  
多组输入  
每次输入圆柱体的底面半径和高

**题解：**  
就只要注意一下不需要四舍五入  
由于最后保留三位小数可以通过**先\*10000，得到数x，然后强制类型转化为int类型，接着对x%10，即：x=x-x%10；** 然后再/(10000\*1.0)即可

(当然其他操作也可以解决）

--------------------

## [H-数素数][H-] ##

--------------------

**题意：**  
给出m，n；求第m个素数到第n个素数  
其中每10个素数为一行（行末不能有空格）

**题解：**  
1、可以用素数筛提前打表，素数筛的话可以使用暴力打表；  
当然为了显得高级点，可以用数论中的**埃氏筛O(nlogn)和欧拉筛O(n)**

可以参考这篇博客：  
[素数筛（埃氏筛+欧拉筛）][Link 1]

2、当然也可以直接暴力，因为数据比较弱，这样也是可以过的

--------------------

## [I-平方与立方][I-] ##

--------------------

**题意：**  
t组数据，每组数据给出n，表示x，y能取到的最大值；  
求满足x*x=y*y\*y的x的个数

**题解：**  
由于n<=1000  
于是可以直接用两重循环即可，一层对x，一层对y

--------------------

## [J-5x+y][J-5x_y] ##

--------------------

**题意：**  
t组数据，每组数据给出n，求在(0,n\]中，满足5\*x+y=n的二元组个数

**题解：**  
同样直接两重循环即可

[A-_2020]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1068&pid=0
[B-XP]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1068&pid=1
[C-XP]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1068&pid=2
[D-_XP]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1068&pid=3
[E-Yftc]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1068&pid=4
[F-]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1068&pid=5
[G-]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1068&pid=6
[H-]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1068&pid=7
[Link 1]: https://blog.csdn.net/boliu147258/article/details/93141173
[I-]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1068&pid=8
[J-5x_y]: http://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1068&pid=9