【题解】CSP-S2019初赛：取石子

最新推荐文章于 2023-04-19 22:14:09 发布

原创最新推荐文章于 2023-04-19 22:14:09 发布 · 2.2k 阅读

3 ·

CC 4.0 BY-SA版权

文章标签：

#题解 #dp #noip #状压

DP 同时被 3 个专栏收录

125 篇文章

订阅专栏

noip

53 篇文章

订阅专栏

状压

12 篇文章

订阅专栏

这篇博客探讨了Alice和Bob玩的取石子游戏的策略问题。通过两种不同的算法实现，一种是暴力的动态规划方法，另一种是位运算优化后的解决方案，来判断先手玩家是否有必胜策略。文章提供了详细的代码实现，并分析了复杂度。

(取石子)Alice和Bob两个人在玩取石子游戏。他们制定了nn条取石子的规则，第ii条规则为：如果剩余石子的个数大于等于a[i]a[i]且大于等于b[ilb[il，那么他们可以取走b[i]b[i]个石子。他们轮流取石子。如果轮到某个人取石子，而他无法按照任何规则取走石子，那么他就输了。一开始石子有mm个。请问先取石子的人是否有必胜的方法？

有两种做法

暴力dp： $dp_i$ 表示 $i$ 是否必胜，对于一个规则 $a,b)(a<=i),dp_i|=(dp_{i-b}==0)$
由于 $b$ 最多是64，所以 $d p$ 数组可以滚动在65位之内，复杂度是 $O (规则数 * 石子数)$
将转移优化成位运算，65位dp数组压成一个 $u l l$ 的数，每一位对应的是当前的 $i$ 减去 $b$ ，这个 $b$ 就是第 $b$ 位，复杂度 $O (石子数)$

Code：

暴力
#pragma GCC optmize("-Ofast")
#include <bits/stdc++.h>
#define maxn 1010
#define Ull unsigned long long
using namespace std;
int n, m, a[maxn], b[maxn], dp[1010];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

int main(){
	freopen("stone.in", "r", stdin);
	freopen("stone1.out", "w", stdout);
	n = read(), m = read();
	for (int i = 1; i <= n; ++i) a[i] = read(), b[i] = read();
	for (int i = 1; i <= n; ++i)
		for (int j = i + 1; j <= n; ++j)
			if (a[i] > a[j]) swap(a[i], a[j]), swap(b[i], b[j]);
	for (int i = 1; i <= m; ++i){
		int now = i % 65;
		dp[now] = 0;
		for (int j = 1; j <= n; ++j)
			if (i >= a[j]) dp[now] |= !dp[(i - b[j]) % 65]; else break;
	} 
	puts(dp[m % 65] ? "Win" : "Loss");
	return 0;
}

正解
#include <bits/stdc++.h>
#define maxn 1010
#define Ull unsigned long long
using namespace std;
int n, m, a[maxn], b[maxn];
Ull status, trans;
bool win;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

int main(){
	freopen("stone.in", "r", stdin);
	freopen("stone.out", "w", stdout);
	n = read(), m = read();
	for (int i = 0; i < n; ++i) a[i] = read(), b[i] = read();
	for (int i = 0; i < n; ++i)
		for (int j = i + 1; j < n; ++j)
			if (a[i] > a[j]) swap(a[i], a[j]), swap(b[i], b[j]);
	status = ~0ull ^ 1, trans = 0;
	for (int i = 1, j = 0; i <= m; ++i){
		while (j < n && a[j] == i) trans |= 1ull << (b[j++] - 1);
		win = ~status & trans, status = status << 1 | win;
	}
	puts(win ? "Win" : "Loss");
	return 0;
}