1028: [JSOI2007]麻将
2024-08-29 12:46:54
1028: [JSOI2007]麻将
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 2638 Solved: 1168
[Submit][Status][Discuss]
Description
麻将是中国传统的娱乐工具之一。麻将牌的牌可以分为字牌(共有东、南、西、北、中、发、白七种)和序数
牌(分为条子、饼子、万子三种花色,每种花色各有一到九的九种牌),每种牌各四张。在麻将中,通常情况下一
组和了的牌(即完成的牌)由十四张牌组成。十四张牌中的两张组成对子(即完全相同的两张牌),剩余的十二张
组成三张一组的四组,每一组须为顺子(即同花色且序数相连的序数牌,例如条子的三、四、五)或者是刻子(即
完全相同的三张牌)。一组听牌的牌是指一组十三张牌,且再加上某一张牌就可以组成和牌。那一张加上的牌可以
称为等待牌。在这里,我们考虑一种特殊的麻将。在这种特殊的麻将里,没有字牌,花色也只有一种。但是,序数
不被限制在一到九的范围内,而是在1到n的范围内。同时,也没有每一种牌四张的限制。一组和了的牌由3m + 2张
牌组成,其中两张组成对子,其余3m张组成三张一组的m组,每组须为顺子或刻子。现给出一组3m + 1张的牌,要
求判断该组牌是否为听牌(即还差一张就可以和牌)。如果是的话,输出所有可能的等待牌。
Input
包含两行。第一行包含两个由空格隔开整数n, m (9<=n<=400, 4<=m<=1000)。第二行包含3m + 1个由空格隔开
整数,每个数均在范围1到n之内。这些数代表要求判断听牌的牌的序数。
Output
输出为一行。如果该组牌为听牌,则输出所有的可能的等待牌的序数,数字之间用一个空格隔开。所有的序数
必须按从小到大的顺序输出。如果该组牌不是听牌,则输出"NO"。
Sample Input
9 4
1 1 2 2 3 3 5 5 5 7 8 8 8
1 1 2 2 3 3 5 5 5 7 8 8 8
Sample Output
6 7 9
刚开始看这题觉得应该是个非常繁琐的搜索。。。然后发现牌的总的数字比较小,然后就有了一个奇怪的思路,不如直接枚举所有可能出现的牌,然后判断它是否是一张听牌就行了。。。
然后发现这个思路并没有什么大问题。对于所有的牌进行桶排计数,然后可以发现的是一个牌如果能组成三个的刻子,那么就组成刻子,剩下的牌和后面的组成顺子,就不会发生冲突。
代码如下:
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(arr) memset(arr, 0, sizeof(arr))
const int inf = 0x3f3f3f3f;
int n,m,cnt[],f[],tot,flag,ans[];
inline int read()
{
int x=,c=;
char ch=' ';
while((ch>''||ch<'')&&ch!='-')ch=getchar();
while(ch=='-') c*=-,ch=getchar();
while(ch<=''&&ch>='')x=x*+ch-'',ch=getchar();
return x*c;
}
int main()
{
//freopen("date.in","r",stdin);
n=read();m=read();
for(re int i=;i<=*m;i++){
int d=read();
cnt[d]++;
}
for(re int i=;i<=n;i++){
cnt[i-]--;cnt[i]++;flag=;
for(re int j=;j<=n;j++){
if(cnt[j]>=){
if(flag) break;
int bj=;
for(re int k=;k<=n;k++) f[k]=cnt[k];
f[j]-=;f[n+]=f[n+]=;
for(re int k=;k<=n;k++){
if(f[k]<){bj=;break;}
f[k]%=;f[k+]-=f[k];f[k+]-=f[k];
}
if(f[n+]<||f[n+]<) bj=;
if(bj==) flag=,ans[++tot]=i;
}
}
}
if(!tot) cout<<"NO";
else for(re int i=;i<=tot;i++)
printf("%d ",ans[i]);
return ;
}
最新文章
- Logstash实践: 分布式系统的日志监控
- TCP/IP、Http、Socket的区别
- python 装饰器初步学习
- Python开发入门与实战11-单元测试
- 设计模式之美:Decorator(装饰)
- Java IO--压缩流
- css行内样式
- Postgresql两表联结更新
- 自定义一个searchBar
- Hibernate事务传播性
- objective-C学习笔记(十)协议
- 二分法查找的C语言实现:
- C# lazy<;T>;的用法
- Selenium自动化脚本开发总结
- Tarjan算法:求解图的割点与桥(割边)
- 《阿里巴巴Android编码规范》阅读纪要(一)
- newInstance()和new()的区别
- FineReport中日期时间函数使用总结
- PHP5.6 Dockerfile
- tensorflow pip install 安装指定版本的包并指定安装源(速度会快很多)
热门文章
- nyoj677 谍战
- HDU3062-Party(2-SAT)
- MVC架构模式概述
- 线性期望(BUPT2015校赛.F)
- 《从零开始学Swift》学习笔记(Day 11)——数据类型那些事儿?
- 关于JAVA中String类型的最大长度
- Asp.Net MVC anti-forgery token的问题:nameidentifier or identityprovider not present
- PAT 1071. 小赌怡情(15) JAVA
- hive bin下的进入beeline 命令行和hive有什么不同?
- 玩转NumPy数组