20231030sol

AisDaeun 28 2023-10-30

A - drone 题解

考察知识点

  • 简单数论
  • 观察

Subtask1 (20pts)

依据题意,暴力模拟即可。

时间复杂度 O(nMax(A_i))

Subtask2 (50pts)

在该数据范围下直接暴力不再可行。

我们考虑当只有两个数 a, b 的情况,容易观察出每次会将 (a, b) 变为 (a-b, b)

这种形式恰与求 gcd 的过程等价。

也就是每次操作并不会改变被操作数的 gcd

那么我们有 gcd(a_1, a_2, ..., a_n) = gcd(ans, ans, ..., ans) = ans

因此所求答案即为所有数的 gcd

Sol (100pts)

在多个维度情况下,容易观察到每个维度的操作是独立的。

因此只需要对每个维度套用 Subtask 2 的做法即可通过此题。

时间复杂度 O(n + log(max(A_i)))

总结

本题考查了简单数论如最大公约数的相关知识,对于 NOIP 级别的选手需要培养一些观察力。

期望均分:AC

B - charge 题解

考察内容

  • 图论
  • Dijkstra
  • 实数基础

Subtask1(20-30pts)

暴力枚举航线顺序;根据剪枝或乱搞能力优劣得分不等。

Subtask2(40pts)

a=b=c=0 时,原问题等价于一个简单的最短路。

直接使用 Dijkstra 即可。

Sol(100pts)

由于 N 较小,我们可以先计算出全部 N^2 个距离后转化为纯图论问题。

对于每次行走所需要耗费的时间为
a+b+c*T+d*dis(i,j)

其中充电时间 T
dis(i,j) + 前往最近充电桩所需要时间

我们分两种情况考虑:

  • 1 号充电桩出发所需要的时间为
    dis(1,j)+j点前往最近充电桩的时间

  • 从除 1 号以外充电桩 i 出发所需要的时间为
    dis(i,j)+j点前往最近充电桩的时间-i点前往最近充电桩的时间

对于每次行走计算过程中的峰值电量判断是否合法,找到所有路径后跑 Dijskra 即可。

总结

本题考察了简单图论问题的转化,同时需要掌握 NOIP 的热点算法单源最短路。

期望均分:60-100

C - average 题解

考察内容

  • dp
  • 复杂度优化
  • 猜结论
  • 单调栈

Subtask1(20pts)

对于每一块积木,我们记录它左侧积木的高度并枚举它的高度,使用 dp[n][h] 记录最优解并转移。

时间复杂度 O(n^2h).

Subtask2(40-60pts)

dp 中包含高度显然会使复杂度无法接受。

我们考虑最后操作的每个发生改动的连续段 [L, R]。这时L-1, R+1 两块积木没有发生过改动;可以得到一个重要结论:

[L, R] 中所有积木一定为相同高度

一个简单的证明:如果他们未被调整到同一高度,那么在操作其中最高的积木时少加一块,一定会使答案更优。

考虑我们目前走到第 i 块积木,枚举 j 使得 [j+1, i-1] 是一个发生改动的连续段,并且这一段的所有积木会被加高到 H 的花费。

dp[i]=min(dp[j]+\sum^{i-1}_{k=j+1}(H-h[k])^2+(h[i]+h[j]-2*H)*c)

后面关于 H 的式子是一个关于 H 的二次函数,可以很容易地 O(1) 求出最小值,之后暴力转移即可。

时间复杂度 O(n^2),依据实现可能获得 40~60pts 不等。

Sol(100pts)

考虑如何优化之前的 dp

于是考虑怎么优化枚举,不难发现只有当 max_{k=j+1}^{i-1} h[k] \leq min(h[i],h[j]) 时,转移才有可能更优。

由于比每一个点高的点只会转移一次,我们可以直接使用单调栈完成该操作。

只需维护一个单调递减的栈,每一次在栈中转移更矮的点,同时将元素一个一个弹出,直到转移到比它高的为止。

时间复杂度 O(n)

总结

本题考察了 NOIP 中常出现的一类 dp 状态设计:通过分析题目结论来优化掉式子中较坏的一维;同时最后一步使用了经典的单调栈优化。

期望均分:60-100

D - bank 题解

考察知识点

  • 线段树
  • 并查集
  • 矩阵基础
  • 图论

Subtask1(30pts)

暴力更新格点信息,询问直接DFS/BFS。

复杂度 O(NMT)

Subtask2(50pts)

使用线段树进行区间赋1操作。

询问等价于询问区间是否全为1,直接求和即可。

复杂度 O(TlogM)

Subtask3(70pts)

考虑每次修改只有一列,用线段树维护矩阵来维护连通性。

矩阵存储相邻两列的9种转移。

复杂度 27O(TlogM)

Sol(100pts)

考虑并查集维护答案。

第一种并查集维护图的连通性,第二种并查集每行维护一个,用来缩点,避免走重复的路。

考虑相邻两行并查集的合并,一定是某行的某个连通块走到尽头时和另一行合并。

总结

本题考察了线段树在具体问题上的应用;部分分设置上给了暴力一档以及简单区间赋值一档较高分数,希望能培养大家的写暴力能力。

期望均分:30-70?