【題解】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;
}