题解：P17092 [ICPC 2017 Qingdao R] Battle in Two Pairs of Heroes

· · 题解

题意简述

Alice 和 Bob 各有两名英雄，并轮流让存活英雄攻击对方。双方均采用最优策略。分别考虑两人先手，判断 Alice 必胜、Bob 必胜或先手方必胜。

解题思路

用状态 (a_1,a_2,b_1,b_2,t) 表示四名英雄的当前生命值与行动方。死亡英雄的生命值统一记为 0。设 dfs 表示 Alice 能否从当前状态必胜。

若 Bob 的两名英雄均死亡，返回真；若 Alice 的两名英雄均死亡，返回假。Alice 行动时对后继状态取逻辑或，Bob 行动时对后继状态取逻辑与。每次行动都会使至少一个生命值严格减小，因此状态转移无环，可以记忆化搜索。

每个状态至多有 4 种攻击分配。若一种分配对两名敌人造成的伤害均不大于另一种分配，则前者不会更优，可以直接删去。

直接搜索仍可能访问大量状态。将生命值转换为：

z=(a_1,a_2,99-b_1,99-b_2)

任一坐标增大都只会让局面对 Alice 更有利。Alice 的行动在较有利状态中能得到不弱的后继。对 Bob 的任一行动，较不利状态也有不强的对应后继。因此，固定另外三个坐标与行动方后，胜负关于剩余坐标单调。较小的一段必败，较大的一段必胜。对每条这样的一维序列，记录已知必胜坐标的最小值。再记录已知必败坐标的最大值加一，即可直接判定落在已知区域内的状态。边界只由完整搜索出的状态更新，避免循环推导。

分别计算 Alice 先手与 Bob 先手时的结果。两次均为 Alice 必胜则输出 Alice wins，两次均为 Bob 必胜则输出 Bob wins，否则输出 It depends。

设完整搜索的状态数为 S。每个状态只处理常数种转移，期望时间复杂度为 O(S)。单调性边界占用 O(100^3) 空间，记忆化表占用 O(S) 空间。

参考代码

#include <bits/stdc++.h>
using namespace std;

using uc=unsigned char;
using ui=unsigned int;
const int M=1000005;
int d[2][2][2];
uc mn[2][4][M],mx[2][4][M];
unordered_map<ui,char> mp;
int cut(int z[4],int p)
{
    int res=0;
    for(int i=0;i<4;i++)if(i!=p)res=res*100+z[i];
    return res;
}
int ask(int a1,int a2,int b1,int b2,int t)
{
    int z[4]={a1,a2,99-b1,99-b2};
    for(int i=0;i<4;i++)
    {
        int s=cut(z,i);
        if(z[i]>=mn[t][i][s])return 1;
        if(z[i]<mx[t][i][s])return 0;
    }
    return -1;
}
void upd(int a1,int a2,int b1,int b2,int t,bool w)
{
    int z[4]={a1,a2,99-b1,99-b2};
    for(int i=0;i<4;i++)
    {
        int s=cut(z,i);
        if(w)mn[t][i][s]=min(mn[t][i][s],uc(z[i]));
        else mx[t][i][s]=max(mx[t][i][s],uc(z[i]+1));
    }
}
void add(int z[4][2],int &cnt,int x,int y)
{
    z[cnt][0]=x;
    z[cnt][1]=y;
    cnt++;
}
bool dfs(int a1,int a2,int b1,int b2,int t)
{
    if(!b1&&!b2)return 1;
    if(!a1&&!a2)return 0;
    ui key=a1|a2<<7|b1<<14|b2<<21|t<<28;
    auto it=mp.find(key);
    if(it!=mp.end())return it->second-1;
    int tmp=ask(a1,a2,b1,b2,t);
    if(tmp!=-1)return tmp;
    int cnt=0;
    int z[4][2];
    bool s0=(t?b1:a1)>0,s1=(t?b2:a2)>0,e0=(t?a1:b1)>0,e1=(t?a2:b2)>0;
    if(s0&&s1)
    {
        if(e0&&e1)
        {
            add(z,cnt,d[t][0][0]+d[t][1][0],0);
            add(z,cnt,0,d[t][0][1]+d[t][1][1]);
            add(z,cnt,d[t][0][0],d[t][1][1]);
            add(z,cnt,d[t][1][0],d[t][0][1]);
        }
        else if(e0)add(z,cnt,d[t][0][0]+d[t][1][0],0);
        else if(e1)add(z,cnt,0,d[t][0][1]+d[t][1][1]);
    }
    else
    {
        int p=s0?0:1;
        if(e0)add(z,cnt,d[t][p][0],0);
        if(e1)add(z,cnt,0,d[t][p][1]);
    }
    int tot=0;
    int nz[4][2];
    for(int i=0;i<cnt;i++)
    {
        bool bad=0;
        for(int j=0;j<cnt;j++)
        {
            if(j!=i&&z[j][0]>=z[i][0]&&z[j][1]>=z[i][1])
            {
                if(z[j][0]>z[i][0]||z[j][1]>z[i][1]||j<i)bad=1;
            }
        }
        if(!bad)
        {
            nz[tot][0]=z[i][0];
            nz[tot++][1]=z[i][1];
        }
    }
    cnt=tot;
    for(int i=0;i<cnt;i++)
    {
        z[i][0]=nz[i][0];
        z[i][1]=nz[i][1];
    }
    bool res=t;
    for(int i=0;i<cnt;i++)
    {
        int na1=a1,na2=a2,nb1=b1,nb2=b2;
        if(!t)
        {
            nb1=max(0,b1-z[i][0]);
            nb2=max(0,b2-z[i][1]);
        }
        else
        {
            na1=max(0,a1-z[i][0]);
            na2=max(0,a2-z[i][1]);
        }
        bool cur=dfs(na1,na2,nb1,nb2,t^1);
        if(cur!=t)
        {
            res=cur;
            break;
        }
    }
    mp[key]=res+1;
    upd(a1,a2,b1,b2,t,res);
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int a1,a2,b1,b2;
        cin>>a1>>a2>>b1>>b2;
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)cin>>d[0][i][j];
        }
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)cin>>d[1][i][j];
        }
        mp.clear();
        mp.reserve(1<<18);
        memset(mn,100,sizeof mn);
        memset(mx,0,sizeof mx);
        bool x=dfs(a1,a2,b1,b2,0),y=dfs(a1,a2,b1,b2,1);
        string ans;
        if(x&&y)ans="Alice wins";
        else if(!x&&!y)ans="Bob wins";
        else ans="It depends";
        cout<<ans<<'\n';
    }
    return 0;
}