https://atcoder.jp/contests/arc105/tasks

C - Camels and Bridge

 

题意：有一座桥，分为 m 部分，每部分长度为 l[i]l[i]，最大承重为 v[i]v[i]，有 n 个骆驼，每个重量为 w[i]w[i]，所有骆驼从桥的一头开始按照某个顺序依次过桥，且相互距离保持不变，每部分桥上的重量不能超过这部分的最大承重，每部分桥两端点的重量不算。要安排过桥顺序和相互的距离，使得桥不塌，且首尾两个骆驼的距离最小，输出最小距离。

枚举+贪心

n 很小，可以枚举排列。所以现在需要在给定排列下，求最短长度。

贪心使得每个骆驼与它前一个的距离最小。

对于一只骆驼，它前面所有骆驼的距离都确定了，需要检查它与前面的所有骆驼，保证如果它们在一个部分，它们的重量之和不超过承重。但不好算距离。

所以考虑对一些骆驼，如果它们重量和为 sum，它们首尾最短需要保持的长度。这可以通过预处理桥的每一部分得到。

这样就可以枚举骆驼的区间，计算当前骆驼与前一只最小要的距离。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 1e8 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m;
int w[100], l[100005], v[100005];
int a[100], sum[100]; ll d[100];
int lim[N], mn = INF;
ll ans = inf;
void cal() {
	for (int i = 1; i <= n; i++) {
		sum[i] = sum[i - 1] + w[a[i]];
	}
	for (int i = 2; i <= n; i++) {
		ll di = lim[w[a[i]]];
		for (int j = i - 1; j >= 1; j--) {	//注意超过N的也要枚举
			di = max(di, lim[min(100000000, sum[i] - sum[j - 1])] - d[i - 1] + d[j]);
		}
		d[i] = d[i - 1] + di;
	}
	ans = min(ans, d[n]);
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &w[i]);
		a[i] = i;
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &l[i], &v[i]);
		lim[v[i] + 1] = max(lim[v[i] + 1], l[i]);
		mn = min(mn, v[i]);
	}
	for (int i = 1; i <= n; i++)if (w[i] > mn) { puts("-1"); return 0; }
	for (int i = 1; i < N; i++)lim[i] = max(lim[i - 1], lim[i]);
	do {
		cal();
	} while (next_permutation(a + 1, a + n + 1));
	if (ans >= inf)while (1);
	printf("%lld\n", ans);
	return 0;
}

 

D - Let’s Play Nim

 

题意：n 个 背包，n 个盘子，两个人，背包里有金币，盘子为空。轮流操作，游戏分为两部分，第一部分：选一个背包以及一个盘子，把背包里的所有金币放到盘子里。当所有背包都空了，第二部分：选一个盘子拿走多于 0 的金币。不能拿的人输。

第二部分显然是一个nim游戏，所以要考虑第一部分的异或和。

如果 n 为奇数，则第二部分后手先拿，后手希望第一部分异或和不为0。

用如下策略：假设先手放入第一个盘子，后手每次都从剩下的包中选金币最多的，放入第一个盘子。

这样第一个盘子的金币必定多于一半，异或和必定不为 0。所以后手必胜。

如果 n 为偶数，则先手先拿。

如果相同含有相同数量金币的背包成对出现，后手总是能复制先手的操作，使得最终异或和为 0。这时后手必胜。

否则，先手用上面的策略，每次选最多的，放入第一个盘子，则超过一半，异或和必不为 0，这时先手必胜。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int T;
int n, a[N];
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
		if (n & 1) {
			puts("Second");
			continue;
		}
		sort(a + 1, a + n + 1);
		bool flg = 0;
		for (int i = 2; i <= n; i += 2) {
			if (a[i] != a[i - 1])flg = 1;
		}
		puts(flg ? "First" : "Second");
	}
	return 0;
}