QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#688222#7705. Make Your Own Morse Code PalindromedbaumgAC ✓0ms3848kbC++202.6kb2024-10-30 00:57:352024-10-30 00:57:35

Judging History

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

  • [2024-10-30 00:57:35]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3848kb
  • [2024-10-30 00:57:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

map<char, string> m;

pair<ll, string> solve(string s) {
    ll n = s.size();
    ll dp[n + 1] = {};
    char prev[n + 1] = {};
    fill_n(dp, n + 1, 1e9);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        for (auto p : m) {
            string cur = p.second;
            reverse(cur.begin(), cur.end());
            if (i + cur.size() - 1 >= n)
                continue;
            bool valid = true;
            for (int j = 0; j < cur.size(); j++)
                valid &= s[i + j] == cur[j];
            if (valid && dp[i + cur.size()] > dp[i] + 1) {
                dp[i + cur.size()] = dp[i] + 1;
                prev[i + cur.size()] = p.first;
            }
        }
    }
    string ans = "";
    ll cur = n;
    while (cur > 0) {
        ans += prev[cur];
        cur -= m[prev[cur]].size();
    }
    return {dp[n], ans};
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    m['A'] = ".-";
    m['B'] = "-...";
    m['C'] = "-.-.";
    m['D'] = "-..";
    m['E'] = ".";
    m['F'] = "..-.";
    m['G'] = "--.";
    m['H'] = "....";
    m['I'] = "..";
    m['J'] = ".---";
    m['K'] = "-.-";
    m['L'] = ".-..";
    m['M'] = "--";
    m['N'] = "-.";
    m['O'] = "---";
    m['P'] = ".--.";
    m['Q'] = "--.-";
    m['R'] = ".-.";
    m['S'] = "...";
    m['T'] = "-";
    m['U'] = "..-";
    m['V'] = "...-";
    m['W'] = ".--";
    m['X'] = "-..-";
    m['Y'] = "-.--";
    m['Z'] = "--..";
    m['0'] = "-----";
    m['1'] = ".----";
    m['2'] = "..---";
    m['3'] = "...--";
    m['4'] = "....-";
    m['5'] = ".....";
    m['6'] = "-....";
    m['7'] = "--...";
    m['8'] = "---..";
    m['9'] = "----.";
    string s;
    getline(cin, s);
    string t = "";
    for (char c : s)
        t += m[c];
    ll k = 0;
    for (int i = 1; i <= t.size(); i++) {
        string s1 = "";
        for (int j = 0; j < i; j++)
            s1 += t[ll(t.size()) - j - 1];
        string s2 = s1;
        reverse(s2.begin(), s2.end());
        if (s1 == s2)
            k = i;
    }
    for (int i = 0; i < k; i++)
        t.pop_back();
    auto ans = solve(t);
    if (k == 0) {
        t.push_back('-');
        auto p1 = solve(t);
        t.pop_back();
        t.push_back('.');
        auto p2 = solve(t);
        ll mn = min(p1.first, p2.first);
        pair<ll, string> ans;
        if (mn == p1.first) ans = p1;
        if (mn == p2.first) ans = p2;
    }
    cout << ans.first << " " << ans.second;
}

詳細信息

Test #1:

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

input:

FOOT

output:

1 L

result:

ok correct

Test #2:

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

input:

FOOTS

output:

3 0QI

result:

ok correct

Test #3:

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

input:

FOOTS

output:

3 0QI

result:

ok correct

Test #4:

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

input:

FOOTSTOOL

output:

0 

result:

ok correct

Test #5:

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

input:

OOTNX

output:

2 J0

result:

ok correct

Test #6:

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

input:

3 FRENCH HENS

output:

6 5RCLXB

result:

ok correct

Test #7:

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

input:

TWAS THE NIGHT BEFORE XMAS

output:

13 YXFOL46PF4VPT

result:

ok correct

Test #8:

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

input:

1A2B3C4D5E6F7G8H9I10J

output:

18 0695OPUC5646R848YG

result:

ok correct

Test #9:

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

input:

A PARTRIDGE IN A PEAR TREE

output:

8 QF3FFCXC

result:

ok correct

Test #10:

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

input:

TEN LORDS ALEAPING

output:

9 BQ4L4R8XA

result:

ok correct

Test #11:

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

input:

XABCDQRST1234567890123456789

output:

7 6CZCBQU

result:

ok correct

Test #12:

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

input:

ASDFGHJKLQWERTYUIOPMNBVCXZ987

output:

23 ZO12FY5ROP8XYLQPRY73LFF

result:

ok correct

Test #13:

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

input:

THE QUICK BROWN FOX JUMPS OVER

output:

17 24YXQ2C2JLUCCLY5T

result:

ok correct

Test #14:

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

input:

1234567891 IS A PRIME NUMBER 0

output:

18 L37YVUC59123456789

result:

ok correct

Test #15:

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

input:

INTRANSIGENCE

output:

0 

result:

ok correct

Test #16:

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

input:

ANTICKING ANTICKING WRECKING A

output:

5 CRCXP

result:

ok correct

Test #17:

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

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

output:

1 E

result:

ok correct

Test #18:

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

input:

ISO9001 "IEEEEEEEEEEEEEEEEEEEE

output:

6 90018S

result:

ok correct