题意:
长度为n的序列a,c,如果 c = 0 且 i>1 ,则 a = a;如果 c = 1 且 i
第1行,一个整数n,表示序列长度;
第2行,n个整数,c ;
输出:
一个整数,答案;
算法标签:**并查集
解法:
并查集的两个模板:
一个查:
int find(int x)
{
if(f[x]!=x)
f[x]=find(f[x]);
return f[x];
}
一个并:
void merge(int l,int r)
{
int t1=find(l),t2=find(r);
f[t2]=t1;
}
注意:这个题目有个坑,就是c** = 0,且 i=1时,此时需要特判,答案需要+1;
AC代码:
#include
using namespace std;
const int N = 5e5+5;
int a[N],f[N];
int find(int x)
{
if(f[x]!=x)
f[x]=find(f[x]);
return f[x];
}
void merge(int l,int r)
{
int lc=find(l),rc=find(r);
f[rc]=lc;
}
int main ()
{
int n,c;
cin>>n;
for (int i=1;i<=n;i++)
f[i]=i;
int g=0;
for (int i=1;i<=n;i++)
{
cin>>c;
if(c==0)
{
merge(i-1,i);
if(i==1)g=1;
}
else merge(i,i+1);
}
int ans=0;
for (int i=1;i<=n;i++)
if(f[i]==i)ans++;
cout<
}