【題目敘述】https://codeforces.com/contest/1194/problem/D
【解題想法】Nim，小數據 DP 找規律
- 本題的數據範圍很大，0 ≤ n ≤ 109, 3 ≤ k ≤ 109
- 用 top-down DP 會 MLE。
- 先利用小數據 DP 找規律。
#include <iostream>
#include <cstring>
using namespace std;
int T, n, k;
int dp[25];
int solve(int x){
if (x < 0) return 0;
if (dp[x] != 0) return dp[x];
int mn = 0;
mn = min(mn, solve(x-1));
mn = min(mn, solve(x-2));
mn = min(mn, solve(x-k));
if (mn == -1) return dp[x] = 1;
else return dp[x] = -1;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> T;
while (T--){
cin >> n >> k;
memset(dp, 0, sizeof(dp));
solve(n);
for (int i=0; i<=n; i++){
cout << dp[i] << ' ';
}
cout << '\n';
}
return 0;
}
- 觀察小數據執行的結果（下圖），
- 當 k 非 3 的倍數時，只要 n 是 3 的倍數，先手輸。
- 當 k 是 3 的倍數時，
- (I) 如果 n 是 (k + 1) 的倍數（n % (k + 1) = 0），先手輸。
- (II) n % (k + 1) 不等於 k，但是 3 的倍數，先手輸。
- 結合 (I) (II)， ( n % (k + 1) ) % 3 == 0 && n % (k + 1) != k，先手輸。
#include <iostream>
#include <bitset>
using namespace std;
int t, n, k;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while (t--){
cin >> n >> k;
if (k % 3 == 0){
n %= (k+1);
if (n % 3 == 0 && n != k) cout << "Bob\n";
else cout << "Alice\n";
}
else {
if (n % 3 == 0) cout << "Bob\n";
else cout << "Alice\n";
}
}
}