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

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

有两种做法

• 暴力dp：$d{p}_i$表示$i$是否必胜，对于一个规则$(a,b)(a<=i),d{p}_i|=(d{p}_{i-b}==0)$
  由于$b$最多是64，所以$dp$数组可以滚动在65位之内，复杂度是$O(规则数\ast 石子数)$
• 将转移优化成位运算，65位dp数组压成一个$ull$的数，每一位对应的是当前的$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;
}