QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#726803#8063. Seven UpBroderAC ✓488ms1957116kbC++232.0kb2024-11-09 08:53:282024-11-09 08:53:28

Judging History

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

  • [2024-11-09 08:53:28]
  • 评测
  • 测评结果:AC
  • 用时:488ms
  • 内存:1957116kb
  • [2024-11-09 08:53:28]
  • 提交

answer

#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>

using namespace std;

#define rep(i, n) for (int i = 0; i < n; i++)
#define sz(x) (long long)(x).size()

string deck;

double dp[78125][25][128];

int fivep[7];

int encode(char c) {
    if (c=='A') return 0;
    if (c=='2') return 1;
    if (c=='3') return 2;
    if (c=='4') return 3;
    if (c=='5') return 4;
    if (c=='6') return 5;
    if (c=='7') return 6;
    return 7;
}

double func(int key, int left, int available) {
    // cout << key << ' ' << left << ' ' << available << endl;
    if (available == 0) return 0;
    if (left < 0) return 0;
    if (dp[key][left][available] == -1) {
        double p = 1;
        double out = 0;
        vector<double> cnt;
        int temp = key;
        double sum = left;
        rep(i, 7) {
            sum+=temp%5;
            cnt.push_back(temp%5);
            temp/=5;
        }
        rep(i, 7) {
            if (cnt[i]==0) continue;
            double pi = cnt[i]/sum;
            int nxtKey = available;
            int curr = i;
            while (curr!=7 and nxtKey & (1<<curr)) {
                nxtKey^=(1<<curr);
                curr = encode(deck[curr]);
            }
            out+=pi*func(key-fivep[i], left, nxtKey);
            p-=pi;
        }
        if (left!=0) out += p * func(key, left-1, available);
        dp[key][left][available] = out+1;
    }
    
    return dp[key][left][available];
}

int main() {
    rep (i, 78125) rep (j, 25) rep (k, 128) {
        dp[i][j][k] = -1;
    }
    cin >> deck;
    fivep[0] = 1;
    rep(i, 6) {
        fivep[i+1]=fivep[i]*5;
    }
    vector<int> cnt(7, 4);
    int extra = 24;
    rep(i, sz(deck)) {
        if (encode(deck[i])!=7) {
            cnt[encode(deck[i])]--;
        }
        else extra--;
    }
    int key = 0;
    rep(i, 7){
        key*=5;
        key+=cnt[6-i];
    }
    cout << fixed << setprecision(10) << func(key, extra, (1<<7)-1) << endl;
}

详细

Test #1:

score: 100
Accepted
time: 219ms
memory: 1957068kb

input:

A9Q22T5

output:

19.8812971342

result:

ok found '19.8812971', expected '19.8812971', error '0.0000000'

Test #2:

score: 0
Accepted
time: 488ms
memory: 1956980kb

input:

JQQQKKK

output:

20.9131450564

result:

ok found '20.9131451', expected '20.9131451', error '0.0000000'

Test #3:

score: 0
Accepted
time: 227ms
memory: 1956924kb

input:

A234567

output:

25.1723868237

result:

ok found '25.1723868', expected '25.1723868', error '0.0000000'

Test #4:

score: 0
Accepted
time: 71ms
memory: 1956988kb

input:

234567A

output:

2.0909090909

result:

ok found '2.0909091', expected '2.0909091', error '0.0000000'

Test #5:

score: 0
Accepted
time: 87ms
memory: 1956988kb

input:

2356A74

output:

6.0475524476

result:

ok found '6.0475524', expected '6.0475524', error '0.0000000'

Test #6:

score: 0
Accepted
time: 131ms
memory: 1956832kb

input:

2A43657

output:

15.7540446396

result:

ok found '15.7540446', expected '15.7540446', error '0.0000000'

Test #7:

score: 0
Accepted
time: 140ms
memory: 1956952kb

input:

AAAA222

output:

18.9345686993

result:

ok found '18.9345687', expected '18.9345687', error '0.0000000'

Test #8:

score: 0
Accepted
time: 115ms
memory: 1957068kb

input:

274AA25

output:

13.2888888889

result:

ok found '13.2888889', expected '13.2888889', error '0.0000000'

Test #9:

score: 0
Accepted
time: 154ms
memory: 1956988kb

input:

7K7A598

output:

19.8812971342

result:

ok found '19.8812971', expected '19.8812971', error '0.0000000'

Test #10:

score: 0
Accepted
time: 131ms
memory: 1956952kb

input:

7K586T4

output:

15.8051282051

result:

ok found '15.8051282', expected '15.8051282', error '0.0000000'

Test #11:

score: 0
Accepted
time: 203ms
memory: 1957116kb

input:

9353K2T

output:

17.5812971342

result:

ok found '17.5812971', expected '17.5812971', error '0.0000000'

Test #12:

score: 0
Accepted
time: 274ms
memory: 1956960kb

input:

K59QKT3

output:

18.9345686993

result:

ok found '18.9345687', expected '18.9345687', error '0.0000000'

Test #13:

score: 0
Accepted
time: 224ms
memory: 1956984kb

input:

52Q2J68

output:

19.8812971342

result:

ok found '19.8812971', expected '19.8812971', error '0.0000000'