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 }
时间: 07-11

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) Problem A - B

Pronlem A In a small restaurant there are a tables for one person and b tables for two persons. It it known that n groups of people come today, each consisting of one or two people. If a group consist of one person, it is seated at a vacant one-seate

Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals)D. High Load

题意:出n个点,其中k个叶子节点,问构造出的树最远的两个点最近是多少 思路:以一个点为中心,然后m个伸出,一层层扩散,(n-1)%m==k,如果k==0,即可以平分,长度就是2*(n-1)/m,如果取模为k==1,说明多出一个,+1,其他的话,就是最后一层补k个,但是最长的还是+2 1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int main(){ 5 int n,m; 6 cin>>n>>m; 7 int

Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) B. Black Square

题意:问是否可以形成一个全黑正方形 思路:可以找出正方形的边,然后判断下这个矩阵是否容得下,n,m都比边短,比赛的时候写麻烦了,还去找了这个正方形究竟在哪个位置,这样的话得考虑很多情况,不如就边*边-黑子的总数 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=2e5+10; 5 char a[102][102]; 6 int main(){ 7 int n,m; 8 s

Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) E DNA Evolution

DNA Evolution 题目让我们联想到树状数组或者线段树,但是如果像普通那样子统计一段的和,空间会爆炸. 所以我们想怎样可以表示一段区间的字符串. 学习一发大佬的解法. 开一个C[10][10][4][n],就可以啦,第二维表示e的长度,第一维表示i%e的长度,第三维表示颜色,第四维求和了. 1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1e5+5; 4 char s[maxn]; 5 map&l

Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) E. DNA Evolution 树状数组

E. DNA Evolution time limit per test 2 seconds memory limit per test 512 megabytes input standard input output standard output Everyone knows that DNA strands consist of nucleotides. There are four types of nucleotides: "A", "T", "

Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals)爆零记

昨晚一个瓜皮说今晚有cf,听说是晚间场,我瞅了一眼,娃,VK Cup,上分的好机会,看着比赛时间就有点心酸了,0:35,当时一直在纠结要不要打的问题,当时想着应该不难吧,要不打一下吧,要不还是看看题先,如果容易就打,难的话就不打了好的吧!于是就这样愉快的决定了.......cf日常延时10分钟,0:45,要不要去睡觉啊,干脆先睡一觉好了,然后又是忍不住诱惑在等待开始! 比赛一开始,瞅了一眼A,这不是一道水题嘛,直接敲啊,然后1分钟就搞定了,交了就过了,B题直接求边界点就好了,扫了一遍就过了,C题

Codeforces Round #423 (Div. 1, rated, based on VK Cup Finals)

A.String Reconstruction B. High Load C. DNA Evolution 题意:给定一个只包含A,T,C,G的字符串S,有如下两种操作 1)修改一个点的字母. 2)给定一个字符串e ($\left | e \right |\leq 10$),生成一个由e重复组成的新串,eee...,问$S_{l..r}$中有几个字母跟这个新的字符串一一对应. SOL:对于每个字母,用BIT[x][y][L]表示$S_{1..L}$中,所有$\equiv x\left (mod

Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals)

D题fst了,生无可恋.第二场rated的CF,打得精神恍惚 A. Unimodal Array 题意:判断数列是否是单峰的. 像题意那样分为三个阶段随便判一判就好了 #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; int n,x[105],part=1; bool f=1; int main() { scanf(&quo

Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals) Problem F (Codeforces 831F) - 数论 - 暴力

Vladimir wants to modernize partitions in his office. To make the office more comfortable he decided to remove a partition and plant several bamboos in a row. He thinks it would be nice if there are n bamboos in a row, and the i-th from the left is a