#423 Div2 C

题意

给出 n 个字符串以及他们在 S 串中出现的位置，求字典序最小的 S 串。保证给出的字符串不会冲突。

分析

模拟就好。用并查集思想优化，数组 nxt[i] 表示从 i 开始接下来还未填字母的第一个位置。初始化 nxt[i] = i 。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 5;

const int N = 2e6 + 10;

char str[N], s[N];

int nxt[N];

int fd(int x) {

    return x == nxt[x] ? x : (nxt[x] = fd(nxt[x]));

}

int main() {

    for(int i = 0; i < N; i++) {

        nxt[i] = i;

    }

    int n;

    scanf("%d", &n);

    for(int i = 0; i < n; i++) {

        scanf("%s", s);

        int len = strlen(s);

        int c;

        scanf("%d", &c);

        for(int j = 0; j < c; j++) {

            int x;

            scanf("%d", &x);

            x--;

            int l = len;

            int pos = 0;

            int nxt_x = fd(x);

            while(nxt_x - x < l) {

                pos = nxt_x - x;

                str[nxt_x] = s[pos];

                nxt[nxt_x] = fd(nxt_x + 1);

                nxt_x = nxt[nxt_x];

            }

        }

    }

    int ii = -1;

    for(int i = N - 1; i >= 0; i--) {

        if(str[i] >= 'a' && str[i] <= 'z') {

            if(ii == -1) ii = i + 1;

        } else {

            str[i] = 'a';

        }

    }

    if(ii == -1) ii = 0;

    str[ii] = 0;

    printf("%s\n", str);

    return 0;

}

巴特西

#423 Div2 C

#423 Div2 C

题意

分析

code

最新文章

热门文章