QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#637242 | #8234. Period of a String | 666ldc | WA | 69ms | 11868kb | C++17 | 4.3kb | 2024-10-13 11:29:05 | 2024-10-13 11:29:06 |
Judging History
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)