本文共 7731 字，大约阅读时间需要 25 分钟。

周赛补题链接：

README

欢迎到我的个人博客查看本文：

本文所列 5 份代码皆通过测试，请不要复制提交测试。

文末有少量参考链接，可以学习一下：）

A、睿智小明买鞭炮

涉及的知识

1. 二分查找
2. 动态规划
3. 勉强可以算作贪心

思路

为了方便叙述，我们先约定：一共有 n 个规则，对于第 i 个规则 rules[i]，rules[i][0] 表示该规则最少购买的鞭炮数，rules[i][1] 表示该规则每盒鞭炮的价格。

假设查询的鞭炮数是 num，满足最少花费所购买的鞭炮数不一定就是 num，因为可能买得越多老板打折越狠，所以就得分情况讨论。

我们先找到可以满足购买数最少的 rules[i]， 因为数组有序，所以可以用二分查找，用 ans 记录下 num * rules[i][1]；打折更狠的规则只可能在 i 之后，所以我们只要找到 i 后面的最小规则花费，这一步查询可以用 dp[i] 记录区间 [i, n] 的规则花费最小值，数组 dp 可以很容易地用递推式 dp[i] = min(dp[i + 1], rules[i][0] * rules[i][1]) 得到。最后的答案就是 min(ans, dp[i + 1])。

代码

#include <iostream>#include <vector>using namespace std;using ll = long long;int find(vector<vector<ll>> &rules, ll num) {     int l = 0, r = rules.size();  while (l < r) {       int mid = l + (r - l) / 2;    if (rules[mid][0] > num) {         r = mid;    } else {         l = mid + 1;    }  }  return l - 1;}int main() {     ll n, q;  scanf("%lld%lld", &n, &q);  // 使用一个二维数组记录规则，因为题目给出的规则已经有序，所以不需要排序  vector<vector<ll>> rules;  for (ll i = 0; i < n; ++i) {       ll s, p;    scanf("%lld%lld", &s, &p);    rules.push_back({   s, p});  }  // dp[i] 表示 rules[i] 到 rules[n] 中最小的规则花费  vector<ll> dp(n + 1);  dp[n] = INT64_MAX;  // 将边界值设置为 long long 的最大值，可以减少边界判断  for (int i = n - 1; i >= 0; --i) {       dp[i] = min(dp[i + 1], rules[i][0] * rules[i][1]);  // 因为最小值具有传递性，所以可以用动态规划来做  }  // 处理每次查询  while (q--) {       ll num;    scanf("%lld", &num);    int id = find(rules, num);  // 二分查找到不少于鞭炮数量 num 的规则的下标 id，查找函数定义在 main 函数上面    ll ans = rules[id][1] * num;    ans = min(ans, dp[id + 1]);    printf("%lld\n", ans);  }}

B、龙卷风摧毁停车场

涉及的知识

1. 模拟
2. 感觉懂一点算法分析可以少走很多弯路

思路

约定：出发城市为 s，目标城市是 t。

这道题其实只要模拟就行，先模拟直达得到一个答案，再模拟换乘得到第二个答案，再输出较小的那个，唯一需要注意的地方就是可能会有无法到达的情况。

我的做法是先定义一个类 Air 表示航线，记录下沿途的城市 cities 和费用 fee，以及其中 s 和 t 的下标 sId 和 tId，记录下标可以简化后面的操作，不用每次都去遍历查询。第一种直达的情况再记录航线的时候就可以得到答案，只要 sId ！= -1 && tId ！= -1 && sId < tId 就说明可以直达；第二种情况就需要遍历所有的航线，选出其中的两条，再判断是否可以从 s 登上航线 air1，再换乘 air2 到达 t，可以转化为判断 air1.cities[sId + 1, ...] 和 air2.cities[..., tId - 1] 中是否有相同的城市，判断是否有重复元素可以用 set 实现。

为什么说懂一点算法分析可以少走弯路呢？因为我一开始想用图算法来写，但不是 TLE 就是 MLE，还写出了 TLE 加上 MLE 的代码，感兴趣的可以到我的 看看错误代码。直到后来我注意到城市和航线数量不多于 500 的条件，我才意识到这么小的数据量就算模拟写出三层循环都不会超时，而图算法动不动就是指数级别的复杂度，所以还是老老实实模拟吧。

代码

#include <iostream>#include <set>#include <vector>using namespace std;int ans = INT32_MAX;  // 偷懒用 int 最大值表示到达不了的情况，幸好没有花费到达最大值的测试数据class Air {    public:  vector<int> cities;  int sId = -1, tId = -1; // 用于记录经过城市中目标城市的下标  int fee;  Air(int s, int t) {    // 通过输入初始化航线    int cityCnt;    scanf("%d%d", &fee, &cityCnt);    int city;    for (int j = 0; j < cityCnt; ++j) {         scanf("%d", &city);      if (city == s) {           sId = j;      } else if (city == t) {           tId = j;      }      cities.push_back(city);    }    // 如果该航线会从 s 到 t 就更新 ans    if (sId != -1 && tId != -1 && sId < tId) {         ans = min(ans, fee);    }  }};int main() {     int s, t, n;  scanf("%d%d%d", &s, &t, &n);  vector<Air> airs;  for (int i = 0; i < n; ++i) {       airs.push_back(Air(s, t));  }  for (int i = 0; i < n; ++i) {       for (int j = 0; j < n; ++j) {         if (i == j) {           continue;      }      if (airs[i].sId == -1 || airs[j].tId == -1) {           continue;      }      set<int> st;  // 用于记录第一条航线的沿途城市      for (int k = airs[i].sId + 1; k < airs[i].cities.size(); ++k) {           st.insert(airs[i].cities[k]);      }      for (int k = 0; k < airs[j].tId; ++k) {           if (st.count(airs[j].cities[k])) {     // 如果第二条航线的沿途城市和第一条有重合那么就可以换乘          ans = min(ans, airs[i].fee + airs[j].fee);          break;        }      }    }  }  if (ans != INT32_MAX) // 偷懒成功    printf("%d\n", ans);  else    printf("-1\n");}

C、5G 传输

涉及的知识

1. 最小生成树（Prim 算法或 Kruskal 算法）
2. 并查集
3. 超级源点

思路

因为最小生成树是很经典的算法，所以我就不多介绍了。这道题主要的难点就在于不仅要考虑边权（连接两个城市的花费），还要考虑点权（也就是建 5G 信号塔的花费），但只要想到加入超级源点就可以转化成简单的求最小生成树了，具体见代码。

我用的是 Kruskal 算法，因为不会 Prim 算法……

代码

#include <algorithm>#include <iostream>#include <vector>using namespace std;class UnionFind {    public:  int cnt;  vector<int> ids;  UnionFind(int n) {       cnt = n;    for (int i = 0; i < n; ++i) {         ids.push_back(i);    }  }  void un(int p, int q) {       int pId = find(p), qId = find(q);    if (pId != qId) {         ids[pId] = qId;      --cnt;    }  }  int find(int p) {       if (p != ids[p]) {         ids[p] = find(ids[p]);    }    return ids[p];  }  bool isConnected(int p, int q) {    return find(p) == find(q); }};int main() {     int n;  scanf("%d", &n);  vector<vector<int>> edges;  for (int i = 0; i < n; ++i) {       int cost;    scanf("%d", &cost);    edges.push_back({   cost, i, n});  // 将建信号塔的花费转化成各点到虚拟出来的超级源点的连接花费  }  for (int i = 0; i < n; ++i) {       for (int j = 0; j < n; ++j) {         int cost;      scanf("%d", &cost);      if (i < j) edges.push_back({   cost, i, j});    }  }  sort(edges.begin(), edges.end());  // 不能使用集合维护边，因为 Kruskal 算法是针对森林设计的  // 已经加入的点并不一定会彼此连通，它们可能处于不同的树中  UnionFind uf(n + 1);  //所以要用并查集  int ans = 0;  int i = 0;  while (uf.cnt > 1) {       if (!uf.isConnected(edges[i][1], edges[i][2])) {         ans += edges[i][0];      uf.un(edges[i][1], edges[i][2]);    }    ++i;  }  printf("%d\n", ans);}

D、神奇的数字串

涉及的知识

1. 前缀和
2. 单调队列

思路

约定：nums[i] 表示第 i 个数字，nums 初始大小为 n。

对于 nums[i] 移位 k 次后就位于 [(i + k) % n]，为了简化移位操作可以将数组复制一份添加到原数组后面，这样 [k, ..., k + n - 1] 就是移位 k 次后得到的数字串了。

如果直接暴力枚举，复杂度为 O(n^2)，注意到 1 <= n <= 1e6，很可能会超时，所以需要优化。

优化的方式是采用单调队列和前缀和，使用 index[i] 记录前 i 个元素的前缀和，对于区间 [l, r]，用 queMin.front() 记录 index[l, r] 中的最小值，具体实现请参考代码，这样时间复杂度就降到了 O(n)。

代码

#include <deque>#include <iostream>#include <vector>using namespace std;int main() {     int n;  scanf("%d", &n);  vector<int> nums;  for (int i = 0; i < n; ++i) {       int num;    scanf("%d", &num);    nums.push_back(num);  }  for (int i = 0; i < n; ++i) {       nums.push_back(nums[i]);  }  vector<int> index{   0};  for (int i = 0; i < 2 * n; ++i) {       index.push_back(index.back() + nums[i]);  }  // 存放 [l, r] 中的最小值  deque<int> queMin;  for (int i = 1; i <= n; ++i) {       // 单调队列需要和队尾比较，因为可能出现新元素不小于队首但小于队尾的情况，这时依然需要更新队列    while (queMin.size() && queMin.back() > index[i]) queMin.pop_back();    queMin.push_back(index[i]);  }  int l = 1, r = n;  int ans = 0;  while (l <= n) {       // 注意单调队列中存放的是整个扩展数组的前缀和    if (queMin.front() - index[l - 1] >= 0) ++ans;    if (index[l] == queMin.front()) queMin.pop_front();    ++l;    ++r;    while (queMin.size() && index[r] < queMin.back()) queMin.pop_back();    queMin.push_back(index[r]);  }  printf("%d\n", ans);}

E、矩阵

涉及的知识

1. 简单的数学推导
2. 前缀和
3. 线段树

思路

线段树学得不好，谁能帮我写一下……

代码

#include <iostream>#include <vector>using namespace std;using ll = long long;ll gcd(ll a, ll b) {     if (b == 0) return a;  return gcd(b, a % b);}vector<ll> as, bs;vector<ll> idx{   0};vector<ll> tree;void build(int l, int r, int p) {     if (l == r) {       tree[p] = bs[l];    return;  }  int m = (l + r) / 2;  build(l, m, p * 2);  build(m + 1, r, p * 2 + 1);  tree[p] = gcd(tree[p * 2], tree[p * 2 + 1]);}ll getGcd(int l, int r, int begin, int end, int p) {     if (l <= begin && end <= r) {       return tree[p];  }  int m = (begin + end) / 2;  if (l <= m && m < r) {       return gcd(getGcd(l, r, begin, m, p * 2),               getGcd(l, r, m + 1, end, p * 2 + 1));  }  if (l > m) {       return getGcd(l, r, m + 1, end, p * 2 + 1);  }  return getGcd(l, r, begin, m, p * 2);}int main() {     int n;  scanf("%d", &n);  for (int i = 0; i < n; ++i) {       ll num;    scanf("%lld", &num);    as.push_back(num);    idx.push_back(idx.back() + num);  }  for (int i = 0; i < n; ++i) {       ll num;    scanf("%lld", &num);    bs.push_back(num);  }  tree = vector<ll>(4 * n);  build(0, n - 1, 1);  int q;  scanf("%d", &q);  while (q--) {       int x1, y1, x2, y2;    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);    ll a = idx[x2] - idx[x1 - 1];    ll b = getGcd(y1 - 1, y2 - 1, 0, n - 1, 1);    printf("%lld\n", a * b);  }}

参考链接

转载地址：http://zmle.baihongyu.com/