【LOJ】#6434. 「PKUSC2018」主斗地

题解

什么，我这题竟然快到了LOJ rk1？？？？

搜起来有点麻烦，不过感觉还是比斗地主好下手（至今没敢写斗地主

首先是暴力搜牌型，最多\(3^16\)（什么判解还要复杂度怂成一团）的样子？？

然后判牌型，显然只要考虑单牌，和3 + x，4+2

然后暴力搜网友的3和4
暴力搜jry的3和4

然后枚举3搭配了几个2,
然后jry从大到小开始去除大小为2的对子，网友从小到大，是个简单的贪心

之后看看可以去掉的单牌的个数，也是jry从大到小，网友从小到大

之后的就是单牌互相压看看合不合法就好了

代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar(‘\n‘)
#define space putchar(‘ ‘)
#define eps 1e-8
#define mo 974711
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < ‘0‘ || c > ‘9‘) {
    if(c == ‘-‘) f = -1;
    c = getchar();
    }
    while(c >= ‘0‘ && c <= ‘9‘) {
    res = res * 10 + c - ‘0‘;
    c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar(‘-‘);}
    if(x >= 10) {
    out(x / 10);
    }
    putchar(‘0‘ + x % 10);
}
char s[20];
int rem[16],A[16],W[16],K[16],ans,jry[16];
int C[16],D[16],H[16],J[16],P[16];
int code(char c) {
    if(c >= ‘4‘ && c <= ‘9‘) return c - ‘4‘ + 1;
    if(c == ‘T‘) return 7;
    if(c == ‘J‘) return 8;
    if(c == ‘Q‘) return 9;
    if(c == ‘K‘) return 10;
    if(c == ‘A‘) return 11;
    if(c == ‘2‘) return 12;
    if(c == ‘w‘) return 13;
    if(c == ‘W‘) return 14;
}
bool check(int f,int t) {
    for(int i = 0 ; i <= t ; ++i) {
    memcpy(H,W,sizeof(H));
    memcpy(J,K,sizeof(K));
    if(2 * i + t - i + f * 2  + f * 4 + t * 3 > 17) break;
    int cnt = 0;
    for(int j = 1 ; j <= 14 ; ++j) {
        if(H[j] >= 2 && cnt < i) {H[j] -= 2;++cnt;}
        if(H[j] >= 2 && cnt < i) {H[j] -= 2;++cnt;}
        if(cnt == i) break;
    }
    if(cnt < i) break;
    cnt = 0;
    for(int j = 14 ; j >= 1 ; --j) {
        if(J[j] >= 2 && cnt < i) {J[j] -= 2;++cnt;}
        if(J[j] >= 2 && cnt < i) {J[j] -= 2;++cnt;}
        if(cnt == i) break;
    }
    if(cnt < i) break;
    memset(P,0,sizeof(P));
    cnt = 2 * f + t - i;
    for(int j = 14 ; j >= 1 ; --j) {
        int t = min(cnt,J[j]);
        J[j] -= t;cnt -= t;
        if(cnt == 0) break;
    }
    if(cnt) continue;
    cnt = 2 * f + t - i;
    for(int j = 1 ; j <= 14 ; ++j) {
        int t = min(cnt,H[j]);
        H[j] -= t;cnt -= t;
        if(cnt == 0) break;
    }
    if(J[14]) continue;
    for(int j = 1 ; j <= 14 ; ++j) {
        P[j] += H[j];
        P[j + 1] -= J[j];
    }
    cnt = 0;
    for(int j = 1 ; j <= 14 ; ++j) {
        cnt += P[j];
        if(cnt > 0) break;
    }
    if(cnt == 0) return true;
    }
    return false;
}
bool brute_jry(int dep,int four,int three,int f,int t,int q1,int q2) {
    if(four == f && t == three) return check(four,three);
    if(dep >= 12) return false;
    q1 += C[dep];q2 += D[dep];
    if(q1 > 0 || q2 > 0) return false;
    if(K[dep] >= 3) {
    K[dep] -= 3;
    if(brute_jry(dep + 1,four,three,f,t + 1,q1 - 1,q2)) return true;
    K[dep] += 3;
    }
    if(K[dep] >= 4) {
    K[dep] -= 4;
    if(brute_jry(dep + 1,four,three,f + 1,t,q1,q2 - 1)) return true;
    K[dep] += 4;
    }
    return brute_jry(dep + 1,four,three,f,t,q1,q2);
}
bool brute_wangyou(int dep,int four,int three) {
    if(four * 6 + three * 4 > 17) return false;
    if(dep > 12) {
    if(brute_jry(1,four,three,0,0,0,0)) return true;
    return false;
    }
    if(W[dep] >= 3) {
    W[dep] -= 3;++C[dep];
    if(brute_wangyou(dep + 1,four,three + 1)) return true;
    W[dep] += 3;--C[dep];
    }
    if(W[dep] >= 4) {
    W[dep] -= 4;++D[dep];
    if(brute_wangyou(dep + 1,four + 1,three)) return true;
    W[dep] += 4;--D[dep];
    }
    if(brute_wangyou(dep + 1,four,three)) return true;
    return false;
}
void dfs(int dep,int r) {
    if(!r) {
    memset(C,0,sizeof(C));
    memset(D,0,sizeof(D));
    memcpy(W,A,sizeof(A));
    memcpy(K,jry,sizeof(jry));
    if(brute_wangyou(2,0,0)) {++ans;}
    return;
    }
    if(dep > 14) return;
    for(int i = 0 ; i <= rem[dep] ; ++i) {
    if(i > r) break;
    jry[dep] = i;
    dfs(dep + 1,r - i);
    jry[dep] = 0;
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    while(scanf("%s",s + 1) != EOF) {
    memset(A,0,sizeof(A));
    for(int i = 1 ; i <= 12 ; ++i) rem[i] = 4;
    rem[13] = rem[14] = 1;
    ans = 0;
    for(int i = 1 ; i <= 17 ; ++i) {
        A[code(s[i])]++;rem[code(s[i])]--;
    }
    dfs(1,17);
    out(ans);enter;
    }
}

【LOJ】#6434. 「PKUSC2018」主斗地

原文：https://www.cnblogs.com/ivorysi/p/10121524.html