QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#650094#4777. TichuSGColin#AC ✓174ms3908kbC++202.6kb2024-10-18 12:47:542024-10-18 12:47:54

Judging History

你现在查看的是最新测评结果

  • [2024-10-18 12:47:54]
  • 评测
  • 测评结果:AC
  • 用时:174ms
  • 内存:3908kb
  • [2024-10-18 12:47:54]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)

const int N = 13;

int f[1 << N], tr[1 << N];

inline void work() {
    memset(f, 0x3f, sizeof(f));
    char nam[N][2];
    int v[N];
    auto weight = [&](char c) {
        if (isdigit(c)) return c - '0';
        if (c == 'T') return 10;
        if (c == 'J') return 11;
        if (c == 'Q') return 12;
        if (c == 'K') return 13;
        return 14;
    };
    rep(i, 0, 12) {
        char c = getchar();
        while (!isalpha(c) && !isdigit(c)) c = getchar();
        nam[i][0] = c;
        v[i] = weight(c);
        nam[i][1] = getchar();
    }
    f[0] = 0;
    auto check = [&](vector<int> &s) {
        bool same = true;
        for (auto x : s) if (x != s[0]) {same = false; break;}
        if (same) return true;
        int n = s.size();
        if (n < 5) return false;
        bool straight = true;
        rep(i, 1, n - 1) if (s[i] - s[0] != i) {straight = false; break;}
        if (straight) return true;
        if (n != 5) return false;
        if (s[0] == s[1] && s[0] == s[2] && s[3] == s[4]) return true;
        if (s[0] == s[1] && s[2] == s[3] && s[3] == s[4]) return true;
        return false;
    };
    rep(s, 1, (1 << N) - 1) { // init
        vector<int> tmp;
        rep(i, 0, N - 1) if ((s >> i) & 1) tmp.eb(v[i]);
        sort(all(tmp));
        if (check(tmp)) f[s] = 1;
    }
    rep(s, 1, (1 << N) - 1)
        for (int _s = s; _s; _s = (_s - 1) & s) {
            int nw = f[_s] + f[s ^ _s];
            if (nw < f[s]) {f[s] = nw; tr[s] = _s;}
        }
    printf("%d\n", f[(1 << N) - 1]);
    queue<int> stas;
    stas.push((1 << N) - 1);
    while (!stas.empty()) {
        int u = stas.front(); stas.pop();
        if (f[u] == 1) {
            bool first = true;
            rep(i, 0, N - 1) if ((u >> i) & 1) {
                if (!first) putchar(' '); first = false;
                putchar(nam[i][0]); putchar(nam[i][1]);
            }
            puts("");
        } else {
            stas.push(tr[u]);
            stas.push(u ^ tr[u]);
        }
    }
}

int main() {
    per(t, rd(), 1) work();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 6ms
memory: 3816kb

input:

2
2h 3c 4d 5d 6s Th Qc Qs Ad Tc Ts 9c 9d
2h 3h 4h 5h 6d 7s 8h 8d 8c 8s 9c Td Js

output:

4
2h 3c 4d 5d 6s
Qc Qs
Th Tc Ts 9c 9d
Ad
2
2h 3h 4h 5h 6d 7s 8s 9c Td Js
8h 8d 8c

result:

ok correct (2 test cases)

Test #2:

score: 0
Accepted
time: 174ms
memory: 3908kb

input:

63
2h 3c 4d 5d 6s Th Qc Qs Ad Tc Ts 9c 9d
2h 3h 4h 5h 6d 7s 8h 8d 8c 8s 9c Td Js
2h 2d 2c 2s 4s 4d 4c Qh Qs Qc Ts Js Ac
5d 5c 7d 5s 3s 3c Qh 3d Qc Ts 5h Js Qs
2s 3h 4d 5d 6d 7s 8s 9s Tc Jd Qc Kc As
2s 3h 4d 5d 6d 7s 8s 9s Tc Jd Qc Kc 8c
2s 3h 4d 5d 6d 7s 8s 9s Tc Jd Qc 8c 7h
3h 4d 5d 6d 7s 8s 9s Tc ...

output:

4
2h 3c 4d 5d 6s
Qc Qs
Th Tc Ts 9c 9d
Ad
2
2h 3h 4h 5h 6d 7s 8s 9c Td Js
8h 8d 8c
5
2h 2d 4s 4d 4c
2c 2s Qh Qs Qc
Ts
Ac
Js
5
7d
5d 5c 3s 3c 3d
Ts
5s Qh Qc 5h Qs
Js
1
2s 3h 4d 5d 6d 7s 8s 9s Tc Jd Qc Kc As
2
2s 3h 4d 5d 6d 7s 9s Tc Jd Qc Kc 8c
8s
2
9s Tc Jd Qc 8c 7h
2s 3h 4d 5d 6d 7s 8s
2
Tc Jd Qc 8c...

result:

ok correct (63 test cases)