LY1371 [ 20231007 NOIP 模拟赛 T0 ] 十一之争

题意

给定一个长度为 \(n\) 的数字串 \(s\) 和只包含 yo 的字符串 \(t\)，yoimiya 会和 oimiya 玩 \(n\) 轮游戏，初始有一个数字串 \(x\) 为 \(0\)，每次：

• 如果 \(t_i\) 是 y 则是 yoimiya 操作，如果是 o 则是 oimiya 操作。
• 每次操作：将 \(s_i\) 或者 \(0\) 加入 \(x\) 的末尾。

如果最后 \(x\) 是 \(11\) 的倍数，那么 yoimiya 获胜，否则 oimiya 获胜。

假设两人都是绝顶聪明的，那么最后谁会获胜？

Sol

简单博弈论，考虑博弈 dp。

\(f_{ij}\) 表示第 \(i\) 次操作，当前 \(x mod 11 = j\) 是否获胜。

转移显然是 trivial 的，\(O(n)\)。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <ctime>
#define int long long
using namespace std;
/* #ifdef ONLINE_JUDGE */

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

/* #endif */
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
string read_() {
	string ans;
	char c = getchar();
	while (c < '0' || c > '9')
		c = getchar();
	while (c >= '0' && c <= '9') {
		ans += c;
		c = getchar();
	}
	return ans;
}
string read__() {
	string ans;
	char c = getchar();
	while (c < 'a' || c > 'z')
		c = getchar();
	while (c >= 'a' && c <= 'z') {
		ans += c;
		c = getchar();
	}
	return ans;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}

const int N = 1e6 + 5;
array <int, N> isl;
array <array <int, 12>, N> f;

string s1, s2;
bool dfs(int step, int sum, int n) {
	if (~f[step][sum]) return f[step][sum];
	if (step == n) {
		if (!sum) return true;
		else return false;
	}
	bool tp1 = dfs(step + 1, (sum + isl[step + 1]) % 11, n),
		tp2 = dfs(step + 1, sum, n);
	if (s2[step + 1] == 'y')
		return f[step][sum] = (tp1 || tp2);
	else
		return f[step][sum] = (tp1 && tp2);
}
signed main() {
	freopen("yo.in", "r", stdin);
	freopen("yo.out", "w", stdout);
	int n = read();
	s1 = " " + read_(), s2 = " " + read__();
	array <int, 12> tp;
	tp.fill(-1);
	f.fill(tp);
	int idx = 1;
	for (int i = n; i; i--) {
		isl[i] = (s1[i] - '0') * idx % 11;
		idx = idx * 10 % 11;
	}
	if (dfs(0, 0, n))
		puts("yoimiya");
	else
		puts("oimiya");
	return 0;
}