本场是比赛有部分题面不够完善，在赛时频繁的更新，可能对大家赛事体验有影响，希望大家谅解，出题组比较菜QWQ。
难度预期分类：
签到：AB
简单：CFGJ
中等：DHL
难：EIK
全部标程请见本文最下方。
A - 恭喜小梁成为了宝可梦训练家~
题意
求n个数字的最大，最小和平均数值
题解
签到题，无特殊解法，循环扫描一次，维护最大值、最小值和平均值即可，注意保留小数。
时间复杂度
B - 皮(A)卡(C)皮(M)~
题意
字符串模拟题，题意大致就是在一串字符串中寻找是否存在A、C、M这三个字母，假如均存在输出-1，假如有缺少则输出缺少的那个（题目已经说了至多缺少一个）。
题解
创建三个变量，分别代表A、C、M是否存在，初始为0，输入字符串后遍历字符串，发现一个ACM中的一个字符则对应的变量加1，遍历完成后检查这三个变量是否有为0的，假如有0则输出对应的字母。
常见错误：
缺少ACM全齐时输出
-1的判断字母没有大写
输出未换行
时间复杂度
C - 杰尼杰尼
题意
给n条直线的方程，问共可以组成多少个不同的交点。
题解
已知两条直线方程，
则交点为
可以知道，交点最多只有5000个，对于重复交点的处理，本题数据不考虑精度问题，可以选择使用set记录坐标。注意两条直线平行的情况。
时间复杂度
D - 古代遗迹：字符王国
题意
S中有多少个子串，可以由T重排列后，最多改变一个字母组成。
题解
滑动窗口。首先维护字符串中的字母个数
，然后建立一个参考值
，其表示S的子串和T有多少个不同的字母。再次遍历字符串
，利用滑动窗口的思想，维护S的字符数量，即加减
的个数，如果
则表示子串符合要求。
时间复杂度
，
和
表示字符串
和
的长度。
E - 皮卡丘这么可爱，当然要.....
题意
在题目中我们可以知道开始时间，结束时间，有n个皮卡丘，每个皮卡丘都有观看需要的时间，观看可获得的可爱度，一定的观赏次数，要求出在这个时间段内能获得的最大可爱度
题解
题目中把n个皮卡丘理解为n种物品，需要的时间理解为体积，获得的可爱度理解为价值，在加上有限定次数，可以显而易见的看出这道题是一道多重背包，再看题面中的数据范围n为10000，n^3的多重背包写法必定会超时，这就要用到了二进制优化。
二进制优化基于数论的一个知识，任意的一个整数中的任意的一个数，都可以由所有不大于这个整数的的
2^n的数组合而成，例如18=1+2+4+8+3, 18中的任意数都可以由1,2,4,8,3组合而成。
当p[i]=0时说明可以无限拿，可以直接转换成完全背包。
其中关于开始时间和结束时间转换成时间段大小有多种方法（这里列出两种，模拟或scanf的格式读入）
我们定义状态
dp[s]表示当时间段大小为s时，能获得的最大可爱度。状态转移方程为
时间复杂度
空间复杂度：
，N代表背包的容量（本题即结束时间-开始时间得到的时间段大小（分钟））
时间复杂度：
，M代表物品的种类（本题即皮卡丘的数量），
代表每种物品的数量（本题即皮卡丘的观赏次数），
代表背包的容量（本题即时间段大小）
F - Doctor Rabbit 的统计
题意
从8点开始计算，量体温需要2分钟，超过37℃的同学无法进入学校。大巴每10分钟一辆，男生寝室需要3分钟，女生寝室需要5分钟。问男生第一个到达寝室的时间和女生最后一个到达寝室的时间。
题解
理清楚题目约束条件，模拟即可。注意时间的输入和输出，需要两位数字。
本题数据不大，对复杂度无特殊要求，标程给出的方法。
时间复杂度
G - 遗迹逃亡
题意
的迷宫，
s起点，g终点，.道路，#落石，求是否可以走出离开迷宫。
题解
跑一次即可。
时间复杂度
H - 阿罗拉联盟赛
题解
首先先存入宝可梦的所有属性，A与B的精灵分别进行排序。
由于A是每次排出综合力最大的精灵，所以按照从大到小排序，B是每次排出综合力最小的精灵，所以按照从小到大排序。
之后根据替换数组分别进行宝可梦对战，记录下数据，最后输出。
注意理解题意。
时间复杂度
I - 雪拉比的求救
题意
给一个 个节点，
条边的无向图，和两个点
和
。询问两个人分别
和
出发，速度都相同，求走最短路不相遇的方案数，并对1e9+7取余。
题解
相遇的情况，可以分为在点相遇，或者在边上相遇，对其分类讨论。
首先用Dijkstra算法，记录到
的最短路径长度为
，路径数量为
。根据乘法原理，全部的方案数量为
。
然后再次跑最短路，记录从 出发走到点
的路程为
，方案为
，记录从
出发走到点
的路程为
，方案为
。
如果考虑在点相遇的情况，当且仅当
时候相遇，其方案数量为
。
如果考虑在边相遇的情况，当且仅当
时候相遇，其方案数量为
。
所以最后的方案数为：，注意取模的情况。
时间复杂度
J - 小梁的背包
题意
给你所有精灵的战斗值和体积
以及背包大小
，求背包能装的最大精灵总战斗值和对应的精灵数量。
题解
该题是个基本裸的01背包，我们可以设置一个dp数组来记录对应背包大小的可容纳的最大精灵总战斗值，用num数组来记录对应背包大小的可容纳的最大精灵数量。遍历精灵的数量，并遍历背包的体积即可。
时间复杂度
K - 训练师的变强秘诀：时间管理
题意
在题目中给了我们个游戏（即
个时间段），每个游戏都要玩一半以上的时间，问是否能玩完所有的游戏。
题解
贪心。先算出每个游戏的最早结束时间，按照最早结束时间升序排序，如果相同则按照开始时间升序排序
因为要连续且完成一半以上，所以先做比较早结束的游戏是较容易想到的，如果结束时间相同，那么先做早开始的游戏也是易想的，然后我们遍历一遍，如果当前的最早结束时间大于了下一个游戏的结束时间-它要玩的时间，退出掉（因为下一个游戏已经不能完成了），如果当前的最早结束时间大于下一个游戏的开始时间且剩下的时间能完成游戏那么更新下个游戏的最早结束时间，如果小于则不变。
时间复杂度
空间复杂度：
时间复杂度：
std
A: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44063168
B: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44063175
C: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44063248
D: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44063250
E: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44039431
F: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44063488
G: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44049847
H: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44063499
I: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44063202
J: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44063505
K: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44039500
L: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44035427
全部评论
(3) 回帖