M_sea

洛谷4050 [JSOI2007]麻将
LuoguBZOJ分析考虑一个很暴力的思路。先枚举缺哪张牌,然后再枚举哪种牌是对子。现在主要是判断刻子和顺子。手玩...
扫描右侧二维码阅读全文
11
2019/01

洛谷4050 [JSOI2007]麻将

Luogu

BZOJ

分析

考虑一个很暴力的思路。

先枚举缺哪张牌,然后再枚举哪种牌是对子。

现在主要是判断刻子和顺子。手玩一下可以发现,优先凑刻子肯定更好。

于是再从小到大遍历每种牌,尽量多地凑刻子(s[i]%=3),再把比它大的两张牌凑成顺子(s[i+1]-=s[i],s[i+2]-=s[i])。

如果有一种牌的数量小于$0$了,那么就不行。

最后注意判一下无解。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400+10,M=1000+10;

int n,m;
int a[3*M+10],s[N],tmp[N];

inline int check(int x) { //判断x是否可行
    ++s[x];
    for (re int i=1;i<=n;++i) { //枚举对子
        if (s[i]<2) continue;
        memcpy(tmp,s,sizeof(tmp));
        tmp[i]-=2; int flag=1;
        for (re int j=1;j<=n;++j) {
            if (tmp[j]<0) { flag=0; break; }
            tmp[j]%=3,tmp[j+1]-=tmp[j],tmp[j+2]-=tmp[j];
        }
        if (tmp[n+1]<0||tmp[n+2]<0) flag=0;
        if (flag) { --s[x]; return 1; }
    }
    --s[x]; return 0;
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=3*m+1;++i) ++s[a[i]=read()];
    int flag=0;
    for (re int i=1;i<=n;++i)
        if (check(i)) flag=1,printf("%d ",i);
    if (!flag) puts("NO");
    else putchar('\n');
    return 0;
}
最后修改:2019 年 01 月 23 日 01 : 05 PM

发表评论