【博弈+dfs】Game with a Strip URAL - 2104

矫情吗；* 2022-06-01 10:40 155阅读 0赞

Think:  
1知识点：【博弈+dfs】  
2题意：第1行输入长方形纸条每一面含有的字母数量，第二行输入长方形纸条正面的字母，第三行输入长方形反面的字母，字母只含有A、B两种，分别代表Alice和Bob。博弈游戏开始，Alice先手，Bob后手。对于每个状态，若长方形纸条某一面字母数量为奇数，则认为结束游戏，游戏平局，除此之外，若不能分成胜负(两面全为A则Alice赢、两面全为B则Bob赢)，则由场次选手选择折叠方向，使得某一面成为新的正反两面。  
3解题思路：写出对应场次必胜态、必败态、平态+dfs递归判断  
Alice场次:

Bob场次:

[vjudge题目链接][vjudge]  
以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    int rec[1004014];
    char st[1004014];
    
    int dfs(int l, int r, int e);
    
    int main(){
      int n, i;
      while(~scanf("%d", &n)){
        scanf("%s", st+1);
        scanf("%s", st+1+n);
        n <<= 1;
        rec[n] = n;
        for(i = n-1; i >= 1; i--){
          if(st[i] == st[i+1]) rec[i] = rec[i+1];
          else rec[i] = i;
        }
        int t = dfs(1, n, 0);
        if(t == 0) printf("Draw\n");
        else if(t == 1) printf("Alice\n");
        else if(t == 2) printf("Bob\n");
      }
      return 0;
    }
    int dfs(int l, int r, int e){
      if(rec[l] >= r){
        if(st[l] == 'A') return 1;
        if(st[l] == 'B') return 2;
      }
      if(((r-l+1)>>1)&1) return 0;
      int mid = (l+r)>>1;
      int t1 = dfs(l, mid, e^1);
      int t2 = dfs(mid+1, r, e^1);
      if(e == 0){
       /*Alice场次*/
        if(t1 == 1 || t2 == 1) return 1;
        else if(t1 == 2 && t2 == 2) return 2;
        else return 0;
      }
      else {
       /*Bob场次*/
        if(t1 == 2 || t2 == 2) return 2;
        else if(t1 == 1 && t2 == 1) return 1;
        else return 0;
      }
    }

[vjudge]: https://vjudge.net/problem/URAL-2104