CF-828C
C. String Reconstructiontime limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
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 ti occurs in string s at least ki times or more, he also remembers exactly ki positions where the string ti occurs in string s: these positions are xi, 1, xi, 2, ..., xi, ki. He remembers n such strings ti.
You are to reconstruct lexicographically minimal string s such that it fits all the information Ivan remembers. Strings ti and string s consist of small English letters only.
InputThe first line contains single integer n (1 ≤ n ≤ 105) — the number of strings Ivan remembers.
The next n lines contain information about the strings. The i-th of these lines contains non-empty string ti, then positive integer ki, which equal to the number of times the string ti occurs in string s, and then ki distinct positive integers xi, 1, xi, 2, ..., xi, ki in increasing order — positions, in which occurrences of the string ti in the string s start. It is guaranteed that the sum of lengths of strings ti doesn't exceed 106, 1 ≤ xi, j ≤ 106, 1 ≤ ki ≤ 106, and the sum of all ki doesn't exceed 106. The strings ti can coincide.
It is guaranteed that the input data is not self-contradictory, and thus at least one answer always exists.
OutputPrint lexicographically minimal string that fits all the information Ivan remembers.
Examplesinput3
a 4 1 3 5 7
ab 2 1 5
ca 1 4outputabacabainput1
a 1 3outputaaainput3
ab 1 1
aba 1 3
ab 2 3 5outputababab
直接暴力一定会超时,对每次输入的ki个数做去重处理就好。
AC代码:
#include<bits/stdc++.h>
using namespace std; const int maxn=2e7+; int n,t,x;
char a[maxn],s[maxn]; int main(){
cin>>n;
int MAX=-maxn;
while(n--){
cin>>s;
int len=strlen(s);
cin>>t;
int cnt=-maxn;
for(int i=;i<t;i++){
cin>>x;
x--;
MAX=max(x+len,MAX);
for(int i=max(cnt,x);i<x+len;i++){
a[i]=s[i-x];
}
cnt=x+len;
}
}
//cout<<a<<endl;
for(int i=;i<MAX;i++){
if(a[i]=='\0')
cout<<'a';
else
cout<<a[i];
}
return ;
}
最新文章
- ST05 跟踪SQL
- W-数据库基础
- zookeeper理论
- npm 介绍
- React可控组件与不可控组件
- 修改ubuntu按下关机键触发的事件
- asp.net 输出 页面内容 在服务器上
- TDD(测试驱动开发)学习一:初识TDD
- 微信公众平台自定义菜单创建代码实现—java版
- Java 集合 LinkedList的ListIterator
- redis-如何在工程中使用redis
- .net core 2.0学习笔记(四):迁移.net framework 工程到.net core
- CSS3美化网页元素
- USACO Training Section 1.1 题解(共4题)
- Java【第四篇】基本语法之--循环
- 加盟阿里!贾扬清被曝从Facebook离职,任阿里硅谷研究院VP
- aspectj 注解
- 汽车车牌JS正则表达式验证(含新能源车牌)
- 服务器重复发送SYN ACK 和 TCP_DEFER_ACCEPT设置
- 详解django三种文件下载方式