COCI 2021-2022 #1 - Kamenčići 题解

本文主要是介绍COCI 2021-2022 #1 - Kamenčići 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

给定长为 $n$ 一个石子序列，其中的石子有红色和蓝色，可以从左边和右边取。

两个人开始取石子，谁先取到 $k$ 个石子就输，求先手是否必胜。

思路

$n$ 比较小，考虑记搜。

设 $f_{l,r,k_1,k_2}$ 表示现在剩的石子序列是 $l$ 到 $r$，先手再取 $k_1$ 个红色石子就输了，后手再取 $k_2$ 个红色石子就输了，此时先手是否必胜。

然后直接记搜即可。

看看时间复杂度，看状态似乎是 $O(n^2\cdot k^2)$ 的，但其实你确定 $l$，$r$，$k_1$ 即可确定 $k_2$，所以时间复杂度是 $O(n^3)$ 的。

代码

#include <bits/stdc++.h>
using namespace std;
int n, k;
char s[405];
map<pair<int, int>, int> bz[355][355];
int dfs(int l, int r, int x1, int x2) {if (x1 == 0)return 2;if (x2 == 0)return 1;if (bz[l][r][{ x1, x2 }])return bz[l][r][{ x1, x2 }];int t1 = dfs(l, r - 1, x2, x1 - (s[r] == 'C')), t2 = dfs(l + 1, r, x2, x1 - (s[l] == 'C'));if (t1 == 2 || t2 == 2)bz[l][r][{ x1, x2 }] = 1;elsebz[l][r][{ x1, x2 }] = 2;return bz[l][r][{ x1, x2 }];
}
int main() {scanf("%d%d", &n, &k);scanf("%s", s + 1);if (dfs(1, n, k, k) == 1)printf("DA");elseprintf("NE");return 0;
}

这篇关于COCI 2021-2022 #1 - Kamenčići 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---