题解：P7387 「EZEC-6」象棋

· · 题解

盯死这道题目做了，我还不信我这种爵士豪猫想不出来了！

模分阶段

5 分做法

额，这可能是给连暴力枚举模拟也不会的同学写的吧？打表输出，不然感觉没有别的做法只能拿 5 分了。

string ans(string t,ll n)
{
    string win="WIN";
    string tie="TIE";
    string tai="LOSE";//汰！
    if(n==1)
    {
        if(t=="1") return win;
        else return tai;
    }
    else if(n==2)
    {
        if(t=="11") return win;
        if(t=="00") return tai;
        return tie;
    }
    else
    {
        //001 110 100 011
        if(t=="111") return win;
        if(t=="000") return tai;
        if(t=="101") return win;
        if(t=="010") return tai;
        //这里才开始有真正的吃子环节
        //顺便分析一下所有可能的行动
        if(t=="001") return tie;//10-
        if(t=="011") return win;//11-
        if(t=="100") return tie;//-01
        if(t=="110") return win;//-11
        //对手的行动对照一下就可以
    }
}

15 分 and 30 分

暴力 DFS 即可，对于 n \le 15 的点看似会炸掉，实际上用二进制存储可以的行动就行了。

至于 DFS 代码……喵的写 WA 了。

所以我去想正解去了，毕竟后面的点都差不多了。

正解

由于 \sum n \le 10^7，考虑线性做法。

再由于是博弈论标签进行一番喵喵博弈。

首先，当红色棋子数量大于黑色棋子数量的时候，你叫我怎么输！ 红色显然必胜。

反过来想一下，开局红色吃一个棋子，之后就是黑色视角，所以此时黑色棋子大于红色棋子数量时，你叫我怎么赢？ 红色显然必输。

上述的数学化表达：

假设开局红色棋子数量为 Q，黑色棋子数量为 R（我也不知道为什么变量名长这样）。

Ans = \begin{cases} WIN & Q>R \\ LOSE & Q+1<R \\ ? & Q \le R \le Q+1 \end{cases}

那就继续分讨喵。

Q=R 时

这个时候由于红色先手，再怎么样也不可能输掉，结局只有可能是胜利或者平局。

然后黑色肯定不想输嘛（不要小看我获胜的决心口牙！）所以红色获胜的可能只有在自己操作完之后黑色无法操作才可以了。

然后黑色无法操作的片段很少，枚举一下。

结果发现只有一种片段。（对于一种的定义：经过反转之后也不完全相同的片段，并且没有包含关系。）

1100

这种情况假如周围有棋子的话得是这样：

10 1100 01

两侧都是可有可无的。

所以黑色肯定不可能造就这个局面，上一步肯定会避开，所以这种情况出现只有可能是开局就刷出来这种局面。

那么结论：除非开局是这种特殊情况使得红色胜利，否则必定平局。

Q+1=R 时

有点经验的都看出来吧，假如开局红色无法操作的话，红色输，否则就是前面 Q=R 但是红黑换位了。（1 和 0 换位？）

那么结论：除非开局红色无法行动导致失败，否则必定平局。

做法见代码：

void solve()
{
    ll n;
    cin >> n;
    vector<ll> pos(n+10);
    pos[0]=-1;
    pos[n+1]=pos[n+2]=pos[n+3]=-1;
    string s;
    cin >> s;
    ll Q=0;
    for(ll i=1;i<=n;++i)
    {
        pos[i]=(s[i-1]=='1');
        Q+=(pos[i]==1);
        //统计数量
    }
    ll R=n-Q;
    if(Q>R)
    {
        cout << "WIN" << endl;
        return;
    }
    if(Q<=R-2)
    {
        cout << "LOSE" << endl;
        return;
    }
    if(Q==R)
    {
        ll ft=0;//第一个红色相邻对的起始下标，0 表示没有
        ll ct=0;//黑色相邻对的总个数
        //扫描所有相邻对，定位关键的红对，统计黑对
        for(ll i=1;i<=n-1;++i)
        {
            if(pos[i]==pos[i+1])//找到一对相邻同色
            {
                if(ft && pos[i]==1)//遇到第二个红对
                {
                    cout << "TIE" << endl;//多个红对，平局
                    return;
                }
                else if(pos[i]==1)//是第一个红对
                {
                    ft=i;
                }
                if(!pos[i])//黑色
                {
                    ct++;
                }
            }
        }
        //没有任何红色相邻对，平局
        if(!ft)
        {
            cout << "TIE" << endl;
            return;
        }
        if((ft==3 && pos[1]==pos[2]) || (ft==n-3 && pos[n-1]==pos[n]))
        {
            cout << "WIN" << endl;
            return;
        }
        //这种结构下红方一步吃子后，黑方被黑炮/空位隔死，无棋可动
        if(ct==2 && ((ft>3 && !pos[ft-1] && !pos[ft-2] && !pos[ft-3]) ||
                     (ft<=n-4 && !pos[ft+2] && !pos[ft+3] && !pos[ft+4])))
        {
            cout << "WIN" << endl;
            return;
        }
        //其余保平
        cout << "TIE" << endl;
        return;
    }
    //剩下一种可能寻找可以行动的地点
    for(ll i=1;i<=n-1;++i)
    {
        if(pos[i]==pos[i+1])
        {
            cout << "TIE" << endl;
            return;
        }
    }
    cout << "LOSE" << endl;
}
//憎しみさん、またよろしくね
//誰も 誰からも愛されなくていいね
//ノドの果てにのさばる
//濁りのない澄んだドロドロに
//塗れている100の中
//さもしい幸せが今を壊さぬように
//余りの1を殺す
//罪でもいいよ じゃあねさよなら

总结：简单的结论题。