无话可说

为什么此题有那么多人玩欺骗^没有人真的做起么?

大家不要再次Cheat了，完全可以1次AC，因为....

http://www.vijos.cn/Record_Show.asp?id=133000

PS:看看记录吧---|多少人在Cheat!!!

经证明，过了此题的6人全都是用“提交答案法”做出来的

……

……

其实是我的猜测

至少

我是你的同学　AKD　cd99xs01　

是这样的

努力做此题中……

在考虑要不要先用老方法得个AC……

PS：同意AKD的看法

居然还有这种题~~~~~~

鄙人佩服~~

Ⅺ

这道题我想做出来,但不知道输入方法,有人能叫我吗?

人员的广泛猜测v功夫茶vv很好

这样例的槽点...
1、三带四带不能带王
2、第十个规则的第二个样例连带了几张牌都没数好...
3、私以为这题是语文题

加joker5，9 WA。。。
不加joker 2,3 WA。。。

这题太阴险，说得不清楚，弄得我用小号4次才A

以下是注意事项：
+ 这题的规则不允许把王带出来：无论是“三带一”or“四带二”or“飞机带翅膀” （感谢讨论区Glaceon08的提示）
+ 四带二时不能带对子
+ 飞机带翅膀中，可以由两个单张拼成对子，也就是说形如 555666777 + 223 的组合是允许的

考虑周全后应该还是可以做的，不要听下面的人用cheat，真没意思

思路：BFS+位运算状态压缩+hash记忆化（其实还有一个DFS，用于找“飞机带翅膀”）
用3位2进制用来存一种牌剩余的张数（因为只有0~4这5种可能），14张牌需要42位二进制，所以要用 long long

代码 200+，但愿有人能看懂

//0: joker
//1: 2
//2~13: 3~A
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 500007
#define INF 100000

typedef struct _nodeH{
struct _nodeH *next;
long long key;
} nodeH;

typedef struct _nodeQ{
struct _nodeQ *next;
long long status;
int step;
} nodeQ;

nodeH *hash[MAX_SIZE];
nodeQ *head, *tail;
int cards[14];

void addToHash(long long key);
int isInHash(long long key);
void addToQueue(long long status, int step);
long long changeStatus(long long status, int cardType, int numCard);
void DFS(long long status, int step, int index, int numLeft);
int BFS(long long initStatus);

int main(){
char line[500];
int i;
long long status;

memset(cards, 0, sizeof(cards));
memset(hash, 0, sizeof(hash));
status = 0;
scanf("%s", line);
for(i=0; line[i]!='\0'; i++){
if(line[i] == '1'){
cards[9]++;
i++;
}else if(line[i] == 'A'){
cards[13]++;
}else if(line[i] == 'D' || line[i] == 'X'){
cards[0]++;
}else if(line[i] == 'J'){
cards[10]++;
}else if(line[i] == 'K'){
cards[12]++;
}else if(line[i] == 'Q'){
cards[11]++;
}else{
cards[line[i]-'2'+1]++;
}
}
for(i=0; i<=13; i++)
status = (status << 3) | cards[i];
printf("%d\n", BFS(status));

return 0;
}

void addToHash(long long key){
nodeH p;
p = (nodeH)malloc(sizeof(nodeH));
p->key = key;
p->next = hash[key % MAX_SIZE];
hash[key % MAX_SIZE] = p;
}
int isInHash(long long key){
nodeH p = hash[key % MAX_SIZE];
while(p != NULL){
if(p->key == key)
return 1;
p = p->next;
}
return 0;
}
void addToQueue(long long status, int step){
if(!isInHash(status)){
addToHash(status);
tail->status = status;
tail->step = step;
tail->next = (nodeQ)malloc(sizeof(nodeQ));
tail = tail->next;
tail->next = NULL;
}
}
long long changeStatus(long long status, int cardType, int numCard){
long long tmp = ~((long long)7 << (3*(13-cardType)));
return (status & tmp) | ((long long)numCard << (3*(13-cardType)));
}
void DFS(long long status, int step, int index, int numLeft){
int i;
if(numLeft == 0){
addToQueue(status, step);
return;
}
for(i=index; i<=14-numLeft; i++){
if(cards[i] >= 1){
cards[i]--;
DFS(changeStatus(status, i, cards[i]), step, i, numLeft-1);
cards[i]++;
}
}
}
int BFS(long long initStatus){
nodeQ *p;
long long status, newStatus;
int step, i, j, k;

tail = (nodeQ*)malloc(sizeof(nodeQ));
head = tail;

addToQueue(initStatus, 0);
while(head != tail){
status = head->status;
step = head->step;
if(status == 0)
return step;

for(i=0; i<=13; i++) //get num of each card
cards[i] = (status >> (3*(13-i))) & 7;

for(i=0; i<=13; i++){
//1 or 2 or 3 or 4
for(j=1; j<=cards[i]; j++)
addToQueue(changeStatus(status, i, cards[i]-j), step+1);
}
for(i=1; i<=13; i++){
if(cards[i] >= 3){
//3+1
cards[i] -= 3;
newStatus = changeStatus(status, i, cards[i]);
for(j=1; j<=13; j++){
if(cards[j] >= 1)
addToQueue(changeStatus(newStatus, j, cards[j]-1), step+1);
}
cards[i] += 3;
}
if(cards[i] >= 4){
//4+1+1
cards[i] -= 4;
for(j=1; j<=13; j++){
if(cards[j] < 1)
continue;
cards[j]--;
newStatus = changeStatus(status, i, cards[i]);
newStatus = changeStatus(newStatus, j, cards[j]);
for(k=1; k<=13; k++){
if(k != j && cards[k] >= 1)
addToQueue(changeStatus(newStatus, k, cards[k]-1), step+1);
}
cards[j]++;
}
cards[i] += 4;
}
}
for(i=2; i<=13; i++){
for(j=i+4; j<=13; j++){
//series of cards x1
newStatus = status;
for(k=i; k<=j; k++){
if(cards[k] < 1)
break;
newStatus = changeStatus(newStatus, k, cards[k]-1);
}
if(k > j)
addToQueue(newStatus, step+1);
}
for(j=i+2; j<=13; j++){
//series of cards x2
newStatus = status;
for(k=i; k<=j; k++){
if(cards[k] < 2)
break;
newStatus = changeStatus(newStatus, k, cards[k]-2);
}
if(k > j)
addToQueue(newStatus, step+1);
}
for(j=i+1; j<=13; j++){
//series of cards x3
newStatus = status;
for(k=i; k<=j; k++){
if(cards[k] < 3)
break;
cards[k] -= 3;
newStatus = changeStatus(newStatus, k, cards[k]);
}
if(k > j){
addToQueue(newStatus, step+1);
DFS(newStatus, step+1, 1, j-i+1);
for(k=i; k<=j; k++)
cards[k] += 3;
}
}
}

p = head;
head = head->next;
free(p);
}

return INF;
}

#0:4
#1:3
#2:3
#3:4
#4:3
#5:3
#6:10
#7:5
#8:6
#9:6
各数据输出

不用cheat用搜索也能过。没人发搜索题解我就说说

麻烦点是考虑可以延展的牌型，三顺（可带可不带）、二顺、一顺

用 dfs(type, start, len, hand) 表示当前顺子类型type（一张还是两张还是三张），出到牌的点数为start，长度为len，目前打了hand手牌

三顺的带牌，可以再加一维dfs(type, start, now, len, hand)，now表示带牌现在有now张（目标当然是len张）

然后炸弹、火箭什么随便搜一下

剩下可以出的只有单和对，可以得到惟一最优出牌方式

为了优化，可以给每种牌型定个编号，这样防止重复搜索（比如先出炸弹再出顺子跟先出顺子再出炸弹是一样的）

注意：本题大王小王不能被带（貌似现实中可以带）

我也来cheat一个,嘻嘻!

数据其实很弱。。。。。

这难度3的题忒高AC率

看来我也来搅和下

练下cheat的技术

实在不明白不cheat怎么过

Yeah，第300题，庆祝一下！！！

我AC了！

不是Cheat！

要方法的找我！

绝对是好方法！

请+ＱＱ　６２３４４５０６７

这种题看似简单，其实要人命~~~~~~

我想了很久找出一种优先算法

按优先排列：

1.双顺（当最长单顺长度的1/2小于双顺长度）and（注意把炸弹拆成两个双顺的情况）

2.单顺（注意把对子或连对或双顺拆成两个单顺的情况）

3.飞机带翅膀

4.三带一

5.三顺

6.四带二

7.对子或单张或炸弹或三张

搞清楚这些出牌顺序的优先度是解这道题的关键~~~~~~

如有错误，恳请批评指正！