暑假集训 Day13 总结

前言：

$450$ 分第一名！为了庆祝，今天的所有题目我都会写题解。

A.蜡烛

场切，没啥好说的，找规律。

正解思路：

分为三种情况，分类讨论。 先看第一种情况：

节点 $r$ 和 $l$ 都是非负数，所以，距离就是从 $0$ 到 $r$ 的距离。

第二种情况：

节点 $r$ 和 $l$ 都是负数，所以，距离就是从 $0$ 到 $l$ 的距离。

第三种情况：

这种情况又分两种局面：

局面一：

局面二：

这时，我们就要对两种局面的距离求最小值。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+20;
int n, k, ans = 0x3f3f3f3f;
int a[N];
signed main() {
	freopen("candy.in", "r", stdin);
	freopen("candy.out", "w", stdout);
	cin >> n >> k;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	for (int i = 0; i <= n - k; i++) {
		int l = i;
		int r = i + k - 1;
		int time = 0;

		if (a[l] >= 0) {
			time = a[r];
		} else if (a[r] <= 0) {
			time = -a[l];
		} else {
			time = min(2 * a[r] - a[l], a[r] - 2 * a[l]);
		}

		ans = min(ans, time);
	}

	cout << ans;
	return 0;
}

B.白日梦

正解思路：

这道题要采用从后往前的顺序。如从前往后的话，出现 dreamerase 或 dreamer 就会出问题。其他的，就按照题意模拟即可。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
string s;
int main() {
	freopen("daydream.in", "r", stdin);
	freopen("daydream.out", "w", stdout);
	cin >> s;

	for (int i = s.size() - 1; i >= 0; i--) {
		if (i - 4 >= 0 && s[i - 4] == 'e' && s[i - 3] == 'r' && s[i - 2] == 'a' && s[i - 1] == 's' && s[i] == 'e') {
			i -= 4;
		} else if (i - 4 >= 0 && s[i - 4] == 'd' && s[i - 3] == 'r' && s[i - 2] == 'e' && s[i - 1] == 'a' && s[i] == 'm') {
			i -= 4;
		} else if (i - 5 >= 0 && s[i - 5] == 'e' && s[i - 4] == 'r' && s[i - 3] == 'a' && s[i - 2] == 's' && s[i - 1] == 'e' && s[i] == 'r') {
			i -= 5;
		} else if (i - 6 >= 0 && s[i - 6] == 'd' && s[i - 5] == 'r' && s[i - 4] == 'e' && s[i - 3] == 'a' && s[i - 2] == 'm' && s[i - 1] == 'e' && s[i] == 'r') {
			i -= 6;
		} else {
			cout << "NO";
			return 0;
		}
	}

	cout << "YES";
	return 0;
}

C.重复重复重复...重复重复

正解思路：

这道题目我们很容易就能提取出一个公式：

$$d\times (10^n-1)\div 9 \bmod m=0$$

由于 $10^n-1$ 一定是每一位都是九的数，除以九后，就变为每一位都是一的数。我们预处理位数从一到 $n$ 的所有全一数，看看到哪一位能被 $m$ 直接整除，根据同余，我们看看这个数乘上从九开始到一的哪一个数能满足，输出最大的。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+20;
int n, m;
int a[N];
signed main() {
	freopen("repeat.in", "r", stdin);
	freopen("repeat.out", "w", stdout);
	cin >> n >> m;
	a[1] = 1 % m;

	for (int i = 2; i <= n; i++) {
		a[i] = (10 * a[i - 1] + 1) % m;
	}

	for (int i = n; i >= 1; i--) {
		if (a[i] == 0) {
			for (int j = 1; j <= i; j++) {
				cout << 9;
			}

			return 0;
		}

		for (int j = 9; j >= 1; j--) {
			if ((j * a[i]) % m == 0) {
				for (int k = 1; k <= i; k++) {
					cout << j;
				}

				return 0;
			}
		}
	}

	cout << -1;
	return 0;
}

D.灯

正解思路：

前缀和，分别求出左右上下四个方向的前缀和，对于任意一个位置，加上这四个值减去重算的三个自己取最大值即可。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e3 + 20;
int h, w, ans;
char a[N][N];
int l[N][N], r[N][N];
int u[N][N], d[N][N];
signed main() {
	freopen("deng.in", "r", stdin);
	freopen("deng.out", "w", stdout);
	cin >> h >> w;

	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cin >> a[i][j];
		}
	}

	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			if (a[i][j] == '#') {
				l[i][j] = 0;
			} else {
				l[i][j] = l[i][j - 1] + 1;
			}
		}

		for (int j = w; j >= 1; j--) {
			if (a[i][j] == '#') {
				r[i][j] = 0;
			} else {
				r[i][j] = r[i][j + 1] + 1;
			}
		}
	}

	for (int j = 1; j <= w; j++) {
		for (int i = 1; i <= h; i++) {
			if (a[i][j] == '#') {
				u[i][j] = 0;
			} else {
				u[i][j] = u[i - 1][j] + 1;
			}
		}

		for (int i = h; i >= 1; i--) {
			if (a[i][j] == '#') {
				d[i][j] = 0;
			} else {
				d[i][j] = d[i + 1][j] + 1;
			}
		}
	}

	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			if (a[i][j] == '.') {
				int sum = l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3;
				ans = max(ans, sum);
			}
		}
	}

	cout << ans;
	return 0;
}

E.最大曼哈顿距离

正解思路：

这道题目就是一道数学题，我们看到绝对值就要把绝对值消除掉，而对于一个有两项的算式，就有四个不同的算式。分别为：

算式一：

$$(x_i-y_i)-(x_j+y_j)$$

算式二：

$$(x_j-y_j)-(x_i+y_i)$$

算式三：

$$(x_i-y_i)-(x_j-y_j)$$

算式四：

$$(x_j+y_j)-(x_i-y_i)$$

现在，我们把 $x+y$ 一类的存入一个数组，$x-y$ 一类的存入另一个数组。把 $x+y$ 一类的数组中求一个最大值和最小值，把 $x-y$ 一类的数组中求一个最大值和最小值，然后做差，求这两者的最大值就是答案。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+20;
int n;
int sum[N], sb[N];
int mxs = -0x3f3f3f3f, mns = 0x3f3f3f3f;
int mxb = -0x3f3f3f3f, mnb = 0x3f3f3f3f;
signed main() {
	freopen("lenth.in", "r", stdin);
	freopen("lenth.out", "w", stdout);
	cin >> n;

	for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		sum[i] = x + y;
		sb[i] = x - y;
	}

	for (int i = 1; i <= n; i++) {
		mxs = max(mxs, sum[i]);
		mns = min(mns, sum[i]);
		mxb = max(mxb, sb[i]);
		mnb = min(mnb, sb[i]);
	}

	cout << max(mxs - mns, mxb - mnb);
	return 0;
}

F.简单dp

正解思路：

这道题目是一道 dp 题，通过集合这一信息可以确定这是一个 01 背包，记录每一步选与不选，同时每一次操作后都要除以一次 $2$，因为每一次操作都会使指数加一，但为了不改变指数，我们只能除以 $2$，但只有除法不满足同余，所以这里还要运用快速幂，求出 $998244353$ 的乘法逆元。最初，要把 $dp_0$ 初始化为 $2^n$。因为所有的数都是从 $dp_0$ 转移出去的，而每一次选 $k$ 个数的贡献都是 $2^{n-k}$，$dp_0$ 初始时就是 $2^{n-0}$ 也就是 $2^n$。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e3+20;
const int M = 998244353;
int n, m;
int a[N], dp[N];
int qm(int x, int y) {
	int ans = 1;

	while (y) {
		if (y & 1) {
			ans = ans * x;
			ans %= M;
		}

		x = x * x;
		x %= M;
		y >>= 1;
	}

	return ans;
}
signed main() {
	freopen("sample.in", "r", stdin);
	freopen("sample.out", "w", stdout);
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	dp[0] = qm(2, n);

	for (int i = 1; i <= n; i++) {
		for (int j = m; j >= a[i]; j--) {
			dp[j] += dp[j - a[i]] * qm(2, M - 2);
			dp[j] %= M;
		}
	}

	cout << dp[m] % M;
	return 0;
}