当前位置：首页 > news >正文

UVa 178 Shuffling Patience

news 2026/5/8 3:57:09

题目分析

Shuffling Patience\texttt{Shuffling Patience}Shuffling Patience是一种纸牌游戏，游戏规则如下：

使用一副标准525252张牌，每张牌由点数（A\texttt{A}A、2\texttt{2}2、3\texttt{3}3、…\dots…、9\texttt{9}9、T\texttt{T}T、J\texttt{J}J、Q\texttt{Q}Q、K\texttt{K}K）和花色（S\texttt{S}S、H\texttt{H}H、C\texttt{C}C、D\texttt{D}D）组成。
游戏在4×44 \times 44×4的网格（最多161616堆）中进行，所有牌面朝上。
在放置新牌之前，检查已有牌堆的顶部牌中是否存在可覆盖的对子或三张：
- 对子：两张牌的点数均在A\texttt{A}A到T\texttt{T}T（即111到101010）之间，且点数之和为111111。
- 三张：恰好为J\texttt{J}J、Q\texttt{Q}Q、K\texttt{K}K（即点数111111、121212、131313）各一张。
如果存在多个可覆盖的对子或三张，按照最早出现的原则选择：
- 首先选择在牌堆顺序中（从左到右、从上到下）最早出现的可覆盖组合。
- 对于三张，三张中的每一张也按最早出现原则确定。
覆盖操作是不可分割的：一次覆盖操作（放置222或333张牌到对应堆顶）完成之前，不会进行新的覆盖判断。
如果无法在161616堆内完成全部525252张牌的放置，输出溢出信息；否则输出每堆的最终牌数（忽略空堆）。

解题思路

整体流程

读取输入，每525252张牌为一副完整的牌堆（deck\texttt{deck}deck）。
模拟游戏过程：
- 维护161616个堆（piles\texttt{piles}piles），每个堆是一个栈（只关心堆顶牌）。
- 维护当前已使用的堆数量currentPile\texttt{currentPile}currentPile。
- 按顺序处理每一张牌：
  - 获取所有非空堆的顶部牌。
  - 判断是否存在可覆盖的对子或三张。
  - 根据规则（最早出现）决定执行对子覆盖、三张覆盖还是新建堆。
  - 执行覆盖操作时，从当前牌中取出222或333张，依次放到对应堆的顶部。
  - 新建堆时，将当前牌放到下一个可用堆位。
- 如果新建堆时已用了161616堆且无可覆盖组合，则溢出。
输出结果：成功则输出每堆牌数（非零），失败则输出溢出信息。

关键数据结构

cards\texttt{cards}cards：存储一副牌的所有525252张牌，每张牌包含face\texttt{face}face（字符串）和value\texttt{value}value（点数数值，A=1\texttt{A}=1A=1，…\dots…，K=13\texttt{K}=13K=13）。
piles[16]\texttt{piles}[16]piles[16]：每个元素是一个vector<card>\texttt{vector<card>}vector<card>，模拟堆（栈）。
top\texttt{top}top：存储当前所有堆顶牌（仅存value\texttt{value}value和堆索引），用于寻找对子/三张。

寻找对子和三张

findTwoPair\texttt{findTwoPair}findTwoPair：遍历top\texttt{top}top中所有点数为111到101010的牌，寻找两数之和为111111的组合。由于题目要求“最早出现”，需要按照原始堆顺序（即top\texttt{top}top中索引顺序）寻找，而不是随意组合。这里采用双重循环，按索引顺序检查。
findThreePair\texttt{findThreePair}findThreePair：需要找到J\texttt{J}J、Q\texttt{Q}Q、K\texttt{K}K各一张。由于点数可以排序判断，但最终仍需按原始堆顺序确定覆盖顺序。实现中先将top\texttt{top}top按数值排序以确认三张是否存在，然后收集三个堆索引并排序，得到最早出现的顺序。

覆盖操作的选择规则

题目规定：

如果同时存在对子和三张，则选择覆盖牌中最早出现的那张牌所属的组合。
具体实现中，比较最早的对子中最小索引和最早的三张中最小索引，较小的优先。

溢出判断

新建堆时若currentPile≥16\texttt{currentPile} \ge 16currentPile≥16，且没有可覆盖组合，则溢出。
输出时需输出“溢出在第几张牌”，注意牌号是从111开始计数的。

代码实现

// Shuffling Patience// UVa ID: 178// Verdict: Accepted// Submission Date: 2016-02-22// UVa Run Time: 0.012s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 牌的结构：面值和数值structcard{string face;// 原始字符串，如 "TS"intvalue;// 数值：A=1, 2=2, ..., K=13};// 堆顶牌的信息：数值和堆索引structtopCard{intvalue,index;};// 用于排序（按数值），以便判断是否存在 JQK 三张booloperator<(topCard x,topCard y){returnx.value<y.value;}string cardValue="A23456789TJQK";// 点数顺序，用于转换vector<card>cards;// 存储一副牌的所有牌vector<topCard>top;// 当前所有堆顶牌vector<vector<card>>piles(16);// 最多 16 个堆inttwoPair[2],threePair[3];// 存储找到的对子/三张的堆索引inttestcase=0;// 当前是第几副牌// 获取所有非空堆的堆顶牌（仅数值和索引）voidgetTop(){top.clear();for(inti=0;i<piles.size();i++)if(piles[i].size()>0)top.push_back({piles[i].back().value,i});}// 寻找和为 11 的对子（数值范围 1~10）// 按堆的原始顺序（top 中顺序）寻找最早出现的一对boolfindTwoPair(){if(top.size()<=1)returnfalse;for(inti=0;i<top.size()-1;i++){if(top[i].value>=1&&top[i].value<=10){for(intj=i+1;j<top.size();j++){if(top[j].value>=1&&top[j].value<=10&&(top[i].value+top[j].value)==11){twoPair[0]=top[i].index;twoPair[1]=top[j].index;returntrue;}}}}returnfalse;}// 寻找 JQK 三张（数值 11,12,13 各一张）boolfindThreePair(){if(top.size()<=2)returnfalse;// 先按数值排序，方便检查是否存在 J、Q、Kstable_sort(top.begin(),top.end());// 依次寻找 J(11)、Q(12)、K(13)for(inti=0;i<3;i++){boolfound=false;for(intj=0;j<top.size();j++){if(top[j].value==(i+11)){threePair[i]=top[j].index;found=true;break;}}if(!found)returnfalse;}// 将三个堆索引排序，得到最早出现的顺序sort(threePair,threePair+3);returntrue;}// 模拟一副牌的完整游戏过程voidplay(){// 清空所有堆for(inti=0;i<=15;i++)piles[i].clear();intindex=0;// 当前要处理的牌在 cards 中的下标intcurrentPile=0;// 下一个可用的新堆索引while(index<cards.size()){getTop();// 获取当前所有堆顶牌booltwoPairFound=findTwoPair();boolthreePairFound=findThreePair();// 决定覆盖对子还是三张// 规则：如果同时存在，选择最早出现的牌所属的组合if((twoPairFound&&!threePairFound)||(twoPairFound&&threePairFound&&twoPair[0]<threePair[0])){// 覆盖对子：需要取 2 张新牌intnumber=0;while(index<cards.size()&&number<2){piles[twoPair[number++]].push_back(cards[index]);index++;}if(number<2)break;// 牌不足（正常情况不会发生）}elseif((!twoPairFound&&threePairFound)||(twoPairFound&&threePairFound&&twoPair[0]>threePair[0])){// 覆盖三张：需要取 3 张新牌intnumber=0;while(index<cards.size()&&number<3){piles[threePair[number++]].push_back(cards[index]);index++;}if(number<3)break;}else{// 没有可覆盖的组合，新建堆if(currentPile>=16)break;// 超出 16 堆，溢出piles[currentPile++].push_back(cards[index]);index++;}}// 输出结果cout<<setw(3)<<right<<testcase<<":";if(index==cards.size()){// 成功处理完全部 52 张牌for(inti=0;i<piles.size();i++)if(piles[i].size()>0)cout<<setw(3)<<right<<piles[i].size();cout<<"\n";}else{// 溢出，输出溢出时即将处理的牌号（index 是已处理的牌数，下一张是 index+1）cout<<" Overflowed on card no";cout<<setw(3)<<right<<(index+1)<<"\n";}}intmain(intargc,char*argv[]){cin.tie(0);cout.sync_with_stdio(false);string oneCard;intcounter=0;// 读取多副牌，每副 52 张，以 '#' 结束while(cin>>oneCard,oneCard!="#"){// 将牌面转换为数值：例如 'T' 对应 10，'J' 对应 11，等等cards.push_back({oneCard,(int)(cardValue.find(oneCard[0]))+1});counter++;// 凑齐一副牌（52 张）后开始模拟if(counter==52){testcase++;play();cards.clear();// 清空，准备下一副牌counter=0;}}return0;}

注意事项

输入中T\texttt{T}T表示点数101010，J\texttt{J}J、Q\texttt{Q}Q、K\texttt{K}K分别对应111111、121212、131313，A\texttt{A}A对应111。
覆盖操作是“不可分割的”，意味着一次覆盖必须连续取多张牌，中间不进行新的覆盖判断。
输出格式要求：每行以“编号:”开头，数字右对齐在宽度为333的字段中，溢出信息中“card no”后跟右对齐的牌号。
当同时存在对子和三张时，必须比较最早出现的单张牌来自哪个组合，而不是简单比较对子索引和三张索引的最小值——但本题中由于对子的“最早”是由其两张牌中靠前的那张决定的，而三张的“最早”也是由其靠前的那张决定的，因此可以直接比较twoPair[0]和threePair[0]。