QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#637242#8234. Period of a String666ldcWA 69ms11868kbC++174.3kb2024-10-13 11:29:052024-10-13 11:29:06

Judging History

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

  • [2024-10-13 11:29:06]
  • 评测
  • 测评结果:WA
  • 用时:69ms
  • 内存:11868kb
  • [2024-10-13 11:29:05]
  • 提交

answer

#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define int long long
#define endl '\n'
using i128 = __int128;
using i64 = long long;
using f128 = long double;
using u64 = unsigned long long;
using pii = pair<int, int>;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const i64 inf = 2e18;
//-------------------------------------------
void solve()
{
    int n;
    cin >> n;
    vector<string> s(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
    }
    /*
    1.字符串长度依次递增的字符串前缀肯定是相同的,且s[i + 1] 余出来的部分对s[i]的前缀组成也有限制
    (会继承长度小于s[i]的前缀限制)
    2.如果前一个字符串的长度大于后一个,那么只需要前一个字符串的前缀等于后一个字符串
    (会全部继承)
    3.确定前缀的字符组成,字符顺序无所谓,只要数量对就行
    */

    vector<map<int, array<int, 26>>> f(n + 1);
    vector<array<int, 26>> cnt(n + 1), pre(n + 1);
    vector<int> psz(n + 1);
    for (int i = n; i >= 1; i--)
    {
        for (auto c : s[i])
        {
            cnt[i][c - 'a']++;
        }
        if (i < n)
        {
            if (s[i].size() <= s[i + 1].size()) // 当字符串长度单调递增的时候
            {
                int k = s[i + 1].size() / s[i].size();
                for (int j = 0; j < 26; j++)
                {
                    if (!((cnt[i][j] == 0) ^ (cnt[i + 1][j] != 0)) || (cnt[i][j] > 0 && cnt[i + 1][j] / cnt[i][j] < k))
                    {
                        cout << "NO" << endl;
                        return;
                    }
                    int w = cnt[i + 1][j] - cnt[i][j] * k;
                    pre[i][j] = w;
                    psz[i] += w;
                }
            }
            else
            {
                for (int j = 0; j < 26; j++)
                {
                    if (cnt[i + 1][j] > cnt[i][j])
                    {
                        cout << "NO" << endl;
                        return;
                    }
                    int w = cnt[i + 1][j];
                    pre[i][j] = w;
                    psz[i] += w;
                }
            }
            for (auto [len, c] : f[i + 1])
            {
                if (len <= s[i].size())
                    f[i][len] = c;
                else
                    break;
            }

            if (f[i].count(psz[i]))
            {
                if (f[i][psz[i]] != pre[i])
                {
                    cout << "NO" << endl;
                    return;
                }
            }
            else
                f[i][psz[i]] = pre[i];
        }

        if (f[i].count(s[i].size()))
        {
            if (f[i][s[i].size()] != cnt[i])
            {
                cout << "NO" << endl;
                return;
            }
        }
        else
            f[i][s[i].size()] = cnt[i];

        array<int, 26> al = {-1};
        for (auto [len, c] : f[i])
        {
            if (al[0] != -1)
            {
                for (int i = 0; i < 26; i++)
                {
                    if (al[i] > c[i])
                    {
                        cout << "NO" << endl;
                        return;
                    }
                }
            }

            al = c;
        }
    }

    vector<string> ans(n + 1);
    cout << "YES" << endl;
    array<int, 26> al = {0};
    for (auto [len, c] : f[1])
    {
        for (int i = 0; i < 26; i++)
        {
            ans[1] += string(c[i] - al[i], (char)(i + 'a'));
        }
        al = c;
    }
    for (int id = 2; id <= n; id++)
    {
        int k = s[id].size() / s[id - 1].size();
        while (k--)
            ans[id] += ans[id - 1];
        ans[id] += ans[id - 1].substr(0, s[id].size() % s[id - 1].size());
    }
    for (int id = 1; id <= n; id++)
    {
        cout << ans[id] << endl;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    cin >> T;
    for (int i = 1; i <= T; i++)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
2
abc
abcd
4
bbcaa
cabb
acabbbb
a
3
ab
aab
bbaaaaab
3
ab
aab
bbaaaaaa

output:

NO
YES
abbca
abbc
abbcabb
a
YES
ab
aba
abaabaab
NO

result:

ok ok (4 test cases)

Test #2:

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

input:

5
1
ccecddbdbbcbbaded
3
cd
d
d
1
dcedec
2
dcec
cce
8
a
e
a
c
cc
cccccccc
c
b

output:

YES
abbbbbccccdddddee
YES
dc
d
d
YES
ccddee
YES
cced
cce
NO

result:

ok ok (5 test cases)

Test #3:

score: -100
Wrong Answer
time: 69ms
memory: 11868kb

input:

100
147
ababbbaaaaaababbbbbaabaabbbbaaaababbbbababaabbbbaaabbabaaaaaabbbbaabbaaaaaababbbaabbabbaaabbbaabbbabaabbbbaabaabbaa
aaaaabbbbababababbbaaaaaabaaaaabbaabaabaaababbabbabbabbaabbaaabbaabbaabaababaaabbababbbbbaabaaaaabbbbaabbbbbbaaabbbbabaababbbbb
ababbabaababbbbaabbbbaaabbabaabbaaaababbbabbaaab...

output:

NO
YES
baaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb
ba
bababababababababababababababababababababab
bababababababababababababababab
babababab
bababababbababababb
bababababbabab
baba
bababababababab
b
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
b
bbbbbbbbbbbbbb
bbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbb...

result:

wrong answer Number of letters do not same (test case 4)