CSUST 2021 周赛 2 题解
本文可以用 GitHub 登录评论，如果有写得不好的地方欢迎提出建议，也欢迎讨论。
本文所列 5 份代码皆通过测试，请不要复制提交测试。
文末有少量参考链接，可以学习一下：）
也可以到 CSDN 阅读
目录
A. 睿智小明买鞭炮
涉及的知识
-
二分查找
-
动态规划
-
勉强可以算作贪心
思路
为了方便叙述，我们先约定：一共有 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. 龙卷风摧毁停车场
涉及的知识
-
模拟
-
感觉懂一点算法分析可以少走很多弯路
思路
约定：出发城市为 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 的代码，感兴趣的可以到我的 gitee 仓库 看看错误代码。直到后来我注意到城市和航线数量不多于 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 传输
涉及的知识
-
最小生成树（Prim 算法或 Kruskal 算法）
-
并查集
-
超级源点
思路
因为最小生成树是很经典的算法，所以我就不多介绍了。这道题主要的难点就在于不仅要考虑边权（连接两个城市的花费），还要考虑点权（也就是建 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. 神奇的数字串
涉及的知识
-
前缀和
-
单调队列
思路
约定：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] 中对最小值有贡献的元素
// queMin.front 始终是 [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. 矩阵
涉及的知识
-
简单的数学推导
-
前缀和
-
线段树
思路
线段树学得不好，谁能帮我写一下……
代码
#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);
}
}