QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#325132#5607. Cribbage On Steroidstom0727AC ✓0ms3752kbC++205.4kb2024-02-11 04:39:242024-02-11 04:39:25

Judging History

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

  • [2024-02-11 04:39:25]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3752kb
  • [2024-02-11 04:39:24]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#if __cplusplus >= 201103L
    struct pairhash {
        static uint64_t splitmix64(uint64_t x) {
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }

        template<class T, class U>
        size_t operator() (const pair<T,U> &p) const {
            static const uint64_t FIXED_RANDOM = (uint64_t)chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(p.first + FIXED_RANDOM) ^ splitmix64(p.second+ FIXED_RANDOM);
        }
    };
    struct custom_hash {
        static uint64_t splitmix64(uint64_t x) {
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }

        size_t operator()(uint64_t x) const {
            static const uint64_t FIXED_RANDOM = (uint64_t)chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(x + FIXED_RANDOM);
        }
    };
    mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
    inline int randint(int l, int r) {
        return uniform_int_distribution<int>(l,r)(rng);
    }
    inline double randdouble(double l, double r) {
        return uniform_real_distribution<double>(l,r)(rng);
    }
    inline long long randll(long long l, long long r) {
        mt19937_64 rng2((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
        return uniform_int_distribution<long long>(l, r)(rng2);
    }
#endif
 
#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) 0
#endif

#define fastio ios::sync_with_stdio(false); cin.tie(0);
#define ll long long
#define ull unsigned long long
#define ll128 __int128_t
#define PI 3.14159265358979323846
#define abs(a) ((a>0)?a:-(a))
#define pii pair<int,int>
#define pll pair<ll,ll>

const long double pi = acos(-1.0);
const long double eps = (double)1e-10;

// const int mod = 1e9+7;
int mod;

template<class T>
T qpow(T a, int b) {
    T res = 1;
    while (b) {
        if (b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}
int norm(int x) {
    if (x < 0) {
        x += mod;
    }
    if (x >= mod) {
        x -= mod;
    }
    return x;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(ll x) : x(norm((int)(x % mod))) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(mod - x));
    }
    Z inv() const {
        assert(x != 0);
        return qpow(*this, mod - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = (int)((ll)(x) * rhs.x % mod);
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        ll v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};

const int maxn = 1001;
const int maxm = 1e6+5;


int n;
char a[maxn];
ll dp[maxn];

int val(char c) {
    if (c == 'A') return 1;
    if (c == 'T') return 10;
    if (c == 'J') return 10;
    if (c == 'Q') return 10;
    if (c == 'K') return 10;
    return c - '0';
}
int trans(char c) {
    if (c == 'A') return 1;
    if (c == 'T') return 10;
    if (c == 'J') return 11;
    if (c == 'Q') return 12;
    if (c == 'K') return 13;
    return c - '0';
}

ll ans = 0;
int cnt[maxn];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    dp[0] = 1;
    // 1. 背包
    for (int i = 1; i <= n; i++) {
        int x = val(a[i]);
        for (int j = 15; j >= 0; j--) {
            if (j+x <= 15) dp[j+x] += dp[j];
        }
    }
    ans += dp[15] * 2;

    // 2, 对子
    for (int i = 1; i <= n; i++) {
        int x = trans(a[i]);
        cnt[x]++;
    }
    for (int i = 1; i <= 13; i++) {
        ans += cnt[i] * (cnt[i]-1);
    }

    // 3, 顺子
    for (int i = 1; i <= 13; i++) {
        if (!cnt[i]) continue;
        ll f = 1;
        int streak = 0;
        for (int j = i; j <= 13; j++) {
            if (!cnt[j]) {
                break;
            }
            f *= cnt[j];
            streak++;
        }
        if (streak < 3) continue;
        // LOG(f); LOG(streak);
        // LOG(f*streak);
        ans += f * streak;
        for (int k = i; k <= i+streak-1; k++) {
            cnt[k] = 0;
        }
    }
    cout << ans << endl;

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3672kb

input:

5
4 5 6 5 5

output:

23

result:

ok single line: '23'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

13
A 2 3 4 5
6 7 8 9 T
J Q K

output:

71

result:

ok single line: '71'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

10
2 2 3 4 5 8 9 T J Q

output:

45

result:

ok single line: '45'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

5
5 5 5 5 J

output:

28

result:

ok single line: '28'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

5
5 5 5 5 5

output:

40

result:

ok single line: '40'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

11
A 2 3 5 6 7 8 T J Q K

output:

41

result:

ok single line: '41'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

20
A 2 3 4 5
A 2 3 4 5
A 2 3 4 5
A 2 3 4 5

output:

20308

result:

ok single line: '20308'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

7
9 6 5 A 4 7 8

output:

16

result:

ok single line: '16'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

11
Q K
2 2 2
3 3 3
A A
4

output:

224

result:

ok single line: '224'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

100
A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A

output:

506676942699987180

result:

ok single line: '506676942699987180'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

100
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5

output:

333300

result:

ok single line: '333300'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

5
K J 2 6 8

output:

0

result:

ok single line: '0'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

7
T J J J Q K K

output:

32

result:

ok single line: '32'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

5
J Q K A 2

output:

3

result:

ok single line: '3'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

14
5 5
A 4
2 3
A 4
2 3
T J Q K

output:

438

result:

ok single line: '438'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

100
A T 4 K K J T 7 4 T Q A 5 K 8 T Q J K 5 3 8 A 9 3 4 7 J 5 7 K J 7 9 3 T 8 9 8 2 8 6 7 J T 6 6 4 5 K 9 6 5 K 5 J T A 4 3 A K 5 T Q T 6 K T 8 Q J K Q 8 A 6 9 5 7 K 3 2 5 Q J 4 T 2 7 2 9 2 T 9 4 5 9 5 5

output:

2440992624714

result:

ok single line: '2440992624714'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

100
K Q 3 K 9 5 5 7 A T K T 8 5 J 3 6 6 5 A 9 9 3 5 2 5 7 4 9 Q 9 4 9 A 2 T Q 2 K 3 4 4 9 8 K 3 K 5 A 2 Q 5 8 6 6 5 K 2 T 3 2 9 2 8 Q 3 A 6 4 K A 3 A 6 4 5 K A 6 4 3 T 3 Q 4 6 8 7 K 2 A J 3 8 5 K 5 A T 4

output:

1127283925810

result:

ok single line: '1127283925810'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

100
Q 6 6 A 8 J T T A 2 7 9 2 9 7 K T T 6 7 T 4 A K 2 T 8 T 5 Q J J 7 8 3 A 7 K A 8 J T J J T J 3 2 2 7 A K A J 6 7 6 Q 4 K 2 2 9 2 4 Q K 5 A T 2 6 5 A J 4 9 A Q 3 T A T 2 T 8 2 6 6 K 7 5 A 9 2 A T A 2 4

output:

1001732618498

result:

ok single line: '1001732618498'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

100
T J 9 2 T 5 3 Q J 6 Q 5 9 Q 4 8 K K 9 3 T Q 9 8 K 3 T A J K K 4 4 4 2 5 A A K A 3 K Q A 6 5 8 A A A 2 T 7 2 7 8 Q J A 8 3 9 2 9 7 7 Q 4 9 5 2 9 J 9 4 2 6 Q 4 2 3 7 5 7 5 7 8 3 9 8 2 Q Q T A A 2 4 6 3

output:

2636894652562

result:

ok single line: '2636894652562'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

100
J 5 Q 3 T J 8 2 T T 7 4 3 K 3 3 4 6 K T T 7 7 A K 8 9 7 7 K 2 K 2 Q K T 7 Q Q 4 9 3 3 4 5 J K T 3 6 4 5 Q 6 7 7 3 9 8 3 3 A T 3 Q 4 9 5 7 A 3 Q 4 6 J A A Q T A J J A 9 K 8 A A 2 6 T 4 T 9 J A 7 6 J 3

output:

1754378063080

result:

ok single line: '1754378063080'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

100
T 7 T 5 6 5 A K 7 8 8 K 6 5 5 8 9 Q 2 7 3 5 9 Q Q 9 Q 2 J 5 J 4 4 4 A 9 Q 5 4 5 6 3 5 3 6 T 5 Q J 8 7 4 A 2 8 2 6 T A 4 4 T 7 A T T 6 9 K 8 5 4 6 K 7 5 9 4 J A K 6 K 3 5 2 4 J 2 Q 6 8 J 9 7 8 6 J 6 2

output:

2519534370948

result:

ok single line: '2519534370948'