【写在前面】：
其实嘛，所谓的总结也就是两道题目罢了
（标题只是吸引你们系列？
UPD：下面的叙述中有些地方会把麻将和纸牌弄混，凑合这看吧，道理是一样的（雾...
【麻将问题】：
首先这类问题大概是怎么样的呢？
它应该是基于麻将和纸牌一类游戏的变种（说了一句废话= =|||
对于这类问题，题目一般不会做成题答让你和AI比智商？
一般的，这类游戏会有若干种麻将，每种有若干张
所谓的“话”可以理解为顺子（数字连续的3张或4张）和刻子（数字一样的3张）
考虑胡牌：即为一副麻将，拿出一对对子后，剩下的全部组成若干句话
纸牌问题的话，倒没什么特别的规矩，顺应题目吧（雾...
【问题解法】：
我们考虑实际问题好了...bzoj 1816: [Cqoi2010]扑克牌
【题目描述】：
你有n种牌，第i种牌的数目为ci。另外有一种特殊的牌：joker，它的数目是m。你可以用每种牌各一张来组成一套牌，也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌。比如，当n=3时，一共有4种合法的套牌：{1,2,3}, {J,2,3}, {1,J,3}, {1,2,J}。 给出n, m和ci，你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里（可以有牌不使用）。
【题目解法】：
看似爆搜的节奏（事实上似乎真的可以...
我们考虑答案具有单调性，即x合法，那么x+1也合法，因此我们转化成二分+判定性问题
对于x，判断是否合法
我们先考虑joker，他有m张，但是当二分到x时，他只能用min(x,m)张（显然
然后我们考虑一种贪心原则，考虑第i种牌，计算他的数量离x还差多少，如果差值的总和不超过min(x,m)，那么x就成立
证明的话个人感觉比较抽象，我们这样考虑，每次找出剩余牌最少的那个，然后用joker补，这样最后我们补的joker数就是每种牌与x的差值，并且每套牌中只有一个joker，然后就成立了bzoj 1028: [JSOI2007]麻将
【题目描述】:
麻将是中国传统的娱乐工具之一。麻将牌的牌可以分为字牌（共有东、南、西、北、中、发、白七种）和序数牌（分为条子、饼子、万子三种花色，每种花色各有一到九的九种牌），每种牌各四张。在麻将中，通常情况下一组和了的牌（即完成的牌）由十四张牌组成。十四张牌中的两张组成对子（即完全相同的两张牌），剩余的十二张组成三张一组的四组，每一组须为顺子（即同花色且序数相连的序数牌，例如条子的三、四、五）或者是刻子（即完全相同的三张牌）。一组听牌的牌是指一组十三张牌，且再加上某一张牌就可以组成和牌。那一张加上的牌可以称为等待牌。
在这里，我们考虑一种特殊的麻将。在这种特殊的麻将里，没有字牌，花色也只有一种。但是，序数不被限制在一到九的范围内，而是在1到n的范围内。同时，也没有每一种牌四张的限制。一组和了的牌由3m + 2张牌组成，其中两张组成对子，其余3m张组成三张一组的m组，每组须为顺子或刻子。现给出一组3m + 1张的牌，要求判断该组牌是否为听牌（即还差一张就可以和牌）。如果是的话，输出所有可能的等待牌。
【题目解法】：
首先考虑每种牌如果出现在3个顺子里，那么显然可以变成三对刻子，所以把每种牌mod 3一下就好了
然后枚举听的牌，在枚举对子，然后O(N)扫一遍，暴力判断是否合法即可
【其他解法】：
其实这题据说还能用爆搜+hash+set，具体解法看下面
不过我觉得这题的数据范围略大...用dp貌似比较蛋疼？bzoj 1860: [Zjoi2006]Mahjong麻将
【题目描述】：
【题目解法】：
我们考虑沿用上一题的方法，发现不可行，原因是与这道题目存在4张牌的刻子，我们无法使用正确的贪心算法
那么我们考虑爆搜，我们发现每个位置的牌只于下个位置，下下个位置有关
因此我们设计状态dfs(x,state,flag)表示当前到达第x位,x x+1 x+2的数量状态为state，是否存在对子（flag）
其实本质上应该是个dp，但是它真的很暴力...
然后我们用set存下三个量进行判重，至于那个state用最简单的hash即可：把三个位置上的数量拼起来（注意要补满三位）即可
然后暴力枚举当前放对子，还是顺子，还是3张牌的刻子，还是4张牌的刻子
貌似状态很多...不过跑的飞快
【标解】；
虽然我有标解的程序，但是完全看不懂啊...
我在下面会贴出来，求大神解释？【总结】：
嘛，如果你耐心的看完了，你会发现...什么鬼？就是3篇题解嘛...
没错就是三篇题解+一些吐槽罢了，求轻D...#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=55;
int n; long long m,l,r,a[N],ans,mid;
inline long long getint()
{
long long x=0; char c=getchar(); bool flag=false;
while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
if (c=='-') flag=true,c=getchar();
while ((c>='0')&&(c<='9')) x=x*10LL+(long long)(c-'0'),c=getchar();
if (flag) return -x; else return x;
}
void init()
{
n=getint(); m=getint(); ans=0; l=0; r=0;
for (int i=1; i<=n; i++) a[i]=getint(),r=max(r,a[i]);
}
inline bool judge(long long x)
{
long long now=min(x,m);
for (int i=1; i<=n; i++) now=now-max(0LL,x-a[i]);
if (now<0) return false; return true;
}
void solve()
{
r+=m;
while (l<=r)
{
int mid=(l+r)/2;
if (judge(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%lld\n",ans);
}
int main()
{
//freopen("1.in","r",stdin);
init();
solve();
return 0;
}bzoj 1816 dfs+set+hash
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
const int N=107;
struct node
{
int x,state; bool flag;
bool operator < (const node &a) const
{
if ((x==a.x)&&(state==a.state)) return flag<a.flag;
if (x==a.x) return state<a.state;
return x<a.x;
}
};
int n,a[N],cases; set<node> S; bool ans;
inline long long getint()
{
long long x=0; char c=getchar(); bool flag=false;
while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
if (c=='-') flag=true,c=getchar();
while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
if (flag) return -x; else return x;
}
void init()
{
n=3; ans=false; S.clear(); n=100;
memset(a,0,sizeof(a));
for (int i=1; i<=n; i++) a[i]=getint();
}
inline int calc(int x)
{
return a[x]*1000000+a[x+1]*1000+a[x+2];
}
void dfs(int x,bool flag)
{
while ((a[x]==0)&&(x<=n)) x++; node now; now.x=x; now.state=calc(x); now.flag=flag;
if ((now.x==n+1)&&(now.flag)) ans=true; if (ans) return; if (now.x>n) return;
if (S.count(now)) return; S.insert(now);
if ((a[x]>=2)&&(!flag)) {a[x]-=2; dfs(x,true); a[x]+=2;}
if ((a[x])&&(a[x+1])&&(a[x+2]))
{
a[x]--; a[x+1]--; a[x+2]--;
dfs(x,flag);
a[x]++; a[x+1]++; a[x+2]++;
}
if (a[x]>=3) {a[x]-=3; dfs(x,flag); a[x]+=3;}
if (a[x]>=4) {a[x]-=4; dfs(x,flag); a[x]+=4;}
}
int main()
{
//freopen("1.in","r",stdin);
cases=getint();
while (cases--)
{
init();
dfs(1,false);
if (ans) printf("Yes\n"); else printf("No\n");
}
return 0;
}bzoj 1816标解
program Mahjong;
const
st = '00110';
inf = 'mahjong.in';
ouf = 'mahjong.out';
maxn = 100;
var
f : array [ 0 .. maxn , 0 .. 6 , 0 .. 6 ] of boolean;
a : array [ -2 .. maxn ] of longint;
n : longint;
procedure openfile;
begin
assign ( input , inf ) ; reset ( input );
assign ( output , ouf ) ; rewrite ( output );
end;
procedure init;
var
i : longint;
begin
fillchar ( a , sizeof ( a ) , 0 );
for i := 1 to maxn do read ( a [ i ] );
end;
function ok ( x : longint ) : boolean;
begin
if ( x > 5 ) or ( x = 0 ) then ok := true else
if x < 0 then ok := false else ok := st [ x ] = '1';
end;
function min ( a , b : longint ) : longint;
begin
if a < b then min := a else min := b;
end;
function match : boolean;
var
i , j , k : longint;
p , l : longint;
begin
fillchar ( f , sizeof ( f ) , false );
match := true;
f [ 0 , 0 , 0 ] := true;
for i := 1 to maxn do
for j := 0 to 6 do
for k := 0 to j do
for l := 0 to 6 do
begin
if f [ i - 1 , l , j - k ] and ok ( a [ i - 2 ] - ( l + k ) ) then
begin
f [ i , j , k ] := true ; break;
end;
end;
for i := 0 to 6 do
if ok ( a [ maxn - 1 ] - i ) then
for j := 0 to 6 do
if ok ( a [ maxn ] - j ) then
if f [ maxn , i , j ] then exit;
match := false;
end;
function check : boolean;
var
i : longint;
begin
check := true;
for i := 1 to maxn do
if a [ i ] >= 2 then
begin
a [ i ] := a [ i ] - 2;
if match then exit;
a [ i ] := a [ i ] + 2;
end;
check := false;
end;
procedure main;
var
i : longint;
begin
readln ( n );
for i := 1 to n do
begin
init;
if check then writeln ( 'Yes' ) else writeln ( 'No' );
end;
end;
procedure closefile;
begin
close ( input );
close ( output );
end;
begin
openfile;
main;
closefile;
end.
鄂公网安备 42010202000505 号