yzoj 2377賛芬梭哈題解
12789 ワード
に言及
AliceとMukyuは最近、偶然にも、クロミ、ハート、梅、キューブのAからKまで52枚のカード(大きさ王なし)を使ったトランプゲームのルールが書かれた説明書を入手した.
残念なことに、ルールの説明ではゲーム全体の進行形に関する部分が引き裂かれ、AliceとMukyuは残っている部分から「手札上限は5枚」という情報しか知られていないので、毎回直接2人に5枚ずつ、誰の手札が大きいかを判定することにした.
すべての5枚のカードの組み合わせは、以下の秩序によって、大きいものから小さいものまで異なるカード型に分けられます.
1、同花順(Straight Flush):同じ花色、順番の札.例:Q♦ J♦ 10♦ 9♦ 8♦;
2、四条(Four of a Kind):同じ点数のカードが4枚あります.例:10♣ 10♦ 10♥ 10♠ 9♥;
3、フルハウス:同じ点数のカードを3枚、他の点数のカードを1対追加します.例:8♣ 8♦ 8♠ K♥ K♠;
4、同花(Flush):同じ花色の札を5枚.例:A♠ K♠ 10♠ 9♠ 8♠;
5、順子(Straight):順連のカードを5枚.例:K♦ Q♥ J♠ 10♦ 9♦;
6、三条(Three of a kind):同じ点数のカードが3枚あります.例:J♣ J♥ J♠ K♦ 9♠;
7、2対(Two Pairs):同じ点数のカードを2枚、同じ点数のカードを2枚追加します.例:A♣ A♦ 8♥ 8♠ Q♠;
8、一対(One Pair):同じ点数のカードを2枚.例:9♥ 9♠ A♣ J♠ 8♥;
9、対なし(Zilch):以上の組み合わせができないカードは、点数で大きさを決めます.例:A♦ Q♦ J♠ 9♣ 8♣.
カード型が同じなら点数と色で勝負を決める.(ポイント優先)
点数の順序(大きいから小さいまで)は、A>K>Q>J>10>9>8>7>6>5>4>3>2である.(注:5枚の手札が5 4 3 2 Aの場合、Aは最小の札と見なすことができ、この時の札型は依然として順子であり、順子の中で最小の1つである).
花色の順(大から小)は、黒桃(♠)>ハート(♥)>梅の花(♣)>四角形(♦).
例:1、Q♦ J♦ 10♦ 9♦ 8♦ > 8♣ 8♥ 8♠ K♥ K♠ (前者の札型は同花順で、後者より大きい).
2、9♣ 9♦ 9♠ Q♥ Q♠ > 8♣ 8♦ 8♠ K♥ K♠ (両者のカード型はいずれも満堂紅で、カード型の3枚の同じ点数のカードを9対8で比較した).
3、A♣ A♦ 8♥ 8♠ Q♠ > A♠ A♥ 7♥ 7♠ K♠ (両者のカード型はいずれも2対で、最大のペアは同じで、この場合比較的大きいペアで、8対7より大きい).
4、A♠ Q♠ J♥ 9♥ 8♥ > A♦ Q♦ J♠ 9♣ 8♣ (どちらもタイプが合っておらず、すべての数字が同じで、この場合は一番大きいカードの色、A♠ > A♦).
5、4♠ 4♥ A♦ Q♦ 5♦ > 4♣ 4♦ A♠ Q♠ 5♠ (どちらも1対で、すべての数字は同じですが、この場合は4が一番大きい部分なので、4を比較します♠ > 4♣)
AliceもMukyuも簡単に結果を判断できるが、現代の科学技術の力を見たいと思っている.
入力フォーマット
第1行は、N組のテストデータがあることを示す正の整数Nを含む.
各グループのテストデータは10行を含み、最初の5行は2つの整数でAliceの手にあるカードを記述し、最初の数はカードの数字(1はA、13はKを表す)、2番目の数はカードの花色(1は黒桃、2は赤心、3は梅、4はブロックを表す)を表す.
後の5行は行ごとに2つの整数でMukyuが手にしたカードを記述し、フォーマットは同じです.
出力フォーマット
テストデータのセットごとに、AliceまたはMukyuを1行ずつ出力し、誰が勝つかを示します.
サンプル入力
サンプル出力
サンプル解釈
Aliceの手札は同花順を構成し、Mukyuの手札は普通の順子のみを構成している.
データ範囲
10%のデータに対して、入力したすべてのカード型が正しいことを保証します.他の30%のデータに対して、入力したすべてのカード型が順子、同花または同花順であることを保証します.100%のデータに対して、N≦100000を保証する.C++選手はcinでデータを読み込むとタイムアウトする可能性が高いのでscanf/printfをお勧めします.
解析
大きなシミュレーションは、題意に従ってシミュレーションすればいいですが、細部はまだ多いので、大まかな考え方を話してください.
1.まず点数降順に並べ替えた後、5枚のカードの中の色の種類と点数の種類と最も多くの同じ点数が現れた回数によって分類することができ、まずカード型とその中の最大の1枚のカードの点数を探し出して、私たちは上のパラメータによって大部分のカード型を見分けることができます.
私たちはmcolで色の種類を表し,mdataは点数の種類を表し,mcomは最も多くの同じ点数が現れる回数を表す.
四条:mcol==4&&mdata==2&&mcom==4
満堂紅:mcol>=3&&mdata==2&&mcom==3
三条:mcol>=3&&mdata=3&&mcom=3
ペア:mcol>=2&&mdata==3&&mcom==2
ペア:mcol>=2&&mdata==4&&mcom==2
順子:mcol>=1&&mdata==5&&mcom==0(ペアなしの場合があります)
同花順、同花:mcol==1&&mdata==5&&mcom=0
その中で順子を細分化するだけで、花順と同じで、花と同じで、残りは間違いありません.
2.題意に従って$A$を特殊に処理すればよい.$A$は$2 3 4 5$と順子を構成してもよいし、$10 JQK$と順子を構成してもよいし、4本、満堂紅、3本、2組、1組、同じ花を使うときは$1->A$をここで特判を覚えておいてください.
3.注目すべきは、この問題の判断が少し面倒で、最大1枚のカードの点数ではなく、カード型の点数を比較する必要があるため、面倒なので、詳しく説明します.
顺子、同花顺:顺子に対して私达は直接上で求めた最大の1枚のカードの点数と花の色を比较することができて、私达は顺子が连続していることを知っているので、もし最大の1枚のカードの点数が同じならば彼らはデジタルはきっと同じです.
四条、満堂紅、三条:真ん中の点数を直接判断し、順番を並べた後、三/四枚同じのは必ず真ん中にあり、52枚のカードしかないので、点数が同じ場合は現れないので、直接点数を比較すればいい.
同花:各カードの点数を逆順に列挙し、コード数が同じなら花色を比較し、52枚のカードだから花色が同じになるはずがない.
2対:その中の2つのペアを探し出して、先に比較的に大きいペアの点数、更に比較的に小さいペアの点数、もしやはり同じならば更に最後の1枚の単札の点数を比較して、最後に比較的に大きいペアの点数、同じ理屈で52枚のカードしかありませんので、コード数が同じならば、花の色は必然的に同じではありません.
単対:同理はまず対子を探し出して、対子の点数を比較して、更に単牌の点数を比較して、最後に対子の花の色を比較します
対なし:逆順列挙して1枚の単牌点数を判断し、最後に最大1枚の花色を判断する.
コード#コード#
AliceとMukyuは最近、偶然にも、クロミ、ハート、梅、キューブのAからKまで52枚のカード(大きさ王なし)を使ったトランプゲームのルールが書かれた説明書を入手した.
残念なことに、ルールの説明ではゲーム全体の進行形に関する部分が引き裂かれ、AliceとMukyuは残っている部分から「手札上限は5枚」という情報しか知られていないので、毎回直接2人に5枚ずつ、誰の手札が大きいかを判定することにした.
すべての5枚のカードの組み合わせは、以下の秩序によって、大きいものから小さいものまで異なるカード型に分けられます.
1、同花順(Straight Flush):同じ花色、順番の札.例:Q♦ J♦ 10♦ 9♦ 8♦;
2、四条(Four of a Kind):同じ点数のカードが4枚あります.例:10♣ 10♦ 10♥ 10♠ 9♥;
3、フルハウス:同じ点数のカードを3枚、他の点数のカードを1対追加します.例:8♣ 8♦ 8♠ K♥ K♠;
4、同花(Flush):同じ花色の札を5枚.例:A♠ K♠ 10♠ 9♠ 8♠;
5、順子(Straight):順連のカードを5枚.例:K♦ Q♥ J♠ 10♦ 9♦;
6、三条(Three of a kind):同じ点数のカードが3枚あります.例:J♣ J♥ J♠ K♦ 9♠;
7、2対(Two Pairs):同じ点数のカードを2枚、同じ点数のカードを2枚追加します.例:A♣ A♦ 8♥ 8♠ Q♠;
8、一対(One Pair):同じ点数のカードを2枚.例:9♥ 9♠ A♣ J♠ 8♥;
9、対なし(Zilch):以上の組み合わせができないカードは、点数で大きさを決めます.例:A♦ Q♦ J♠ 9♣ 8♣.
カード型が同じなら点数と色で勝負を決める.(ポイント優先)
点数の順序(大きいから小さいまで)は、A>K>Q>J>10>9>8>7>6>5>4>3>2である.(注:5枚の手札が5 4 3 2 Aの場合、Aは最小の札と見なすことができ、この時の札型は依然として順子であり、順子の中で最小の1つである).
花色の順(大から小)は、黒桃(♠)>ハート(♥)>梅の花(♣)>四角形(♦).
例:1、Q♦ J♦ 10♦ 9♦ 8♦ > 8♣ 8♥ 8♠ K♥ K♠ (前者の札型は同花順で、後者より大きい).
2、9♣ 9♦ 9♠ Q♥ Q♠ > 8♣ 8♦ 8♠ K♥ K♠ (両者のカード型はいずれも満堂紅で、カード型の3枚の同じ点数のカードを9対8で比較した).
3、A♣ A♦ 8♥ 8♠ Q♠ > A♠ A♥ 7♥ 7♠ K♠ (両者のカード型はいずれも2対で、最大のペアは同じで、この場合比較的大きいペアで、8対7より大きい).
4、A♠ Q♠ J♥ 9♥ 8♥ > A♦ Q♦ J♠ 9♣ 8♣ (どちらもタイプが合っておらず、すべての数字が同じで、この場合は一番大きいカードの色、A♠ > A♦).
5、4♠ 4♥ A♦ Q♦ 5♦ > 4♣ 4♦ A♠ Q♠ 5♠ (どちらも1対で、すべての数字は同じですが、この場合は4が一番大きい部分なので、4を比較します♠ > 4♣)
AliceもMukyuも簡単に結果を判断できるが、現代の科学技術の力を見たいと思っている.
入力フォーマット
第1行は、N組のテストデータがあることを示す正の整数Nを含む.
各グループのテストデータは10行を含み、最初の5行は2つの整数でAliceの手にあるカードを記述し、最初の数はカードの数字(1はA、13はKを表す)、2番目の数はカードの花色(1は黒桃、2は赤心、3は梅、4はブロックを表す)を表す.
後の5行は行ごとに2つの整数でMukyuが手にしたカードを記述し、フォーマットは同じです.
出力フォーマット
テストデータのセットごとに、AliceまたはMukyuを1行ずつ出力し、誰が勝つかを示します.
サンプル入力
1
1 3
5 3
4 3
3 3
2 3
6 1
10 4
7 1
8 1
9 2
サンプル出力
Alice
サンプル解釈
Aliceの手札は同花順を構成し、Mukyuの手札は普通の順子のみを構成している.
データ範囲
10%のデータに対して、入力したすべてのカード型が正しいことを保証します.他の30%のデータに対して、入力したすべてのカード型が順子、同花または同花順であることを保証します.100%のデータに対して、N≦100000を保証する.C++選手はcinでデータを読み込むとタイムアウトする可能性が高いのでscanf/printfをお勧めします.
解析
大きなシミュレーションは、題意に従ってシミュレーションすればいいですが、細部はまだ多いので、大まかな考え方を話してください.
1.まず点数降順に並べ替えた後、5枚のカードの中の色の種類と点数の種類と最も多くの同じ点数が現れた回数によって分類することができ、まずカード型とその中の最大の1枚のカードの点数を探し出して、私たちは上のパラメータによって大部分のカード型を見分けることができます.
私たちはmcolで色の種類を表し,mdataは点数の種類を表し,mcomは最も多くの同じ点数が現れる回数を表す.
四条:mcol==4&&mdata==2&&mcom==4
満堂紅:mcol>=3&&mdata==2&&mcom==3
三条:mcol>=3&&mdata=3&&mcom=3
ペア:mcol>=2&&mdata==3&&mcom==2
ペア:mcol>=2&&mdata==4&&mcom==2
順子:mcol>=1&&mdata==5&&mcom==0(ペアなしの場合があります)
同花順、同花:mcol==1&&mdata==5&&mcom=0
その中で順子を細分化するだけで、花順と同じで、花と同じで、残りは間違いありません.
2.題意に従って$A$を特殊に処理すればよい.$A$は$2 3 4 5$と順子を構成してもよいし、$10 JQK$と順子を構成してもよいし、4本、満堂紅、3本、2組、1組、同じ花を使うときは$1->A$をここで特判を覚えておいてください.
3.注目すべきは、この問題の判断が少し面倒で、最大1枚のカードの点数ではなく、カード型の点数を比較する必要があるため、面倒なので、詳しく説明します.
顺子、同花顺:顺子に対して私达は直接上で求めた最大の1枚のカードの点数と花の色を比较することができて、私达は顺子が连続していることを知っているので、もし最大の1枚のカードの点数が同じならば彼らはデジタルはきっと同じです.
四条、満堂紅、三条:真ん中の点数を直接判断し、順番を並べた後、三/四枚同じのは必ず真ん中にあり、52枚のカードしかないので、点数が同じ場合は現れないので、直接点数を比較すればいい.
同花:各カードの点数を逆順に列挙し、コード数が同じなら花色を比較し、52枚のカードだから花色が同じになるはずがない.
2対:その中の2つのペアを探し出して、先に比較的に大きいペアの点数、更に比較的に小さいペアの点数、もしやはり同じならば更に最後の1枚の単札の点数を比較して、最後に比較的に大きいペアの点数、同じ理屈で52枚のカードしかありませんので、コード数が同じならば、花の色は必然的に同じではありません.
単対:同理はまず対子を探し出して、対子の点数を比較して、更に単牌の点数を比較して、最後に対子の花の色を比較します
対なし:逆順列挙して1枚の単牌点数を判断し、最後に最大1枚の花色を判断する.
コード#コード#
#include
using namespace std;
struct node{
int data;//
int col;//
}b[10],c[20];
struct Node{
int data;//
int col;//
int num;//
};
int n,ans;
bool cmp(node a,node b){
return a.data=1;--i){// !
if(a[i].data>=maxdata){
maxdata=a[i].data;
maxcol=max(a[i].col,maxcol);
}
}
p.data=maxdata;
p.col=maxcol;
return p;
}
Node cheak(node a[]){
int mdata=0;//
int mcol=0;//
int mcom=0;//
int book[20];
memset(book,0,sizeof(book));
for(int i=1;i<=5;++i){//
if(!book[a[i].col]){
book[a[i].col]=1;
mcol++;
}
}
memset(book,0,sizeof(book));
for(int i=1;i<=5;++i){//
if(!book[a[i].data]){
book[a[i].data]++;
mdata++;
}else{
book[a[i].data]++;
mcom=max(mcom,book[a[i].data]);
}
}
if(mcol==4&&mdata==2&&mcom==4){// , 1 A
for(int i=1;i<=5;++i){
if(a[i].data==1) a[i].data=14;
}
sort(a+1,a+6,cmp);
node tmp=find(a);
Node ans;
ans.col=tmp.col;
ans.data=tmp.data;
ans.num=2;
return ans;
}
else if(mcol>=3&&mdata==2&&mcom==3){// , 1 A
for(int i=1;i<=5;++i){
if(a[i].data==1) a[i].data=14;
}
sort(a+1,a+6,cmp);
node tmp=find(a);
Node ans;
ans.col=tmp.col;
ans.data=tmp.data;
ans.num=3;
return ans;
}
else if(mcol>=3&&mdata==3&&mcom==3){// , 1 A
for(int i=1;i<=5;++i){
if(a[i].data==1) a[i].data=14;
}
sort(a+1,a+6,cmp);
node tmp=find(a);
Node ans;
ans.col=tmp.col;
ans.data=tmp.data;
ans.num=6;
return ans;
}
else if(mcol>=2&&mdata==3&&mcom==2){// , 1 A
for(int i=1;i<=5;++i){
if(a[i].data==1) a[i].data=14;
}
sort(a+1,a+6,cmp);
node tmp=find(a);
Node ans;
ans.col=tmp.col;
ans.data=tmp.data;
ans.num=7;
return ans;
}
else if(mcol>=2&&mdata==4&&mcom==2){// , 1 A
for(int i=1;i<=5;++i){
if(a[i].data==1) a[i].data=14;
}
sort(a+1,a+6,cmp);
node tmp=find(a);
Node ans;
ans.col=tmp.col;
ans.data=tmp.data;
ans.num=8;
return ans;
}
else if(mcol>=1&&mdata==5&&mcom==0){// , ,
if(mcol>1){//
bool flag=1;
for(int i=2;i<5;++i){// 2-5
if(a[i+1].data!=a[i].data+1) flag=0;
}
if(flag){
bool tmp=1;
for(int i=2;i<=5;++i){// 10-A
if(a[i].data!=i+8)tmp=0;
}
if((a[2].data==a[1].data+1)||(tmp&&a[1].data==1)) flag=1;//
else flag=0;
}
if(!flag){//
for(int i=5;i>=1;--i){
if(a[i].data==1) a[i].data=14;
}
sort(a+1,a+6,cmp);
node tmp=find(a);
Node ans;
ans.col=tmp.col;
ans.data=tmp.data;
ans.num=9;
return ans;
}
node tmp=find(a);
Node ans;
ans.col=tmp.col;
if(a[1].data==1&&a[2].data!=2){// 10-A
ans.data=14;
ans.col=a[1].col;
}
else ans.data=tmp.data;
ans.num=5;
return ans;
}else{
bool flag=1;
for(int i=1;i<5;++i){// 2-5
if(a[i+1].data!=a[i].data+1) flag=0;
}
if(flag){
bool tmp=1;
for(int i=2;i<=5;++i){// 10-A
if(a[i].data!=i+8) tmp=0;
}
if((a[2].data==a[1].data+1)||(tmp&&a[1].data==1)) flag=1; //
else flag=0;
}
if(flag){//
node tmp=find(a);
Node ans;
ans.col=tmp.col;
if(a[1].data==1&&a[2].data==2) ans.data=1;
else if(a[1].data==1) ans.data=14;
else ans.data=tmp.data;
ans.num=1;
return ans;
}
else{//
for(int i=1;i<=5;++i){// 1 A
if(a[i].data==1) a[i].data=14;
}
sort(a+1,a+6,cmp);
node tmp=find(a);
Node ans;
ans.col=tmp.col;
ans.data=tmp.data;
ans.num=4;
return ans;
}
}
}
else{//
for(int i=5;i>=1;--i){
if(a[i].data==1) a[i].data=14;
}
sort(a+1,a+6,cmp);
node tmp=find(a);
Node ans;
ans.col=tmp.col;
ans.data=tmp.data;
ans.num=9;
return ans;
}
}
bool judge(Node x1,Node y1){//
if(x1.numy1.num) return false;
else{
if(x1.num==2||x1.num==3||x1.num==6){// , ,
return b[3].data>c[3].data;//
}
if(x1.num==4){//
for(int i=5;i>=1;--i){//
if(b[i].data>c[i].data) return true;
else if(b[i].data==c[i].data) continue;
else return false;
}
if(x1.col>y1.col) return true;
else return false;
}
if(x1.num==7){//
int tmp1=0;
int tmp2=0;
int tmp3=0;
int tmp4=0;
for(int i=1;i<5;++i){//
if(b[i].data==b[i+1].data){
if(!tmp1)tmp1=i;
else tmp3=i;
}
if(c[i].data==c[i+1].data){//
if(!tmp2)tmp2=i;
else tmp4=i;
}
}
if(b[tmp1].datac[tmp2].data) return true;//
else if(b[tmp1].datac[tmp4].data) return true;//
else if(b[tmp3].data=1;--i){//
if(b[i].data>c[i].data) return true;
else if(b[i].data==c[i].data) continue;
else return false;
}
if(max(b[tmp1].col,b[tmp1+1].col)>max(b[tmp2].col,b[tmp2+1].col)) return true;// ,
else return false;
}
}
}
else if(x1.num==8){//
int tmp1=0;
int tmp2=0;
for(int i=1;i<5;++i){//
if(b[i].data==b[i+1].data) tmp1=i;
if(c[i].data==c[i+1].data) tmp2=i;
}
if(b[tmp1].data>c[tmp2].data) return true;
else if(b[tmp1].data=1;--i){
if(b[i].data>c[i].data) return true;
else if(b[i].data==c[i].data) continue;
else return false;
}
if(b[tmp1].col>c[tmp2].col) return true;
else return false;
}
}
else if(x1.num==9){//
for(int i=5;i>=1;--i){
if(b[i].data>c[i].data) return true;
else if(b[i].data==c[i].data) continue;
else return false;
}
if(b[5].col>c[5].col) return true;// A 13
else return false;
}
else{//
if(x1.data>y1.data) return true;
else if(x1.datay1.col) return true;
else return false;
}
}
}
}
int main(){
//freopen("ptgiving.in","r",stdin);
//freopen("ptgiving.out","w",stdout);
scanf("%d",&n);
while(n--){
for(int i=1;i<=5;++i){
scanf("%d %d",&b[i].data,&b[i].col);
b[i].col=5-b[i].col;//
}
sort(b+1,b+6,cmp);
Node tmp1=cheak(b);
for(int i=1;i<=5;++i){
scanf("%d %d",&c[i].data,&c[i].col);
c[i].col=5-c[i].col;//
}
sort(c+1,c+6,cmp);
Node tmp2=cheak(c);
if(judge(tmp1,tmp2)) printf("Alice
");
else printf("Mukyu
");
}
return 0;
}