网站建设中图标,东道网站建设,自建网站费用,犀浦网站建设Digital Deletions
思路
一道博弈论的题目#xff0c;考虑到题目所给的范围是字符长度为1−61- 61−6#xff0c;所以我们可以考虑暴力打表出10610 ^ 6106内的所有状态#xff0c;
确定基本的两个状态sg[0]1[先手胜],sg[1]0[后手胜]sg[0] 1[先手胜], sg[1] …Digital Deletions
思路
一道博弈论的题目考虑到题目所给的范围是字符长度为1−61- 61−6所以我们可以考虑暴力打表出10610 ^ 6106内的所有状态
确定基本的两个状态sg[0]1[先手胜],sg[1]0[后手胜]sg[0] 1[先手胜], sg[1] 0[后手胜]sg[0]1[先手胜],sg[1]0[后手胜]然后再考虑其他的情况。
我们考虑单独改变某一位假设当前枚举到第iii位那么枚举它的所有情况0−num[i]−10 - num[i] - 10−num[i]−1
计算改变后它的sgsgsg函数因为这个数是变小的所以它之前的sgsgsg函数已经全部求出来了
这个时候如果改变后的状态是必败状态我们就可以认定这个状态为必胜状态了
反之我们应该继续枚举它的所有状态直到找到这个状态下的必胜或者枚举完所有状态还是必败。
特殊情况
当这一位是0时我们只能删去这一位所以我们考虑如果它前面的数字构成的是必败的话那么就可以确定这个数是必胜状态当前到最高位时注意这一位不能变成0因为它的下一个状态永远是必败状态对这个数来说没意义。
开局特殊情况
最高位一开始就是0时我们不用去用sg函数计算胜负直接特判必胜。
代码
/*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 pairint, 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;
}
