prow2012-A3-0018

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

zYc学长怎么没写题意啊？？？

题意：最正常的平胡麻将题（无十三幺，无七对糊法），问补上哪块牌可以胡。

模拟即可，加上某块牌后，用最暴力的DFS每次消去三块能连的，最后判断即可。



{{{


#include <iostream>
#include <vector>
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
using namespace std;
int p[10],s[10],m[10],z[10],debug;
bool dfs(int a[],int limit,int lian){
    int i;
    for (i=1;i<10;i++)
        if (a[i]>0){
            if (a[i]>=3){
                a[i]-=3;
                if (dfs(a,limit,lian)) return true;
                a[i]+=3;
            }
            if (lian&&i+2<10&&a[i]>0&&a[i+1]>0&&a[i+2]>0)
            {
                a[i]--,a[i+1]--,a[i+2]--;
                if (dfs(a,limit,lian)) return true;
                a[i]++,a[i+1]++,a[i+2]++;
            }
        }
    int t = 0,dui=0;
    for (i=1;i<10;i++)
        if (a[i]>0)
        t+=a[i],dui++;
    //if (debug==28&&lian==0) printf("%d %d %d\n",limit,t,dui);
    if (limit==2&&t==2&&dui==1) return true;
    if (limit==0&&t==0) return true;
    return false;
}


bool find(int a[],int limit,int lian){
//  if (debug==28&&lian==0) printf("%d %d %d\n",limit,lian,z[0]);
    if (limit==1) return false;
    int b[10];
    for (int i=0;i<10;i++) {
        b[i] = a[i];

        if (i>0&&b[i]>4) return false;
    }
//  if (debug==28&&lian==0) printf("--------\n");
    bool res = dfs(a,limit,lian);
    for (int i=0;i<10;i++) a[i] = b[i];
    return res;
}
bool check(int i){
    int eye = 0;
    debug = i;
/*  if (i==28){
        for (int j=0;j<10;j++) 
            printf("%d ",z[j]);
        printf("\n");
    }*/
    if (!find(p,p[0]%3,1)) return false;
    if (p[0]%3==2) eye++;
//  if (i==28)printf("p\n");
    if (!find(s,s[0]%3,1)) return false;
    if (s[0]%3==2) eye++;
//  if (i==28)printf("s\n");
    if (!find(m,m[0]%3,1)) return false;
    if (m[0]%3==2) eye++;
//  if (i==28)printf("m\n");
    if (!find(z,z[0]%3,0)) return false;
    if (z[0]%3==2) eye++;
//  if (i==28) printf("%d\n",z[0]%3);
    if (eye==1) return true;
    return false;
}
int main(){
    char str[100];
    int i,j;
    int ans[100],res = 0;
    while(scanf("%s",str)!=EOF){
        memset(p,0,sizeof(p));
        memset(s,0,sizeof(s));
        memset(m,0,sizeof(m));
        memset(z,0,sizeof(z));
        for (i=0;i<26;i+=2){
            int c = str[i]-'0',d = str[i+1];
            if (d=='s')
                s[0]++,s[c]++;
            else if (d=='p')
                p[0]++,p[c]++;
            else if (d=='m')
                m[0]++,m[c]++;
            else if (d=='z')
                z[0]++,z[c]++;
        }
        res = 0;
        for (i=0;i<34;i++){
            if (i/9==0) m[0]++,m[i%9+1]++;
            else if (i/9==1) p[0]++,p[i%9+1]++;
            else if (i/9==2) s[0]++,s[i%9+1]++;
            else if (i/9==3) z[0]++,z[i%9+1]++;
            if (check(i)){
                ans[res++] = i;
            }
            if (i/9==0) m[0]--,m[i%9+1]--;
            else if (i/9==1) p[0]--,p[i%9+1]--;
            else if (i/9==2) s[0]--,s[i%9+1]--;
            else if (i/9==3) z[0]--,z[i%9+1]--;
        }
        if (res==0) printf("0");
            else 
            printf("%d ",res);
        char ch;
        for (j=0;j<res;j++){
            i = ans[j];
            if (i/9==0) ch = 'm';
            else if (i/9==1) ch='p';
            else if (i/9==2) ch = 's';
            else if (i/9==3) ch = 'z';
            printf("%d%c",i%9+1,ch);
        }
        printf("\n");
    }
}



}}}

zYc学长怎么没写题意啊？？？

题意：最正常的平胡麻将题（无十三幺，无七对糊法），问补上哪块牌可以胡。

模拟即可，加上某块牌后，用最暴力的DFS每次消去三块能连的，最后判断即可。

#include <iostream>
#include <vector>
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
using namespace std;
int p[10],s[10],m[10],z[10],debug;
bool dfs(int a[],int limit,int lian){
    int i;
    for (i=1;i<10;i++)
        if (a[i]>0){
            if (a[i]>=3){
                a[i]-=3;
                if (dfs(a,limit,lian)) return true;
                a[i]+=3;
            }
            if (lian&&i+2<10&&a[i]>0&&a[i+1]>0&&a[i+2]>0)
            {
                a[i]--,a[i+1]--,a[i+2]--;
                if (dfs(a,limit,lian)) return true;
                a[i]++,a[i+1]++,a[i+2]++;
            }
        }
    int t = 0,dui=0;
    for (i=1;i<10;i++)
        if (a[i]>0)
        t+=a[i],dui++;
    //if (debug==28&&lian==0) printf("%d %d %d\n",limit,t,dui);
    if (limit==2&&t==2&&dui==1) return true;
    if (limit==0&&t==0) return true;
    return false;
}
bool find(int a[],int limit,int lian){
//  if (debug==28&&lian==0) printf("%d %d %d\n",limit,lian,z[0]);
    if (limit==1) return false;
    int b[10];
    for (int i=0;i<10;i++) {
        b[i] = a[i];
        if (i>0&&b[i]>4) return false;
    }
//  if (debug==28&&lian==0) printf("--------\n");
    bool res = dfs(a,limit,lian);
    for (int i=0;i<10;i++) a[i] = b[i];
    return res;
}
bool check(int i){
    int eye = 0;
    debug = i;
/*  if (i==28){
        for (int j=0;j<10;j++) 
            printf("%d ",z[j]);
        printf("\n");
    }*/
    if (!find(p,p[0]%3,1)) return false;
    if (p[0]%3==2) eye++;
//  if (i==28)printf("p\n");
    if (!find(s,s[0]%3,1)) return false;
    if (s[0]%3==2) eye++;
//  if (i==28)printf("s\n");
    if (!find(m,m[0]%3,1)) return false;
    if (m[0]%3==2) eye++;
//  if (i==28)printf("m\n");
    if (!find(z,z[0]%3,0)) return false;
    if (z[0]%3==2) eye++;
//  if (i==28) printf("%d\n",z[0]%3);
    if (eye==1) return true;
    return false;
}
int main(){
    char str[100];
    int i,j;
    int ans[100],res = 0;
    while(scanf("%s",str)!=EOF){
        memset(p,0,sizeof(p));
        memset(s,0,sizeof(s));
        memset(m,0,sizeof(m));
        memset(z,0,sizeof(z));
        for (i=0;i<26;i+=2){
            int c = str[i]-'0',d = str[i+1];
            if (d=='s')
                s[0]++,s[c]++;
            else if (d=='p')
                p[0]++,p[c]++;
            else if (d=='m')
                m[0]++,m[c]++;
            else if (d=='z')
                z[0]++,z[c]++;
        }
        res = 0;
        for (i=0;i<34;i++){
            if (i/9==0) m[0]++,m[i%9+1]++;
            else if (i/9==1) p[0]++,p[i%9+1]++;
            else if (i/9==2) s[0]++,s[i%9+1]++;
            else if (i/9==3) z[0]++,z[i%9+1]++;
            if (check(i)){
                ans[res++] = i;
            }
            if (i/9==0) m[0]--,m[i%9+1]--;
            else if (i/9==1) p[0]--,p[i%9+1]--;
            else if (i/9==2) s[0]--,s[i%9+1]--;
            else if (i/9==3) z[0]--,z[i%9+1]--;
        }
        if (res==0) printf("0");
            else 
            printf("%d ",res);
        char ch;
        for (j=0;j<res;j++){
            i = ans[j];
            if (i/9==0) ch = 'm';
            else if (i/9==1) ch='p';
            else if (i/9==2) ch = 's';
            else if (i/9==3) ch = 'z';
            printf("%d%c",i%9+1,ch);
        }
        printf("\n");
    }
}