蓝桥杯国赛

admin管理员组

文章数量:1794759

蓝桥杯国赛

平局博弈

文章目录

• 平局博弈
• • ~~未优化，只能过20%数据~~
  • 记忆化DFS

1. 模拟博弈过程
2. 当我们选择一个*为，填入L或O时。
   递归函数发f()，对于当前调用该函数的人来说，是做最优决策的。
   例如，当试探到一种输的局面时，它依旧会去试探对于当前调用者平局或者胜利的局面。
   当试探到平局的局面，它依旧会去试探是否存在胜利的局面。
   当试探到胜利的局面时，直接返回胜利即可。

未优化，只能过20%数据

import java.util.Scanner;public class 填字母游戏 {public static void main(String[] args) {// TODO Auto-generated method stubScanner sc = new Scanner(System.in);int n = sc.nextInt();sc.nextLine();while (n-- != 0) {char[] chs = sc.nextLine().toCharArray();int ans = dfs(chs);System.out.println(ans);}}private static int dfs(char[] chs) {String s = new String(chs);if (s.contains("LOL"))return -1;if (!s.contains("*"))return 0;int ans = -1;int ping = -1;for (int i = 0; i < s.length(); i++) {// 选择落子的位置if (chs[i] == '*') {// 试填Lchs[i] = 'L';int temp = dfs(chs);if (temp == -1) {chs[i] = '*';return 1;} else if (temp == 0)ping = 1;elseans = -1;// 试填Ochs[i] = 'O';temp = dfs(chs);if (temp == -1) {chs[i] = '*';return 1;} else if (temp == 0)ping = 1;elseans = -1;chs[i] = '*';}}if (ping == 1)return 0;return ans;}}

记忆化DFS

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class 填字母游戏 {static Map<String, Integer> map = new HashMap<String, Integer>();public static void main(String[] args) {// TODO Auto-generated method stubScanner sc = new Scanner(System.in);int n = sc.nextInt();sc.nextLine();while (n-- != 0) {char[] chs = sc.nextLine().toCharArray();int ans = dfs(chs);System.out.println(ans);}}private static int dfs(char[] chs) {String s = toS(chs);if (map.containsKey(s))return map.get(s);if (s.contains("LOL"))return -1;if (!s.contains("*"))return 0;int ans = -1;int ping = -1;for (int i = 0; i < s.length(); i++) {// 选择落子的位置if (chs[i] == '*') {// 试填Lchs[i] = 'L';int temp = dfs(chs);map.put(toS(chs), temp);if (temp == -1) {chs[i] = '*';return 1;} else if (temp == 0)ping = 1;elseans = -1;// 试填Ochs[i] = 'O';temp = dfs(chs);map.put(toS(chs), temp);if (temp == -1) {chs[i] = '*';return 1;} else if (temp == 0)ping = 1;elseans = -1;chs[i] = '*';}}if (ping == 1) {map.put(s, 0);return 0;}map.put(s, ans);return ans;}private static String toS(char[] chs) {StringBuilder sb = new StringBuilder();for (int i = 0; i < chs.length; i++) {sb.append(chs[i]);}return sb.toString();}}

本文标签： 蓝桥杯国赛