[JSOI2007]麻将

贪心

题面

有$3m+1$张牌，范围$1-n$，询问插入哪一张牌后，可以使牌由一个对子（$2$张相同牌)、$m$个刻子（$3$张相同牌）或顺子（$3$张序数连续牌）组成。

• $n\leq400,m\leq1000$

解析

首先要枚举插入的那张牌。
数据显然用桶维护。
然而我们并不好区分几张相同牌是构成刻子、对子还是顺子。
举个栗子，$2\ 2\ 2\ 2\ 2\ 2\ 3\ 3\ 3\ 3\ 3\ 4\ 4\ 4\ 4\ 4\ $，一下子很有可能把它划为两个刻子，然而实际上是一刻一对一顺（构成顺子）。
由于对子只有一个，我们可以同时枚举对子。
然后从小往大枚举，能构成刻子就构，剩下的看能不能构成顺子即可。因$3$个顺子等价于$3$个刻子，出不了篓子。

然而作为一个逗逼，我先把所有的桶$\%3$。
这样会有什么后果呢？一个桶$4$顺了解一下。$2\ 2\ 3\ 3\ 3\ 3\ 4\ 4\ $
所以我们枚到当前位后才能模。

并且还要注意的是，我们要检查$n+1$和$n+2$这两个桶是否小于$0$。
还是思维不严密的锅

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define re register
#define il inline
#define ll long long
#define pf(x) ((x)*(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e4+100;
int n,m,a[N],tong[N],tot,p[N],sta[N],top;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=gi();m=gi();
  fp(i,1,3*m+1) a[i]=gi(),tong[a[i]]++;
  fp(i,1,n)
    {
      tong[i]++;
      fp(j,1,n)
    if(tong[j]>=2)
      {
        re int flag=1;
        tong[j]-=2;
        fp(o,1,n+2) p[o]=tong[o];
        fp(k,1,n+2)
          {
        if(tong[k]<0) {flag=0;break;}
        tong[k]%=3;tong[k+1]-=tong[k];tong[k+2]-=tong[k];
          }
        if(flag) sta[++top]=i;
        fp(o,1,n+2) tong[o]=p[o];
        tong[j]+=2;
        if(flag) break;
      }
      tong[i]--;
    }
  fp(i,1,top) printf("%d ",sta[i]);
  if(!top) puts("NO");
  else puts("");
  return 0;
}