首页 > 代码库 > Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) C. String Reconstruction
Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) C. String Reconstruction
题意:给出各个字符串出现的起始位置,问整个的字符串是什么,(字典序最小)
思路:开始写的是用set+优先队列存取每个位置出现的最长字符串,然后遍历,爆内存。。。爆。。。内。。。存。。。我们可以用并查集,已经确认的位置他们并在一起,指向后面第一个没有被确认的(看代码理解吧)
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=2e6+10; 4 5 int n,fa[N]; 6 char s[N],b[N]; 7 8 int Find(int x) { return fa[x]==x ? x : fa[x]=Find(fa[x]); } 9 int main(){ 10 int k; 11 scanf("%d",&n); 12 for(int i=1;i<=2000000;i++) { 13 fa[i]=i;b[i]=‘a‘; 14 } 15 int Max=0,x; 16 for(int i=1;i<=n;i++){ 17 scanf("%s%d",s+1,&k); 18 int len=strlen(s+1); 19 for(int j=1;j<=k;j++){ 20 scanf("%d", &x); 21 Max=max(Max, x+len-1); 22 int y=x; 23 while(y <= x+len-1) 24 { 25 b[y]=s[y-x+1]; 26 fa[y]=y+1;y=Find(y); 27 } 28 } 29 } 30 31 for(int i=1;i<=Max;i++) putchar(b[i]); 32 printf("\n"); 33 }
Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) C. String Reconstruction
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。