解题报告 生物

3、烦人的生物(biology)

题目描述

最后一题了,当然是要让我们的jz出场了(jz就是zj,zj就是jz,至于为什么……&),处于某种ws的对知识的渴望,jz非常喜欢生物。

现在jz发现自己本身就是个非常纠结的动物,jz发现如果把自身的细胞排成一排,根据细胞某种性质的不同,可将细胞分成两类,如果将这两类细胞分别用0/1表示,就得到了一个能表示自身细胞的0/1串。jz发现了自身的0/1是个奇妙的东西,就决定出个题来恶心你。

他会告诉你自身0/1串的长度m,和给出你的描述0/1串的语句条数n。

每条语句都符合以下格式:

a, ,b, ,even/odd

表示自身 0/1串中第a~b位上数字的和是偶数/奇数

jz想让你说出最早出现的与前面描述矛盾的语句是谁,你能解决这个问题吗?

输入格式

第一行,一个整数m,表示jz自身0/1串的长度

第二行,一个整数n,表示jz给出的语句数目。

第三行~,共n行,为jz给出的语句,保证按上文所述格式给出。

 

输出格式

输出zj最早说出的与前面语句矛盾的语句的位置-1

Eg:如果该语句是第2句,输出1

如果没有矛盾,则输出n

样例输入

10

5

1 2 even

3 4 odd

5 6 even

1 6 even

7 10 odd

样例输出

3

数据范围

40% m<=1000000 

100% m<=maxlongint

100% n<=5000

 

 

Liukeke 的学科试题之六·生物。

 

这个题的标准算法是并查集。

首先,用 f[x] 存 的祖宗, b[x] 存 到祖宗的距离。

然后,用向量,可以将新合并的节点到祖宗的距离合并出来,即 b[x]:=(b[f[x]] + b[x]) mod 2.

每次读入新数据,如果不在一个集合就合并,如果在一个集合就用向量计算出他们中距离的奇偶性,判断。

 

点范围太大,个数太少, HASH 

 

代码 (Liukeke

program liukeke;

const maxn=999987;

type pointer=^rec;

     rec=record

 dot:longint;

 num:longint;

 next:pointer;

 end;

 

var

  hash:array[0..999987] of pointer;

  f:array[0..10001] of longint;

  p:array[0..10001] of longint;

  m,n,x,y,fx,fy,xx,yy,i,tot,temp:longint;

  kong:char;

  s:string;

 

function findhash(x:longint):longint;

var

  temp:longint;

  p:pointer;

  flag:boolean;

begin

  temp:=x mod maxn;

  p:=hash[temp];

  flag:=false;

  while p<>nil do

  begin

    if (p^.dot=x) then

  exit(p^.num);

p:=p^.next;

  end;

  new(p);

  inc(tot);

  p^.dot:=x;

  p^.num:=tot;

  p^.next:=hash[temp];

  hash[temp]:=p;

  exit(p^.num);

end;

 

function find(x:longint):longint;

begin

  if f[x]=x then exit(x);

  find:=find(f[x]);

  p[x]:=(p[x]+p[f[x]]) mod 2;

  f[x]:=find;

  exit(f[x]);

end;

 

begin

  assign(input,'biology.in');reset(input);

  assign(output,'biology.out');rewrite(output);

  readln(m);

  readln(n);

  tot:=0;

  for i:=1 to 2*n do

  begin

    f[i]:=i;

p[i]:=0;

  end;

  for i:=1 to n do

  begin

    read(x,y);

if x>y then

begin

  temp:=x;

  x:=y;

  y:=temp;

end;

x:=x-1;

xx:=findhash(x);

yy:=findhash(y);

fx:=find(xx);

fy:=find(yy);

read(kong);

read(s);

if s='even' then

begin

  if fx=fy then

    if (p[xx]-p[yy]+2) mod 2<>0 then

begin

  writeln(i-1);

  close(input);

  close(output);

  halt;

end;

  if fx<>fy then

  begin

    f[fx]:=fy;

p[fx]:=(p[xx]+p[yy])mod 2;

      end;

end

else

begin

  if fx=fy then

    if (p[xx]-p[yy]+2) mod 2<>1 then

begin

  writeln(i-1);

  close(input);

  close(output);

  halt;

end;

  if fx<>fy then

  begin

    f[fx]:=fy;

p[fx]:=(p[xx]+p[yy]+1) mod 2;

      end;

end;

  end;

  writeln(n);

  close(input);

  close(output);

end.

 

原文地址:https://www.cnblogs.com/SueMiller/p/2224058.html