题目描述钟面纸牌Clock Solitaire\texttt{Clock Solitaire}Clock Solitaire是一种使用一副525252张标准扑克牌的纸牌游戏。牌面点数与钟面小时对应关系如下J\texttt{J}J对应111点钟2\texttt{2}2到10\texttt{10}10分别对应222到101010点钟A\texttt{A}A对应111111点钟Q\texttt{Q}Q对应121212点钟K\texttt{K}K对应钟面中心游戏开始时将525252张牌按顺序发成131313堆121212个钟点位置加中心每堆444张牌牌面朝下。第一轮翻开中心堆最上面的牌然后根据翻开牌的点数将其放到对应位置K\texttt{K}K放回中心并翻开该位置最上面的牌如此循环。若最终525252张牌全部被翻开则游戏成功若某次需要翻开某堆牌但该堆已空则游戏失败。给定一个长度为525252的牌序列按顺时针从111点钟堆的最下面到中心堆的最上面依次给出考虑该序列的525252个循环移位每个移位对应另一种发牌顺序问其中有多少个移位能导致游戏成功。输入格式输入包含多组数据每组数据为一行包含525252个字符字符为J、2–9、T代表101010、A、Q、K。输入以单独一行0结束。输出格式对于每组牌序列输出一个整数表示该序列的525252个循环移位中成功的个数。样例输入7 J 9 3 J Q K A 2 3 4 5 6 7 8 9 T 8 Q K A 2 3 4 5 6 7 8 9 1 J Q K A 2 3 4 5 6 7 8 9 T J Q K A 2 1 4 5 6 0输出4题目分析本题模拟钟面纸牌游戏并统计循环移位的成功次数。由于只有525252张牌每个循环移位独立模拟一次每次模拟最多翻开525252张牌因此总操作数为52×52270452 \times 52 270452×522704非常小可以直接模拟。关键在于理解牌的布局方式给定序列按“从111点钟堆的最下面到中心堆的最上面”顺序给出即前444张牌属于111点钟堆从下到上第555到888张属于222点钟堆……第494949到525252张属于中心堆。游戏开始时中心堆最上面的牌是序列中第525252张即最后一格。每次翻开一张牌后根据其点数决定下一次翻开哪一堆的最上面一张。循环移位将整个序列循环左移一位相当于改变发牌时从哪张牌开始作为第一堆的最下面。例如原序列abcdef...循环左移一位得到bcdef...a这对应另一种发牌顺序。我们需要统计525252种移位中能成功完成游戏的数量。解题思路映射点数到堆索引建立从牌面字符到000到121212的映射其中000对应J\texttt{J}J111点钟111对应2\texttt{2}2……101010对应A\texttt{A}A111111点钟111111对应Q\texttt{Q}Q121212点钟121212对应K\texttt{K}K中心。这样翻开一张牌后下一个堆的索引即为该牌对应的映射值。模拟单次游戏使用二维数组cards[13][4]存储当前移位下每堆的444张牌按从下到上顺序。游戏开始时指针指向中心堆索引121212翻开该堆最上面一张牌即cards[12][0]。每翻开一张牌记录该堆已翻开数量uncovered[pointer]若该堆已翻开444张则游戏失败。否则根据牌面字符映射到下一个堆索引继续翻开该堆最上面一张。循环直到翻开的牌数达到525252成功或某堆已空失败。循环移位生成对于每个原始序列生成其525252个循环左移位对每个移位运行一次模拟统计成功的次数。复杂度每组数据525252个移位每个移位模拟最多525252步总操作约270427042704次非常快。复杂度分析对于每组输入循环移位数为525252每次模拟最多525252步时间复杂度为O(522)O(2704)O(52^2) O(2704)O(522)O(2704)。空间复杂度为O(52)O(52)O(52)用于存储牌堆。代码实现// Clock Solitaire// UVa ID: 635// Verdict: Accepted// Submission Date: 2016-08-30// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string lettersJ23456789TAQK;mapchar,intpiles;for(inti0;iletters.length();i)piles[letters[i]]i;charcard,cards[13][4];while(cincard,card!0){cin.putback(card);stringsequence(52,0);for(inti0;i52;i)cinsequence[i];intsuccess0;for(intk1;k52;k){for(inti0;i13;i)for(intj0;j4;j)cards[i][j]sequence[i*4j];intshifts0,uncovered[13];memset(uncovered,0,sizeof(uncovered));intpointer12;while(true){if(uncovered[pointer]3)break;uncovered[pointer];pointerpiles[cards[pointer][uncovered[pointer]-1]];shifts;}if(shifts52)success;sequence.push_back(sequence.front());sequence.erase(sequence.begin());}coutsuccess\n;}return0;}总结本题模拟了钟面纸牌游戏并通过循环移位测试了所有可能的发牌顺序。核心在于正确理解牌堆的存储顺序从下到上以及游戏规则每次翻开指定堆最上面一张。由于数据规模很小直接暴力模拟即可。该解法思路清晰实现简单适合作为模拟题的练习。