题解：P11526 [THUPC 2025 初赛] Imyourfan

fish_love_cat · 2025-01-27 21:53:01 · 题解

好久没有这么酣畅淋漓的分讨过了。依我看这坨仍是史中史。

上一次抑郁成这样还是这个。

错的点主要是细节不到位和复制导致的输出写错。

我的锅，我对不起队伍。

但咱就是说这什么运气一开赛就开这题创似了呢……

首先可以把 \texttt{X} 视作分割线，将原字符串砍成若干段不含 \texttt{X} 的字符串。

注意到卡片是一段一段取走的，所以对于一段连续的 \texttt{M\dots M} 或 \texttt{W\dots W} 可以直接压缩成为等价的 \texttt{M} 或 \texttt{W}。

对于处理后的字符串，我们发现两人轮流对其进行操作一个回合后，固定会消除一对 \texttt{MW} 或者 \texttt{WM}。

据此我们可以进一步转化：

• 形如 \texttt{MMM\dots M} 的字符串，进行一定消除后会变成 \texttt{M}。

• 形如 \texttt{WWW\dots W} 的字符串，进行一定消除后会变成 \texttt{W}。

• 形如 \texttt{MWM\dots W} 的字符串，进行一定消除后会变成 \texttt{MW}。

• 形如 \texttt{WMW\dots M} 的字符串，进行一定消除后会变成 \texttt{WM}。

• 形如 \texttt{MWM\dots WM} 的字符串，进行一定消除后会变成 \texttt{MWM}。

• 形如 \texttt{WMW\dots MW} 的字符串，进行一定消除后会变成 \texttt{WMW}。

然后分别统计六种字符串的数量，记为 a_0,a_1,a_2,a_3,a_4,a_5。

具体做法：

    for(int i=1;i<s.size();i++){
        if(s[i]=='X'){
            if(x.size()==0)continue;
            if(x[0]==x[x.size()-1]){
                if(x[0]=='M'&&x.size()==1)a[0]++;
                else if(x[0]=='M')a[4]++;
                else if(x.size()!=1)a[5]++;
                else a[1]++;
            }else{
                if(x[0]=='M')a[2]++;
                else a[3]++;
            }
            x="";
        }else if(s[i]!=s[i-1])x+=s[i];
    }

我们还要明确一下这些值的意义。

    int flc=min(a[0],a[1]);
    a[0]-=flc;
    a[1]-=flc;

我们令 a_0,a_1 重新赋值为处理后的结果。

那么接下来我们可以开始分讨了。

• 当 a_0\ne0 时：
• • 当 a_5<a_0+a_4 时，W 老师可以挖掉 a_4 中间的 \texttt{W}，增加 a_0 数量与 Menji 对耗，此时 Menji 最优解显然是消 a_0，所以最后局面会变成只剩余 a_0,a_5。由原式得 a_5<a_0，此时 W 老师不顾对方棋子硬吃 a_5 都能赢。答案为 Water。
  • 当 a_5=a_0+a_4 时：
  • • 当 a_4=0 时，原式可转化为 a_5=a_0，此时 W 老师先手，赢。答案仍为 Water。
  • 当 a_4=1 时，原式可转化为 a_5-1=a_0，当 a_0 消完后，会残留有 1 个 a_5。虽然仍为 W 老师先手，但此时只要 Menji 单取中间就赢了，W 老师被迫选择全吃平局。答案为 Draw。
  • 当 a_4>1 时，原式可转化为 a_5>a_0+1：
  • • 若仍旧按照上述方案实施，等到 a_0 消完后仍会残留有大量 a_5。此时虽仍为 W 老师先手，但只要 Menji 出手，W 老师立马被动，结局必输，而此时连平局的选择都没有。
    • 所以 W 老师要用新方案，不管 a_4 直接从头到尾将 a_5 整个拿掉。此时 Menji 显然还是会优先消 a_0。对于剩下的 a_4，如果分开拿 \texttt{M}，W 老师消完 a_5 若反将一军陷入被动的将会是 Menji。所以 Menji 也会整个拿。最后会刚好留下 1 个 a_4，此时 Menji 先手，最优解是全拿平局。答案为 Draw。
  • 当 a_5=a_0+a_4+1 时，一样不理 a_4，拿 a_5 直接爆，与上一段区别在于现在最后会留下的是 a_5，而先手是 W 老师。最优解一样是全拿。答案为 Draw。
  • 当 a_5>a_0+a_4+1 时，无论怎样，最后一定会出现如下局面：只剩下了若干 a_5，先手 Menji。W 老师显然是被压着打的死局。答案 Menji。
• 当 a_1\ne 0 时，我们可以先将 a_1 自减，然后先后手互换。也就是说我们完全可以将 Menji 和 W 老师互换身份了。那么关于答案的处理显然也是基本一致。然后我们继续分类讨论：
• • 当 a_1\ne 0 时，处理同上文 a_0\ne 0。注意互换身份，判断条件中先后手的相关数值也要记得更替。
  • 当 a_0=a_1=0 时，处理同下文 a_0=a_1=0。修改注意点同上。真的不是懒而是控制题解篇幅（）
• 当 a_0=a_1=0 时：
• • 当 a_4=a_5=0 时，那说明要么此时还剩了 a_2 或 a_3，要么就是前面第一轮纯种互爆清干净了。不管怎么样，肯定是后手来不及，顺出局先手必定领先一步。答案 Water。
  • 当 a_4>a_5 时，W 老师清完 a_5 后轮到她先手时一定还有 a_4 剩余，此时就可以把 Menji 压着打了。答案仍为 Water。
  • 当 a_4=a_5 时，W 老师清完以后，剩 Menji 和一个 a_4，Menji 一口闷，平。答案 Draw。
  • 当 a_4+1=a_5 时，Menji 清空 a_4 后，剩的变成了 W 老师和她的一只 a_5。W 老师也只好一口闷，也是平。答案又是 Draw。
  • 当 a_4+1<a_5 时，Menji 清空后，看着 W 老师和一群 a_5。W 老师在吃掉一个 a_5 后，还剩有一堆 a_5，陷入大被动成功被压着打了。答案 Menji。

分讨完成！

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
    string s;
    cin>>s;
    string x;
    x+=s[0];
    s+='X';
    if(x=="X")x="";
    int top=0;
    int a[6]={};//M W MW WM MWM WMW 
    for(int i=1;i<s.size();i++){
        if(s[i]=='X'){
            if(x.size()==0)continue;
            if(x[0]==x[x.size()-1]){
                if(x[0]=='M'&&x.size()==1)a[0]++;
                else if(x[0]=='M')a[4]++;
                else if(x.size()!=1)a[5]++;
                else a[1]++;
            }else{
                if(x[0]=='M')a[2]++;
                else a[3]++;
            }
            x="";
        }else if(s[i]!=s[i-1])x+=s[i];
    }
//  cout<<a[0]<<' '<<a[1]<<' '<<a[2]<<' '<<a[3]<<' '<<a[4]<<' '<<a[5]<<'\n';
    int flc=min(a[0],a[1]);
    a[0]-=flc;
    a[1]-=flc;
    if(a[0]){
        if(a[5]<a[0]+a[4]||a[5]==a[0]+a[4]&&a[4]==0){
            puts("Water");
            return;
        }else if(a[5]==a[0]+a[4]+1||a[5]==a[0]+a[4]){
            puts("Draw");
            return;
        }else{
            puts("Menji");
            return;
        }
    }else if(a[1]){
        a[1]--;
        if(a[1]){
            if(a[4]<a[1]+a[5]||a[4]==a[1]+a[5]&&a[5]==0){
                puts("Menji");
            return;
            }else if(a[4]==a[1]+a[5]+1||a[4]==a[1]+a[5]){
                puts("Draw");
            return;
            }else{
                puts("Water");
            return;
            }
        }else{
            if(!a[4]&&!a[5]){
                puts("Menji");
            return;
            }else if(a[4]<a[5]){
                puts("Menji");
            return;
            }else if(a[4]==a[5]+1||a[4]==a[5]){
                puts("Draw");
            return;
            }else{
                puts("Water");
            return;
            }
        }
    }else{
        if(!a[4]&&!a[5]){
            puts("Water");
            return;
        }else if(a[4]>a[5]){
            puts("Water");
            return;
        }else if(a[4]+1==a[5]||a[4]==a[5]){
            puts("Draw");
            return;
        }else{
            puts("Menji");
            return;
        }
    }
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
//WXWXMMWMXMWMXMWWMMX

疑似全世界最繁琐的做法。

循 序 渐 进。

诶话说为什么总觉得 a_5 被我写的跟只鸡一样（）