编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

---|---|---|---|---|---|---|---|---|---|---|

终于AC了，居然忘了最后再用FLOYED处理下，真囧.............

晕。。提交10次终于弄出了第二组数据

第二组数据是

2 2 0

l1 p l2

l1 p l2

这个竟然算是There must be something wrong...

可以用 1(平行) 和 -1(垂直) 来记录;

这样在传递关系的时候可以用 相乘；

大大降低编程复杂度。

原来是L1,L2,不是11,12

我日

C,48行

flody....................60+代码长度..........

注意：平行 and垂直=垂直

垂直 and垂直=平行

并查集然后用一个数组表示垂直，但比赛时得了80分

为什么这么多人贴程序不删，就删我的 555555.。。。。。。

可用Floyd算法...

正好练练并查集~~~~

这个题的数据不是一般的水，P、V输出反了都得80分。。。

program vijos_1697;

type

TNode=record

fa:longint;

data:boolean

end;

const

maxN=200;

var

n,m,q:longint;

d:array[1..maxN] of TNode;

procedure init;

var

i:longint;

begin

readln(n,m,q);

for i:=1 to n do d[i].fa:=i;

end;

procedure _read(var n:longint);

var

c:char;

begin

repeat read(c); until c='l';;

read(n);

end;

procedure _read(var b:boolean);

var

c:char;

begin

repeat read(c); until c in ['p','v'];

b:=c='v';

end;

function root(i:longint):longint;

begin

if d[i].fa=i then exit(i);

root:=root(d[i].fa);

d[i].data:=d[i].data xor d[d[i].fa].data;

d[i].fa:=root;

end;

function getData(x,y:longint):boolean;

begin

root(x);

root(y);

exit(d[x].data xor d[y].data);

end;

procedure union(x,y:longint;newD:boolean);

var

i,j:longint;

begin

i:=root(x);

j:=root(y);

d[i].fa:=j;

d[i].data:=d[x].data or newD xor d[y].data;

end;

procedure print(flag:longint);

begin

case flag of

0:begin

writeln('There must be something wrong...');

halt;

end;

1:writeln('No idea.');

2:writeln('Vertical.');

3:writeln('Parallel.');

end;

end;

procedure main;

var

i,j,x,y,ans:longint;

d:boolean;

begin

for i:=1 to m do begin

_read(x); _read(d); _read(y);

readln;

if root(x)root(y) then union(x,y,d)

else

if getData(x,y)d then print(0);

end;

ans:=0;

for i:=1 to n do

for j:=i+1 to n do

if (root(i)=root(j)) and (getData(i,j)=false) then inc(ans);

writeln(ans);

for i:=1 to q do begin

_read(x); _read(y); readln;

if root(x)root(y) then print(1)

else print(2+ord(not getData(x,y)));

end;

end;

begin

init;

main;

end.

囧囧的。交了3次才AC

f=true表示Li和Lj平行

g=true表示Li和Lj垂直

f:=f or (f and f[k,j]) or (g and g[k,j])

g:=g or (f and g[k,j]) or (g and f[k,j])

如果f=true and g=true则为wrong

对于直线i,j，如果垂直则连接两点，权1，若平行则权0.（无向边）

则两条直线之间，如果所有路径的路径权和mod2都相等，那么两条直线之间的关系就是mod2后值对应的关系。如果存在不等，则错误信息。

类似floyd的，令f[i][j][k]表示i~j只经过1~k的顶点时，i~j路径mod2，转移类似floyd即可。

这题比较囧的地方在于l1 l2可以多次出现，但是一个可以是v一个可以是p。

我怎么觉得这题是二分图啊

Accepted 有效得分：100 有效耗时：0ms

诧异了……第一感觉这道题是并查集，但是并查集不大会用……然后这几天在练图论，突然想起了可不可以用图……所以想了个个人感觉比较奇怪的方法……

f=0表示i和j平行,f=1表示i和j垂直,每次输入后利用floyd的类似思想进行2次两重循环(因为第1重k已经确定，即是读入的i和j)，进行更新判断处理……(第一次这里的更新居然想简单了,直接写了上交，没检查=wa……)

接着的主程序就很简单了~

这样居然过了~~~构图时间复杂度就已经O(mn^2)，幸好数据不强~~~

考试时 因为 机器卡 最后没交上去。。。这回交上去就AC了

发个核心代码

f表示平行 g表示垂直 然后Floyd 若f&g=1则error

f[i][j] |= f[i][k]&&f[k][j];

f[i][j] |= g[i][k]&&g[k][j];

g[i][j] |= f[i][k]&&g[k][j];

g[i][j] |= g[i][k]&&f[k][j];

谁能帮我看看错在哪里

案例对。。

type zz=record

xans:longint;

yans:longint;

end;

var st:string;

n,m,q,m3,m4:longint;

map:array[1..200,1..200]of char;

fmap:array[1..200]of zz;

ans1,ans2:char;

i1,i2,ans3,ans4:longint;

procedure mappd;

var l1,l2,l3:longint;

begin

for l1:=1 to 200 do

for l2:=1 to 200 do

for l3:=1 to 200 do

begin

if (map[l1,l2]='p')and(map[l2,l3]='p')then

begin

map[l1,l3]:='p';

map[l3,l1]:='p';

end;

if (map[l1,l2]='v')and(map[l2,l3]='v')then

begin

map[l1,l3]:='p';

map[l3,l1]:='p';

end;

if ((map[l1,l2]='v')and(map[l2,l3]='p')) or ((map[l1,l2]='p')and(map[l2,l3]='v'))then

begin

map[l1,l3]:='v';

map[l3,l1]:='v'

end;

end;

end;

procedure www(cq1,cq2:longint);

begin

if (map[cq1,cq2]='v')or (map[cq2,cq1]='v')then

writeln('Vertical.')

else

if (map[cq1,cq2]='p')or (map[cq2,cq1]='p')then

writeln('Parallel.')

else

writeln('No idea.');

end;

begin

readln(n,m,q);

fillchar(map,sizeof(map),'o');

for i1:=1 to m do

begin

readln(st);

ans3:=0;

ans4:=0;

while st[1]=' 'do delete(st,1,1);

while st[length(st)]=' 'do delete(st,length(st),1);

for m3:=1 to pos(' ',st)-1 do

ans3:=ord(st[m3])-ord('0')+ans3*10;

while st[m3+1]=' 'do

delete(st,m3+1,1);

ans2:=st[m3+1];

while st[m3+2]=' 'do

delete(st,m3+2,1);

for m4:=m3+2 to length(st) do

ans4:=ord(st[m4])-ord('0')+ans4*10;

map[ans3,ans4]:=ans2;

map[ans4,ans3]:=ans2;

end;

mappd;

if q0 then begin

for i2:=1 to q do

readln(fmap[i2].xans,fmap[i2].yans);

for i2:=1 to q do

www(fmap[i2].xans,fmap[i2].yans);

end

else

writeln('There must be something wrong...');

end.

惨剧

用C的同学注意了，字符数组的长度要在5以上

虽然字符l+三位数长度为4，但是结束符'\0'也是要占空间的

如果不给它空间的话strlen就不知道是多少了

我把字符数组大小由4改为5就A了……吐血中

由此得到的教训是只要允许就不要吝惜空间，能开多大开多大，= =

一通乱搞...

编译通过...

├ 测试数据 01：答案正确...ms

├ 测试数据 02：答案正确...ms

├ 测试数据 03：答案正确...ms

├ 测试数据 04：答案正确...ms

├ 测试数据 05：答案正确...255ms

Accepted 有效得分：100 有效耗时：0ms

Floyd-Washall....

这绝对是并查集啊，可能数据范围小了点，别的也能过

昨日写完并查集，竟然没保存，巨汗，直接不考了