PDF《NOIP 模拟赛试题讨论》

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . NOIP 模拟赛试题讨论 wzj52501

2018 年10 月27 日wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Results wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . defile 得分统计 wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . random 随机输出 Yes 或 No . wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . random 随机输出 Yes 或 No . 哦,你得了满分(逃wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100pts 枚举每个友方随从攻击了哪一个敌方随从,然后检验即可. wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100pts 枚举每个友方随从攻击了哪一个敌方随从,然后检验即可. 实现时需要注意很多细节,如随从可以不攻击、攻击力为

0 的随 从无法攻击等. wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100pts 枚举每个友方随从攻击了哪一个敌方随从,然后检验即可. 实现时需要注意很多细节,如随从可以不攻击、攻击力为

0 的随 从无法攻击等. 时间复杂度为 O(nm * mn ). wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . treasure 得分统计 wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20pts BFS 判断起点到唯一宝藏点距离是否相等即可. wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20pts BFS 判断起点到唯一宝藏点距离是否相等即可. 时间复杂度为 O(n * m). wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40 - 60pts 每次我们肯定是从某个宝藏点或起点出发,沿最短路径到达另一 个宝藏点. wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40 - 60pts 每次我们肯定是从某个宝藏点或起点出发,沿最短路径到达另一 个宝藏点. 我们可以全排列枚举访问顺序,依次判断最多访问到哪一处宝藏. wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40 - 60pts 每次我们肯定是从某个宝藏点或起点出发,沿最短路径到达另一 个宝藏点. 我们可以全排列枚举访问顺序,依次判断最多访问到哪一处宝藏. 预处理每个宝藏间的最短距离和每个宝藏到起点的最短距离,时 间复杂度为 O(k * m * n + (k + 1)!). wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100pts 我们可以在上面算法的基础上进一步改进,为了方便把起点作为

0 号宝藏点.设f(i, S) 表示当前在 i 号宝藏点,且已经到达过 S 集 合内的宝藏点的最短时间. wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100pts 我们可以在上面算法的基础上进一步改进,为了方便把起点作为

0 号宝藏点.设f(i, S) 表示当前在 i 号宝藏点,且已经到达过 S 集 合内的宝藏点的最短时间. 转移时枚举下一次去哪个宝藏点,f(i, S) + dist(i, j) → f(j, S ∪ {j}). wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100pts 我们可以在上面算法的基础上进一步改进,为了方便把起点作为

0 号宝藏点.设f(i, S) 表示当前在 i 号宝藏点,且已经到达过 S 集 合内的宝藏点的最短时间. 转移时枚举下一次去哪个宝藏点,f(i, S) + dist(i, j) → f(j, S ∪ {j}). 初始只有 f(0, {0}) 为0,其余均设为无穷大,最后在所有 f(j, S) ≤ T 的S中选出 |S| 最大的集合即为答案. wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100pts 我们可以在上面算法的基础上进一步改进,为了方便把起点作为

0 号宝藏点.设f(i, S) 表示当前在 i 号宝藏点,且已经到达过 S 集 合内的宝藏点的最短时间. 转移时枚举下一次去哪个宝藏点,f(i, S) + dist(i, j) → f(j, S ∪ {j}). 初始只有 f(0, {0}) 为0,其余均设为无穷大,最后在所有 f(j, S) ≤ T 的S中选出 |S| 最大的集合即为答案. 时间复杂度为 O(k * m * n + k2 * 2k ). wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . instrument 得分统计 wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20pts 不说了. . . wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60pts 对于这一部分数据,n ≤ 2501. wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60pts 对于这一部分数据,n ≤ 2501. 设fi 表示前 i 个音符已经划分完毕,已经划分过的最短乐章最长 是多少,易得 fi = max {min(fj, i ? j)},其中 [j + 1, i] 区间没有相 同的音符. wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60pts 对于这一部分数据,n ≤ 2501. 设fi 表示前 i 个音符已经划分完毕,已经划分过的最短乐章最长 是多少,易得 fi = max {min(fj, i ? j)},其中 [j + 1, i] 区间没有相 同的音符. 计算方案的话可以设 gi 表示前 i 个音符已经划分完毕,已经划分 过的乐章长度均 ≥ fn,可得 gi = ∑i?fn j=0 gj,其中 [j + 1, i] 区间没有 相同的音符. wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60pts 对于这一部分数据,n ≤ 2501. 设fi 表示前 i 个音符已经划分完毕,已经划分过的最短乐章最长 是多少,易得 fi = max {min(fj, i ? j)},其中 [j + 1, i] 区间没有相 同的音符. 计算方案的话可以设 gi 表示前 i 个音符已经划分完毕,已经划分 过的乐章长度均 ≥ fn,可得 gi = ∑i?fn j=0 gj,其中 [j + 1, i] 区间没有 相同的音符. 答案即为 fn 和gn,时间复杂度为 O(n2 ). wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100pts 我们先对于每个右端点 r,求出极小左端点 leftr 满足 [leftr, r] 区间 没有相同的音符. wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100pts 我们先对于每个右端点 r,求出极小左端点 leftr 满足 [leftr, r] 区间 没有相同的音符. 可以递推求出 leftr = max(leftr?1, lastpos(Ar)). wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100pts 我们先对于每个右端点 r,求出极小左端点 leftr 满足 [leftr, r] 区间 没有相同的音符. 可以递推求出 leftr = max(leftr?1, lastpos(Ar)). 所以我们可以利用前缀和在 O(n) 的时间内计算出 g 数组,那么 瓶颈就在于求 fn. wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100pts 我们先对于每个右端点 r,求出极小左端点 leftr 满足 [leftr, r] 区间 没有相同的音符. 可以递推求出 leftr = max(leftr?1, lastpos(Ar)). 所以我们可以利用前缀和在 O(n) 的时间内计算出 g 数组,那么 瓶颈就在于求 fn. 考虑二分答案,如何判断是否存在一个方案使得每段乐章长度均 ≥ x 呢? wzj52501 NOIP 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100pts 我们先对于每个右端点 r,求出极小左端点 leftr 满足 [leftr, r] 区间 没有相同的音符. 可以递推求出 leftr = max(leftr?1, lastpos(Ar)). 所以我们可以利用前缀和在 O(n) ........