AC. 梦想

frank_c1

[NOIP 2015] 斗地主

发布于2016年01月14日 | 暂无评论 | 1,919阅读 | 搜索

题目描述

牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏。在斗地主中,牌的大小关系根据牌的数码表示如下:3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王,而花色并不对牌的大小产生影响。每一局游戏中,一副手牌由n张牌组成。游戏者每次可以根据规定的牌型进行出牌,首先打光自己的手牌一方取得游戏的胜利。现在,牛牛只想知道,对于自己的若干组手牌,分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。需要注意的是,本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下:
2016011401

输入格式

第一行包含用空格隔开的2个正整数T,N,表示手牌的组数以及每组手牌的张数。

接下来T组数据,每组数据N行,每行一个非负整数对Ai,Bi,表示一张牌,其中Ai表示牌的数码,Bi表示牌的花色,中间用空格隔开。特别的,我们用1来表示数码A,11表示数码J,12表示数码Q,13表示数码K;黑桃、红心、梅花、方片分别用1-4来表示;小王的表示方法为0 1,大王的表示方法为0 2。

输出格式

共T行,每行一个整数,表示打光第T组手牌的最少次数。

题目解析

NOIP 2015 D1T3,我的伤心题QAQ 现在做了这题后突然好后悔,如果当时能够更坚定一些,相信暴力出奇迹,坚持打完搜索,或许结果就不一样了呢~~

正如上文所言,这道题是可以直接暴搜过的。固然还有状压DP等高端做法,但蒟蒻的我还是得先想想怎么打搜索。题目要求的操作有点多,我们分类进行讨论。

首先根据题意和数据范围,可以注意到每次答案最大只有14。为什么呢?因为除去大小王,总共只有13种数码,每种数码的牌最多只有4张,而出单张、两张(对子)、三张、四张(炸弹)都计作一次,我们全部分开打,最多也只需要14次即可出完。这样的话,加上最优性剪枝后,搜索的深度可以保证不超过14层。

单一数码的出牌比较简单,比较复杂的是顺子。这里由于数据量比较小,可以每次暴力枚举三种顺子。还有就是带牌操作,其实三带二、三带一、四带二道理都差不多,都是先找到主牌,然后枚举可以带的牌,搜索下去即可。

考场上也基本有这种思路,但是实在觉得会T,而且比较难调,还是放弃了。事实证明,这道题编程复杂度和调试难度均不是很高,如果细心一点,过随机数据应该不是一件困难的事。其实一定程度上比的是心态。

目前只过了官方数据,UOJ上加强版数据实在因为程序太过暴力TLE。以后再研究一下更好一些的方法吧。本题具体实现细节详见代码。