[JSOI2007]麻将

[JSOI2007]麻将

Time Limit:1000MS  Memory Limit:165536K
Total Submit:31 Accepted:10

Description

麻将是中国传统的娱乐工具之一。麻将牌的牌可以分为字牌(共有东、南、西、北、中、发、白七种)和序数牌(分为条子、饼子、万子三种花色,每种花色各有一 到九的九种牌),每种牌各四张。在麻将中,通常情况下一组和了的牌(即完成的牌)由十四张牌组成。十四张牌中的两张组成对子(即完全相同的两张牌),剩余 的十二张组成三张一组的四组,每一组须为顺子(即同花色且序数相连的序数牌,例如条子的三、四、五)或者是刻子(即完全相同的三张牌)。一组听牌的牌是指 一组十三张牌,且再加上某一张牌就可以组成和牌。那一张加上的牌可以称为等待牌。

在这里,我们考虑一种特殊的麻将。在这种特殊的麻将里,没有字牌,花色也只有一种。但是,序数不被限制在一到九的范围内,而是在1到n的范围内。 同时,也没有每一种牌四张的限制。一组和了的牌由3m + 2张牌组成,其中两张组成对子,其余3m张组成三张一组的m组,每组须为顺子或刻子。现给出一组3m + 1张的牌,要求判断该组牌是否为听牌(即还差一张就可以和牌)。如果是的话,输出所有可能的等待牌。

Input

包含两行。
第一行包含两个由空格隔开整数n, m (9<=n<=400, 4<=m<=1000)。第二行包含3m + 1个由空格隔开整数,每个数均在范围1到n之内。这些数代表要求判断听牌的牌的序数。

Output

输出为一行。
如果该组牌为听牌,则输出所有的可能的等待牌的序数,数字之间用一个空格隔开。所有的序数必须按从小到大的顺序输出。如果该组牌不是听牌,则输 出"NO"。

Sample Input

9 4
1 1 2 2 3 3 5 5 5 7 8 8 8

Sample Output

6 7 9

Source

我真是吐血啊。。两个麻将题完全不一样的瀑布汗。。。我顺着上一题的办法拼命搞。。
各种TLE+WA+MLE大囧。。。
最后发现TMD这题分明是贪心题啊。。我真是个沙茶。。。
首先枚举等的牌,
然后枚举哪个是一对,
然后从小到大扫描过去。。
可以发现当前的如果用3次或以上的顺子是沙茶的,所以用的顺子正好是除3的余数。。
然后扫描过去就OK了。。
复杂度是O(N^3)。。。
实际上Hash+Dp也能过很多点的样子。。
Code:
#include <cstdio>
#include <map>
#include <iostream>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=400;
using namespace std;
typedef unsigned long long ull;
int A[maxn]={},B[maxn]={},n,m;
bool Check()
{
rep(cur,n)
if(A[cur]>=2)
{
A[cur]-=2;
rep(i,n)B[i]=A[i];
bool ok=true;
for(int i=0;i<n;)
{
B[i]%=3;
if(!B[i])i++;
else
{
if(i+2<n)
{
if(B[i+1]<B[i]){ok=false;break;}
B[i+1]-=B[i];
if(B[i+2]<B[i]){ok=false;break;}
B[i+2]-=B[i];
i++;
}
else
{
ok=false;
break;
}
}
}
A[cur]+=2;
if(ok)return true;
}
return false;
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
cin>>n>>m;int x;
rep(i,m*3+1)
{
scanf("%d",&x);
A[–x]++;
}
int s=0;
rep(i,n)
{
A[i]++;
if(Check())
{
s++;
printf("%d ",i+1);
}
A[i]–;
}
if(!s)puts("NO");
}

One thought on “[JSOI2007]麻将

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>