自动搬运

查看原文

来自洛谷，原作者为

	fish_love_cat 「要毁灭世界，根本不需要邪恶。起初，那些都是不会被任何人怪罪的小小愿望。而那样的愿望却如此轻易地，和末日相连在一起。」

搬运于2025-08-24 23:08:05，当前版本为作者最后更新于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];
	}

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

• $a_0,a_1$ 显然要优先消除，因为是纯粹的自己人，消除起来放心。这两者可以先互相消耗掉，对结果没什么影响。

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

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

• $a_2,a_3$ 没有意义，显然可以在不变先后手的情况下轮流消除。

• $a_4,a_5$ 有的时候可以连着一起爆了，让对手讨不到好闹个平局。这就是为什么要分讨统计这两个值的原因。

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

• 当 $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$ 被我写的跟只鸡一样（）