Digital Deletions

思路

一道博弈論的題目，考慮到題目所給的范圍是字符長度為$1?>6$，所以我們可以考慮暴力打表出$10^6$內(nèi)的所有狀態(tài)，

確定基本的兩個(gè)狀態(tài)$sg[0]=1[先手勝],sg[1]=0[后手勝]$，然后再考慮其他的情況。

我們考慮單獨(dú)改變某一位，假設(shè)當(dāng)前枚舉到第$i$位，那么枚舉它的所有情況，$0?>num[i]?1$，

計(jì)算改變后它的$sg$函數(shù)，因?yàn)檫@個(gè)數(shù)是變小的所以它之前的$sg$函數(shù)已經(jīng)全部求出來了，

這個(gè)時(shí)候如果改變后的狀態(tài)是必?cái)顟B(tài)，我們就可以認(rèn)定這個(gè)狀態(tài)為必勝狀態(tài)了，

反之我們應(yīng)該繼續(xù)枚舉它的所有狀態(tài)，直到找到這個(gè)狀態(tài)下的必勝，或者枚舉完所有狀態(tài)還是必?cái)　?/p>

特殊情況：

• 當(dāng)這一位是0時(shí)，我們只能刪去這一位，所以我們考慮如果它前面的數(shù)字構(gòu)成的是必?cái)〉脑?#xff0c;那么就可以確定這個(gè)數(shù)是必勝狀態(tài)，
• 當(dāng)前到最高位時(shí)，注意這一位不能變成0，因?yàn)樗南乱粋€(gè)狀態(tài)永遠(yuǎn)是必?cái)顟B(tài)，對這個(gè)數(shù)來說沒意義。

開局特殊情況：

最高位一開始就是0時(shí)，我們不用去用sg函數(shù)計(jì)算勝負(fù)，直接特判必勝。

代碼

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h>#define mp make_pair #define pb push_back #define endl '\n' #define mid (l + r >> 1) #define lson rt << 1, l, mid #define rson rt << 1 | 1, mid + 1, r #define ls rt << 1 #define rs rt << 1 | 1using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii;const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }const int N = 1e6 + 10;int sg[N], n;char str[10];int get_sg(int x) {int temp = x, cnt = 0, num[10] = {0}, flag = 0;while(temp) {num[++cnt] = temp % 10;temp /= 10;}for(int i = 1; i <= cnt; i++) {if(num[i] == 0) {int k = 0;for(int j = cnt; j > i; j--) {k = k * 10 + num[j];}if(!sg[k]) {flag = 1;}}else {if(i == cnt) {for(int j = 1; j < num[i]; j++) {int p = j;for(int k = cnt - 1; k >= 1; k--) {p = p * 10 + num[k];}if(!sg[p]) {flag = 1;break;}}}else {for(int j = 0; j < num[i]; j++) {int p = 0;for(int k = cnt; k >= 1; k--) {if(k == i) {p = p * 10 + j;}else {p = p * 10 + num[k];}}if(!sg[p]) {flag = 1;break;}}}}if(flag) break;}return flag; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);sg[0] = 1, sg[1] = 0;for(int i = 2; i < N; i++) {sg[i] = get_sg(i);}while(scanf("%s", str + 1) != EOF) {if(str[1] == '0') {puts("Yes");continue;}n = strlen(str + 1);int ans = 0;for(int i = 1; i <= n; i++) {ans = ans * 10 + (str[i] - '0');}puts(sg[ans] ? "Yes" : "No");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的HDU 1404 Digital Deletions（博弈 + SG函数打表）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。