mfunction96 / hs2znoip Goto Github PK

中文题面，很简单，签到题。
转换成绩为等级，不满足要求做特殊输出。
难点在多组输入，多组输入要用以下结构

int n;
while (scanf("%d", &n) == 1)
{
	...
}

利用scanf函数返回值判断输入终止条件。scanf函数返回正确输入变量的个数，当输入无效时返回EOF。
与之同理，cin同样具有返回值可以作为输入终止的判断条件，常用以下结构：

int n;
while (cin >> n)
{
	...
}

这样的话，题迎刃而解。

Accepted代码

本题为阅读题，读懂后即可明白使用贪心法，比较简单。

贪心策略：

• 尽可能所有数变成正数
• 如果不能所有数变正数，尽可能让绝对值大的数变成正数。

注意：

• 题干中描述同一个数可以变许多次，没有次数限制
• 一定会做k次操作，不能多不能少

因此，只需要根据负数个数与操作数的关系，分情况计算即可Accepted。

Accepted代码

中文题面，同样比较简单，属于签到题。
多组输入，与A题相同，多组输入不再重复讲解。
不过本题需要考虑清楚所有情况，最好的办法是设置缓存存储数据，再立一个flag标记缓存中是否存在数据。
遍历字符串时，若flag标记缓存中有数据且读取到了5关键字，那么存储数据并清除缓存，否则继续读。
此外，注意最后的数据不要忘记存储，不然会WA。
Accepted代码

题意简单来说：

• Emma要选择最大的数
• Jack要选择最小的数
• Emma选一行
• Jack选一列
• Emma先选Jack后选

此题还有提示，针对输入

4 1 3 5
2 2 2 2
5 4 5 1

如果Emma选择第一行和第三行，Jack一定要选择1，因此选择第二行能达到Emma选择的最大值

根据提示思考片刻。
于是乎，题意变为了

选择每一行最小的，然后在最小的中选择最大

这样一来，题变得非常简单了。

Accepted代码

这题没什么好讲的。。。。
英语阅读题，读懂了就会写，模拟题中的过程就可以Accepted。
注意： 用到了植树问题的起点终点的判断，注意不要多算。

Accepted代码

读题便知本题为最短路模板题。
套最短路模板即可Accepted。

不过，由于朴素最短路算法，如朴素Dijkstra算法时间复杂度为O(n^2)，时间复杂度较高并且存在优化空间。
根据Dijkstra算法过程，可以使用堆优化最小点权点的选择，因此采用优先队列（优先队列采用堆的数据结构）优化Dijkstra算法，时间复杂度期望从O(n^2)降低到O(nlogn)。

Accepted代码