题面描述
塔子哥组织了一场消消乐小游戏,共有 ( N ) 名玩家参与,手中各有 ( M/N ) 张卡片,游戏由塔子哥开始,玩家依次出牌,若出牌与桌面上的牌相同,则可以将相同牌及其夹在其中的牌拿走并放回手牌中。游戏持续进行,直到倒数第二位玩家出完手牌,最终输出获胜者的轮数、编号以及最后手中的牌顺序。
题解:模拟
使用双端队列+哈希表来模拟整个游戏的过程
玩家手里面的牌可以使用双端队列来模拟,出牌操作就是弹出队头元素,用哈希表记录当前桌面上的牌,如果哈希表检测到玩家打出的牌桌面上存在,则需要把桌面的部分牌回收到当前玩家手中,并更新哈希表中的元素。
P2350.第1题-消消乐
题目描述
小明组织宿舍的同学们玩消消乐小游戏, 游戏可由N人参与, 总共有M张卡片平均分成N份, 保证M能被N整除。
- 游戏从"小明"开始,然后依次轮到其他牌友。出牌顺序是:小明 -> 同学1 -> 同学2 -> ... -> 同学N -> 小明 -> ...
- 每位同学每次出牌时,只能打出手中的第一张牌,并将其放在桌面的牌上。如果桌面上没有牌,则直接将牌打在桌面上。
- 如果某人打出的牌与桌面上的某张牌面相同,那么可以将两张相同牌面的牌及其夹在其中的所有牌拿走,并且将这些牌按照桌面上从上到下的顺序依次放回自己手牌的末尾。
- 当有人手中的牌全部出完时,即判出局,不再参与后续游戏。直到倒数第二位同学将手中的牌出完时,游戏立即结束。
输入描述
第一行输入为一个正整数N(2≤N≤4),表示参与的人数, 包括小明在内;
第二行输入为一个正整数M(4≤M≤104),用例保证M能被N整除
接下来一行,M/N个数字,表示一开始小明手中的牌面 num(1≤num≤13)
接下来N−1行,每行M/N个数字,分别表示一开始各位同学手中的牌面 num(1≤num≤13)
输出描述
第一行输出为产生获胜者的轮数;
第二行为获胜者编号,小明编号为1,同学1编号为2,同学2编号为3, 以此类推;
第三行输出获胜者最后手中的牌,顺序为出牌的顺序
样例
输入1
2
4
2 4
4 1
输出1
2
1
4 4
说明
第一轮:小明出2,同学1出4,桌上牌从上到下为[4 2],小明手中牌剩余4,牌友1手中牌剩余1;
第二轮:小明出4,桌面有相同牌4,小明将桌面的2张4拿回来,小明手中牌剩余[4 4],同学1出1,与桌面的牌不同,同学2手中无牌、游戏结束,小明胜出,手中剩余的牌为[4 4]。
输入2
2
6
2 4 1
3 2 1
输出2
3
2
1 2 4 3 2