282 条题解
-
0
石力铭 LV 8 @ 2009-06-27 13:53:36
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-program skjl;
begin
randomize;
if random(2)+1=1 then writeln('Yes')
else writeln('No');
end. -
0
flywithwing LV 9 @ 2009-06-11 17:12:07
program p1034;
var n,m,p,i,k,x,y:integer;
f:array[1..6001] of integer;procedure un(n:integer);
begin
for i:=1 to n do
f[i]:=i;
end;function getfather(i:integer):integer;
begin
if f[i]=i then exit(i) else
begin
f[i]:=getfather(f[i]);
exit(f[i]);
end;
end;procedure union(x,y:integer);
begin
if getfather(x)getfather(y) then f[getfather(x)]:=getfather(y);
end;begin
readln(n,m,p);
un(n);
for i:=1 to m do
begin
readln(x,y);
union(x,y);
end;
for k:=1 to p do
begin
readln(x,y);
if getfather(x)=getfather(y) then writeln('Yes') else
writeln('No');
end;
end. -
0
数组做的并查集,O(n)的复杂度
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms#include
int n,m,p;
int a[5001][5001],top[5001];
int b[5001];
int main()
{
int i,j,x,y,tmp;
scanf("%d %d %d",&n,&m,&p);
for(i=1;i -
0
一次AC...被惊到
var
f,d:array [1..5000] of integer;
n,m,p,i,x,y:integer;function find(xx:integer):integer;
var t:integer;
begin
t:=xx;
while f[t]t do t:=f[t];
exit(t);
end;procedure union(xx,yy:integer);
var fx,fy:integer;
begin
fx:=find(xx);fy:=find(yy);
if d[fx]>d[fy] then f[fy]:=fx
else f[fx]:=fy;
if d[fx]=d[fy] then inc(d[fy]);
end;begin
readln(n,m,p);
for i:=1 to n do begin
f[i]:=i;d[i]:=0;
end;
for i:=1 to m do begin
readln(x,y);
union(x,y);
end;
for i:=1 to p do begin
readln(x,y);
if find(x)=find(y) then writeln('Yes')
else writeln('No');
end;
end. -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案错误... ├ 标准行输出
├ 错误行输出
├ 测试数据 05：答案错误... ├ 标准行输出
├ 错误行输出
├ 测试数据 06：答案正确... 994ms
├ 测试数据 07：答案错误...程序输出比正确答案长
├ 测试数据 08：答案错误...程序输出比正确答案短
├ 测试数据 09：答案错误... ├ 标准行输出
├ 错误行输出
├ 测试数据 10：运行超时|格式错误...
为什么会这样??
下面是我的程序:
var k,a,b,i,ii,jj,n1,k1,m1,ans:longint;
a1,b1:array[1..50,1..50] of longint;
c:array[1..50] of boolean;
procedure mfh(i1:longint);
var j:longint;
begin
k:=k+1;
c[i1]:=true;
for j:=1 to n1 do
if (a1[i1,j]=1)and(c[j]=false) then
begin
b1[k1,k]:=j;
mfh(j);
end;end;
begin
readln(n1,k1,m1);
for i:=1 to k1 do
begin
readln(a,b);
a1[a,a]:=1;
a1:=1;
a1[a,b]:=1;
a1:=1;
end;
k1:=1;
for i:=1 to n1 do
begin
k:=1;
if c[i]=false then
begin
b1[k1,k]:=i;
mfh(i);
k1:=k1+1;
end;
end;
for i:=1 to m1 do
begin
readln(a,b);
for ii:=1 to k1 do
begin ans:=0;
for jj:=1 to n1 do
if (b1[ii,jj]=a)or(b1[ii,jj]=b) then ans:=ans+1;
if ans=2 then begin writeln('Yes'); break; end
else if ii=k1 then writeln('No');
end;
end;
end. -
0
给出我的程序，看似没有任何优化
//Vjios P1034 Relations
//Algorithm: Use array Rel to record A's Relations.
#include
using namespace std;
#define MAX 5020
int Rel[MAX];int Fa ( int a ) {
int x = a;
while ( x != Rel[x]) {
x = Rel[x];
}
Rel[a] = x;
return x;
}void Cha ( int a , int b) {
Rel[a] = Rel[Rel[a]] = Fa(b);
}int main() {
int n, m, p;
cin >> n >> m >> p;
int i;
for ( i = 0; i < n; ++i) {
Rel[i] = i; }
int a, b;
for ( i = 0; i < m; ++i) {
cin >> a >> b;
if (Fa(a) != Fa(b)) Cha(a, b);
}
for ( i = 0; i < p; ++i) {
cin >> a >> b;
if (Fa(a) == Fa(b))
cout -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms#include "stdio.h"
int father[5001];
int find(int x)
{
if(father[x]==x) return x;
else father[x]=find(father[x]);
return(find(father[x]));
}
int main()
{
int n,m,p,i,a,b;
scanf("%d%d%d",&n,&m,&p);
for(i=1;i -
0
Flag Accepted
题号 P1034
类型(?) 并查集
通过 3100人
提交 7855次
通过率 39%
难度 2第3100个 庆祝下~
好简单 直接在提交里打的
var f:array[1..5000] of integer;
n,m,p,i,x,y,fx,fy:integer;
function findf(x:integer):integer;
begin
if f[x] = x then exit(x);
f[x]:=findf(f[x]);
exit(f[x]);
end;
begin
readln(n,m,p);
for i:= 1 to n do f[i]:=i;
for i:= 1 to m do
begin
readln(x,y);
fx:=findf(x);
fy:=findf(y);
f[fy]:=fx;
end;
for i:= 1 to p do
begin
readln(x,y);
fx:=findf(x);
fy:=findf(y);
if fx = fy then writeln('Yes')
else writeln('No');
end;
end. -
0
var
n,m,p,i,j,x,y,t:integer;
a:array[1..1000]of integer;
begin
read(n,m,p);
for i:=1 to n do a[i]:=i;
for j:=1 to m do
begin
read(x,y);
t:=a[x];
a[x]:=y;
while a[y]a[x] do
y:=a[y];
a[y]:=t;
end;
for j:=1 to p do
begin
read(x,y);
t:=x;
while (a[x]y)and(a[x]t) do x:=a[x];
if a[x]=y then writeln('Yes') else writeln('No');
end;
end. -
0
jkjkjk50474 LV 7 @ 2009-03-29 08:47:04
最最基本的并查集,连一丁点优化都不用的,嗖~就过了~
program sdfsdf;
var m,n,x,i,j,b,e,q:integer;
p:array[1..5000] of integer;
k:array[1..5000] of 0..1;procedure makeset(a:integer);
begin
p[a]:=a;
//depth[a]:=0;
end;function find(a:integer):integer;
begin
if a=p[a] then find:=a else find:=find(p[a]);
end;procedure union(a,b:integer) ;
var fa,fb:integer;
begin
fa:=find(a); fb:=find(b) ;
p[fa]:=fb;
end;begin
readln(n,m,x);
i:=0;b:=0;e:=0;for i:=1 to n do makeset(i);
for i:=1 to m do
begin
readln(b,e);
union(b,e);
end;for i:=1 to x do
begin
readln(b,e);
if find(b)=find(e) then begin inc(q); k[q]:=1; end else begin inc(q); k[q]:=0; end;
end;
for i:=1 to x do if k[i]=1 then writeln('Yes') else writeln('No');end.
-
0
abc1405abc LV 8 @ 2009-03-11 17:17:05
第3千个人过。。。
太好了 3000万岁 ~(≧▽≦)/~
-
0
whosyour789 LV 8 @ 2009-03-10 16:13:50
const
maxn=6000;var
n,m,p:longint;
i,j,k:longint;
tree:array[1..maxn] of longint;function getfather(x:longint):longint;
beginif tree[x]=x then exit(x);
tree[x]:=getfather(tree[x]);
getfather:=tree[x];end;
procedure work;
beginfor i:=1 to p do
begin
readln(j,k);
if getfather(j)=getfather(k) then writeln('Yes')
else writeln('No');
end;end;
procedure fil;
beginfor i:=1 to n do tree[i]:=i;
end;
procedure init;
beginreadln(n,m,p);
fil;
for i:=1 to m do
begin
readln(j,k);
j:=getfather(j);
k:=getfather(k);
if jk then tree[k]:=j;end;
end;
begin
init;
work;end.
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 41ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：41ms最后一组数据是不是特别大？
(不懂并查集，用了图的遍历,一次AC)program P1034;
const maxn=5000;
type gtype=array[1..maxn,1..maxn] of boolean;
list=array[1..maxn] of longint;
var a:gtype;b:list;
n,m,p,i,j,k:longint;
function check:longint;
var i:longint;
begin i:=1;while (i -
0
program vijos1034;
var
n,m,p,i,fy,fx,x,y,a,b:longint;
fa:array[0..10000] of longint;
function get(v:longint):longint;
begin
if fa[v]=v then get:=v
else
begin
fa[v]:=get(fa[v]);
get:=fa[v];
end;
end;
begin
readln(n,m,p);
for i:=1 to n do fa[i]:=i;
for i:=1 to m do
begin
readln(x,y);
fx:=get(x);fy:=get(y);
fa[fy]:=fx;
end;
for i:=1 to p do
begin
readln(a,b);
fx:=get(a);
fy:=get(b);
if fx=fy then writeln('Yes') else writeln('No');
end;
end. -
0
图的遍历也可以过....无向定义成有向结果爆了2次
program p1034;
var a:array[0..5000,0..5000] of byte;
t,d:array[1..5000] of integer;
z,y,i,j,k,n,m,p,kk:integer;
v:array[1..5000] of boolean;procedure dfs(k:integer);
var i,j:integer;
begin
t[k]:=kk;
v[k]:=true;
for i:=1 to n do
if (v[i]=false) and (a[k,i]0)
then dfs(i);
end;begin
readln(n,m,p);
fillchar (a,sizeof(a),0);
for i:=1 to m do
begin
readln(z,y);
a[z,y]:=1;
a[y,z]:=1;
end;
kk:=1;
for i:=1 to n do
if v[i]=false then
begin
dfs(i);
inc(kk);
end;
for i:=1 to p do
begin
readln(z,y);
if t[z]=t[y] then writeln('Yes')
else writeln('No');
end;
end. -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msprogram P1034;
var father:array [1..5001] of integer;
i,n,m,p,a,b,x:integer;
function find(a:integer):integer;
begin
if father[a]=a then exit(a)
else father[a]:=find(father[a]);
exit(find(father[a]));
end;
begin
readln(n,m,p);
for i:=1 to n do
father[i]:=i;
for i:=1 to m do
begin
readln(a,b);
a:=find(a);
b:=find(b);
if ab then father[a]:=b;
end;
for i:=1 to p do
begin
readln(a,b);
if find(a)=find(b) then writeln('Yes')
else writeln('No');
end;
end.并查集原来如此简单.......（要加路径压缩）
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 9ms
├ 测试数据 10：答案正确... 25ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：34ms
石力铭
LV 8
@ 2009-06-27 13:53:36
