【題解】CSP-S2019初賽：取石子

(取石子)Alice和Bob兩個人在玩取石子游戲，他們制定了nn條取石子的規則，第ii條規則為：如果剩余石子的個數大于等于a[i]a[i]且大于等于b[ilb[il， 那么他們可以取走b[i]b[i]個石子，他們輪流取石子，如果輪到某個人取石子， 而他無法按照任何規則取走石子，那么他就輸了，一開始石子有mm個，請問先取石子的人是否有必勝的方法？

有兩種做法

• 暴力dp： d p i dp_i dpi?表示 i i i是否必勝，對于一個規則 ( a , b ) ( a < = i ) , d p i ∣ = ( d p i ? b = = 0 ) (a,b)(a<=i),dp_i|=(dp_{i-b}==0) (a,b)(a<=i),dpi?∣=(dpi?b?==0)
  由于 b b b最多是64，所以 d p dp dp陣列可以滾動在65位之內，復雜度是 O ( 規 則 數 ? 石 子 數 ) O(規則數*石子數) O(規則數?石子數)
• 將轉移優化成位運算，65位dp陣列壓成一個 u l l ull ull的數，每一位對應的是當前的 i i i減去 b b b，這個 b b b就是第 b b b位，復雜度 O ( 石 子 數 ) O(石子數) 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;
}