『RetOI』Round 1 全题解

AAA混泥土批发ppl哥

2025-09-21 13:10:11

发布于：浙江

20阅读

0回复

0点赞

『RetOI』Round 1 全题解

T1 损友

题目大意

给定一张 $n \times m$ 地图，且每个格点都有一个权值 $w_{i,j}$ ，再给你 $k$ 个传送门，限制最多只能使用 $p$ 次，求从 $(1,1)$ 到 $(n,m)$ 的最小权值和。

题目分析

Subtask 1

~~说句实话，针对于本部分分出题人并没有想到合理的做法，用来留给一些奇奇怪怪的搜索。~~

Subtask 2

注意到 $k \lt 1$ ，而题目又保证了 $k$ 为整数，且 $k \ge 0$ ，所以 $k=0$ ，也就是说该地图没有传送门，所以只需要跑一个简单的 dp 就行了，代码就不贴了。

Subtask 3 & 4

~~两个部分分较为相似，同样是留给一些奇奇怪怪的搜索，也可以理解为是出题人为了防止你们太快猜出正解所设置的误导部分分。~~

Subtask 5（正解）

想象一下，在地图上我们找到两个关键格点 $A,B$ （起点和终点不算），那么只传送一次（ $A$ 传到 $B$ ）的费用为 $d_{(1,1),A} + d_{B,(n,m)}$ ，其中我们用 $d_{X,Y}$ 表示从 $X$ 到 $Y$ 不使用传送门的最小代价。
同理，传送两次（ $A$ 传到 $C$ 和 $D$ 传到 $B$ ）我们需要找到四个关键点，费用为 $d_{(1,1),A}+d_{C,D}+d_{B,(n,m)}$ ，为了方便表述，我们将 $A,B,C,D$ 的顺序进行了调换。
我们注意到题目中保证了对于任意的 $i,j(1 \le i\le n,1 \le j \le m,)$ ，满足 $w_{i,j} \ge 0$ ，也就是说 $d_{C,D}$ 一定为非负整数。利用小奥作差法，我们可以得出 $d_{(1,1),A} + d_{B,(n,m)} \le d_{(1,1),A}+d_{C,D}+d_{B,(n,m)}$ ，再形象点，我们可以得出：传送两次一定没有只传送一次更优。
以此类推，无论传送几次，一定没有只传送一次更优，所以我们可以将上面的结论推广成：传送多次一定没有只传送一次更优。

根据上述结论，我们可以将最终答案分成两种形式，一种是使用传送门，一种是不使用传送门。前者的答案为有传送门的最靠近起点的的格点到起点的距离加有传送门的最靠近终点的格点到终点的距离，其中我们说的“最靠近”指距离最短，后者的答案为起点到终点的最短距离，最终答案为两者中的最小值。
形式化的，

$ans=min\{d_{(1,1),(n,n)},min\{d_{(1,1),I},isok_I=1\}+min\{d_{J,(n,m)},isok_J=1\}\}。$

其中我们用 $isok_X$ 表示 $X$ 格点上有没有传送门， $isok_X=1$ 表示有，否则反之。
当然，如果 $k<2$ 或是 $p=0$ ，最终答案 $ans$ 就等于 $d_{(1,1),(n,m)}$ 。

小注：有些人可能会问当 $I$ 和 $J$ 表示同一个格点时是不是还有减掉它们重复计算的 $w_I$ ，答案是不用的，至于为什么留给读者自己研究。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf LONG_LONG_MAX
const int maxn = 2e3 + 10;
int n, m, k, p, w[maxn][maxn], f[maxn][maxn], g[maxn][maxn];
bool isok[maxn][maxn];
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> k >> p;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> w[i][j];
	for (int i = 1, x, y; i <= k; i++) cin >> x >> y, isok[x][y] = 1;//正常读入
	memset(f, 0x3f, sizeof f), memset(g, 0x3f, sizeof g);
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) f[i][j] = min({f[i - 1][j], f[i][j - 1], (i == 1 && j == 1 ? 0 : inf)}) + w[i][j];
	for (int i = n; i >= 1; i--) for (int j = m; j >= 1; j--) g[i][j] = min({g[i + 1][j], g[i][j + 1], (i == n && j == m ? 0 : inf)}) + w[i][j];
    //分别求出每个格点到起点/终点的最短距离
	int start = inf, end = inf;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (isok[i][j]) start = min(start, f[i][j]), end = min(end, g[i][j]);
	cout << min(f[n][m], (p >= 1 && k >= 2? start + end : inf));//求值输出
	return 0;
}

T2 海岛

题目大意

pzh 被困在一个长为 $n$ 的正方形海岛上，其所在坐标为 $(x,y)$ ，给定救援队的速度 $k$ 、距离 $m$ 以及海岛的下沉速度 $s$ 、每个坐标的海拔 $h$ ，求救援队到达时 pzh 能否获救。

题目分析

救援队正在 $m$ 米外以 $k$ 米每秒的速度向海岛驶来，则救援队还要 $\frac{m}{k} $ 秒抵达海岛，又因为海岛正以 $s$ 米每秒的速度下沉，所以在救援队来到之前海岛下沉了 $\frac{ms}{k} $ 米，救援队到达时 $(i,j)$ 的海拔变为 $h_{i,j}-\frac{ms}{k} $。
如题目所述，只有当 $(x,y)$ 海拔小于 $0$ 且其周围至少存在一个位置同样满足其坐标小于 $0$ ，我们才认为 $(x,y)$ 被淹没。

考虑一种极端情况

救援队到达之前海岛下沉 $3$ 米，此时海岛各个坐标上的海拔为：

1 1 1
1 -2 1
1 1 1

pzh 所在坐标 $(2,2)$ 此时海拔为 $-2$ ，虽然海拔低于 $0$ ，但他周围四个坐标均为被淹没，所以 pzh 得救。
数据范围中 $1 \le n \le 100$ ，用 DFS 搜索一遍即可。
注意：DFS 记得要在四个边各搜一遍，否则可能搜不完整！！

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
//定义变量
int n, m, k, s;
int x, y;
int a[102][102];
int vis[102][102];
void dfs(int o, int p) {
	//记忆化搜索
	if (vis[o][p] == 1) return;
	//判断越界
	if (o < 1 || p < 1 || o > n || p > n) return;
	if (a[o][p] >= 0) return;
	vis[o][p] = 1;
	//搜索旁边的4个坐标
	dfs(o + 1, p);
	dfs(o - 1, p);
	dfs(o, p + 1);
	dfs(o, p - 1);
}
signed main() {
	memset(a, 0, sizeof a);
	memset(vis, 0, sizeof vis);
	cin >> n >> m >> k >> s >> x >> y;
	//救援队到达时海岛下沉m/k*s米
	m = m / k * s;
	//输入
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
			//直接在这里减去下降海拔
			a[i][j] -= m;
		}
	}
	//dfs搜四遍
	for (int i = 1; i <= n; i++) {
		dfs(1, i);
		dfs(n, i);
		dfs(i, 1);
		dfs(i, n);
	}
	//输出
	if (vis[x][y] == 1) cout << "See you again.";
	else cout << "yes";
	return 0;
}

T3 最佳出题人

题目大意

给定 $n$ 个人，每个人都有 $m$ 个指标，按照三条评定规则对他们进行排序，求出第 $p$ 个人的编号。

题目分析

每个人都含有 $m$ 个指标，所以考虑结构体排序，具体也没什么好讲的，直接看代码吧。

code

比较方差

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
struct Person {
	long long sum, t;//总和and方差 
	int id;//编号 
} a[maxn];
int b[maxn];//临时数组 
int n, m, p;//如题目所述 
bool cmp(const Person& x, const Person& y) {
	if (x.sum != y.sum) return x.sum > y.sum;
	if (x.t != y.t) return x.t < y.t;
	return x.id < y.id;
}//按题意排序 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);//输入/输出 优化 
	cin >> n >> m >> p;
	for (int i = 1; i <= n; i++) {
		long long sum = 0, ux = 0, t = 0;//注意开long long 
		for (int j = 1; j <= m; j++) cin >> b[j], sum += b[j];
		ux = sum / m;//应该可以看出来，ux为平均值 
		for (int j = 1; j <= m; j++) t += 1LL * (ux - b[j]) * (ux - b[j]);//计算方差 
		a[i] = {sum, t, i};
	}
	sort(a + 1, a + n + 1, cmp);//排序 
	cout << a[p].id;//输出 
	return 0;
}

另外，针对于此类涉及到方差的比较都可以通过一些操作（具体操作可以自行上网学习）改为平方和的比较，这样就可以避免一些精度问题。不过本题保证“每个人所有指标之和是 $m$ 的倍数”，所以即使不优化也可以 AC 本题。

比较平方和

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
struct Person {
	long long sum, sum_sq;//总和and平方和
	int id;
} a[maxn];
int n, m, p;
bool cmp(const Person& x, const Person& y) {
	if (x.sum != y.sum) return x.sum > y.sum;
	if (x.sum_sq != y.sum_sq) return x.sum_sq < y.sum_sq;
	return x.id < y.id;
}//排序
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> p;
	for (int i = 1; i <= n; i++) {
		long long sum = 0, sum_sq = 0;//注意开long long
		for (int j = 1, x; j <= m; j++) {
			cin >> x;
			sum += x, sum_sq += (long long)x * x;//总和and平方和
		}
		a[i] = {sum, sum_sq, i};
	}
	sort(a + 1, a + n + 1, cmp);//排序
	cout << a[p].id;//输出
	return 0;
}

T4 高塔

题目大意

把 $n$ 个元素插进有一个长度为 $h$ 的序列中，其中序列的每个格点里最多只能容纳 $k$ 个元素，且第 $n$ 元素只能插进序列中下标小于或等于 $f_i$ 的元素。已知序列中下标为 $i$ 的每有一个元素，就需要 $m_i$ 的代价，求将所有元素插入序列中的最小代价。

题目分析

我的老师教过我一个分辨贪心和背包 DP 的方法：一般对于既有代价又有价值的题目，如果所有元素的代价和价值均不相同，那么这题就是 DP，否则就是贪心。
我们注意到这道题每个元素都只会占用一个空间，所以只能是贪心。
对于贪心策略，最好的方法就是无脑猜，如果猜完可以证，那么它就一定是对的，~~如果猜完不可以证明且没时间了，那么它也一定是正确的~~（自信
让我们考虑一下这道题的贪心策略，对于两个元素 $i,j$ ，满足 $f_i \ge f_j$ ，且 $m_p=min\{m_l(f_j \le l \le h)\}$ ，那么肯定优先将元素 $i$ 插入格点 $p$ ，如果还有空位再插 $j$ ，否则将 $j$ 插入 $o$ ，其中 $o$ 满足 $m_o=min\{m_l(f_j \le l \le h)\}$ 。
那么为什么会这样呢？其实也很好证明，因为 $f_i \ge f_j$ ，所以元素 $j$ 可以插入的范围是严格包含元素 $i$ 可以插入的范围的，换句话说，元素 $i$ 可以插入的格点元素 $j$ 一定能，反之则不一定能。那么感性理解，既然这样如果有空出来一个空位肯定优先选择插入 $i$ ，因为 $j$ 可以插入的范围更大。

code

//声明：本题不同做法差异较大，只要基于大致相同的贪心策略即可，具体实现方法依个人习惯
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>//[代价，还可以容多少人]
const int maxn = 1e3 + 10;
int n, h, k;
int m[maxn], need[maxn];//m和题意相同，need指层数需要大于或等于这一层有多少个人
priority_queue<pii, vector<pii>, greater<pii>> q;//存当前所需代价最小的层
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> h >> k;
	for (int i = 1; i <= h; i++) cin >> m[i];
	for (int i = 1, x; i <= n; i++) cin >> x, need[x]++;//注意啦，这个和题面的f不一样
	int ans = 0;//总和
	for (int i = h; i >= 1; i--) {//倒序枚举，因为每个人的约束是从f_i-n，右端点都是n
		q.push({m[h - i + 1], k});//将当前点存入优先队列
		if (!need[i]) continue;//如果需要至于大于或等于当前层数没人，就直接返回，因为更高层数的都已经处理过了
		while (need[i] && !q.empty()) {//其实第二个队列非空的条件可以去掉，因为题目保证n<=h*k。
			pii t = q.top();//去除队首，也就是目前最小值
			q.pop();
			int w = t.first;
			int sum = t.second;
			if (sum >= need[i]) {
				ans += w * need[i];
				sum -= need[i];
				need[i] = 0;
				if (sum > 0) q.push({w, sum});
			} else {
				ans += w * sum;
				need[i] -= sum;
			}
			//计算
		}
	}
	cout << ans;
	return 0;
}