String Reconstruction (并查集)
2024-08-29 16:55:35
并查集维护和我这个位置的字母连续的已经被填充的字母能到达的最右边的第一个还没有填充的位置,然后把这个位置填上应该填的东西,然后把这个位置和下一个位置连接起来,如果下一个位置还没有填,我就会把下一个位置填上,如果填过了,就会跳到后面的还没有填的地方
#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lowbit(x) (x & (-x))
#define INOPEM freopen("in.txt", "r", stdin)
#define OUTOPEN freopen("out.txt", "w", stdout) typedef unsigned long long int ull;
typedef long long int ll;
const double pi = 4.0*atan(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = 2e6+;
const int maxm = ;
const int mod = 1e9+;
using namespace std; int n, m;
int T, tol;
char tmp[maxn];
char s[maxn];
int fa[maxn]; int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
} void bind(int u, int v) {
int x = find(u);
int y = find(v);
if(x == y) return ;
if(x < y) fa[x] = y;
else fa[y] = x;
return ;
} int main() {
memset(s, , sizeof s);
for(int i=; i<maxn; i++) fa[i] = i;
scanf("%d", &m);
n = ;
int q;
while(m--) {
scanf("%s", tmp);
int len = strlen(tmp);
scanf("%d", &q);
while(q--) {
int pos;
scanf("%d", &pos);
n = max(n, pos+len-);
for(int i=find(pos); i<pos+len; i=find(i+)) {
s[i] = tmp[i-pos];
bind(i, i+);
}
}
}
for(int i=; i<=n; i++) printf("%c", s[i] ? s[i] : 'a');
printf("\n");
return ;
}
最新文章
- 在centos7中安装Robot Framework
- C# 字符编码解码 Encoder 和Decoder
- App 即时通讯 SDK
- J2EE中关于tomcat的maxIdle、maxActive、maxActive相关配置
- cf.301.D. Bad Luck Island(dp + probabilities)
- [http session]
- Android显示基础--单位与尺寸
- 1、JavaScript入门篇
- $geoNear
- git推送本地分支到远端 以及删除远端分支的 命令
- Git分支学习总结
- UIAlertController(警告栏) 自学之初体验
- Eclipse用法和技巧二十:一个快速打印技巧
- 【算法】赫夫曼树(Huffman)的构建和应用(编码、译码)
- 天梯赛-L1-018. 大笨钟
- 【Linux】配置SSH Key到GitHub/GitLab
- 转:Flutter动画二
- SpringBoot笔记十五:任务
- 通过adb启动app应用
- Maths | Metropolis-Hastings algorithm