- 题解
打磨你!
- @ 2026-10-6 16:27:29
#include<bits/stdc++.h>
using namespace std;
const int N=(1<<18)+5;
bool vis[N][2][3][7];
int n,t,full;
bool die[N];
int c[3][6],x[3][6];
int s(int st,int p,int x){
//把第 p 个人手里的第 x 张牌在 st 中标记为 0
return st^=1<<(p*n+x);
}
bool have(int st,int p,int x){
//判断在 st 情况下,第 p 个人手里第 x 张牌还在不在
return st&(1<<(p*n+x));
}
//计算下一个人是谁
int nx(int b,int dir,int p){
if(dir==0) b+=p;
else b-=p;
if(b>2) b-=3;
if(b<0) b+=3;
return b;
}
// 判断这张牌是否能出
bool legal(int a,int b,int c,int d){
return a==4||c==4||a==c||b==d;
}
// 现在的出牌情况为 st,出牌方向是 dir
// 上一个出牌的人是 lp,出的是第 lx 张牌
bool dfs(int st,int dir,int lp,int lx){
//若所有牌都出完了,则返回 true
if(st==0) return true;
//碰到非法情况则结束(剪枝)
if(die[st]) return false;
//记忆化搜索,相同状态不需要重复搜索
if(vis[st][dir][lp][lx]) return 0;
vis[st][dir][lp][lx]=1;
//获取上一张牌的信息
int col=c[lp][lx],num=x[lp][lx];
//计算现在轮到谁出牌
int p;
if(num!=10)//如果上一张牌不是 skip,则朝 dir 方向移动一步
p=nx(lp,dir,1);
else//如果上一张牌是 skip,则朝 dir 方向移动两步
p=nx(lp,dir,2);
//判断第 p 个人手里还有没有牌
bool flag=0;
for(int i=0;i<n;i++)
if(have(st,p,i))
flag=1;
//如果下一个人没有牌,则一直找到一个有牌的人
while(!flag){
p=nx(p,dir,1);
for(int i=0;i<n;i++)
if(have(st,p,i))
flag=1;
}
//枚举当前这个人出哪张牌
for(int i=0;i<n;i++){
//如果他有这张牌,并且能打出这张牌
if(have(st,p,i) && legal(col,num,c[p][i],x[p][i])){
int gost=s(st,p,i);
int godir=dir;
if (x[p][i]==11) godir=!godir;
if(dfs(gost,godir,p,i))
return true;
}
}
return false;
}
void solve(){
cin>>n;
full=(1<<(3*n))-1;
//先标记所有失败的情况
//即有一个人的牌全打完了,其他人手里不是1张牌的情况
for(int i=1;i<(1<<n);i++){
if(i&(i-1)){
for(int j=1;j<(1<<n);j++){
die[i|(j<<n)]=1;
die[i|(j<<(n+n))]=1;
die[(i<<n)|j]=1;
die[(i<<n)|(j<<(n+n))]=1;
die[(i<<(n+n))|j]=1;
die[(i<<(n+n))|(j<<n)]=1;
}
}
}
for(int i=0;i<3;i++)
for(int j=0;j<n;j++)
cin>>c[i][j]>>x[i][j];
memset(vis,0,sizeof(vis));
//枚举先向左还是向右
for(int i=0;i<2;i++)
// 枚举第一张出的牌
for(int j=0;j<n;j++){
if(dfs(s(full,0,j),i,0,j)){
printf("Yes!\n");
return;
}
}
printf("No!\n");
return;
}
int main(){
freopen("uno.in","r",stdin);
freopen("uno.out","w",stdout);
cin>>t;
while(t--)solve();
return 0;
}
0 条评论
目前还没有评论...