P1076 寻宝

作者

[永遠の記憶 ~ Precious Memories]施工D14

2020.8.25
转载自luogu

P1076 寻宝

Noip2012 T2

题目传送门

马上开学了，赶快把坑给填了。

学校某次考试的T2，同时也是一道很坑的题（大雾）。我把教练写的答案复制了还TLE

来说一下题，这是一道模拟。模拟的是一个走楼梯和找楼梯的过程，初见可能觉得有点迷，看两遍后会发现这就是一道水题（捶地）。

根据题意，我们不难写出以下的代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e4 + 5;
const int maxm = 105;
const int mod = 20123;
int m, n;
int d[maxn][maxm];
int e[maxn][maxm];
int f[maxm];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; ++i) {
		f[i] = 0;
		for (int j = 0; j < m; ++j) {
			scanf("%d%d", &d[i][j], &e[i][j]);
			if (d[i][j] == 1) {
				++f[i];
			}
		}
	}
	int s, ans = 0;
	scanf("%d", &s);
	for (int i = 0, j; i < n; ++i) {
		ans += e[i][s];
		ans %= mod;
		e[i][s] %= f[i];
		if (e[i][s] == 0) {
			e[i][s] = f[i];
		}
		j = s;
		if (d[i][s] == 1) {
			e[i][s]--;
		}
		while (e[i][s] > 0) {
			if (++j == m) {
				j = 0;
			}
			if (d[i][j] == 1) {
				--e[i][s];
			}
		}
		s = j;
	}
	printf("%d\n", ans);
	return 0;
}

因为年代过于久远，所以我也不记得这具体写的是什么了
交了一发以后，发现只有30分， $RE$ 了7个点 。

这时我们重读题目，发现题目中写道：

这个数可能会很大，请输出对 20123 取模的结果即可。

很明显，题目说要取模。那么对于所定义的变量，我们要么在定义时定义为 $long\ long$ ，要么在运算时取模。对于所用的算法，如果不进行优化，最后也不可能 $AC$ 。

我们将数据类型改为 $long\ long$ 后尝试对算法进行优化。

我们在最初超时的代码中，把模拟走楼梯的一段撷取出来，如下所示:

for (int i = 0, j; i < n; ++i) {
	ans += e[i][s];
	ans %= mod;
	e[i][s] %= f[i];
	if (e[i][s] == 0) {
		e[i][s] = f[i];
	}
	j = s;
	if (d[i][s] == 1) {
		e[i][s]--;
	}
	while (e[i][s] > 0) {
		if (++j == m) {
			j = 0;
		}
		if (d[i][j] == 1) {
			--e[i][s];
		}
	}
	s = j;
}
简要描述以上代码的思路为:
累加指示牌上的数字，并且简单粗暴地按照题意，逆时针寻找上楼的楼梯。

考虑：逆时针寻找上楼楼梯的过程是否可以简化？

首先，当此时指示牌上的数字$(x)$小于等于此层总共可上楼楼梯数$(m)$时，无法优化，且时间复杂度为 $O(m)$
其次，当此时指示牌上的数字$(x)$大于此层总共可上楼楼梯数$(m)$时，我们最初的算法复杂度为 $O(x)$

手动模拟发现，当 $x > m$ 时，在运算过程中有 $x – (x \bmod m)$ 次操作是重复的，也就是说，运算中只有 $x \bmod m$ 次操作是有效的。

知道了这一点后，优化以上的代码得到的代码如下：

for (int i = 1; i <= n; ++i) {
	ll temp = 0;
	ll ind = x;
	anss += a[i][x];
	a[i][x] = (a[i][x] - 1) % s[i] + 1;
	for (;temp < a[i][ind];) {
		temp += st[i][x];
		if (temp == a[i][ind]) break;
		x++;
		if (x >= m) x -= m;
	}
}

变量名不同敬请忽略
可以看到，上面的代码使用模操作，大大减小了程序的运算量。

$AC$ 代码如下:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll const maxn = 10005;
ll const maxm = 105;
ll const mod = 20123;
ll m, n;
ll a[maxn][maxm];
ll st[maxn][maxm];
ll s[maxn];
ll x, anss;

int main() {
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < m; ++j) {
			scanf("%lld%lld", &st[i][j], &a[i][j]);
			s[i] += st[i][j];
		}
	}
	scanf("%lld", &x);
	for (int i = 1; i <= n; ++i) {
		ll temp = 0;
		ll ind = x;
		anss += a[i][x];
		a[i][x] = (a[i][x] - 1) % s[i] + 1;
		for (;temp < a[i][ind];) {
			temp += st[i][x];
			if (temp == a[i][ind]) break;
			x++;
			if (x >= m) x -= m;
		}
	}
	anss = anss % mod;
	printf("%lld", anss);
}

赶快继续去写了，争取一周内把后面好多好多年的写完（

加油龟比！

发表评论