NC20158. [JSOI2007]麻将
描述
输入描述
包含两行。第一行包含两个由空格隔开整数n, m (9 ≤ n ≤ 400, 4 ≤ m ≤ 1000)。
第二行包含3m + 1个由空格隔开整数，每个数均在范围1到n之内。这些数代表要求判断听牌的牌的序数。
输出描述
输出为一行。如果该组牌为听牌，则输出所有的可能的等待牌的序数，数字之间用一个空格隔开。所有的序数必须按从小到大的顺序输出。如果该组牌不是听牌，则输出"NO"。
示例1
输入:
9 4 1 1 2 2 3 3 5 5 5 7 8 8 8
输出:
6 7 9
C++11(clang++ 3.9) 解法, 执行用时: 78ms, 内存消耗: 504K, 提交时间: 2020-03-28 23:13:38
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<bitset>
#include<ctime>
#include<deque>
#include<stack>
#include<functional>
#include<sstream>
using namespace std;
#define maxn 200005
#define inf 0x7fffffff
#define rdint(x) scanf("%d",&x)
#define rdllt(x) scanf("%lld",&x)
#define rdult(x) scanf("%lu",&x)
#define rdlf(x) scanf("%lf",&x)
#define rdstr(x) scanf("%s",x)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int U;
#define ms(x) memset(x,0,sizeof(x))
const long long int mod=1e9;
#define Mod 1000000000
#define sq(x) x*x
#define eps 1e-5
typedef pair<int,int> pii;
#define pi acos(-1.0)
#define REP(i,n) for(int i=0;i<n;i++)
typedef pair<int,int> pii;
inline int rd()
{
int x=0;
char c=getchar();
bool f=false;
while(!isdigit(c))
{
if(c=='-') f=true;
c=getchar();
}
while(isdigit(c))
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return f?-x:x;
}
ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
int sqr(int x)
{
return x*x;
}
int n,m;
int but[maxn];
bool fg;
int tmp[maxn];
bool OK()
{
for(int i=1;i<=n;i++)
{
if(but[i]>=2)
{
but[i]-=2;
bool ok=1;
for(int j=1;j<=n+2;j++)
tmp[j]=but[j];
for(int j=1;j<=n+2;j++)
{
if(tmp[j]<0)
{
ok=0;
break;
}
tmp[j]%=3;
tmp[j+1]-=tmp[j];
tmp[j+2]-=tmp[j];
}
but[i]+=2;
if(ok) return true;
}
}
return false;
}
int main()
{
n=rd();
m=rd();
for(int i=1;i<=3*m+1;i++)
{
int x;
x=rd();
but[x]++;
}
for(int i=1;i<=n;i++)
{
but[i]++;
if(OK())
{
fg=1;
cout<<i<<' ';
}
but[i]--;
}
if(fg==0) cout<<"NO"<<endl;
return 0;
}