传送门 :
$tag :$思维
回文
数据结构
题意 :
给定一个数组$a[]$,你可以进行操作,询问最少操作使得这个数组变回文串
操作定义如下 :
选择一个$a_x,a_y$将数组中的所有$a_y$改变成$a_x$
思路 :
对于回文串的考虑
-
如果$a[l] ==a[r]$显然是不需要操作的,贪心的想的话,不然会使得操作次数变多
-
否则$a[l],a[r]$就需要改变,我们考虑将$a[l]$变成$a[r]$,或者$a[l]$变成$a[r]$,如果变成其他的话,显然操作次数有可能变多
因为题目中有全部变为$a_x$,因此我们考虑使用并查集来维护如下的操作
Code :
int find(int x){
if(x!=p[x])return p[x] = find(p[x]);
return p[x];
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=2e5;i++) p[i] = i ,sz[i] = 1;
for(int i=1,j=n;i<=j;i++,j--){
if(a[i] == a[j])continue;
int fx = find(a[i]);
int fy = find(a[j]);
if(fx!=fy){
p[fx] =fy;
sz[fy]+=sz[fx];
}
}
ll ans = 0 ;
for(int i=1;i<=N;i++){
if(p[i] ==i){
ans += sz[i]-1;
}
}
cout<<ans<<endl;
}