2026“钉耙编程”中国大学生算法设计春季联赛 - 热身赛
1001 - 最大的公约数
题意
给定一个正整数 ，求两个正整数满足且时，的值。
题解
可以发现一定是的一个因子，直接暴力遍历即可，可以发现，是最大的两个约数，所以只需要找不是这两个数字的最大约数。
代码
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
const int N = 32005;
void solve() {
int n;
scanf("%d", & n);
int ans = 1;
for (int i = 1; i * i <= n; i++) {
if (n % i == 0) {
if (i >= 3) ans = max(ans, n / i);
if (n / i >= 3) ans = max(ans, i);
}
}
printf("%d\n", ans);
}
int main() {
int T;
scanf("%d", & T);
while (T--) solve();
return 0;
}1002 - 雪蜜冰城柠檬茶的神秘成分魔法
题意
个数字，范围在~之间，次操作，操作有三种类型，1.将序列中的集体变成，2.序列末尾插入一个数字，3.删除数列中值为的数字，求最终序列。
题解：
最开始想的是开个set，每个set[i]存储i所在的位置，如果你对set足够熟悉的话，你会知道两个set交换的时间复杂度是的（赛时从队友哪里知道的），即不依赖两个set的大小，只需要交换两个set的地址，clear的复杂度是的，即依赖于set的大小。
所以操作1只需要启发式地将小的集合合并到大的集合中，合并完以后再检查一下是否需要交换，需要的话直接换，然后把x所在的集合清空，操作2相当于直接在set中插入一个数字，操作3相当于直接删除掉一个set。
操作1和操作3,都需要删除操作比较耗时，但是据观察可以发现，全部数字的个数不会超过个，所以直接clear即可，操作1由于使用到了启发式方法，所以总的时间复杂度是，两个log一个是set插入操作带来的，一个是启发式操作带来的。
最终扫描全部的set，将所有数字按照位置排序后输出即可得到最终答案。
按照上面的思路完整坐下来会MLE，因为个set太占空间了，考虑优化，最终用到的数字不会超过个，可以使用map进行映射，因为映射空间是，所以不用STL中的map，直接开大小的mp数组就可以，同时用一个iv数组记录反映射数组用来记录被映射的数字原来表示的是那个数字，这样操作总规模是级别的，就不用扫描到所有个set了。
代码：
#include <bits/stdc++.h>
using namespace std;
inline int read() {
char ch = getchar();
int x = 0, f = 1;
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x * f;
}
set<int> s[300010];
int n, m, a[200010];
struct Query {
int op, x, y;
}q[300010];
int mp[10000001], iv[300010];
int main() {
int _ = read();
while (_--) {
n = read();
int idx = 0;
for (int i = 1; i <= n; i++) {
a[i] = read();
if (!mp[a[i]]) mp[a[i]] = ++idx, iv[idx] = a[i];
}
m = read();
for (int i = 1; i <= m; i++) {
q[i].op = read(), q[i].x = read();
if (!mp[q[i].x]) mp[q[i].x] = ++idx, iv[idx] = q[i].x;
if (q[i].op == 1) {
q[i].y = read();
if (!mp[q[i].y]) mp[q[i].y] = ++idx, iv[idx] = q[i].y;
}
}
for (int i = 1; i <= n; i++) {
s[mp[a[i]]].insert(i);
}
for (int i = 1; i <= m; i++) {
if (q[i].op == 1) {
if (q[i].x == q[i].y) continue;
int x = mp[q[i].x], y = mp[q[i].y];
if (s[x].size() > s[y].size()) {
for (auto & t: s[y]) s[x].insert(t);
s[y].swap(s[x]);
s[x].clear();
} else {
for (auto & t: s[x]) s[y].insert(t);
s[x].clear();
}
} else if (q[i].op == 2) s[mp[q[i].x]].insert(++n);
else s[mp[q[i].x]].clear();
}
vector < pair < int, int >> p;
for (int i = 1; i <= idx; i++) {
for (auto & t: s[i]) p.emplace_back(t, iv[i]);
s[i].clear();
mp[iv[i]] = 0;
iv[i] = 0;
}
sort(p.begin(), p.end());
if (p.size()) {
printf("%d", p[0].second);
for (int i = 1; i < p.size(); i++) printf(" %d", p[i].second);
}
puts("");
}
return 0;
}1003 - 杂草蔓延
题意
给定一个 n × m 网格，初始时可任意选择一些格子长草。
之后每轮，所有与至少两个已长草格子四联通相邻的空格子，也会长草。
求最少初始长草格子数，使最终整个网格都能长满草。
题解
容易发现的网格中只需要填充对角线就能覆盖所有格子，考虑的时候剩余个格子应该怎么填，可以发现如下图这样，空出一列来放一个杂草，可以将范围内的格子填充满，所以可以得到总需要的杂草数量的公式为.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int _ = 1;
cin >> _;
while (_--) {
ll n, m;
cin >> n >> m;
if (n < m) swap(n, m);
cout << m + (n - m + 1) / 2 << '\n';
}
return 0;
}1004 - 小z的开箱
题意
给定一个环上的 n 个数 a_i。你可以任选起点和方向走一圈，并任意选择吸收哪些数。
当前幸运值初始为 0，每次吸收一个数 x 后，新的幸运值变为 不超过原幸运值 + x 的最大质数，若不存在则变为 0。
求最后能得到的最大幸运值。
数据范围： 1 ≤ T ≤ 10，1 ≤ n ≤ 10^5，1 ≤ a_i ≤ 10
题解：
观察数据范围，打表可以发现，113后面的死一个质数是127，而127-113>10，所以最大幸运值只能为113，从每个非1的位置开始遍历一遍，如果记录p[s]为当前数字s跳到下一个位置需要的最大值，这个值可以提前预处理出来，因为总的质数个数很少，所以直接跑暴力就可以，后面要做的就是找到下一步应该跳到哪里，通过预处理ST表，可以在的时间内算出应该跳到哪一个位置，这个过程最多大约30步（1-113内质数的个数），最后记得将数组反向再处理一遍，总时间复杂度。
代码
#include <bits/stdc++.h>
using namespace std;
inline int read() {
char ch = getchar();
int x = 0, f = 1;
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x * f;
}
bool isp(int n) {
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return 0;
}
return 1;
}
int p[130], a[200010];
int f[200010][19], lg[200010], jump[200];
int main() {
int lst = 0;
vector <int> pri;
for (int i = 2; i <= 128; i++) {
if (isp(i)) {
pri.push_back(i);
lst = i;
}
jump[i] = lst;
}
for (int i = 2; i <= 113; i++) {
if (isp(i)) {
p[i] = pri[upper_bound(pri.begin(), pri.end(), i) - pri.begin()] - i;
}
}
for (int i = 2; i <= 200005; i++) {
lg[i] = lg[i >> 1] + 1;
}
int _ = read();
while (_--) {
int n = read();
for (int i = 1; i <= n; i++) a[i] = read();
auto calc = [ & ]() -> int {
for (int i = 1; i <= n; i++) a[i + n] = f[i][0] = f[i + n][0] = a[i];
n *= 2;
for (int j = 1; j < 19; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
auto check = [ & ](int l, int r) -> int {
int k = lg[r - l + 1];
return max(f[l][k], f[r - (1 << k) + 1][k]);
};
int ans = 0;
for (int i = 1; i <= n / 2; i++) {
if (a[i] == 1) continue;
int s = a[i];
if (s >= 7) s = 7;
else if (s >= 5) s = 5;
else if (s >= 3) s = 3;
else s = 2;
int L = i, R = i + n / 2 - 1;
for (int j = L + 1; j <= R;) {
if (check(j, R) < p[s]) break;
if (s == 113) break;
int l = j, r = R;
while (l < r) {
int mid = l + r >> 1;
if (check(j, mid) >= p[s]) r = mid;
else l = mid + 1;
}
s = jump[s + a[l]];
j = l + 1;
}
ans = max(ans, s);
if (ans == 113) break;
}
n /= 2;
return ans;
};
int ans = calc();
if (ans != 113) {
reverse(a + 1, a + 1 + n);
ans = max(ans, calc());
}
printf("%d\n", ans);
}
return 0;
}1006 - 光辉岁月
题意
给定一个长度为 的 序列，第 位为 表示这一年“记得”，为 表示这一年“忘记”。
接下来有 次操作，每次给出一个区间 ，表示将这段区间内的所有位置都变成 ，且这种修改是永久的。
对于每次操作后，需要求出一个最大的整数 ，满足存在某个区间 ，其中所有值为 的位置按从小到大排列后恰好构成一个长度为 的等差数列。输出每次操作后的答案。
题解
考虑把所有当前为 的位置记下来，设这些位置为 。如果某个区间内所有为 的位置能构成等差数列，那么相邻两个位置的差一定全部相同。
于是定义一个辅助数组 ：
- 若第 位当前为 ，则
- 若第 位当前为 ，并且下一个为 的位置是 ，则令
- 若第 位是最后一个为 的位置，则
这样一来，一个区间内所有为 的位置构成等差数列，当且仅当这个区间对应的 数组中，去掉所有的 以后，剩下的数都相同。也就是说，问题转化成了维护“忽略 后最长连续相同数段”的长度。
每次把区间 变成 时， 数组只会在很少的位置发生变化：
- 对于区间内部的所有位置 ，因为它们的下一个为 的位置就是 ，所以这些位置的 都会变成
- 设 表示 左边最近的一个为 的位置，那么它的下一个为 的位置会改成 ，因此需要把 改成
- 设 表示 右边最近的一个为 的位置，那么位置 的下一个为 的位置会变成 ，因此需要把 改成 ；如果右边不存在这样的点，则
于是每次操作本质上就是：
- 一段区间赋值为
- 两个单点修改
用一个 set / ODT 维护当前哪些位置已经是 ，从而快速找到 和 。再用线段树维护 数组的信息：
lnum,lcnt：区间左端第一段非零数的值及长度rnum,rcnt：区间右端最后一段非零数的值及长度cnt：区间内非零数个数ans：忽略 后，区间内最长连续相同非零段长度
这样合并两个儿子时，如果左儿子右端的非零值和右儿子左端的非零值相同，就可以把它们拼起来更新答案。
由于线段树里维护的是“相同公差段的边数”，而题目要求的是等差数列中的点数，所以每次输出答案时需要再加 。
时间复杂度为 。
代码
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define mk make_pair
using namespace std;
using ll = long long;
using PII = pair < ll, ll > ;
const int N = 200010;
const ll INF = 1e9;
inline int read() {
char ch = getchar();
int x = 0, f = 1;
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x * f;
}
struct ODT {
struct node {
int l, r;
mutable ll v;
node(int l, int r = -1, ll v = 0): l(l), r(r), v(v) {}
bool operator < (const node & o) const {
return l < o.l;
}
};
set < node > s;
ODT() {
s.clear();
}
auto split(int pos) {
auto it = s.lower_bound(node(pos));
if (it != s.end() && it -> l == pos) return it;
it--;
int l = it -> l, r = it -> r;
ll v = it -> v;
s.erase(it);
s.insert(node(l, pos - 1, v));
return s.insert(node(pos, r, v)).first;
}
void assign(int l, int r, ll x) {
auto itr = split(r + 1), itl = split(l);
s.erase(itl, itr);
s.insert(node(l, r, x));
}
};
struct Node {
int l, r;
int lnum, lcnt, rnum, rcnt;
int cnt, ans, tag;
}tr[N << 2];
int n, q, f[N], a[N];
ODT odt;
void pushup(Node & u, Node l, Node r) {
if (l.cnt == 0 && r.cnt == 0) {
u.lnum = u.lcnt = u.rnum = u.rcnt = u.cnt = u.ans = 0;
} else if (l.cnt == 0) {
u.lnum = r.lnum;
u.lcnt = r.lcnt;
u.rnum = r.rnum;
u.rcnt = r.rcnt;
u.cnt = r.cnt;
u.ans = r.ans;
} else if (r.cnt == 0) {
u.lnum = l.lnum;
u.lcnt = l.lcnt;
u.rnum = l.rnum;
u.rcnt = l.rcnt;
u.cnt = l.cnt;
u.ans = l.ans;
} else {
u.cnt = l.cnt + r.cnt;
u.lnum = l.lnum, u.lcnt = l.lcnt;
if (u.lcnt == l.cnt && l.rnum == r.lnum) u.lcnt = l.cnt + r.lcnt;
u.rnum = r.rnum, u.rcnt = r.rcnt;
if (r.rcnt == r.cnt && l.rnum == r.lnum) u.rcnt = r.cnt + l.rcnt;
u.ans = max(l.ans, r.ans);
if (l.rnum == r.lnum) u.ans = max(u.ans, l.rcnt + r.lcnt);
}
u.tag = 0;
}
void pushup(int u) {
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r) {
tr[u]=Node({l,r,0,0,0,0,0,0,0});
if(l==r){
if(f[l]) tr[u]=Node({l,r,f[l],1,f[l],1,1,1,0});
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void pushdown(int u) {
if (tr[u].tag) {
tr[u << 1].lnum = tr[u << 1].rnum = tr[u << 1].tag = 1;
tr[u << 1].lcnt = tr[u << 1].rcnt = tr[u << 1].cnt = tr[u << 1].ans = tr[u << 1].r - tr[u << 1].l + 1;
tr[u << 1 | 1].lnum = tr[u << 1 | 1].rnum = tr[u << 1 | 1].tag = 1;
tr[u << 1 | 1].lcnt = tr[u << 1 | 1].rcnt = tr[u << 1 | 1].cnt = tr[u << 1 | 1].ans = tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1;
tr[u].tag = 0;
}
}
void modify(int u, int l, int r, int x) {
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].lnum = tr[u].rnum = tr[u].tag = 1;
tr[u].lcnt = tr[u].rcnt = tr[u].cnt = tr[u].ans = tr[u].r - tr[u].l + 1;
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, x);
if (r > mid) modify(u << 1 | 1, l, r, x);
pushup(u);
}
void modify(int u, int x, int v) {
if (tr[u].l == tr[u].r) {
if(v)tr[u]=Node({tr[u].l,tr[u].r,v,1,v,1,1,1,0});
else tr[u]=Node({tr[u].l,tr[u].r,0,0,0,0,0,0,0});
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
int main() {
int _ = read();
while (_--) {
n = read(), q = read();
vector < int > pos;
odt = ODT();
for (int i = 1; i <= n; i++) a[i] = read(), f[i] = 0;
int st = 1;
for (int i = 2; i <= n; i++) {
if (a[i] ^ a[i - 1]) {
odt.s.insert(ODT::node({st,i-1,a[st]}));
st = i;
}
}
odt.s.insert(ODT::node({st,n,a[st]}));
odt.s.insert(ODT::node({n+1,n+1,0}));
for (int i = 1; i <= n; i++)
if (a[i]) pos.pb(i);
for (int i = 0; i + 1 < pos.size(); i++) {
f[pos[i]] = pos[i + 1] - pos[i];
}
if (pos.size()) f[pos.back()] = 0;
build(1, 1, n);
while (q--) {
int l = read(), r = read();
auto find_pre = [ & ](int pos) {
auto it = odt.split(pos);
while (it != odt.s.begin()) {
--it;
if (it -> l == n + 1) continue;
if (it -> v == 1) return it -> r;
}
return -1;
};
auto find_nxt = [ & ](int pos) {
auto it = odt.split(pos + 1);
while (it != odt.s.end()) {
if (it -> l == n + 1) return -1;
if (it -> v == 1) return it -> l;
++it;
}
return -1;
};
int pre = find_pre(l);
int nxt = find_nxt(r);
odt.assign(l, r, 1);
if (l <= r - 1) modify(1, l, r - 1, 1);
if (pre != -1) modify(1, pre, l - pre);
if (nxt != -1) modify(1, r, nxt - r);
else modify(1, r, 0);
printf("%d\n", tr[1].ans + 1);
}
}
return 0;
}1007 - 最大三段和
题意
给定序列 a，选三个互不相交的子段，且相邻两段之间至少隔一个数，其中第二段长度必须恰好为 1，求三段元素和的最大值。
题解
枚举中间长度为 1 的子段，答案为“左侧最大非空子段和 + 中间点 + 右侧最大非空子段和”，用前后缀预处理即可，复杂度 O(n)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _ = 1;
cin >> _;
while (_--) {
int n;
cin >> n;
vector<ll> a(n + 2), p(n + 2), s(n + 2), pm(n + 2), sm(n + 2), pmx(n + 2), smx(n + 2);
for (int i = 1; i <= n; i++) cin >> a[i];
pmx[0] = smx[n + 1] = -1e9;
pm[0] = sm[n + 1] = -1e9;
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] + a[i];
pmx[i] = max(pmx[i - 1], a[i]);
if (p[i] <= 0) p[i] = 0;
pm[i] = max(pm[i - 1], p[i]);
}
for (int i = n; i; i--) {
s[i] = s[i + 1] + a[i];
smx[i] = max(smx[i + 1], a[i]);
if (s[i] <= 0) s[i] = 0;
sm[i] = max(sm[i + 1], s[i]);
}
ll ans = a[1] + a[3] + a[5];
for (int i = 3; i <= n - 2; i++) {
ll sum = a[i] + (pmx[i - 2] >= 0 ? pm[i - 2] : pmx[i - 2]) + (smx[i + 2] >= 0 ? sm[i + 2] : smx[i + 2]);
ans = max(ans, sum);
}
cout << ans << '\n';
}
return 0;
}1008 - 单十一花钱计划
题意
有件衣服，第件衣服有两种原价，分别为和 ，进行次购买操作。对于第次购买，会给出一个区间，以及两种涨价幅度参数。设上一次购买得到的答案为 （规定 ），则本次真实涨价为：在本次购买中，区间 内的每件衣服价格都会临时变为：其中购买结束后价格恢复原状，不会对后续操作造成实际修改。
现在需要在区间 中选择一件衣服购买。 由于歪歪“有钱但不傻”，她会对每件衣服选择两种价格中较小的那一个； 但她又希望买到“最贵”的衣服，所以本次询问要求输出：，也就是：在当前询问给定的区间内，所有衣服按照“取两种价格较小者”后的最终价格中，最大的那个值，对于每次询问，输出对应答案。
题解
可以发现，对于一件固定的衣服，最终价格是.
当 时取前者，否则取后者。整理可得：
也就是说，对于一次询问，真正起决定作用的只有固定的阈值 。
于是我们先把每件衣服按 从小到大排序。对于一个给定的 ，所有满足 的衣服都会取 ，其余衣服都会取 。这启发我们预处理出 个版本的可持久化线段树：初始版本中所有位置都属于“取 ”这一类，线段树维护区间内这部分的最大 ；然后按 从小到大依次把对应位置从 A 类切换到 B 类，也就是把该位置的贡献从 改成 。因此第 个版本就表示前 个最小的 已经被划入“取 ”这一类。
查询时，先根据当前的 在排序后的数组中二分，找到最后一个满足 的位置，对应选择合适的版本。然后在线段树上查询原区间 ，得到当前区间内两类衣服的最大值：一类是仍取 的最大 ，另一类是已切换为 的最大 。最后答案就是.
这样每次询问只需要一次二分和一次线段树查询，时间复杂度为 ，总复杂度为 。
代码
#include <bits/stdc++.h>
#define x first
#define y second
#define eb emplace_back
#define mk make_pair
using namespace std;
using ll = long long;
using PII = pair < ll, ll > ;
const int N = 50010;
const ll INF = 1e9;
inline int read() {
char ch = getchar();
int x = 0, f = 1;
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x * f;
}
struct Node {
int l, r;
ll mx1, mx2;
}tr[N << 5];
int n, m, a[N], b[N];
int root[N], tot;
int build(int l, int r) {
int p = ++tot;
if (l == r) {
tr[p].mx1 = a[l], tr[p].mx2 = -INF;
return p;
}
int mid = l + r >> 1;
tr[p].l = build(l, mid);
tr[p].r = build(mid + 1, r);
tr[p].mx1 = max(tr[tr[p].l].mx1, tr[tr[p].r].mx1);
tr[p].mx2 = max(tr[tr[p].l].mx2, tr[tr[p].r].mx2);
return p;
}
int modify(int p, int l, int r, int x) {
int q = ++tot;
tr[q] = tr[p];
if (l == r) {
tr[q].mx1 = -1e9, tr[q].mx2 = b[x];
return q;
}
int mid = l + r >> 1;
if (x <= mid) tr[q].l = modify(tr[p].l, l, mid, x);
else tr[q].r = modify(tr[p].r, mid + 1, r, x);
tr[q].mx1 = max(tr[tr[q].l].mx1, tr[tr[q].r].mx1);
tr[q].mx2 = max(tr[tr[q].l].mx2, tr[tr[q].r].mx2);
return q;
}
pair < ll, ll > query(int p, int l, int r, int ql, int qr) {
if (ql <= l && qr >= r) return mk(tr[p].mx1, tr[p].mx2);
int mid = l + r >> 1;
PII res1 = {-INF, -INF}, res2 = res1;
if (ql <= mid) res1 = query(tr[p].l, l, mid, ql, qr);
if (qr > mid) res2 = query(tr[p].r, mid + 1, r, ql, qr);
return mk(max(res1.x, res2.x), max(res1.y, res2.y));
}
int main() {
int _ = read();
while (_--) {
n = read(), m = read();
vector < PII > p(n + 1);
for (int i = 1; i <= n; i++) a[i] = read(), b[i] = read(), p[i] = mk(b[i] - a[i], i);
sort(p.begin() + 1, p.end());
tot = 0;
root[0] = build(1, n);
for (int i = 1; i <= n; i++) {
root[i] = modify(root[i - 1], 1, n, p[i].y);
}
ll ans = 0, x = 0, y = 0;
while (m--) {
ll l = read(), r = read(), x = read() ^ ans, y = read() ^ ans;
int rt = upper_bound(p.begin() + 1, p.end(), mk(x - y, n * 1 ll)) - p.begin() - 1;
PII res = query(root[rt], 1, n, l, r);
printf("%lld\n", ans = max(res.x + x, res.y + y));
}
}
return 0;
}1009 - 临渊羡鱼
题意
给定 n 条鱼的大小 a_i. 一张网能抓到所有大小在区间 [L,R] 内的鱼，网的大小定义为 R-L+1。求抓住全部鱼所需的最小网大小。
题解
签到题，直接输出max(a) - min(a) + 1.
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int _ = 1;
cin >> _;
while (_--) {
int n;
cin >> n;
vector<int> a(n);
for (auto & t: a) cin >> t;
sort(a.begin(), a.end());
cout << a.back() - a[0] + 1 << '\n';
}
return 0;
}1010 - 收买时间
题意
给定一个 网格，每个格子 t[i][j] 表示最早可进入时间。你可以在已开放格子间免费移动，也可以花钱走单向传送门。要求总花费不超过 money，求最早什么时候能从 (1,1) 到 (n,m)。
题解
二分答案 T，判断在时间 T 时能否到达终点。
检查时把所有 t[i][j] <= T 的格子看作可用点，在这些点之间建图：
- 相邻格子连一条费用
0的边 - 可用传送门连一条费用为其代价的有向边
然后从起点跑最短路，判断能否在总代价不超过 money 的情况下到达终点。
时间复杂度约为 。
代码
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define get(i, j)((i) * m + (j))
using namespace std;
using ll = long long;
using PII = pair<ll, int> ;
inline int read() {
char ch = getchar();
int x = 0, f = 1;
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x * f;
}
int n, m, money, k;
struct Query {
int x, y, p, q, w;
}q[200010];
vector<pair<int, int>> e[170000];
ll dis[170000];
int main() {
int _ = read();
while (_--) {
n = read(), m = read(), money = read(), k = read();
vector a(n, vector<int>(m));
vector<int> tim;
tim.reserve(n * m);
for (auto & v: a) for (auto & t: v) t = read(), tim.pb(t);
for (int i = 0; i < k; i++) q[i].x = read() - 1, q[i].y = read() - 1, q[i].p = read() - 1, q[i].q = read() - 1, q[i].w = read();
sort(tim.begin(), tim.end());
tim.erase(unique(tim.begin(), tim.end()), tim.end());
auto add = [ & ](int a, int b) {
e[a].eb(0, b), e[b].eb(0, a);
};
auto check = [ & ](int lim) -> bool {
for (int i = 0; i < n * m; i++) e[i].clear(), dis[i] = 1e18;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] > lim) continue;
if (i + 1 < n && a[i + 1][j] <= lim) add(get(i, j), get(i + 1, j));
if (j + 1 < m && a[i][j + 1] <= lim) add(get(i, j), get(i, j + 1));
}
}
for (int i = 0; i < k; i++) {
if (a[q[i].x][q[i].y] > lim || a[q[i].p][q[i].q] > lim) continue;
e[get(q[i].x, q[i].y)].eb(q[i].w, get(q[i].p, q[i].q));
}
priority_queue < PII, vector < PII > , greater < PII >> h;
h.push({0,0});
dis[0] = 0;
while (h.size()) {
auto[d, v] = h.top();
h.pop();
if (d != dis[v]) continue;
if (v + 1 == n * m) return d <= money;
for (auto[w, to]: e[v]) {
if (dis[to] > d + w && d + w <= money) {
dis[to] = d + w;
h.push({dis[to],to});
}
}
}
return 0;
};
int l = 0, r = tim.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (check(tim[mid])) r = mid;
else l = mid + 1;
}
printf("%d\n", tim[l]);
}
return 0;
}
Comment seems to stuck. Try to refresh?✨