计蒜客 ACM训练联盟周赛 第一场 从零开始的神棍之路 暴力dfs
题目描述
ggwdwsbs最近被Zeratul和Kyurem拉入了日本麻将的坑。现在,ggwdwsbs有13张牌,Kyurem又打了一张,加起来有14张牌。ggwdwsbs想拜托你帮他判断一下,这14张牌能否和。
为了方便起见,本题不考虑字牌,即只有万,筒,条三种类型的牌,牌上带有数字1~9,相同的牌最多可能出现四次。
麻将想要和,必须把14张牌凑成指定的类型——七对子(2222222的形式)或四面子一雀头(23333的形式)。
其中,七对子是指14张牌恰好是7对相同的牌(每两对牌不得相同),如果凑出这样的牌,就可以直接和了;
四面子一雀头是指有一对相同的牌,且其他12张牌凑出四个“3”,这里的“3”可以是三个一样的牌(即刻子),也可以是数字连续且种类一样的三张牌(即顺子)。
在日本麻将中,把牌凑成第二种类型(“23333”)是不足以和牌的,还需要满足另一个条件——存在役。
下面介绍本题要求考虑的四种役。
1. 断幺九:14张牌里没有带数字1和数字9的牌出现。
2. 纯全带幺九:与第一种相反,这种类型要求,那一对相同牌和四个“3”中都要出现至少一张带数字1或9的牌。
3. 平和:四个“3”全部以顺子的形式出现。
4. 对对和:四个“3”全部以刻子的形式出现
满足上述四种中的一种,且满足“23333”的格式,也可以和牌。
请帮ggwdwsbs判断一下,他这14张牌能否和。
输入
第一行一个整数t,表示测试数据组数.
第二行到第t+1,每行有14个范围在1到27之间的整数,每个整数代表一张牌编号。
其中,编号1~9表示“万”的1~9,编号10~18表示“筒”的1~9,编号19~27表示“条”的1~9。
数据保证t≤100,每行的14张牌按编号从小到大给出。
输出
输出t行,每行一个整数,如果能和请输出1,不能和请输出0。
注:日麻的规则还有有很多本题所没有提及,如果你是一个日麻高手,请假装自己不知道那些规则以AC本题。
输出时每行末尾的多余空格,不影响答案正确性
样例输入
6
1 1 2 2 3 3 4 4 5 5 6 6 7 7
1 2 3 4 5 6 7 8 9 10 10 10 13 13
1 1 1 2 2 2 3 3 3 4 4 4 5 5
1 1 1 2 3 4 5 6 7 8 9 10 11 12
1 1 1 1 2 3 10 11 12 19 20 21 27 27
2 2 2 3 4 5 6 7 8 11 11 11 12 13
样例输出
1
0
1
1
1
1
题目来源
分析:比赛的时候用循环模拟的,结果模拟到心态爆炸,是有想过dfs,但是当时总是觉得循环差一点就出来了不想重新写dfs,于是循环模拟到了炸。。
比赛完后看完题解,和自己开始想的差不多,但是在处理23333的情况的时候,判断1,9和顺子还是刻字的时候优化了太多。。
接下来看代码把,解析写在代码里
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define debug(a) cout << #a << " " << a << endl
using namespace std;
const int maxn = 1e4 + 10;
const int mod = 1e9 + 7;
typedef long long ll;
ll cnt1, cnt2, num, vis[30];
ll dfs( ll x ) {
if( x == 6 ) { //到6时,就是遍历到了最后一个3
if( num == 0 || num == 5 ) { //满足第一种或第二种情况
return 1;
}
if( cnt1 == 4 || cnt2 == 4 ) { //满足第三种或第四种情况
return 1;
}
return 0;
} else if( x == 1 ) {
for( ll i = 1; i <= 27; i ++ ) {
if( vis[i] >= 2 ) { //第一步先取出一个对子,一定要有对子才能继续接下来的步骤
vis[i] -= 2;
if( i%9 == 0 || i%9 == 1 ) { //有幺九就记录加上
num ++;
}
if( dfs(x+1) ) {
return 1;
}
if( i%9 == 0 || i%9 == 1 ) {
num --;
}
vis[i] += 2;
}
}
return 0;
} else {
for( ll i = 1; i <= 27; i ++ ) {
if( vis[i] >= 3 ) { //判断是否有刻子
vis[i] -= 3;
if( i%9 == 0 || i%9 == 1 ) {
num ++;
}
cnt1 ++;
if( dfs(x+1) ) {
return 1;
}
if( i%9 == 0 || i%9 == 1 ) {
num --;
}
cnt1 --;
vis[i] += 3;
}
if( i%9 != 0 && i%9 != 8 && vis[i] && vis[i+1] && vis[i+2] ) { //判断是否有顺子
vis[i] --, vis[i+1] --, vis[i+2] --;
if( i%9 == 7 || i%9 == 1 ) {
num ++;
}
cnt2 ++;
if( dfs(x+1) ) {
return 1;
}
cnt2 --;
if( i%9 == 7 || i%9 == 1 ) {
num --;
}
vis[i] ++, vis[i+1] ++, vis[i+2] ++;
}
}
return 0;
}
}
int main() {
ll t;
cin >> t;
while( t -- ) {
memset( vis, 0, sizeof(vis) );
cnt1 = cnt2 = num = 0;
for( ll i = 0; i < 14; i ++ ) {
ll x;
cin >> x;
vis[x] ++;
}
ll cnt = 0;
for( ll i = 1; i <= 27; i ++ ) {
if( vis[i] == 2 ) {
cnt ++;
}
}
if( cnt == 7 ) { //是否满足七个对子
cout << 1 << endl;
continue;
}
if( dfs(1) ) {
cout << 1 << endl;
} else {
cout << 0 << endl;
}
}
return 0;
}
最新文章
- Python基础(二)之list
- C 替换字符方法--1
- jsp页面添加一个集合数组到action(用序列化提交)
- Codeforces Round #374 (Div. 2) A B C D 水 模拟 dp+dfs 优先队列
- Json数据解析在Unity3d中的应用
- python+matplotlib+web.py
- [BZOJ]1005 明明的烦恼(HNOI2008)
- Visual Studio Shortcuts
- Python内置函数(31)——id
- MariaDB 和 MySQL 比较
- arithmetic-02
- express koa koa2 优缺点分析
- 由于防火墙限制无法访问linux服务器上的tomcat应用
- iOS UI-文本视图(UITextView)
- dbvis的使用
- JS实现填报时对修改过的单元格进行标识
- PO_职位职务审批模式详解(设定)
- 用python实现购物车功能
- mac 上使用octave的plot错误的解决办法
- 一道关于数据库(经典父子级 ID 关联)更新题,大家帮忙想想还有其它解决思路没有?
热门文章
- codeforces 339 D.Xenia and Bit Operations(线段树)
- tab切换echarts无法正常显示问题
- jenkins弱口令漏洞
- Web容器启动中执行某个Java类
- vue-cli3.0创建项目报npm install --loglevel error 踩坑的那把辛酸泪
- C#的委托事件总结
- 【Kubernetes 系列五】在 AWS 中使用 Kubernetes:EKS
- 基于SMS短信平台给手机发送短信
- 实现ssr服务端渲染demo
- Appium+python自动化(三十一)- 元芳,你怎么看? - 日志收集-logging(超详解)