题意(说真的看样例都比题面好懂):
给定一个长度为 $n$ 的字符串 $s$，以及一个类似于并查集的 $fa$ 数组的一个长度为 $m$ 序列 $a$ ，这可以近似的将 $a$ 数组理解为:若 $a_i=a_j$ ，则 $s_i$ 与 $s_j$ 属于一个集合(我自己的理解),
现在，将为同一个集合中的 $s_i,s_j,…..,s_p,s_k$ 变为 $s_k,s_i,s_j,……,s_p$，这相当于将整个集合位移一下。
求最后的字符串。
新奇而奇怪的思路
看到这道题我第一时间想到的居然是图论（不知道正解是不是），很显然，如果是同一个集合中的字符，则相当于这些字符连通，且是一个边数正好为集合大小的环。
由于需要位移，所以可以建图，再用 dfs 跑一遍,跑的过程中将答案记录到 $ans$ 中，最后输出即可。
难点是建图，显然我们需要建一个向前的环，倒着枚举，设 $q[a[i]]$ 为在 $a[i]$ 这个集合中的前一个的下标，有点抽象，可以理解为：当前为 $a[i]$ ，则 $q[a[i]]$ 表示在 $i$ 后面的第一个与 $a[i]$ 相等的数下标，这样建的边便是 add(i,q[a[i]]) ，但是保险起见我建的双向边。
由于集合的最后一个要向集合的第一个建边，所以再处理一下，最后 dfs 跑一遍记录答案。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| #include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
template<typename P>
inline void read(P &x){
P res=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
res=res*10+ch-'0';
ch=getchar();
}
x=res*f;
}
int T=1;
int n,m;
char s[200020];
int a[200020];
const int Max=200020;
struct edge{
int to,nxt;
}e[Max<<1];
int head[Max],cnt=0;
void add(int u,int v){
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
return;
}
map<int,int> q;
bool vis[200010];
char ans[200010];
void dfs(int u,int k,int fa){
vis[u]=1;
if(k==1){
for(int i=head[u];i;i=e[i].nxt){
int to=e[i].to;
if(to!=fa) dfs(to,k+1,u);
}
return;
}
ans[u]=s[fa];
for(int i=head[u];i;i=e[i].nxt){
int to=e[i].to;
if(to!=fa) dfs(to,k+1,u);
}
return;
}
map<int,int> fir;
signed main(){
read(n),read(m);
for(int i=1;i<=n;++i) cin>>s[i];
for(int i=1;i<=n;++i){
read(a[i]);
}
for(int i=n;i>=1;--i){
if(!q[a[i]]) q[a[i]]=i;
else{
add(i,q[a[i]]);
add(q[a[i]],i);
q[a[i]]=i;
}
if(!fir[a[i]]) fir[a[i]]=i;
}
for(int i=1;i<=n;++i){
if(!vis[i]){
char w=s[i];
dfs(i,1,0);
ans[i]=s[fir[a[i]]];
}
}
for(int i=1;i<=n;++i){
cout<<ans[i];
}
cout<<endl;
return 0;
}
|
