题目描述
Ivan had string $s$ consisting of small English letters. However, his friend Julia decided to make fun of him and hid the string $s$. Ivan preferred making a new string to finding the old one.
Ivan knows some information about the string $s$. Namely, he remembers, that string $t_i$ occurs in string $s$ at least $k_i$ times or more, he also remembers exactly $k_i$ positions where the string $t_i$ occurs in string $s$: these positions are $x_{i, 1}, x_{i, 2}, \ldots, x_{i, k_i}$. He remembers $n$ such strings $t_i$.
You are to reconstruct lexicographically minimal string $s$ such that it fits all the information Ivan remembers. Strings $t_i$ and string $s$ consist of small English letters only.
题意概述
有一个未知的字符串$s$,只知道$n$个它的子串$t_i$以及它们在$s$中出现的次数$k_i$和位置$x_{i, j}$。要求构造出字典序最小的原串。
数据范围:$1 \le n \le 10^5, \; 1 \le \sum |t_i|, \sum k_i, x_{i, j} \le 10^6$。
算法分析
建立双向链表,记录某个位置上一个未填充的位置和下一个未填充的位置。为了防止填充到一个已填充的位置上,我们将子串以位置为第一关键字从大到小排序,以长度为第二关键字从大到小排序,在填充时修改一下链表。最后若有未填充的位置则直接输出a。
代码
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; string s[100001]; struct cons { int n, p; bool operator < (const cons &a) const { return p > a.p ? true : p == a.p ? s[n].length() > s[a.n].length() : false; } } con[1000001]; int n, c, p, l, len, ma, top, pre[2000001], nxt[2000001]; char str[2000001]; int main() { scanf("%d", &n); for (int i = 1; i <= 2000000; ++i) pre[i] = i - 1, nxt[i] = i + 1; for (int i = 1; i <= n; ++i) { cin >> s[i]; scanf("%d", &c); for (int j = 1; j <= c; ++j) { scanf("%d", &p), con[++top].n = i, con[top].p = p; } } sort(con + 1, con + top + 1); for (int i = 1; i <= top; ++i) { if (con[i].p == con[i - 1].p) continue; l = len = s[con[i].n].length(), p = con[i].p; while (l > 0) { ma = max(ma, p), str[p] = s[con[i].n][len - l]; nxt[pre[p]] = nxt[p]; pre[nxt[p]] = pre[p]; l -= nxt[p] - p, p = nxt[p]; } } for (int i = 1; i <= ma; ++i) { if (str[i] >= 'a' && str[i] <= 'z') printf("%c", str[i]); else printf("a"); } printf("\n"); return 0; }