列表

详情

NC222523. 残局

描述

法外狂徒张三和AI玩起了斗地主残局这个棋牌游戏，斗地主的规则是这样的：
斗地主是一种使用黑桃、红心、梅花、方片的 A到 K加上大小王的共54张牌来进行的扑克牌游戏。
在斗地主中，牌的大小关系根据牌的数码表示如下： 小王 大王，而花色并不对牌的大小产生影响。为了简化题目，本题不考虑花色的影响，即**所有的相同的数码的牌都是被视为一样的**
3<4<5<6<7<8<9<10<j<q<k<A<2<小王<大王
为了方便输入，本题中，用大写字母T来表示10，用小写字母w表示小王，用大写字母W表示大王
每一局游戏中，一副手牌由n张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。
在这道题中，允许的出牌牌型有（为降低难度，这一部分与传统的斗地主相比有所区别请注意）：
名称
 解释
 举例
 注
火箭
 双王
 wW
炸弹
 相同数码的四张牌
 6666
单牌
 单独的一张牌
 6
 单张的王也是单牌
对子
 相同数码的两张牌
 66 大小王不是对子 
三张牌
 相同数码的三张牌
 666
三带一
 相同数码的三张牌带上一张另外数码的单牌
 6669 炸弹不是三带一 
三带二
 相同数码的三张牌带上一个另外数码的对子
 66699 不能带双王 
顺子
 相牌的大小连续的 5 张及以上单牌
 3456789 不能含有大小王和 2 
连对
 牌的大小连续的 3 对及以上的对子
 33445566 不能含有大小王和 2 
四带二
 四张相同数码的牌带上两张单牌
444456
444455
可以带大小王
四带两对
 四张相同数码的牌带上两对牌
44445566
33335555
33335555 
可以被认为是 3333 带上两个对五
也可以是 5555 带上两个对三

两手牌是属于相同牌型的当且仅当他们的名称相同且包含牌的数量相同。相同牌型的牌之间存在着大小关系（火箭是唯一的，不需要比大小）：

  1. 三带一三带二的大小取决于那三张相同牌的数码；
  2. 四带二的大小取决于四张相同牌的大小；
  3. 其他牌型的大小取决于牌中的最大的一张牌；
下面是对这一斗地主游戏的过程描述（这一部分与传统的斗地主有所不同）：

• 在斗地主中，只有两个玩家，分别为张三和 AI，张三手上有 n 张牌，AI 手上有 m 张牌，张三和
AI 可以互相看得到对方手中的牌；
• 游戏分成若干轮，每一轮由上一轮的胜者率先出牌（第一轮由张三最先出牌）。张三和 AI 轮流出
牌。这是一个十分坑爹的斗地主残局游戏，即使张三足够聪明，他也有可能无法获胜；
• 每一轮第一个出牌的玩家可以出任意牌型任意大小的牌。接着轮到每一个玩家出牌时，他有如下选
择：

  1. 不出（过牌）；
  2. 出与这一轮中上一次被打出的牌相同牌型但是大小严格更大的牌；
  3. 如果上一次被打出的牌不是炸弹或者火箭，那么可以打出任意大小的炸弹；
  4. 打出火箭；
• 在一轮中，如果在一个玩家打出牌后，如果对方选择不出，那么这一轮结束，这一个玩家作为本轮的胜者并开始下一轮；
• 任何时刻如果一个玩家的所有手牌都已打出，那么游戏结束，这一个玩家获胜；

张三和AI正在玩斗地主，万万没有想到，张三连输多局。“必有诈”，张三心想。
于是，张三找到了你。在他的回忆中，他和AI总共进行了次斗地主。对于每一次斗地主，张三都会给你他的牌和AI的牌（每个玩家手上的牌数均不多于10张），他想知道他的牌是否是先手必胜的，如是，请输出"YES"，否则请输出"NO"。
假设对手的牌为：AA2；
你手上的牌为：667788A2；
那么在你首次出牌时，你可以出连对667788，也可以出2，共计两种方法，使得对手无法赢你。但假如你开局出66，对手将出AA，你无法接牌，对手单走一张2即可获得胜利。

输入描述

第一行一个整数，表示数据组数；

接下来T组数据，每组数据包含两行共两个字符串，第一个字符串为AI手中的牌，第二个字符串为张三手中的牌；

给出的牌，将按照牌的大小从小到大给出，每个玩家手上的牌数均不多于10张；

对于同一种牌，AI和张三手上加起来均不会超过四张（大小王除外，这两种牌每种至多一张）。

输出描述

对于每一组数据，输出一个"YES"或者"NO"，如题目所示。

示例1

输入: 

5
55
76543
ATT6
2KK998773
W223
76655443
KQJJJTT97
wAAKT6333
AAQJJTT998
wKKKQT8774

输出: 

YES
YES
NO
YES
NO

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 2940ms, 内存消耗: 197508K, 提交时间: 2021-06-03 12:11:24 

#include <bits/stdc++.h>
using namespace std;
const int S = 1000000;
vector<int> gao(string u) {
	vector<int> w(15);
	for (int i=0; i<u.size(); ++i) {
		if (u[i]=='3') ++w[0];
		if (u[i]=='4') ++w[1];
		if (u[i]=='5') ++w[2];
		if (u[i]=='6') ++w[3];
		if (u[i]=='7') ++w[4];
		if (u[i]=='8') ++w[5];
		if (u[i]=='9') ++w[6];
		if (u[i]=='T') ++w[7];
		if (u[i]=='J') ++w[8];
		if (u[i]=='Q') ++w[9];
		if (u[i]=='K') ++w[10];
		if (u[i]=='A') ++w[11];
		if (u[i]=='2') ++w[12];
		if (u[i]=='w') ++w[13];
		if (u[i]=='W') ++w[14];
	}
	return w;
}
uint64_t Hash(vector<int> &a, vector<int> &b, int x, int y, int len) {
	uint64_t w = 0;
	w = w*5+a[0];
	w = w*5+a[1];
	w = w*5+a[2];
	w = w*5+a[3];
	w = w*5+a[4];
	w = w*5+a[5];
	w = w*5+a[6];
	w = w*5+a[7];
	w = w*5+a[8];
	w = w*5+a[9];
	w = w*5+a[10];
	w = w*5+a[11];
	w = w*5+a[12];
	w = w*5+b[0];
	w = w*5+b[1];
	w = w*5+b[2];
	w = w*5+b[3];
	w = w*5+b[4];
	w = w*5+b[5];
	w = w*5+b[6];
	w = w*5+b[7];
	w = w*5+b[8];
	w = w*5+b[9];
	w = w*5+b[10];
	w = w*5+b[11];
	w = w*5+b[12];
	w *= 9;
	if (a[13]&&a[14]) ;
	else if (a[13]) {
		if (b[14]) ++w;
		else w += 2;
	}
	else if (a[14]) {
		if (b[13]) w += 3;
		else w += 4;
	}
	else { 
		if (b[13]&&b[14]) w += 5;
		else if (b[13]) w += 6;
		else if (b[14]) w += 7;
		else w += 8;
	}
	uint64_t k = ((x+2)*20+y+2)*20+len+2;
	k = k*k, k = k*k;
	return w^k;
}
namespace mp {
	const int hashmod = 15485863;
	int clk, vis[hashmod];
	bool v[hashmod];
	uint64_t h[hashmod];
}
int dfs(vector<int> a, vector<int> b, int tp, int w, int len) {
	int sum = 0;
	for (int i=0; i<15; ++i) sum += a[i];
	if (sum==0) return 1;
    sum = 0;
    for (int i=0; i<15; ++i) sum += b[i];
    if (sum==0) return 0;
	auto sta = Hash(a,b,tp,w,len);
	int ii = sta%mp::hashmod;
	for (; mp::vis[ii]==mp::clk && mp::h[ii]!=sta; ii=(ii+1)%mp::hashmod) ;
	if (mp::vis[ii]==mp::clk) return mp::v[ii];
	mp::h[ii] = sta;
	mp::vis[ii] = mp::clk;
	if (a[13]&&a[14]) {
		a[13] = a[14] = 0;
		if (dfs(a,b,-1,-1,-1)) return mp::v[ii]=1;
		a[13] = a[14] = 1;
	}
	if (tp==-1) {
		for (int i=1; i<11; ++i) if (dfs(a,b,i,-1,-1)) return mp::v[ii]=1;
		return mp::v[ii]=0;
	}
	if (w!=-1&&!dfs(b,a,-1,-1,-1)) return mp::v[ii]=1;
	if (tp==1) {
		for (int i=w+1; i<13; ++i) if (a[i]==4) {
			a[i] = 0;
			if (!dfs(b,a,tp,i,-1)) return mp::v[ii]=1;
			a[i] = 4;
		}
		return mp::v[ii]=0;
	}
	else {
		for (int i=0; i<13; ++i) if (a[i]==4) {
			a[i] = 0;
			if (!dfs(b,a,1,i,-1)) return mp::v[ii]=1;
			a[i] = 4;
		}
	}
	if (tp==2) {
		for (int i=w+1; i<15; ++i) if (a[i]) {
			--a[i];
			if (!dfs(b,a,tp,i,-1)) return mp::v[ii]=1;
			++a[i];
		}
		return mp::v[ii]=0;
	}
	if (tp==3) {
		for (int i=w+1; i<13; ++i) if (a[i]>=2) {
			a[i] -= 2;
			if (!dfs(b,a,tp,i,-1)) return mp::v[ii]=1;
			a[i] += 2;
		}
		return mp::v[ii]=0;
	}
	if (tp==4) {
		for (int i=w+1; i<13; ++i) if (a[i]>=3) {
			a[i] -= 3;
			if (!dfs(b,a,tp,i,-1)) return mp::v[ii]=1;
			a[i] += 3;
		}
		return mp::v[ii]=0;
	}
	if (tp==5) {
		for (int i=w+1; i<13; ++i) if (a[i]>=3) {
			a[i] -= 3;
			for (int j=0; j<15; ++j) if (j!=i&&a[j]) {
				--a[j];
				if (!dfs(b,a,tp,i,-1)) return mp::v[ii]=1;
				++a[j];
			}
			a[i] += 3;
		}
		return mp::v[ii]=0;
	}
	if (tp==6) {
		for (int i=w+1; i<13; ++i) if (a[i]>=3) {
			a[i] -= 3;
			for (int j=0; j<13; ++j) if (a[j]>=2) {
				a[j] -= 2;
				if (!dfs(b,a,tp,i,-1)) return mp::v[ii]=1;
				a[j] += 2;
			}
			a[i] += 3;
		}
		return mp::v[ii]=0;
	}
	if (tp==7) {
		if (len==-1) {
			for (int i=w+1; i<12; ++i) if (a[i]) {
				auto tmp = a;
				for (int j=i; j>=0; --j) {
					if (a[j]) {
						--a[j];
						if (i-j>=4&&!dfs(b,a,tp,j,i-j+1)) return mp::v[ii]=1;
					}
					else break;
				}
				a = tmp;
			}
			return mp::v[ii]=0;
		}
		else {
			int L = 0;
			for (int i=11; i>w; --i) {
				if (a[i]) ++L;
				else L = 0;
				if (L>=len) {
					auto tmp = a;
					for (int j=i; j<=i+len-1; ++j) --a[j];
					if (!dfs(b,a,tp,i,len)) return mp::v[ii]=1;
					a = tmp;
				}
			}
			return mp::v[ii]=0;
		}
	}
	if (tp==8) {
		if (len==-1) {
			for (int i=w+1; i<12; ++i) if (a[i]>=2) {
				auto tmp = a;
				for (int j=i; j>=0; --j) {
					if (a[j]>=2) {
						a[j] -= 2;
						if (i-j>=2&&!dfs(b,a,tp,i,i-j+1)) return mp::v[ii]=1;
					}
					else break;
				}
				a = tmp;
			}
			return mp::v[ii]=0;
		}
		else {
			int L = 0;
			for (int i=11; i>w; --i) {
				if (a[i]>=2) ++L;
				else L = 0;
				if (L>=len) {
					auto tmp = a;
					for (int j=i; j<=i+len-1; ++j) a[j] -= 2;
					if (!dfs(b,a,tp,i,len)) return mp::v[ii]=1;
					a = tmp;
				}
			}
			return mp::v[ii]=0;
		}
	}
	if (tp==9) {
		for (int i=w+1; i<12; ++i) if (a[i]==4) {
			a[i] -= 4;
			for (int j=0; j<15; ++j) if (a[j]) {
				--a[j];
				for (int k=0; k<15; ++k) if (a[k]) {
					--a[k];
					if (!dfs(b,a,tp,i,-1)) return mp::v[ii]=1;
					++a[k];
				}
				++a[j];
			}
			a[i] += 4;
		}
		return mp::v[ii]=0;
	}
	if (tp==10) {
		for (int i=w+1; i<12; ++i) if (a[i]==4) {
			a[i] -= 4;
			for (int j=0; j<12; ++j) if (a[j]>=2) {
				a[j] -= 2;
				for (int k=0; k<12; ++k) if (a[k]>=2) {
					a[k] -= 2;
					if (!dfs(b,a,tp,i,-1)) return mp::v[ii]=1;
					a[k] += 2;
				}
				a[j] += 2;
			}
			a[i] += 4;
		}
		return mp::v[ii]=0;
	}
	throw;
}
int main() {
    int T;
	cin >> T;
	for (int cas=1; cas<=T; ++cas) {
		string u,v;
		cin >> u >> v;
		++mp::clk;
		auto x = gao(u), y = gao(v);
		int ans = dfs(y,x,-1,-1,-1);
		puts(ans?"YES":"NO");
	}
//	printf("%.5lfms\n",(double)clock()/CLOCKS_PER_SEC*1000);
}

上一题

© 2024 nowcoder.com