题意分析

本题描述了一个称为"三角战争"的双人博弈游戏，其核心规则可以形式化表示为：

1. 游戏状态：设$G=(V,E)$为一个三角网格图，其中：

   • $V$为顶点集
   • $E$为边集，初始时所有边均为虚线（未填充）

2. 玩家轮流：

   • 玩家$A$和$B$轮流选择$e \in E$进行填充
   • 每次填充需满足$e \notin E_{filled}$

3. 得分规则：

   • 若填充$e$后形成$k$个新三角形$\Delta_1,...,\Delta_k$，则：$$\text{score}(player) += k$$ $$\text{获得额外回合}$$

4. 终止条件：

   $$\text{当}|E_{filled}|=|E|\text{时游戏结束}$$

5. 胜负判定：

   $$\text{winner} = \begin{cases} A & \text{if } s_A > s_B \\ B & \text{otherwise} \end{cases} $$

解题思路

1. 游戏建模

使用以下数据结构表示游戏状态：

• 边状态数组$f[18]$（$|E|=18$）
• 三角形集合$a[9][3]$（9个三角形，每个由3条边组成）

2. 关键函数

1. 边查找函数：

   $$\text{getid}(x,y): \text{返回边}(x,y)\text{的索引}$$

2. 三角形计数函数：

   $$\text{cal}() = \sum_{i=0}^8 [f[a[i][0]] \land f[a[i][1]] \land f[a[i][2]]] $$

3. 博弈树搜索

采用带Alpha-Beta剪枝的Minimax算法：

• Max节点（A的回合）：

  $$\text{maxdfs}(\beta,a,b) = \max_{\text{valid moves}} \text{mindfs}(\alpha,a,b) $$

• Min节点（B的回合）：

  $$\text{mindfs}(\alpha,a,b) = \min_{\text{valid moves}} \text{maxdfs}(\beta,a,b) $$

• 剪枝条件：

  $$\alpha \geq \beta \Rightarrow \text{终止当前分支搜索}$$

4. 胜负判定

$$\text{result} = \begin{cases} \text{inf} & \text{A必胜} \\ \text{-inf} & \text{B必胜} \end{cases} $$

复杂度分析

• 状态空间：$O(2^{18}) = O(262,144)$
• 时间复杂度：$O(b^d)$，其中$b\approx18$（分支因子），$d\approx18$（最大深度）
• 空间复杂度：$O(d)$（DFS栈深度）

解决代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<queue>
#define MOD 100003
#define inf 2147483640
#define LL long long
#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
using namespace std;
///           0     1     2     3     4     5     6     7     8     9     10    11   12    13     14     15    16    17
int e[][2]={{1,2},{1,3},{2,4},{2,5},{2,3},{3,5},{3,6},{4,5},{4,7},{4,8},{5,6},{5,8},{5,9},{6,9},{6,10},{7,8},{8,9},{9,10}};
int a[][3]={{0,1,4},{2,3,7},{3,4,5},{5,6,10},{8,9,15},{7,9,11},{11,12,16},{10,12,13},{13,14,17}};
int n,cnt,f[20];
 
int getid(int x,int y) {
    for (int i=0;i<18;i++)
        if ((e[i][0]==x && e[i][1]==y) || (e[i][0]==y && e[i][1]==x)) return i;
    return -1;
}
int cal() {
    int tt=0;
    for (int i=0;i<9;i++) if (f[a[i][0]] && f[a[i][1]] && f[a[i][2]]) tt++;
    return tt;
}
int maxdfs(int beta,int a,int b);
int mindfs(int alpha,int a,int b) {
    if (cnt==18) return a>b ? inf : -inf;
    if (a>=5) return inf;
    if (b>=5) return -inf;
    int tmp=inf;
    for (int i=0;i<18;i++) if (!f[i]) {
            f[i]=1;cnt++;
            int c=cal();
            if (c>a+b) tmp=min(mindfs(alpha,a,c-a),tmp);
            else tmp=min(maxdfs(tmp,a,b),tmp);
            f[i]=0;cnt--;
            if (tmp<=alpha) return tmp;
        }
    return tmp;
}
int maxdfs(int beta,int a,int b) {
    if (cnt==18) return a>b ? inf : -inf;
    if (a>=5) return inf;
    if (b>=5) return -inf;
    int tmp=-inf;
    for (int i=0;i<18;i++) if (!f[i]) {
            f[i]=1;cnt++;
            int c=cal();
            if (c>a+b) tmp=max(maxdfs(beta,c-b,b),tmp);
            else tmp=max(mindfs(tmp,a,b),tmp);
            f[i]=0;cnt--;
            if (tmp>=beta) return tmp;
        }
    return tmp;
}
int main() {
    int T,t=0;scanf("%d",&T);
    while (T--) {
        scanf("%d",&n);
        memset(f,0,sizeof(f));
        cnt=n;
        int w=0,ans[2]={0,0};
        for (int x,y,i=1;i<=n;i++) {
            scanf("%d%d",&x,&y);
            int id=getid(x,y);
            f[id]=1;
            int c=cal();
            if (c>ans[0]+ans[1]) ans[w]+=c-ans[0]-ans[1];
            else w^=1;
        }
        int res=0;
        if (!w) res=maxdfs(inf,ans[0],ans[1]);
        else res=mindfs(-inf,ans[0],ans[1]);
        printf("Game %d: %c wins.\n",++t,res==inf ? 'A' : 'B');
    }
    return 0;
}

代码解释

1. 输入处理：
   • 读取测试用例数量 T。
   • 对于每个测试用例，读取已进行的移动序列，初始化边线填充状态 f。
2. 游戏状态更新：
   • 根据移动序列更新 f，计算当前完成的三角形数量 c。
   • 如果 c 增加，当前玩家继续行动；否则切换玩家。
3. 博弈树搜索：
   • maxdfs 和 mindfs 分别模拟 A 和 B 的最优策略。
   • Alpha-Beta 剪枝优化搜索过程。
4. 胜负判断：
   • 根据搜索结果输出获胜玩家。