https://codeforces.com/contest/1201

B. Zero Array

 

题意：n个数，每次挑两个数各-1，问能否都等于0。

显然总和为偶数不行。

如果最大值大于总和一半，也不行。

其他都可以，比如3，4，5，可以把3拆成1和2，5-2变3，4-1变3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
int n;
ll a[N];
ll mx, sum;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%lld", &a[i]), mx = max(mx, a[i]), sum += a[i];
	if (sum & 1 || mx > sum / 2)puts("NO");
	else puts("YES");
	return 0;
}

 

D. Treasure Hunting

 

题意：n*m网格，有几格有宝藏，从（1，1）出发，可以向下，左，右走，有一些列是安全的，只有在安全的列才能向下走。问最少走几步拿走所有宝藏。

模拟

思路很简单，每次走到这一行的最左边或最右边的宝箱然后到最近的安全列向下走，dp[i][0/1]dp[i][0/1] 表示到第i行最左/右，拿完1到i-1所有宝藏最小花费。

难点在模拟的细节处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 500005;

int n, m, k, q, l[N], r[N], f[N][2], b[N], pl[N], pr[N];

int dist(int p, int q) {
	if (p > q) swap(p, q);
	if (pr[p] <= q || pl[q] >= p) return 0;
	return min(pr[q] - q, p - pl[p]);
}

signed main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> k >> q;
	for (int i = 1; i <= n; i++) l[i] = 1e9, r[i] = 0;
	for (int i = 1; i <= k; i++) {
		int t1, t2;
		cin >> t1 >> t2;
		l[t1] = min(l[t1], t2);
		r[t1] = max(r[t1], t2);
	}
	for (int i = 1; i <= q; i++) {
		int t1;
		cin >> t1;
		b[t1] = 1;
	}
	pl[0] = -1e9;
	for (int i = 1; i <= m; i++) {
		if (b[i] == 1) pl[i] = i;
		else pl[i] = pl[i - 1];
	}
	pr[m + 1] = 1e9;
	for (int i = m; i >= 1; --i) {
		if (b[i] == 1) pr[i] = i;
		else pr[i] = pr[i + 1];
	}
	if (r[1]) f[1][0] = l[1] - 1, f[1][1] = r[1] - 1;
	else l[1] = 1, r[1] = 1, f[1][0] = f[1][1] = 0;
	int ans = f[1][1];
	for (int i = 2; i <= n; i++) {
		if (r[i] == 0) {
			f[i][0] = f[i - 1][0];
			f[i][1] = f[i - 1][1];
			l[i] = l[i - 1];
			r[i] = r[i - 1];
			++f[i][0]; ++f[i][1];
			continue;
		}
		f[i][0] = min(f[i - 1][0] + 2 * dist(r[i - 1], l[i]) + abs(l[i] - r[i - 1]) + r[i - 1] - l[i - 1],
			f[i - 1][1] + 2 * dist(l[i - 1], l[i]) + abs(l[i] - l[i - 1]) + r[i - 1] - l[i - 1]);
		f[i][1] = min(f[i - 1][0] + 2 * dist(r[i - 1], r[i]) + abs(r[i] - r[i - 1]) + r[i - 1] - l[i - 1],
			f[i - 1][1] + 2 * dist(l[i - 1], r[i]) + abs(r[i] - l[i - 1]) + r[i - 1] - l[i - 1]);
		++f[i][0]; ++f[i][1];
        
		ans = min(f[i][0], f[i][1]) + r[i] - l[i];
	}
	cout << ans;
}