2020.9.27 63 级考试题解
- 写在前面
- 原则？
- 优点？
- 缺陷？
- T1 sanae
- 定位
- 60pts
- 100pts
- 代码
- T2 telephone
- 定位
- 暴力
- 100pts
- 代码
- T3 bus
- 定位
- 30pts
- 50pts
- 70pts
- 100pts
- 100pts 的一种更优解法
- 代码
- 附加题 lunch
- 定位
- 100pts
- 代码
- 写在最后
写在前面
原则？
题目选择的原则？
一道签到题，一道课上例题，一道简单 DP。
去年同期做过，或者以去年同期的实力能够刚出来。
难度在 普及- 到 提高- 之间。
对于 DP，只是简单的线性 DP，不涉及其他 DP 类型。
不是太毒瘤，是给人做的题。
优点？
认为这几个题有哪些优点？
T1 东方题面好评。
T2 和上课的例题「通向奥格瑞玛的道路」思路相似好评。
T3 优秀区分度好评。
T4 小清新，有适合提高组选手的思维难度好评。
缺陷？
认为这几个题有什么缺陷？
T2 部分分的分布不怎么合理= =
本来 DP 部分想用午餐的，虽然对我来说挺有趣的，但是可能不大适合你们= =
就换用了摆渡车这道虽然比较普及但是很好的题。
T1 sanae
Link：P1724 东风谷早苗
定位
签到题，难度在普及 T2 左右。
60pts
直接暴力模拟。
复杂度 \(O(T)\)。
100pts
发现命令串长度远小于时间，说明存在很多循环节。
预处理循环部分对坐标的影响，再加上剩余部分对坐标的影响。
设命令串长度为 \(l\)，复杂度 \(O(l)\)。
代码
100pts
//知识点：模拟
/*
By:Luckyblock
签到题
*/
#include
#include
#include
#include
#define ll long long
const int kMaxn = 5010;
//=============================================================
char s[kMaxn];
int lth, T, ansx, ansy;
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void SolveRepeat(int times_) {
for (int i = 0; i < lth; ++ i) {
if (s[i] == 'E') ansx ++;
if (s[i] == 'S') ansy --;
if (s[i] == 'W') ansx --;
if (s[i] == 'N') ansy ++;
}
ansx *= times_, ansy *= times_;
}
void SolveRemain(int remain_) {
for (int i = 0; i < remain_; ++ i) {
if (s[i] == 'E') ansx ++;
if (s[i] == 'S') ansy --;
if (s[i] == 'W') ansx --;
if (s[i] == 'N') ansy ++;
}
}
//=============================================================
int main() {
scanf("%s", s);
lth = strlen(s);
T = read();
SolveRepeat(T / lth);
SolveRemain(T % lth);
printf("%d %d", ansx, ansy);
return 0;
}
T2 telephone
Link：P1948 [USACO08JAN]Telephone Lines S
定位
套路题，上课的时候没有睡觉就能做出来。
难度在普及 T3 以上，提高组 D1T2 以下。
暴力
dfs 枚举起点为 \(1\)，终点为 \(n\) 的所有路径。
对于一条确定的路径，枚举路径上所有边，将它们排序后找到第 \(k + 1\) 大值，即为该路径的花费。
复杂度 \(O(\text{玄学})\)，大概可以过 4 个点。
这暴力比正解还要难写。
100pts
答案为 最小 的 路径上的 最大 的边权值，显然满足单调性。
二分答案枚举 最长的边权值 \(mid\)。
问题转化为：仅经过不超过 \(k\) 条权值 \(>mid\) 的边，能否找到一条从 \(1\) 到 \(n\) 的路径。
考虑 Check 函数要怎么写。
对于一条 \(1\rightarrow n\) 的路径，上面权值 \(>mid\) 的边越少，就越有可能满足要求。
则 Check 时，应找到权值 \(>mid\) 的边最少的， \(1\rightarrow n\) 的路径。
若该路径上权值 \(>mid\) 的边数仍然 \(>k\)，则枚举的 \(mid\) 不合法。
考虑怎么求得权值 \(>mid\) 的边最少的， \(1\rightarrow n\) 的路径。
要求路径上这样的边最少，想到用最短路。
考虑建一张新图：
将 \(>mid\) 的边的权值变为 \(1\)，表明经过这条边需要 \(1\) 的代价。
将其他边的权值其他变为 \(0\)，表明经过它不需要代价。
转化后，求得 \(1\rightarrow n\) 新图中的最短路，即为上面想要的 \(1\rightarrow n\) 路径上 \(>mid\) 的边的最少数量。
使用堆优化 Dijkstra，单次 Check 复杂度为 \(O((n+p)\log (n+p))\)。
总复杂度为 \(O((n+p)\log (n+p)\log w_i)\)，稳过。
大概不用堆优化也可以过。
代码
100pts
//知识点：二分答案，最短路
/*
By:Luckyblock
用脚做题
*/
#include
#include
#include
#include
#include
#define ll long long
#define pr std::pair
#define mp std::make_pair
const int kMaxn = 1010;
const int kMaxm = 5e4 + 10;
const int kInf = 1e6 + 2077;
//=============================================================
int n, p, k, ans;
int e_num, head[kMaxn], v[kMaxm], w[kMaxm], ne[kMaxm];
int dis[kMaxn];
bool vis[kMaxn];
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void AddEdge(int u_, int v_, int w_) {
v[++ e_num] = v_, w[e_num] = w_;
ne[e_num] = head[u_], head[u_] = e_num;
}
void Dijkstra(int s_, int lim_) {
std :: priority_queue > q;
memset(vis, false, sizeof (vis));
memset(dis, 63, sizeof (dis));
dis[s_] = 0;
q.push(mp(0, s_));
while (! q.empty()) {
int u_ = q.top().second;
q.pop();
if (vis[u_]) continue;
vis[u_] = true;
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i], w_ = (w[i] > lim_);
if (dis[v_] > dis[u_] + w_) {
dis[v_] = dis[u_] + w_;
q.push(mp(- dis[v_], v_));
}
}
}
}
bool Check(int lim_) {
Dijkstra(1, lim_);
return dis[n] <= k;
}
//=============================================================
int main() {
freopen("telephone.in", "r", stdin);
freopen("telephone.out", "w", stdout);
n = read(), p = read(), k = read();
for (int i = 1; i <= p; ++ i) {
int u_ = read(), v_ = read(), w_ = read();
AddEdge(u_, v_, w_), AddEdge(v_, u_, w_);
}
ans = - 1;
for (int l = 0, r = kInf; l <= r; ) {
int mid = (l + r) >> 1;
if (Check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
printf("%d\n", ans);
return 0;
}
T3 bus
Link：P5017 摆渡车
定位
简单 DP，区分度好题。
各部分分依次对应普及，提高-，提高水平的选手。
这题是普及 T3，正解难度在提高 D1T2 左右。
30pts
设 \(f_i\) 在 \(i\) 时间发车，发车时等待的时间和的最小值。则显然有：
\[f_i = \min_{j\le i-m}(f_j + \sum_{j < t_k \le i}^{n}{(i-t_k)}) \]对于每个 \(f_i\)，当在 \(i\) 时刻时发第一班车，\(f_i\)最大，则其初始值为：
\[f_i = \sum_{t_k为保证载上所有人，最后一班车需在 \([t_{max}, t_{max}+m)\)内发车，则：
\[ans = \min_{i=t_{max}}^{t_{max}+m}(f_i) \]复杂度 \(O(nt^2)\)，期望得分 \(30\text{pts}\)。
50pts
前缀和优化。
设 ：
\[cnt_i=\sum\limits_{t_k\le i} 1,\ pos_i = \sum\limits_{t_k\le i}{t_k} \]对于上式中的 \(\sum\limits_{j < t_k \le i}{i-t_k}\)，有：
\[\sum\limits_{j < t_k \le i}{i-t_k} = (cnt_i-cnt_j)\times i - (pos_i-pos_j)\]替换状态转移方程。
复杂度 \(O(t^2)\)，期望得分 \(50\text{pts}\)。
70pts
优化转移方程。
对于状态转移方程：
\[f_i = \min_{j\le i-m}(f_j + (cnt_i-cnt_j)\times i - (pos_i-pos_j)) \]显然，若 \(j\le i-2m\)，则在 \(j+m\) 时刻可多发一班车，不影响在 \(i\) 时刻发车，且答案不会变劣。
即：停车时间 \(i- (j+m) < m\)。
故转移方程可替换为：
\[f_i = \min_{i-2m\le j\le i-m}(f_j + (cnt_i-cnt_j)\times i - (pos_i-pos_j)) \]复杂度 \(O(mt)\)，期望得分 \(70\text{pts}\)。
100pts
减去无用状态。
若 \(cnt_i=cnt_{i-m}\)，说明时间段 \([i-m,i]\)内没有需要坐车的人。
则在 \(i-m\) 时刻发车，在 \(i\) 时刻不发车，不会使答案变劣，\(f_i\) 是一个无用状态。
则可将状态转移方程改为：
\[f_i = \begin{cases}f_{i-m} &cnt_i=cnt_{i-m}\\ \min\limits_{i-2m\le j\le i-m}(f_j + (cnt_i-cnt_j)\times i - (pos_i-pos_j))& \text{otherwise}\end{cases} \]当满足 \(t_i = t_{i-1}+m\) 时，有用的位置最多，为 \(nm\) 个。
复杂度 \(O(nm^2 + t)\)，期望得分 \(100\text{pts}\)。
100pts 的一种更优解法
由 70pts解法，停车时间 \(i- (j+m) < m\)。
车往返一次时间 \(m\)，则人等车时间 \(< 2m\)。
设 \(f_{i,j}\) 表示第 \(i\) 个人，等待时间为 \(j\)，且前 \(i\) 个人已到达的时间最小值。
初始值 \(f_{1,i} = i\)。
分类讨论：
- 若 \(t_{i+1} \le t_{i+1} + j\)，则第 \(i+1\) 个人可和 第 \(i\) 个人坐同一辆车走。
第 \(i+1\) 个人的等待时间 \(k = t_i+j-t_{i+1}\)
状态转移方程式为：
- 否则，枚举第 \(i+1\) 个人的等待时间 \(k\)。\[k\in [\max(0, t_i + j + m - t_{i+1}), 2m) \]状态转移方程式同上，为：\[f_{i+1,k} = \min (f_{i+1}, k, f_{i,j} + k) \]
复杂度 \(O(nm^2)\)，期望得分 \(100\text{pts}\)。
代码
100pts
//知识点：DP
/*
By:Luckyblock
*/
#include
#include
#include
#include
#define ll long long
const int kMaxn = 4e6 + 2077;
//=============================================================
ll n, m, ans, maxt;
ll cnt[kMaxn], pos[kMaxn], f[kMaxn];
//=============================================================
inline ll read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
n = read(), m = read();
for (int i = 1; i <= n; ++ i) {
ll t = read();
maxt = std :: max(maxt, t);
cnt[t] ++, pos[t] += t;
}
for (int i = 1; i < maxt + m; ++ i) {
cnt[i] += cnt[i - 1];
pos[i] += pos[i - 1];
}
memset(f, 63, sizeof(f)); ans = f[0];
for (int i = 0; i < maxt + m; ++ i) {
if (i >= m && cnt[i - m] == cnt[i]) {
f[i] = f[i - m];
continue;
}
f[i] = cnt[i] * i - pos[i];
for (int j = std :: max(i - 2 * m, 0ll); j <= i - m; ++ j) {
f[i] = std :: min(f[i],
f[j] + (cnt[i] - cnt[j]) * i - (pos[i] - pos[j]));
}
}
for (int i = maxt; i < maxt + m; ++ i) {
ans = std :: min(ans, f[i]);
}
printf("%lld\n", ans);
return 0;
}
100pts 的一种更优解法
空间需求比较奇怪，总是RE，于是开了很大。
//知识点：DP
/*
By:Luckyblock
*/
#include
#include
#include
#include
#define ll long long
const int kMaxn = 5010;
//=============================================================
ll n, m, ans, t[kMaxn], f[kMaxn][kMaxn / 4];
//=============================================================
inline ll read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
n = read(), m = read();
for (int i = 1; i <= n; ++ i) t[i] = read();
std :: sort(t + 1, t + n + 1);
memset(f, 63, sizeof(f)); ans = f[0][0];
for (int i = 0; i <= 2 * m; ++ i) f[1][i] = i;
for (int i = 1; i <= n; ++ i) {
for (int j = 0; j < 2 * m; ++ j) {
if (t[i + 1] <= t[i] + j) {
int k = t[i] + j - t[i + 1];
f[i + 1][k] = std :: min(f[i + 1][k], f[i][j] + k);
} else {
for (int k = std :: max(0ll, t[i] + j + m - t[i + 1]); k < 2 * m; ++ k) {
f[i + 1][k] = std :: min(f[i + 1][k], f[i][j] + k);
}
}
}
}
for (int i = 0; i <= m; ++ i) ans = std :: min(ans, f[n][i]);
printf("%lld\n", ans);
return 0;
}
附加题 lunch
Link：P2577 [ZJOI2004]午餐
定位
小清新贪心排序 + DP。
虽然代码比较好写，但较前三道题略微增加了思维难度，不是那么套路，难度大概在提高 D2T1 ~ D2T2 左右。
个人认为比起 CSP2019 的 D2T2 划分来说要难一点？
划分的维护手段有点套路，只是高精比较烦人。
100pts
设第 \(i\) 个人打饭时间，吃饭时间分别为 \(a_i\) 与 \(b_i\)，前 \(i\) 个人打饭时间总和为 \(sum_i\)。
先考虑 只排一队 的情况，对于一给定的队列完成的时间，有：
\[time = \max_{i=1}^{n}\{sum_i+b_i\} \]考虑两个相邻的人 \(i\) 与 \(i+1\)，若有 \(b_{i+1} > b_i\)：
-
当 \(i+1\) 在后面时，两者完成时间分别为：
\[\begin{aligned} & sum_{i-1} + (a_i + b_i)\\ & sum_{i-1} + a_i + (a_{i+1}+b_{i+1}) \end{aligned}\]显然第 \(i+1\) 个人一定后吃完，即有下式成立：
\[sum_{i-1} + a_i +(a_{i+1}+b_{i+1})> sum_{i-1} + (a_i + b_i) \] -
当 \(i+1\) 在前面时，完成时间分别为：
\[\begin{aligned} & sum_{i-1}+ (a_{i+1} + b_{i+1})\\ & sum_{i-1} + a_{i+1}+ (a_i + b_i) \end{aligned}\]两人吃完的先后顺序不定。
显然有：
\[\begin{aligned} & sum_{i-1} + a_i +(a_{i+1}+b_{i+1})> \\ & \max\{sum_{i-1}+ (a_{i+1} + b_{i+1}), sum_{i-1} + a_{i+1}+ (a_i + b_i)\} \end{aligned}\]则欲使 \(\max\limits_{i=1}^{n}\{sum_i+b_i\}\) 尽可能小，令\(i+1\) 排在前面更优。
感性理解一下，吃饭慢的放在前面一定更优。
则可先将 \(n\) 个人按照吃饭时间降序排序，逐个加入队列的人变成有序的了。
可以考虑线性 DP 求解此题。
发现窗口二的队列，必定为窗口一的补集。
设当前第 \(i\) 个人加入队列，令窗口一队列 打饭时间总和为 \(j\)，则窗口二 打饭时间 总和为 \(sum_i - j\)。
若已知 \(j\)，则可计算第 \(i\) 个人加入窗口 一/二 的 完成时间。
考虑枚举窗口一打饭时间总和 \(j\)，来更新答案。
设 \(f_{i,j}\) 表示，前 \(i\) 个人加入队列，窗口一队列打饭时间总和为 \(j\)时，两窗口的最小完成时间。
考虑第 \(i\) 个人排到窗口 一/二：
- 排到窗口一，则有：\[f_{i,j} = \max\{j + b_i,\ f_{i-1,j-a_i}\}
\]\(j + b_i\) 为新加入窗口一的人的完成时间。
\(f_{i-1,j-a_i}\) 为：不加此人时，窗口一的完成时间 与 窗口二的完成时间 的最小值，用于更新答案，不会导致漏解。 - 排到窗口二，则有：\[f_{i,j} = \max\{f_{i-1,j},\ sum_i-j+b_i\}
\]\(sum_i-j+b_i\) 为新加入窗口二的人的完成时间。
\(f_{i-1,j}\) 也为不加此人时，窗口一的完成时间 与 窗口二的完成时间 的最小值。
上述两种情况取最小值即可。
复杂度 \(O(nT)\) (\(T\) 为最大时间)，期望得分 \(100\text{pts}\)。
代码
//知识点:DP
/*
By:Luckyblock
*/
#include
#include
#include
#include
#define min std::min
#define max std::max
#define ll long long
const int kMaxn = 210;
const int kInf = 1e9 + 2077;
//=============================================================
struct Data {
int a, b;
} d[kMaxn];
int n, ans = kInf, sum[kMaxn], f[kMaxn][kMaxn * kMaxn];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
bool Compare(Data fir, Data sec) {
return fir.b > sec.b;
}
//=============================================================
int main() {
n = read();
for (int i = 1; i <= n; ++ i) {
d[i].a = read(), d[i].b = read();
}
std :: sort(d + 1, d + n + 1, Compare);
memset(f, 63, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= n; ++ i) sum[i] = sum[i - 1] + d[i].a;
for (int i = 1; i <= n; ++ i) {
int a = d[i].a, b = d[i].b;
for (int j = 1; j <= sum[i]; ++ j) {
f[i][j] = max(f[i - 1][j], sum[i] - j + b);
if (j - a >= 0) f[i][j] = min(f[i][j], max(f[i - 1][j - a], j + b));
}
}
for (int i = 1; i <= sum[n]; ++ i) {
ans = min(ans, f[n][i]);
}
printf("%d\n", ans);
return 0;
}
写在最后
我个人是比较喜欢 DP 和数据结构的/se
感觉他们非常优美和好玩，有这方面问题可以多来叨扰我/se