NOIP 2015 信息传递

NOIP 2015 信息传递kawayi

题目描述

有n个同学(编号为1到n)正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为i的同学的信息传递对象是编号为Ti同学。

游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息,但是每人只会把信息告诉一个人,即自己的信息传递对象)。当有人从别人口中得知自己的生日时,游戏结束。请问该游戏一共可以进行几轮?

输入输出格式

输入格式:

输入共2行。

第1行包含1个正整数n表示n个人。

第2行包含n个用空格隔开的正整数T1,T2,……,Tn其中第i个整数Ti示编号为i

的同学的信息传递对象是编号为Ti的同学,Ti≤n且Ti≠i

数据保证游戏一定会结束。

输出格式:

输出共 1 行,包含 1 个整数,表示游戏一共可以进行多少轮。

输入输出样例

输入样例#1:
5
2 4 2 3 1
输出样例#1:
3

说明

样例1解释

NOIP 2015 信息传递

游戏的流程如图所示。当进行完第 3 轮游戏后, 4 号玩家会听到 2 号玩家告诉他自

己的生日,所以答案为 3。当然,第 3 轮游戏后, 2 号玩家、 3 号玩家都能从自己的消息

来源得知自己的生日,同样符合游戏结束的条件。

对于 30%的数据, n ≤ 200;

对于 60%的数据, n ≤ 2500;

对于 100%的数据, n ≤ 200000。 数据范围暴露算法系列

首先,我表示这个题有很多种解法 cgk大神说是裸的tarjan(本蒟蒻不会(@-@));裸的并查集......(%-%)

我写的是难度较为low的算法————————————循环,循环,循环;

首先,本题有无数性质,key点在于每个节点都有且只有一个出度;

那么.....一大堆性质正在逼近(放豌豆)

1:在同一个链里不会出现两个环

2:在每一条不相连的链中都必有一个环

3:无论从某条链的哪个节点开始搜索,都能搜到该条链的环。

然后,可以引入时间戳......

program ex02;

var next,time:

      array[..] of longint;

      n,i,p:longint; ans:longint;

procedure find(x:longint);

var now,pre:longint;

begin

  now:=next[x];  //枚举点

  pre:=;

  while time[now]= do

  begin

     inc(p);           //时间戳

     time[now]:=p; pre:=now;

     now:=next[now];

  end;

  if time[now]>=time[x] then   //如果环

  begin

    if ans>(time[pre]-time[now])+ then

    ans:=(time[pre]-time[now])+;

  end;

end;

begin

  ans:=maxlongint;

  readln(n);

  for i:= to n do

  read(next[i]);

  for i:= to n do

  if time[i]= then  //如果不重复

  begin

     inc(p);

     time[i]:=p;

     find(i);

  end;

  writeln(ans);

end.
上一篇:Michael Kors - Wikipedia, the free encyclopedia


下一篇:java笔记5之逻辑运算符以及&&与&的区别