[Zjoi2006]Mahjong麻将

[Zjoi2006]Mahjong麻将

Time Limit:1000MS  Memory Limit:65536K
Total Submit:3 Accepted:3

Description

Input

第一行一个整数N(N<=100),表示玩了N次超级麻将。
接下来N行,每行100个数a1..a100,描述每次玩牌手中各种牌的数量。ai表示数字为i的牌有ai张。(0<=ai& lt;=100)

Output

输出N行,若胡了则输出Yes,否则输出No,注意区分Yes,No的大小写!

Sample Input

3
2 4 0 0 0 0 0 …… 0(一共98个0)
2 4 2 0 0 0 0 …… 0(一共97个0)
2 3 2 0 0 0 0 …… 0(一共97个0)

Sample Output

Yes
Yes
No

Source

Day2

一开始我看AC人数这么少。。以为是BT的难题。。不敢做。。
不过刚刚仔细看了下怎么好像仿佛。。是水题?
注意到从左往右消去每个麻将,首先当前的只能影响3个。。
所以记录当前3个的个数就足够了囧。。同时还要知道那一对有没有被用过。。
所以状态就是 (pos,Apos,Apos+1,Apos+2,have_pair_used)
应该说Dp就可以了。。不过我有点懒。。。所以用了Hash+set。。速度很快啊囧。。
Code:
#include <cstdio>
#include <set>
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
#define Debug(x) cout<<#x<<"="<<x<<endl;
const int inf=~0U>>1,seed=131,maxn=100;
using namespace std;
typedef unsigned long long ull;
ull P[maxn+1];
set<ull> S;
int A[maxn];
bool ok;
void dfs(int p,bool can,ull code)
{
if(!S.insert(code).second)return;
while(p<maxn&&A[p]==0)p++;
if(p==maxn){if(!can)ok=true;return;}
//three consecutive
if(p+2<maxn&&A[p]&&A[p+1]&&A[p+2])
{
A[p]–;A[p+1]–;A[p+2]–;
ull ncode=code-P[p]-P[p+1]-P[p+2];
dfs(p,can,ncode);if(ok)return;
A[p]++;A[p+1]++;A[p+2]++;
}
//three same
if(A[p]>=3)
{
A[p]-=3;
ull ncode=code-P[p]*3;
dfs(p,can,ncode);if(ok)return;
A[p]+=3;
}
//four same
if(A[p]>=4)
{
A[p]-=4;
ull ncode=code-P[p]*4;
dfs(p,can,ncode);if(ok)return;
A[p]+=4;
}
//use pair
if(A[p]>=2&&can)
{
A[p]-=2;
ull ncode=code-P[p]*2-P[maxn];
dfs(p,!can,ncode);if(ok)return;
A[p]+=2;
}
}
void Solve()
{
ull ret=0;
rep(i,maxn)
{
scanf("%d",A+i);
ret*=seed;ret+=A[i];
}
ret*=seed;ret+=1;
S.clear();
ok=false;
dfs(0,true,ret);
if(ok)puts("Yes");
else puts("No");
}
int main()
{
//freopen("in","r",stdin);
P[0]=1;rep(i,maxn)P[i+1]=P[i]*seed;
int t;cin>>t;rep(i,t)Solve();
}

3 thoughts on “[Zjoi2006]Mahjong麻将

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>