QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#670179 | #8234. Period of a String | Calculatelove | RE | 0ms | 0kb | C++14 | 3.6kb | 2024-10-23 20:45:52 | 2024-10-23 20:45:52 |
answer
#include <bits/stdc++.h>
const int N = 100100;
const int SZ = 5000100;
int n;
char str[SZ];
struct limit {
int len, num[26];
limit() {
len = 0;
memset(num, 0, sizeof(num));
}
bool operator < (const limit &rhs) const {
return len < rhs.len;
}
bool operator <= (const limit &rhs) const {
for (int i = 0; i < 26; i ++)
if (num[i] > rhs.num[i]) return 0;
return 1;
}
limit operator * (const int &b) const {
limit c = *this;
c.len *= b;
for (int i = 0; i < 26; i ++) c.num[i] *= b;
return c;
}
limit operator - (const limit &rhs) const {
limit c = *this;
c.len -= rhs.len;
for (int i = 0; i < 26; i ++) c.num[i] -= rhs.num[i];
return c;
}
bool check() {
for (int i = 0; i < 26; i ++)
if (num[i] < 0) return 0;
return 1;
}
int get() {
for (int i = 0; i < 26; i ++)
if (num[i]) {
num[i] --;
return i;
}
}
} a[N];
int len[N];
int seq_len;
limit seq[N];
namespace ST {
int logx[N];
int f[17][N];
void init() {
logx[0] = -1;
for (int i = 1; i <= n; i ++) logx[i] = logx[i >> 1] + 1;
for (int i = 1; i <= n; i ++) f[0][i] = len[i];
for (int j = 1; j <= 16; j ++)
for (int i = 1; i <= n - (1 << j) + 1; i ++)
f[j][i] = std::min(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
}
int query(int l, int r) {
int k = logx[r - l + 1];
return std::min(f[k][l], f[k][r - (1 << k) + 1]);
}
}
bool solve(int u, limit cur) {
if (u == 1) {
seq[++ seq_len] = cur;
return 1;
}
int l = 1, r = u - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (ST::query(mid, u - 1) <= cur.len) l = mid; else r = mid - 1;
}
cur = cur - a[l] * (cur.len / a[l].len);
return cur.check() ? solve(l, cur) : 0;
}
int last_len, last_ans[SZ];
int cur_len, cur_ans[SZ];
void work() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++) {
scanf("%s", str);
len[i] = strlen(str);
a[i] = limit();
a[i].len = len[i];
for (int j = 0; j < len[i]; j ++) a[i].num[str[j] - 'a'] ++;
}
ST::init();
seq_len = 0;
for (int i = 1; i <= n; i ++)
if (!solve(i, a[i])) {
puts("NO");
return;
}
std::sort(seq + 1, seq + 1 + seq_len);
for (int i = 1; i < seq_len; i ++)
if (!(seq[i] <= seq[i + 1])) {
puts("NO");
return;
}
puts("YES");
for (int i = seq_len; i >= 2; i --)
seq[i] = seq[i] - seq[i - 1];
last_len = 0;
for (int i = 1; i <= seq_len; i ++)
for (int T = seq[i].len; T; T --) last_ans[last_len ++] = seq[i].get();
for (int i = 0; i < last_len; i ++)
printf("%c", last_ans[i] + 'a');
puts("");
for (int i = 2; i <= n; i ++) {
cur_len = len[i];
for (int x = 0; x < cur_len; x ++) cur_ans[x] = last_ans[x % last_len];
for (int x = 0; x < cur_len; x ++)
printf("%c", cur_ans[x] + 'a');
puts("");
last_len = cur_len;
for (int x = 0; x < last_len; x ++) last_ans[x] = cur_ans[x];
}
}
int main() {
freopen("E.in", "r", stdin);
freopen("E.out", "w", stdout);
int T;
scanf("%d", &T);
while (T --)
work();
return 0;
}
詳細信息
Test #1:
score: 0
Dangerous Syscalls
input:
4 2 abc abcd 4 bbcaa cabb acabbbb a 3 ab aab bbaaaaab 3 ab aab bbaaaaaa