「QQ红包」 @ 2016-01-28 09:10:22
type node=record
x,y,t:longint;
end;
var a:array[0..800100]of node;
i,j,n,m,k,xx,yy,c,lbf:longint;
f,d,p,ans,lb,flag:array[0..400000]of longint;
function gf(u:longint):longint;
begin
if f[u]=u then exit(u);
f[u]:=gf(f[u]);
exit(f[u]);
end;
procedure hb(u,v:longint);
begin
if gf(u)<>gf(v) then begin
dec(c);f[f[u]]:=f[f[v]]; end;
end;
begin
assign(input,'p1197.in');
assign(output,'p1197.out');
reset(input);
rewrite(output);
readln(n,m);
for i:=0 to n do f[i]:=i;
for i:=1 to m do
begin
readln(xx,yy);
a[i*2-1].x:=xx;a[i*2-1].y:=yy;a[i*2-1].t:=lb[xx];lb[xx]:=2*i-1;
a[i*2].x:=yy;a[i*2].y:=xx;a[i*2].t:=lb[yy];lb[yy]:=2*i;
end;
readln(k);
for i:=1 to k do begin readln(p[i]);flag[p[i]]:=1;end;
c:=n-k;
for i:=1 to m do
begin
if (flag[a[i*2-1].x]=0) and(flag[a[i*2-1].y]=0)then hb(a[i*2-1].x,a[i*2-1].y);
end;
ans[k]:=c;
for i:=k downto 1 do
begin
lbf:=lb[p[i]];flag[p[i]]:=0;inc(c);
repeat
if flag[a[lbf].y]=0 then hb(a[lbf].x,a[lbf].y);
lbf:=a[lbf].t;
until lbf=0;
ans[i-1]:=c;
end;
for i:=0 to k do
writeln(ans[i]);
close(output);
end.
by 「QQ红包」 @ 2016-01-28 09:32:26
这样看着不爽，还是这样吧。
[codep]
type node=record
x,y,t:longint;
end;
var a:array[0..800100]of node;
i,j,n,m,k,xx,yy,c,lbf:longint;
f,d,p,ans,lb,flag:array[0..400000]of longint;
function gf(u:longint):longint;
begin
if f[u]=u then exit(u);
f[u]:=gf(f[u]);
exit(f[u]);
end;
procedure hb(u,v:longint);
begin
if gf(u)<>gf(v) then begin
dec(c);f[f[u]]:=f[f[v]]; end;
end;
begin
readln(n,m);
for i:=0 to n do f[i]:=i;
for i:=1 to m do
begin
readln(xx,yy);
a[i*2-1].x:=xx;a[i*2-1].y:=yy;a[i*2-1].t:=lb[xx];lb[xx]:=2*i-1;
a[i*2].x:=yy;a[i*2].y:=xx;a[i*2].t:=lb[yy];lb[yy]:=2*i;
end;
readln(k);
for i:=1 to k do begin readln(p[i]);flag[p[i]]:=1;end;
c:=n-k;
for i:=1 to m do
begin
if (flag[a[i*2-1].x]=0) and(flag[a[i*2-1].y]=0)then hb(a[i*2-1].x,a[i*2-1].y);
end;
ans[k]:=c;
for i:=k downto 1 do
begin
lbf:=lb[p[i]];flag[p[i]]:=0;inc(c);
repeat
if flag[a[lbf].y]=0 then hb(a[lbf].x,a[lbf].y);
lbf:=a[lbf].t;
until lbf=0;
ans[i-1]:=c;
end;
for i:=0 to k do
writeln(ans[i]);
end.
[/codep]by 1124828077ccj @ 2016-01-28 09:50:33
。。。
by 胡重阳 @ 2016-01-28 10:44:14
。。。
by 「QQ红包」 @ 2016-01-28 12:57:39
为何你几天之内ac这么多题，感觉有点不正常 @[url=/space/show?uid=14738]2016陈常杰[/url]
by 1124828077ccj @ 2016-01-28 14:34:15
@[url=/space/show?uid=2674]redbag[/url] 我之前有学过，最近才开洛谷
by 「QQ红包」 @ 2016-02-01 12:17:33
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
struct haha
{
int l,r,c;
}t[200000];
void bt(int p,int a,int b)//建树
{
t[p].l=a;
t[p].r=b;
int mid=(a+b)/2;
if (a==b) return;
bt(2*p,a,mid);
bt(2*p+1,mid+1,b);
}
void weihu(int p,int a,int b)//染色
{
if (t[p].c==1) return;
if ((a<=t[p].l)&&(t[p].r>=b))
{
t[p].c=1;
return;
}
int mid=(t[p].l+t[p].r)/2;
if (a<mid) weihu(2*p,a,mid);
if (b>mid) weihu(2*p+1,mid+1,b);
if ((t[2*p].c==1)&&(t[2*p+1].c==1))
{
t[p].c=1;
}
}
int count(int p,int a,int b)//求和
{
if (t[p].c==1) return b-a;
if (t[p].c==0) return 0;
int mid=(t[p].l+t[p].r)/2;
int sum=0;
if (a<mid) sum=(2*p,a,mid);
if (b>mid) sum+=(2*p+1,mid+1,b);
return sum;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
for (int i=1;i<=m;i++)
{
int he,ha;
scanf("%d %d",&he,&ha);
weihu(1,he,ha);
printf("%d\n",count(1,1,n));
}
return 0;
}by 「QQ红包」 @ 2016-02-01 15:23:43
[codec]
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
struct haha
{
int l,r,c;
}t[200000];
void bt(int p,int a,int b)//建树 没问题
{
t[p].l=a;
t[p].r=b;
//if (a=b) return;
int mid=(a+b)/2;
if (b>a)
{
bt(2*p,a,mid);
bt(2*p+1,mid+1,b);
}
}
void weihu(int p,int a,int b)//染色 这个似乎也没问题
{
if (t[p].c==1) //全覆盖
{
return;
}
t[p].c=-1;//不完全覆盖
if ((a<=t[p].l)&&(t[p].r<=b)) //全包括在内
{
t[p].c=1;
return;
}
int mid=(t[p].l+t[p].r)/2;
if (a<=mid) //左边有
{
weihu(2*p,a,b);
}
if (b>mid)//右边有
{
weihu(2*p+1,a,b);
}
/*if (b<=mid)
{
weihu(2*p,a,b);
} else
if (a>mid)
{
weihu(2*p+1,a,b);
} else
{
weihu(2*p,a,mid);
weihu(2*p,mid+1,b);
}*/
if ((t[2*p].c==1)&&(t[2*p+1].c==1))//下面的全覆盖
{
t[p].c=1;
}
}
int co(int p,int a,int b)//求和
{
if (t[p].c==1) return b-a+1;
if (t[p].c==0) return 0;
int mid=(t[p].l+t[p].r)/2;
int sum=0;
if (a<=mid) sum=co(2*p,a,mid);
if (b>mid) sum+=co(2*p+1,mid+1,b);
return sum;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
bt(1,1,n);
for (int i=1;i<=m;i++)
{
int he,ha;
scanf("%d %d",&he,&ha);
weihu(1,he,ha);
printf("%d\n",n-co(1,1,n));
}
return 0;
}
[/codec]by 「QQ红包」 @ 2016-02-01 16:41:53
[codec]
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define LL unsigned long long
using namespace std;
struct haha
{
int l,r,c;
}t[500000];
void bt(int p,int a,int b)//建树 没问题
{
t[p].l=a;
t[p].r=b;
//if (a=b) return;
int mid=(a+b)/2;
if (b>a)
{
bt(2*p,a,mid);
bt(2*p+1,mid+1,b);
}
}
void weihu(int p,int a,int b)//染色 这个似乎也没问题
{
if (t[p].c==1) //全覆盖
{
return;
}
t[p].c=-1;//不完全覆盖
if ((a<=t[p].l)&&(t[p].r<=b)) //全包括在内
{
t[p].c=1;
return;
}
int mid=(t[p].l+t[p].r)/2;
if (a<=mid) //左边有
{
weihu(2*p,a,b);
}
if (b>mid)//右边有
{
weihu(2*p+1,a,b);
}
/*if (b<=mid)
{
weihu(2*p,a,b);
} else
if (a>mid)
{
weihu(2*p+1,a,b);
} else
{
weihu(2*p,a,mid);
weihu(2*p,mid+1,b);
}*/
if ((t[2*p].c==1)&&(t[2*p+1].c==1))//下面的全覆盖
{
t[p].c=1;
}
}
int co(int p,int a,int b)//求和
{
if (t[p].c==1) return b-a+1;
if (t[p].c==0) return 0;
int mid=(t[p].l+t[p].r)/2;
int sum=0;
if (a<=mid) sum=co(2*p,a,mid);
if (b>mid) sum+=co(2*p+1,mid+1,b);
return sum;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
bt(1,1,n);
for (int i=1;i<=m;i++)
{
int he,ha;
scanf("%d %d",&he,&ha);
weihu(1,he,ha);
printf("%d\n",n-co(1,1,n));
}
return 0;
}
[/codec]by 6QWQ6 @ 2017-03-16 13:02:52
干脆发题解去吧。。。。。。
by 蒟蒻lxy @ 2018-08-15 16:26:30
为什么我存代码一个小时就被删了，而这个帖子这么久还安然无恙？？？