本蒟蒻的第二篇题解！

题目传送门

P2953

前置芝士（博弈论结论）

当某种状态的后继状态都是必胜状态时，该状态为必败状态；

否则，该状态为必胜状态。

原因很简单，因为，如果是第一种情况，你无论执行什么操作，都会变成对面操作的必胜状态，对面必胜，你必败。

否则，你只要能把当前状态变成对面操作的必败状态，则对面必败，你必胜。

解法

很多人都认为这题不能用 DFS，但是，DFS 不行，我们可以用记忆化 DFS！至于怎么用，就需要搭配上博弈论，食用更放心。（注释写在代码里）

代码

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define str string

using namespace std;

int t, n;
bool win[1000001], vis[1000001]; //状态记忆化
int get_digit(int n, int x){ //得到数字的某一位
	return int(n / pow(10, x - 1)) % 10;
}
int get_how_many_digits(int x){ //得到数字的位数
	int ans = 0;
	while (x > 0){
		x /= 10;
		ans ++;
	}
	return ans;
}
bool solve(int x){ //dfs
	if (vis[x]) return win[x]; //记忆化
	int hmd = get_how_many_digits(x), maxn = 0, minn = 10, gd;
	for (int i = 1;i <= hmd;i ++){
		gd = get_digit(x, i);
		if (gd > 0){
			maxn = max(gd, maxn);
			minn = min(gd, minn);
		}
	} //枚举最大最小数
	if (solve(x - maxn) && solve(x - minn)) win[x] = false; //博弈论定理运用
	else win[x] = true;
	vis[x] = true;
	return win[x]; //记忆化
}
int main(){
	cin >> t;
	win[0] = false, vis[0] = true; //初始化（0是必败状态，vis[i]代表第i项是否被设置过）
	for (int i = 0;i < t;i ++){
		cin >> n; //输入初始数
		if (solve(n)) cout << "YES\n";
		else cout << "NO\n"; //输出
	}
}

成功
AC

完结撒花