题目分析10-20-30\texttt{10-20-30}10-20-30是一种简单的单人纸牌游戏使用标准525252张扑克牌牌面花色无关紧要。牌面价值规定如下JJJ、QQQ、KKK花牌的价值为101010AAA王牌的价值为111其余牌的价值为其面值222到101010。游戏开始前有一叠初始牌堆525252张牌。游戏过程如下发牌规则从左到右依次形成777个牌堆。每张牌被发到当前牌堆的顶部堆叠在已有牌的上方。发完最右边牌堆后下一张牌发到最左边牌堆如此循环。取牌规则每次将一张牌放到某个牌堆后需要检查该牌堆是否能取出三张牌。检查按照以下三种组合顺序进行组合一最前面两张牌 最后一张牌组合二最前面一张牌 最后面两张牌组合三最后面三张牌如果这三种组合中任意一种的三张牌点数之和等于101010、202020或303030则将该三张牌从牌堆中取出并按它们在牌堆中出现的顺序从上到下即从堆顶到堆底放置到主牌堆的底部。连锁反应取走三张牌后该牌堆可能暴露出新的三张牌组合需要继续检查并处理直到该牌堆没有符合条件的组合为止。牌堆消失如果一个牌堆刚好只有三张牌且这三张牌被取走则该牌堆消失后续发牌时跳过该位置。游戏结束条件胜利Win\texttt{Win}Win所有777个牌堆都消失。失败Loss\texttt{Loss}Loss主牌堆无牌可发但还有牌堆未消失。平局Draw\texttt{Draw}Draw游戏状态重复出现进入循环此时无法确定最终胜负。题目要求对于每组输入的初始牌堆525252张牌输出游戏结果以及发牌的总次数即总共处理了多少张牌。输入以单独的一个000结束。解题思路1. 整体框架本题的核心是模拟游戏过程同时需要检测游戏状态是否重复判断平局。由于游戏状态数量有限可以使用集合set\texttt{set}set来记录所有出现过的状态。2. 数据结构设计根据参考代码使用以下数据结构主牌堆使用string\texttt{string}string类型存储每个字符代表一张牌。字符A到K分别对应牌面值111到101010其中A111B222…J101010K101010。这种映射方式将牌面值编码为单个字符便于存储和比较。牌堆数组使用vectorstring\texttt{vectorstring}vectorstring存储777个牌堆。每个牌堆也是一个string\texttt{string}string字符串中的字符顺序代表从堆底到堆顶的顺序。状态记录使用setstring\texttt{setstring}setstring记录所有出现过的游戏状态。状态编码格式为主牌堆内容 * 牌堆1内容 # 牌堆2内容 # ... # 牌堆7内容 $ 当前发牌位置其中*、#、$作为分隔符确保状态编码的唯一性。3. 牌面值映射题目中牌面值与数字的对应关系如下牌面价值A1112222333344445555666677778888999910101010J101010Q101010K101010参考代码中使用cards ABCDEFGHIJK进行映射A对应111B对应222…J对应101010K对应101010。读取输入时将数字转换为对应的字符存储。4. 模拟过程详解模拟主循环的条件是主牌堆非空while (deck.size())。每轮循环执行以下步骤4.1 状态记录与平局检测在发新牌之前将当前游戏状态编码成字符串检查是否已经出现过如果出现过说明游戏进入循环标记为平局draw true跳出循环。否则将当前状态插入集合中。4.2 发牌取主牌堆顶部的第一张牌deck.front()将其放入当前牌堆piles[currentPile]的顶部即字符串末尾。然后从主牌堆中删除这张牌deck.erase(deck.begin())。发牌次数times自增111。4.3 处理牌堆的取牌逻辑如果当前牌堆的张数小于333则无法取牌直接移动到下一个牌堆。如果当前牌堆张数大于等于333则进入一个while循环反复检查是否满足取牌条件直到无法继续取牌为止。检查顺序严格按照题目要求组合一首两张 末一张piles[currentPile][0]piles[currentPile][1]piles[currentPile].back()计算这三个字符对应的数值之和。如果和为101010、202020或303030则取出这三张牌按顺序放入主牌堆底部deck.push_back(...)三次从当前牌堆中删除这三张牌先删末一张再删前两张组合二首一张 末两张检查条件满足则类似地取出并删除。组合三末三张检查条件满足则取出并删除。每次成功取牌后continue回到循环开头继续检查该牌堆是否还有新的组合可以取出。如果三种组合都不满足则break跳出循环。4.4 牌堆消失与移动取牌结束后检查当前牌堆是否为空如果为空从牌堆数组中删除该牌堆piles.erase(piles.begin() currentPile)。此时需要调整currentPile的位置如果currentPile超出了新的牌堆数组大小则重置为000下一张牌发到最左边牌堆。如果不为空移动到下一个牌堆currentPile并对牌堆数量取模实现循环发牌。4.5 胜利检测如果所有牌堆都消失piles.size() 0则游戏胜利跳出循环。5. 游戏结束后的输出循环结束后根据标志位判断结果如果draw为true输出Draw: times否则如果主牌堆非空且牌堆数为000输出Win : times注意样例中Win后面有两个空格否则如果主牌堆为空且牌堆数非000输出Loss: times6. 复杂度分析游戏状态的总数是有限的主牌堆的牌序最多52!52!52!种但由于游戏规则限制实际可达状态远小于此。各牌堆的牌序组合每个牌堆最多525252张牌。发牌位置最多777种。由于使用set\texttt{set}set进行状态查重每次状态编码的字符串长度约为O(527×平均牌堆长度)O(52 7 \times \text{平均牌堆长度})O(527×平均牌堆长度)总时间复杂度在可控范围内。7. 注意事项字符映射与数值计算计算牌面值时需要将字符转换为数值。参考代码中使用(piles[currentPile][0] - A)获得映射值。A索引000→ 牌值111B索引111→ 牌值222…I索引888→ 牌值999J索引999→ 牌值101010K索引101010→ 牌值101010。输出格式注意样例输出中Win : 66中Win后面有两个空格Loss:和Draw:后面只有一个空格。参考代码中分别使用了Win : 两个空格和Loss: 一个空格以及Draw: 一个空格与样例一致。多组输入输入包含多组测试用例每组525252个整数最后以单独的一个000结束。每组数据独立模拟。完整代码// 10-20-30// UVa ID: 246// Verdict: Accepted// Submission Date: 2016-05-15// UVa Run Time: 0.010s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;string deck;// 主牌堆字符序列代表从顶部到底部的牌vectorstringpiles;// 7个牌堆每个牌堆是一个字符串字符从底到顶setstringappeared;// 记录所有出现过的游戏状态// 调试用函数打印当前游戏状态voiddisplay(inttimes){coutTIMES:timesendl;coutDECK:;for(inti0;ideck.size();i)cout deck[i];coutendl;for(inti0;ipiles.size();i){cout(i1):;for(intj0;jpiles[i].size();j)cout piles[i][j];coutendl;}coutendl;}// 牌面值映射表cards[1]B代表牌值1cards[2]C代表牌值2...cards[10]K代表牌值10string cardsABCDEFGHIJK;intmain(intargc,char*argv[]){intcard;while(cincard,card)// 读入第一张牌若为0则结束{appeared.clear();// 清空状态记录deck.clear();// 清空主牌堆piles.clear();// 清空所有牌堆piles.resize(7);// 重新初始化为7个空牌堆// 将第一张牌存入主牌堆deck.push_back(cards[card]);// 读入剩余的51张牌for(inti1;i51;i){cincard;deck.push_back(cards[card]);}intcurrentPile0;// 当前发牌的牌堆索引0到6inttimes0;// 发牌总次数booldrawfalse;// 是否为平局// 主游戏循环当主牌堆非空时继续while(deck.size()){// 构建当前游戏状态的唯一标识字符串string tagdeck;tag*;// 分隔符for(inti0;ipiles.size();i){tagpiles[i];tag#;// 分隔符}tag$;// 分隔符tagto_string(currentPile);// 检查状态是否重复平局判定if(appeared.count(tag)0){drawtrue;break;}elseappeared.insert(tag);// 发牌从主牌堆顶部取一张牌放到当前牌堆的顶部字符串末尾carddeck.front();piles[currentPile].push_back(card);deck.erase(deck.begin());// 从主牌堆中移除该牌times;// 发牌次数加1// 如果当前牌堆少于3张无法取牌直接移动到下一个牌堆if(piles[currentPile].size()3){currentPile;currentPilecurrentPile%piles.size();continue;}// 反复检查当前牌堆是否可以取牌直到不能取为止while(piles[currentPile].size()3){// 组合一最前面两张牌 最后一张牌intcombination(piles[currentPile][0]-A)(piles[currentPile][1]-A)(piles[currentPile].back()-A);if(combination10||combination20||combination30){// 将三张牌按顺序放入主牌堆底部deck.push_back(piles[currentPile][0]);deck.push_back(piles[currentPile][1]);deck.push_back(piles[currentPile].back());// 从当前牌堆中删除这三张牌piles[currentPile].erase(piles[currentPile].end()-1);piles[currentPile].erase(piles[currentPile].begin());piles[currentPile].erase(piles[currentPile].begin());continue;// 继续检查该牌堆}// 组合二最前面一张牌 最后面两张牌combination(piles[currentPile].front()-A)(piles[currentPile][piles[currentPile].size()-2]-A)(piles[currentPile][piles[currentPile].size()-1]-A);if(combination10||combination20||combination30){deck.push_back(piles[currentPile].front());deck.push_back(piles[currentPile][piles[currentPile].size()-2]);deck.push_back(piles[currentPile][piles[currentPile].size()-1]);piles[currentPile].erase(piles[currentPile].end()-1);piles[currentPile].erase(piles[currentPile].end()-1);piles[currentPile].erase(piles[currentPile].begin());continue;}// 组合三最后面三张牌combination(piles[currentPile][piles[currentPile].size()-3]-A)(piles[currentPile][piles[currentPile].size()-2]-A)(piles[currentPile][piles[currentPile].size()-1]-A);if(combination10||combination20||combination30){deck.push_back(piles[currentPile][piles[currentPile].size()-3]);deck.push_back(piles[currentPile][piles[currentPile].size()-2]);deck.push_back(piles[currentPile][piles[currentPile].size()-1]);piles[currentPile].erase(piles[currentPile].end()-1);piles[currentPile].erase(piles[currentPile].end()-1);piles[currentPile].erase(piles[currentPile].end()-1);continue;}break;// 三种组合都不满足跳出循环}// 处理牌堆消失和移动发牌位置if(piles[currentPile].size()0){// 当前牌堆消失从数组中删除piles.erase(piles.begin()currentPile);// 调整下一个发牌位置如果越界则回到最左边if(currentPilepiles.size())currentPile0;}else{// 移动到下一个牌堆循环currentPile;currentPilecurrentPile%piles.size();}// 胜利条件所有牌堆都消失了if(piles.size()0)break;}// 根据结果输出if(draw)coutDraw: timesendl;elseif(deck.size()piles.size()0)coutWin : timesendl;// 注意Win后面有两个空格elseif(deck.size()0piles.size())coutLoss: timesendl;}return0;}