2019年4月17日更新：
将搜索主函数优化为局部记忆化搜索，再次提高若干倍搜索速度
更新了main和player，helper无更新
#include "Player-v3.0.cpp"
#include "Helper.cpp" #define END {if(fir){newA=a; newB=b;} return 1;}
#define NXT {if(ok&&play(b,a,0)==0) return 1; else return 0;}
#define NO {printf("Can't Out\n"); newA=a; newB=b;}
player newA,newB;
bool play(player,player,bool); bool Play_Rocket(player a,player b,bool fir){
if(b.empty()) return ;
if(a.CanPlayRocket()){
a.PlayRocket();
bool now=play(a,b,);
if(now){
if(fir) Out_Rocket();
END;
}
}
return ;
} bool Play_Boom(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
if(Play_Rocket(a,b,fir)) return ;
player _a=a;
if(a.CanBoom)
for(int i=last+;i<;i++)
if(a.CanPlayBoom(i)){
a.PlayBoom(i);
a.ResetCan();
bool now=Play_Boom(b,a,i,,);
if(!now){
if(fir) Out_Boom(i);
END;
}
a=_a;
}
NXT;
} bool Play_Single(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++)
if(a.CanPlaySingle(i)){
a.PlaySingle(i);
bool now=Play_Single(b,a,i,,);
if(!now){
if(fir) Out_Single(i);
END;
}
a=_a;
}
NXT;
} bool Play_Couple(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++)
if(a.CanPlayCouple(i)){
a.PlayCouple(i);
bool now=Play_Couple(b,a,i,,);
if(!now){
if(fir) Out_Couple(i);
END;
}
a=_a;
}
NXT;
} bool Play_Three(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
if(a.CanThree)
for(int i=last+;i<;i++)
if(a.CanPlayThree(i)){
a.PlayThree(i);
a.ResetCan();
bool now=Play_Three(b,a,i,,);
if(!now){
if(fir) Out_Three(i);
END;
}
a=_a;
}
NXT;
} bool Play_3Single(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++) if(a.CanPlayThree(i))
if(a.CanThree)
for(int j=;j<;j++)
if(a.CanPlay3Single(i,j)){
a.Play3Single(i,j);
a.ResetCan();
bool now=Play_3Single(b,a,i,,);
if(!now){
if(fir) Out_3Single(i,j);
END;
}
a=_a;
}
NXT;
} bool Play_3Couple(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++) if(a.CanPlayThree(i))
if(a.CanThree)
for(int j=;j<;j++)
if(a.CanPlay3Couple(i,j)){
a.Play3Couple(i,j);
a.ResetCan();
bool now=Play_3Couple(b,a,i,,);
if(!now){
if(fir) Out_3Couple(i,j);
END;
}
a=_a;
}
NXT;
} bool Play_4Single(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++) if(a.CanPlayBoom(i))
if(a.CanBoom)
for(int j=;j<;j++)
for(int k=;k<;k++)
if(a.CanPlay4Single(i,j,k)){
a.Play4Single(i,j,k);
a.ResetCan();
bool now=Play_4Single(b,a,i,,);
if(!now){
if(fir) Out_4Single(i,j,k);
END;
}
a=_a;
}
NXT;
} bool Play_4Couple(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++) if(a.CanPlayBoom(i))
if(a.CanBoom)
for(int j=;j<;j++)
for(int k=;k<;k++)
if(a.CanPlay4Couple(i,j,k)){
a.Play4Couple(i,j,k);
a.ResetCan();
bool now=Play_4Couple(b,a,i,,);
if(!now){
if(fir) Out_4Couple(i,j,k);
END;
}
a=_a;
}
NXT;
} bool Play_MS(player a,player b,int l,int r,bool fir,bool ok){
if(b.empty()) return ;
player _a=a; int pls=r-l;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
if(a.CanMS)
for(int i=l+;i+pls<=;i++)
if(a.CanPlayMoreSingle(i,i+pls)){
a.PlayMoreSingle(i,i+pls);
a.ResetCan();
bool now=Play_MS(b,a,i,i+pls,,);
if(!now){
if(fir) Out_MS(i,i+pls);
END;
}
a=_a;
}
NXT;
} bool Play_MC(player a,player b,int l,int r,bool fir,bool ok){
if(b.empty()) return ;
player _a=a; int pls=r-l;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
if(a.CanMC)
for(int i=l+;i+pls<=;i++)
if(a.CanPlayMoreCouple(i,i+pls)){
a.PlayMoreCouple(i,i+pls);
a.ResetCan();
bool now=Play_MC(b,a,i,i+pls,,);
if(!now){
if(fir) Out_MC(i,i+pls);
END;
}
a=_a;
}
NXT;
} map<pair<long long,long long>,int> Visit;
bool play(player a,player b,bool fir=){
if(b.empty()) return Visit[make_pair(a.Hash(),b.Hash())]=;
if(a.cnt+b.cnt<&&fir==){
if(Visit.count(make_pair(a.Hash(),b.Hash())))
return Visit[make_pair(a.Hash(),b.Hash())];
}
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return Visit[make_pair(a.Hash(),b.Hash())]=;
if(a.CanMS)
for(int i=;i>=;i--){
if(Play_MS(a,b,-,-+i,fir,)) return Visit[make_pair(a.Hash(),b.Hash())]=;
}
if(a.CanMC)
for(int i=;i>=;i--){
if(Play_MC(a,b,-,-+i,fir,)) return Visit[make_pair(a.Hash(),b.Hash())]=;
}
if(a.CanThree) if(Play_Three(a,b,-,fir,)) return Visit[make_pair(a.Hash(),b.Hash())]=;
if(a.CanThree) if(Play_3Single(a,b,-,fir,)) return Visit[make_pair(a.Hash(),b.Hash())]=;
if(a.CanThree) if(Play_3Couple(a,b,-,fir,)) return Visit[make_pair(a.Hash(),b.Hash())]=;
if(Play_Couple(a,b,-,fir,)) return Visit[make_pair(a.Hash(),b.Hash())]=;
if(Play_Single(a,b,-,fir,)) return Visit[make_pair(a.Hash(),b.Hash())]=;
if(a.CanBoom) if(Play_4Single(a,b,-,fir,)) return Visit[make_pair(a.Hash(),b.Hash())]=;
if(a.CanBoom) if(Play_4Couple(a,b,-,fir,)) return Visit[make_pair(a.Hash(),b.Hash())]=;
return Visit[make_pair(a.Hash(),b.Hash())]=;
} int Main(){
Visit.clear();
player a,b;
printf("INPUT AI:\n");
b.read();
printf("INPUT PLAYER:\n");
a.read();
int staT=clock();
if(!play(a,b,)){
printf("DIE\n");
return ;
}
printf("\nFirst Time Use %dms\n",clock()-staT);
while(){
a=newA; b=newB;
printf("\n");
if(a.empty()){
printf("WIN\n");
return ;
} string now; cin>>now;
if(now=="EXIT") return ;
if(Is_Empty(now)){
if(!play(a,b,)){
printf("DIE\n");
}
continue;
}
for(int i=;i<now.length();i++) b.PlaySingle(GetVal(now[i])); if(Is_Single(now)&&Play_Single(a,b,GetVal(now[]),,)==) NO;
if(Is_Couple(now)&&Play_Couple(a,b,GetVal(now[]),,)==) NO;
if(Is_Three(now)&&Play_Three(a,b,GetVal(now[]),,)==) NO;
if(Is_Boom(now)&&Play_Boom(a,b,GetVal(now[]),,)==) NO;
if(Is_Rocket(now)&&Play_Rocket(a,b,)==) NO;
if(Is_3Single(now)&&Play_3Single(a,b,GetVal(now[]),,)==) NO;
if(Is_3Couple(now)&&Play_3Couple(a,b,GetVal(now[]),,)==) NO;
if(Is_4Single(now)&&Play_4Single(a,b,GetVal(now[]),,)==) NO;
if(Is_4Couple(now)&&Play_4Couple(a,b,GetVal(now[]),,)==) NO;
if(Is_MS(now)&&Play_MS(a,b,GetVal(now[]),GetVal(now[now.length()-]),,)==) NO;
if(Is_MC(now)&&Play_MC(a,b,GetVal(now[]),GetVal(now[now.length()-]),,)==) NO;
}
} int main(){
while() Main();
}
main-v3.0
/*
???????????????????
??
??????
*/ #include<bits/stdc++.h>
using namespace std; int GetVal(char c){
if(c=='T') return ;
if(c=='J') return ;
if(c=='Q') return ;
if(c=='K') return ;
if(c=='A') return ;
if(c=='') return ;
if(c=='w') return ;
if(c=='W') return ;
if(''<=c&&c<='') return c-'';
assert();
}
char SetChar(int x){
if(x<=) return ''+x;
if(x==) return 'T';
if(x==) return 'J';
if(x==) return 'Q';
if(x==) return 'K';
if(x==) return 'A';
if(x==) return '';
if(x==) return 'w';
if(x==) return 'W';
assert();
} struct player{
int a[],cnt;
bool CanThree,CanBoom,CanMS,CanMC;
player(){memset(a,,sizeof(a));cnt=;} void out(){//Output Poker
for(int i=;i<;i++)
for(int j=;j<a[i];j++)
putchar(SetChar(i));
putchar('\n');
} inline bool CanPlaySingle(int x){return a[x]>=;}//? inline bool CanPlayCouple(int x){return a[x]>=;}//? inline bool CanPlayThree(int x){return a[x]>=;}//?? inline bool CanPlayBoom(int x){return a[x]>=;}//?? inline bool CanPlayRocket(){return a[]&&a[];}//?? inline bool CanPlayMoreSingle(int l,int r){//??
if(r-l+<||r>=) return ;
for(int i=l;i<=r;i++) if(!CanPlaySingle(i)) return ;
return ;
} inline bool CanPlayMoreCouple(int l,int r){//??
if(r-l+<||r>=) return ;
for(int i=l;i<=r;i++) if(!CanPlayCouple(i)) return ;
return ;
} inline bool CanPlayMoreThree(int l,int r){//??
if(r-l+<||r>=) return ;
for(int i=l;i<=r;i++) if(!CanPlayThree(i)) return ;
return ;
} inline bool CanPlay4Single(int x,int l,int r){//???
if(x==l||x==r) return ;
if(l==r) return CanPlayBoom(x)&&CanPlayCouple(l);
return CanPlayBoom(x)&&CanPlaySingle(l)&&CanPlaySingle(r);
} inline bool CanPlay4Couple(int x,int l,int r){//???
if(x==l||x==r) return ;
if(l==r) return CanPlayBoom(x)&&CanPlayBoom(l);
return CanPlayBoom(x)&&CanPlayCouple(l)&&CanPlayCouple(r);
} inline bool CanPlay3Single(int x,int y){
if(x==y) return ;
return CanPlayThree(x)&&CanPlaySingle(y);
} inline bool CanPlay3Couple(int x,int y){
if(x==y) return ;
return CanPlayThree(x)&&CanPlayCouple(y);
} inline void PlaySingle(int x){a[x]--; cnt--;} inline void PlayCouple(int x){a[x]-=; cnt-=;} inline void PlayThree(int x){a[x]-=; cnt-=;} inline void PlayBoom(int x){a[x]-=; cnt-=;} inline void PlayRocket(){a[]--;a[]--; cnt-=;} inline void PlayMoreSingle(int l,int r){for(int i=l;i<=r;i++) PlaySingle(i);} inline void PlayMoreCouple(int l,int r){for(int i=l;i<=r;i++) PlayCouple(i);} inline void PlayMoreThree(int l,int r){for(int i=l;i<=r;i++) PlayThree(i);} inline void Play4Single(int x,int l,int r){PlayBoom(x); PlaySingle(l); PlaySingle(r);} inline void Play4Couple(int x,int l,int r){PlayBoom(x); PlayCouple(l); PlayCouple(r);} inline void Play3Single(int x,int y){PlayThree(x); PlaySingle(y);} inline void Play3Couple(int x,int y){PlayThree(x); PlayCouple(y);} inline bool empty(){
return cnt==;
}//?????? inline long long Hash(){long long res=; for(int i=;i<;i++) res=res<<|a[i]; return res;}//??? inline int GetMin(){for(int i=;i<;i++) if(a[i]) return i; assert();}
inline int GetMax(){for(int i=;~i;i--) if(a[i]) return i; return -;} inline void ResetCan(){
CanThree=CanBoom=CanMS=CanMC=;//!!!
for(int i=;i<;i++){
if(CanPlayThree(i)) CanThree=;
if(CanPlayBoom(i)) CanBoom=;
}
if(CanPlayRocket()) CanBoom=;
for(int i=;i<=;i++){
if(CanPlayMoreSingle(i,i+)) {CanMS=; break;}
}
for(int i=;i<=;i++){
if(CanPlayMoreCouple(i,i+)) {CanMC=; break;}
}
} void read(){//Input Poker
memset(a,,sizeof(a)); cnt=;
string s; cin>>s; int len=s.length(); cnt=len;
for(int i=;i<len;i++)
a[GetVal(s[i])]++;
ResetCan();
}
};
Player-v3.0
3.0版本在双方牌数不大于15张时，基本可以在1s内出解
（OFast编译，CPU：I5-4210M，辣鸡CPU）
2019年4月16日更新：
优化了分支判断速度，快了若干倍
更新了main和player，helper无更新
#include "Player-v2.0.cpp"
#include "Helper.cpp" #define END {if(fir){newA=a; newB=b;} return 1;}
#define NXT {if(ok&&play(b,a,0)==0) return 1; else return 0;}
#define NO {printf("Can't Out\n"); newA=a; newB=b;}
player newA,newB;
bool play(player,player,bool); bool Play_Rocket(player a,player b,bool fir){
if(b.empty()) return ;
if(a.CanPlayRocket()){
a.PlayRocket();
bool now=play(a,b,);
if(now){
if(fir) Out_Rocket();
END;
}
}
return ;
} bool Play_Boom(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
if(Play_Rocket(a,b,fir)) return ;
player _a=a;
if(a.CanBoom)
for(int i=last+;i<;i++)
if(a.CanPlayBoom(i)){
a.PlayBoom(i);
a.ResetCan();
bool now=Play_Boom(b,a,i,,);
if(!now){
if(fir) Out_Boom(i);
END;
}
a=_a;
}
NXT;
} bool Play_Single(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++)
if(a.CanPlaySingle(i)){
a.PlaySingle(i);
bool now=Play_Single(b,a,i,,);
if(!now){
if(fir) Out_Single(i);
END;
}
a=_a;
}
NXT;
} bool Play_Couple(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++)
if(a.CanPlayCouple(i)){
a.PlayCouple(i);
bool now=Play_Couple(b,a,i,,);
if(!now){
if(fir) Out_Couple(i);
END;
}
a=_a;
}
NXT;
} bool Play_Three(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
if(a.CanThree)
for(int i=last+;i<;i++)
if(a.CanPlayThree(i)){
a.PlayThree(i);
a.ResetCan();
bool now=Play_Three(b,a,i,,);
if(!now){
if(fir) Out_Three(i);
END;
}
a=_a;
}
NXT;
} bool Play_3Single(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++) if(a.CanPlayThree(i))
if(a.CanThree)
for(int j=;j<;j++)
if(a.CanPlay3Single(i,j)){
a.Play3Single(i,j);
a.ResetCan();
bool now=Play_3Single(b,a,i,,);
if(!now){
if(fir) Out_3Single(i,j);
END;
}
a=_a;
}
NXT;
} bool Play_3Couple(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++) if(a.CanPlayThree(i))
if(a.CanThree)
for(int j=;j<;j++)
if(a.CanPlay3Couple(i,j)){
a.Play3Couple(i,j);
a.ResetCan();
bool now=Play_3Couple(b,a,i,,);
if(!now){
if(fir) Out_3Couple(i,j);
END;
}
a=_a;
}
NXT;
} bool Play_4Single(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++) if(a.CanPlayBoom(i))
if(a.CanBoom)
for(int j=;j<;j++)
for(int k=;k<;k++)
if(a.CanPlay4Single(i,j,k)){
a.Play4Single(i,j,k);
// a.ResetCan();
bool now=Play_4Single(b,a,i,,);
if(!now){
if(fir) Out_4Single(i,j,k);
END;
}
a=_a;
}
NXT;
} bool Play_4Couple(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++) if(a.CanPlayBoom(i))
if(a.CanBoom)
for(int j=;j<;j++)
for(int k=;k<;k++)
if(a.CanPlay4Couple(i,j,k)){
a.Play4Couple(i,j,k);
a.ResetCan();
bool now=Play_4Couple(b,a,i,,);
if(!now){
if(fir) Out_4Couple(i,j,k);
END;
}
a=_a;
}
NXT;
} bool Play_MS(player a,player b,int l,int r,bool fir,bool ok){
if(b.empty()) return ;
player _a=a; int pls=r-l;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
if(a.CanMS)
for(int i=l+;i+pls<=;i++)
if(a.CanPlayMoreSingle(i,i+pls)){
a.PlayMoreSingle(i,i+pls);
a.ResetCan();
bool now=Play_MS(b,a,i,i+pls,,);
if(!now){
if(fir) Out_MS(i,i+pls);
END;
}
a=_a;
}
NXT;
} bool Play_MC(player a,player b,int l,int r,bool fir,bool ok){
if(b.empty()) return ;
player _a=a; int pls=r-l;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
if(a.CanMC)
for(int i=l+;i+pls<=;i++)
if(a.CanPlayMoreCouple(i,i+pls)){
a.PlayMoreCouple(i,i+pls);
a.ResetCan();
bool now=Play_MC(b,a,i,i+pls,,);
if(!now){
if(fir) Out_MC(i,i+pls);
END;
}
a=_a;
}
NXT;
} bool play(player a,player b,bool fir=){
if(b.empty()) return ;
if(a.CanBoom) if(Play_Boom(a,b,-,fir,)) return ;
if(a.CanMS)
for(int i=;i>=;i--){
if(Play_MS(a,b,-,-+i,fir,)) return ;
}
if(a.CanMC)
for(int i=;i>=;i--){
if(Play_MC(a,b,-,-+i,fir,)) return ;
}
if(a.CanThree) if(Play_Three(a,b,-,fir,)) return ;
if(a.CanThree) if(Play_3Single(a,b,-,fir,)) return ;
if(a.CanThree) if(Play_3Couple(a,b,-,fir,)) return ;
if(Play_Couple(a,b,-,fir,)) return ;
if(Play_Single(a,b,-,fir,)) return ;
if(a.CanBoom) if(Play_4Single(a,b,-,fir,)) return ;
if(a.CanBoom) if(Play_4Couple(a,b,-,fir,)) return ;
return ;
} int Main(){
player a,b;
printf("INPUT AI:\n");
b.read();
printf("INPUT PLAYER:\n");
a.read();
if(!play(a,b,)){
printf("DIE\n");
return ;
}
while(){
a=newA; b=newB;
printf("\n");
if(a.empty()){
printf("WIN\n");
return ;
} string now; cin>>now;
if(now=="EXIT") return ;
if(Is_Empty(now)){
if(!play(a,b,)){
printf("DIE\n");
}
continue;
}
for(int i=;i<now.length();i++) b.PlaySingle(GetVal(now[i])); if(Is_Single(now)&&Play_Single(a,b,GetVal(now[]),,)==) NO;
if(Is_Couple(now)&&Play_Couple(a,b,GetVal(now[]),,)==) NO;
if(Is_Three(now)&&Play_Three(a,b,GetVal(now[]),,)==) NO;
if(Is_Boom(now)&&Play_Boom(a,b,GetVal(now[]),,)==) NO;
if(Is_Rocket(now)&&Play_Rocket(a,b,)==) NO;
if(Is_3Single(now)&&Play_3Single(a,b,GetVal(now[]),,)==) NO;
if(Is_3Couple(now)&&Play_3Couple(a,b,GetVal(now[]),,)==) NO;
if(Is_4Single(now)&&Play_4Single(a,b,GetVal(now[]),,)==) NO;
if(Is_4Couple(now)&&Play_4Couple(a,b,GetVal(now[]),,)==) NO;
if(Is_MS(now)&&Play_MS(a,b,GetVal(now[]),GetVal(now[now.length()-]),,)==) NO;
if(Is_MC(now)&&Play_MC(a,b,GetVal(now[]),GetVal(now[now.length()-]),,)==) NO;
}
} int main(){
while() Main();
}
main-v2.0
/*
???????????????????
??
??????
*/ #include<bits/stdc++.h>
using namespace std; int GetVal(char c){
if(c=='T') return ;
if(c=='J') return ;
if(c=='Q') return ;
if(c=='K') return ;
if(c=='A') return ;
if(c=='') return ;
if(c=='w') return ;
if(c=='W') return ;
if(''<=c&&c<='') return c-'';
assert();
}
char SetChar(int x){
if(x<=) return ''+x;
if(x==) return 'T';
if(x==) return 'J';
if(x==) return 'Q';
if(x==) return 'K';
if(x==) return 'A';
if(x==) return '';
if(x==) return 'w';
if(x==) return 'W';
assert();
} struct player{
int a[];
bool CanThree,CanBoom,CanMS,CanMC;
player(){memset(a,,sizeof(a));} void out(){//Output Poker
for(int i=;i<;i++)
for(int j=;j<a[i];j++)
putchar(SetChar(i));
putchar('\n');
} inline bool CanPlaySingle(int x){return a[x]>=;}//? inline bool CanPlayCouple(int x){return a[x]>=;}//? inline bool CanPlayThree(int x){return a[x]>=;}//?? inline bool CanPlayBoom(int x){return a[x]>=;}//?? inline bool CanPlayRocket(){return a[]&&a[];}//?? inline bool CanPlayMoreSingle(int l,int r){//??
if(r-l+<||r>=) return ;
for(int i=l;i<=r;i++) if(!CanPlaySingle(i)) return ;
return ;
} inline bool CanPlayMoreCouple(int l,int r){//??
if(r-l+<||r>=) return ;
for(int i=l;i<=r;i++) if(!CanPlayCouple(i)) return ;
return ;
} inline bool CanPlayMoreThree(int l,int r){//??
if(r-l+<||r>=) return ;
for(int i=l;i<=r;i++) if(!CanPlayThree(i)) return ;
return ;
} inline bool CanPlay4Single(int x,int l,int r){//???
if(x==l||x==r) return ;
if(l==r) return CanPlayBoom(x)&&CanPlayCouple(l);
return CanPlayBoom(x)&&CanPlaySingle(l)&&CanPlaySingle(r);
} inline bool CanPlay4Couple(int x,int l,int r){//???
if(x==l||x==r) return ;
if(l==r) return CanPlayBoom(x)&&CanPlayBoom(l);
return CanPlayBoom(x)&&CanPlayCouple(l)&&CanPlayCouple(r);
} inline bool CanPlay3Single(int x,int y){
if(x==y) return ;
return CanPlayThree(x)&&CanPlaySingle(y);
} inline bool CanPlay3Couple(int x,int y){
if(x==y) return ;
return CanPlayThree(x)&&CanPlayCouple(y);
} inline void PlaySingle(int x){a[x]--;} inline void PlayCouple(int x){a[x]-=;} inline void PlayThree(int x){a[x]-=;} inline void PlayBoom(int x){a[x]-=;} inline void PlayRocket(){a[]--;a[]--;} inline void PlayMoreSingle(int l,int r){for(int i=l;i<=r;i++) PlaySingle(i);} inline void PlayMoreCouple(int l,int r){for(int i=l;i<=r;i++) PlayCouple(i);} inline void PlayMoreThree(int l,int r){for(int i=l;i<=r;i++) PlayThree(i);} inline void Play4Single(int x,int l,int r){PlayBoom(x); PlaySingle(l); PlaySingle(r);} inline void Play4Couple(int x,int l,int r){PlayBoom(x); PlayCouple(l); PlayCouple(r);} inline void Play3Single(int x,int y){PlayThree(x); PlaySingle(y);} inline void Play3Couple(int x,int y){PlayThree(x); PlayCouple(y);} inline bool empty(){
for(int i=;i<;i++)
if(a[i])
return ;
return ;}//?????? inline long long Hash(){long long res=; for(int i=;i<;i++) res=res<<|a[i]; return res;}//??? inline int GetMin(){for(int i=;i<;i++) if(a[i]) return i; assert();}
inline int GetMax(){for(int i=;~i;i--) if(a[i]) return i; return -;} inline void ResetCan(){
CanThree=CanBoom=CanMS=CanMC=;//!!!
for(int i=;i<;i++){
if(CanPlayThree(i)) CanThree=;
if(CanPlayBoom(i)) CanBoom=;
}
if(CanPlayRocket()) CanBoom=;
for(int i=;i<=;i++){
if(CanPlayMoreSingle(i,i+)) {CanMS=; break;}
}
for(int i=;i<=;i++){
if(CanPlayMoreCouple(i,i+)) {CanMC=; break;}
}
} void read(){//Input Poker
memset(a,,sizeof(a));
string s; cin>>s; int len=s.length();
for(int i=;i<len;i++)
a[GetVal(s[i])]++;
ResetCan();
}
};
Player-v2.0
众所周知欢乐斗地主这个游戏有一个叫做残局的模式
模式的特征：你和机器人都互相知道对方的牌，且对面的机器人绝顶聪明。
正常的斗地主规则，问你要如何出牌，才能保证你一定能赢。
我们考虑直接爆搜，发现需要搜一年。
于是我们加一个Alpha-Beta剪枝来加速整个爆搜过程即可。
貌似绝大部分情况下都是秒出结果的
目前最长时间只搜了15s（这是v2.0的时间，旧版貌似接近一分钟了）
正确率100%，快速通关利器233333
输入牌型要求：2~9直接输入，JQKA直接输入，10用T表示，大王小王分别用Ww表示。
输入顺子/连对要从小到大输入（按照斗地主规则的从小到大），输入三带一/对，四带二/对，需要先输入三张/四张，再输入剩下的东西
代码貌似只要10k多一点
注意细节
两个关联文件的代码：
/*
该部分函数用于输出打出的牌
以及
分析当前输入的牌型 */ inline void Out_Single(int x){printf("%c",SetChar(x));} inline void Out_Couple(int x){printf("%c%c",SetChar(x),SetChar(x));} inline void Out_Three(int x){printf("%c%c%c",SetChar(x),SetChar(x),SetChar(x));} inline void Out_Boom(int x){printf("%c%c%c%c",SetChar(x),SetChar(x),SetChar(x),SetChar(x));} inline void Out_3Single(int x,int y){Out_Three(x); Out_Single(y);} inline void Out_3Couple(int x,int y){Out_Three(x); Out_Couple(y);} inline void Out_MS(int l,int r){for(int i=l;i<=r;i++) Out_Single(i);} inline void Out_MC(int l,int r){for(int i=l;i<=r;i++) Out_Couple(i);} inline void Out_M3(int l,int r){for(int i=l;i<=r;i++) Out_Three(i);} inline void Out_Rocket(){printf("Ww");} inline void Out_4Single(int x,int l,int r){Out_Boom(x); Out_Single(l); Out_Single(r);} inline void Out_4Couple(int x,int l,int r){Out_Boom(x); Out_Couple(l); Out_Couple(r);} inline bool Is_Empty(string s){return s.length()==&&s[]=='*';} inline bool Is_Single(string s){return s.length()==;} inline bool Is_Rocket(string s){return s=="Ww"||s=="wW";} inline bool Is_Couple(string s){return s.length()==&&s[]==s[];} inline bool Is_Three(string s){return s.length()==&&s[]==s[]&&s[]==s[];} inline bool Is_Boom(string s){return s.length()==&&s[]==s[]&&s[]==s[]&&s[]==s[];} inline bool Is_3Single(string s){return s.length()==&&s[]==s[]&&s[]==s[]&&s[]!=s[];} inline bool Is_3Couple(string s){return s.length()==&&s[]==s[]&&s[]==s[]&&s[]!=s[]&&s[]==s[];} inline bool Is_MS(string s){
int len=s.length(); if(len<) return ;
for(int i=;i<len;i++) if(GetVal(s[i-])+!=GetVal(s[i])) return ;
return ;
} inline bool Is_MC(string s){
int len=s.length(); if((len&)||len<) return ;
for(int i=;i<len;i+=){
if(s[i]!=s[i-]) return ;
}
for(int i=;i<len;i+=){
if(GetVal(s[i-])+!=GetVal(s[i])) return ;
}
return ;
} inline bool Is_4Single(string s){return s.length()==&&s[]==s[]&&s[]==s[]&&s[]==s[]&&s[]!=s[];} inline bool Is_4Couple(string s){return s.length()==&&s[]==s[]&&s[]==s[]&&s[]==s[]&&s[]!=s[]&&s[]==s[]&&s[]==s[];}
Helper.cpp
/*
该部分函数用于判定是否可以出该类型的牌
以及
模拟出牌过程
*/ #include<bits/stdc++.h>
using namespace std; int GetVal(char c){
if(c=='T') return ;
if(c=='J') return ;
if(c=='Q') return ;
if(c=='K') return ;
if(c=='A') return ;
if(c=='') return ;
if(c=='w') return ;
if(c=='W') return ;
if(''<=c&&c<='') return c-'';
assert();
}
char SetChar(int x){
if(x<=) return ''+x;
if(x==) return 'T';
if(x==) return 'J';
if(x==) return 'Q';
if(x==) return 'K';
if(x==) return 'A';
if(x==) return '';
if(x==) return 'w';
if(x==) return 'W';
assert();
} struct player{
int a[];
player(){memset(a,,sizeof(a));}
void read(){//Input Poker
memset(a,,sizeof(a));
string s; cin>>s; int len=s.length();
for(int i=;i<len;i++)
a[GetVal(s[i])]++;
} void out(){//Output Poker
for(int i=;i<;i++)
for(int j=;j<a[i];j++)
putchar(SetChar(i));
putchar('\n');
} inline bool CanPlaySingle(int x){return a[x]>=;}//单 inline bool CanPlayCouple(int x){return a[x]>=;}//对 inline bool CanPlayThree(int x){return a[x]>=;}//三张 inline bool CanPlayBoom(int x){return a[x]>=;}//炸弹 inline bool CanPlayRocket(){return a[]&&a[];}//火箭 inline bool CanPlayMoreSingle(int l,int r){//顺子
if(r-l+<||r>=) return ;
for(int i=l;i<=r;i++) if(!CanPlaySingle(i)) return ;
return ;
} inline bool CanPlayMoreCouple(int l,int r){//连对
if(r-l+<||r>=) return ;
for(int i=l;i<=r;i++) if(!CanPlayCouple(i)) return ;
return ;
} inline bool CanPlayMoreThree(int l,int r){//飞机
if(r-l+<||r>=) return ;
for(int i=l;i<=r;i++) if(!CanPlayThree(i)) return ;
return ;
} inline bool CanPlay4Single(int x,int l,int r){//四带二
if(x==l||x==r) return ;
if(l==r) return CanPlayBoom(x)&&CanPlayCouple(l);
return CanPlayBoom(x)&&CanPlaySingle(l)&&CanPlaySingle(r);
} inline bool CanPlay4Couple(int x,int l,int r){//四带对
if(x==l||x==r) return ;
if(l==r) return CanPlayBoom(x)&&CanPlayBoom(l);
return CanPlayBoom(x)&&CanPlayCouple(l)&&CanPlayCouple(r);
} inline bool CanPlay3Single(int x,int y){
if(x==y) return ;
return CanPlayThree(x)&&CanPlaySingle(y);
} inline bool CanPlay3Couple(int x,int y){
if(x==y) return ;
return CanPlayThree(x)&&CanPlayCouple(y);
} inline void PlaySingle(int x){a[x]--;} inline void PlayCouple(int x){a[x]-=;} inline void PlayThree(int x){a[x]-=;} inline void PlayBoom(int x){a[x]-=;} inline void PlayRocket(){a[]--;a[]--;} inline void PlayMoreSingle(int l,int r){for(int i=l;i<=r;i++) PlaySingle(i);} inline void PlayMoreCouple(int l,int r){for(int i=l;i<=r;i++) PlayCouple(i);} inline void PlayMoreThree(int l,int r){for(int i=l;i<=r;i++) PlayThree(i);} inline void Play4Single(int x,int l,int r){PlayBoom(x); PlaySingle(l); PlaySingle(r);} inline void Play4Couple(int x,int l,int r){PlayBoom(x); PlayCouple(l); PlayCouple(r);} inline void Play3Single(int x,int y){PlayThree(x); PlaySingle(y);} inline void Play3Couple(int x,int y){PlayThree(x); PlayCouple(y);} inline bool empty(){
for(int i=;i<;i++)
if(a[i])
return ;
return ;}//判断是否出完 inline long long Hash(){long long res=; for(int i=;i<;i++) res=res<<|a[i]; return res;}//哈希值 inline int GetMin(){for(int i=;i<;i++) if(a[i]) return i; assert();}
inline int GetMax(){for(int i=;~i;i--) if(a[i]) return i; return -;}
};
Player.cpp
主代码：
#include "Player.cpp"
#include "Helper.cpp" #define END {if(fir){newA=a; newB=b;} return 1;}
#define NXT {if(ok&&play(b,a,0)==0) return 1; else return 0;}
#define NO {printf("Can't Out\n"); newA=a; newB=b;}
player newA,newB;
bool play(player,player,bool); bool Play_Rocket(player a,player b,bool fir){
if(b.empty()) return ;
if(a.CanPlayRocket()){
a.PlayRocket();
bool now=play(a,b,);
if(now){
if(fir) Out_Rocket();
END;
}
}
return ;
} bool Play_Boom(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
if(Play_Rocket(a,b,fir)) return ;
player _a=a;
for(int i=last+;i<;i++)
if(a.CanPlayBoom(i)){
a.PlayBoom(i);
bool now=Play_Boom(b,a,i,,);
if(!now){
if(fir) Out_Boom(i);
END;
}
a=_a;
}
NXT;
} bool Play_Single(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++)
if(a.CanPlaySingle(i)){
a.PlaySingle(i);
bool now=Play_Single(b,a,i,,);
if(!now){
if(fir) Out_Single(i);
END;
}
a=_a;
}
NXT;
} bool Play_Couple(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++)
if(a.CanPlayCouple(i)){
a.PlayCouple(i);
bool now=Play_Couple(b,a,i,,);
if(!now){
if(fir) Out_Couple(i);
END;
}
a=_a;
}
NXT;
} bool Play_Three(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++)
if(a.CanPlayThree(i)){
a.PlayThree(i);
bool now=Play_Three(b,a,i,,);
if(!now){
if(fir) Out_Three(i);
END;
}
a=_a;
}
NXT;
} bool Play_3Single(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++) if(a.CanPlayThree(i))
for(int j=;j<;j++)
if(a.CanPlay3Single(i,j)){
a.Play3Single(i,j);
bool now=Play_3Single(b,a,i,,);
if(!now){
if(fir) Out_3Single(i,j);
END;
}
a=_a;
}
NXT;
} bool Play_3Couple(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++) if(a.CanPlayThree(i))
for(int j=;j<;j++)
if(a.CanPlay3Couple(i,j)){
a.Play3Couple(i,j);
bool now=Play_3Couple(b,a,i,,);
if(!now){
if(fir) Out_3Couple(i,j);
END;
}
a=_a;
}
NXT;
} bool Play_4Single(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++) if(a.CanPlayBoom(i))
for(int j=;j<;j++)
for(int k=;k<;k++)
if(a.CanPlay4Single(i,j,k)){
a.Play4Single(i,j,k);
bool now=Play_4Single(b,a,i,,);
if(!now){
if(fir) Out_4Single(i,j,k);
END;
}
a=_a;
}
NXT;
} bool Play_4Couple(player a,player b,int last,bool fir,bool ok){
if(b.empty()) return ;
player _a=a;
if(Play_Boom(a,b,-,fir,)) return ;
for(int i=last+;i<;i++) if(a.CanPlayBoom(i))
for(int j=;j<;j++)
for(int k=;k<;k++)
if(a.CanPlay4Couple(i,j,k)){
a.Play4Couple(i,j,k);
bool now=Play_4Couple(b,a,i,,);
if(!now){
if(fir) Out_4Couple(i,j,k);
END;
}
a=_a;
}
NXT;
} bool Play_MS(player a,player b,int l,int r,bool fir,bool ok){
if(b.empty()) return ;
player _a=a; int pls=r-l;
if(Play_Boom(a,b,-,fir,)) return ;
for(int i=l+;i+pls<=;i++)
if(a.CanPlayMoreSingle(i,i+pls)){
a.PlayMoreSingle(i,i+pls);
bool now=Play_MS(b,a,i,i+pls,,);
if(!now){
if(fir) Out_MS(i,i+pls);
END;
}
a=_a;
}
NXT;
} bool Play_MC(player a,player b,int l,int r,bool fir,bool ok){
if(b.empty()) return ;
player _a=a; int pls=r-l;
if(Play_Boom(a,b,-,fir,)) return ;
for(int i=l+;i+pls<=;i++)
if(a.CanPlayMoreCouple(i,i+pls)){
a.PlayMoreCouple(i,i+pls);
bool now=Play_MC(b,a,i,i+pls,,);
if(!now){
if(fir) Out_MC(i,i+pls);
END;
}
a=_a;
}
NXT;
} bool play(player a,player b,bool fir=){
if(b.empty()) return ;
if(Play_Boom(a,b,-,fir,)) return ;
for(int i=;i>=;i--){
if(Play_MS(a,b,-,-+i,fir,)) return ;
}
for(int i=;i>=;i--){
if(Play_MC(a,b,-,-+i,fir,)) return ;
}
if(Play_Three(a,b,-,fir,)) return ;
if(Play_3Single(a,b,-,fir,)) return ;
if(Play_3Couple(a,b,-,fir,)) return ;
if(Play_Couple(a,b,-,fir,)) return ;
if(Play_Single(a,b,-,fir,)) return ;
if(Play_4Single(a,b,-,fir,)) return ;
if(Play_4Couple(a,b,-,fir,)) return ;
return ;
} int Main(){
player a,b;
printf("INPUT AI:\n");
b.read();
printf("INPUT PLAYER:\n");
a.read();
if(!play(a,b,)){
printf("DIE\n");
return ;
}
while(){
a=newA; b=newB;
printf("\n");
if(a.empty()){
printf("WIN\n");
return ;
} string now; cin>>now;
if(now=="EXIT") return ;
if(Is_Empty(now)){
if(!play(a,b,)){
printf("DIE\n");
}
continue;
}
for(int i=;i<now.length();i++) b.PlaySingle(GetVal(now[i])); if(Is_Single(now)&&Play_Single(a,b,GetVal(now[]),,)==) NO;
if(Is_Couple(now)&&Play_Couple(a,b,GetVal(now[]),,)==) NO;
if(Is_Three(now)&&Play_Three(a,b,GetVal(now[]),,)==) NO;
if(Is_Boom(now)&&Play_Boom(a,b,GetVal(now[]),,)==) NO;
if(Is_Rocket(now)&&Play_Rocket(a,b,)==) NO;
if(Is_3Single(now)&&Play_3Single(a,b,GetVal(now[]),,)==) NO;
if(Is_3Couple(now)&&Play_3Couple(a,b,GetVal(now[]),,)==) NO;
if(Is_4Single(now)&&Play_4Single(a,b,GetVal(now[]),,)==) NO;
if(Is_4Couple(now)&&Play_4Couple(a,b,GetVal(now[]),,)==) NO;
if(Is_MS(now)&&Play_MS(a,b,GetVal(now[]),GetVal(now[now.length()-]),,)==) NO;
if(Is_MC(now)&&Play_MC(a,b,GetVal(now[]),GetVal(now[now.length()-]),,)==) NO;
}
} int main(){
while() Main();
}