QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#670179#8234. Period of a StringCalculateloveRE 0ms0kbC++143.6kb2024-10-23 20:45:522024-10-23 20:45:52

Judging History

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

  • [2024-10-23 20:45:52]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [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

output:


result: