p2661信息传递

2019-11-11 19:53 来源:未知

P2661 音信传送,p2661音讯传递

题目汇报

有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解释

图片 1

娱乐的流程如图所示。当实行完第 3 轮游戏后, 4 号游戏发烧友会听到 2 号游戏的使用者告诉她自

己的寿辰,所以答案为 3。当然,第 3 轮游戏后, 2 号游戏者、 3 号游戏用户都能从友好的音讯

根源获悉本人的生辰,形似切合游戏截止的准绳。

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

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

对于 100%的数据, n ≤ 200000。

 

 

以此题很三人都用裸的DFS跑出了70分可能80分。

下一场自甘堕落的说认为永久突不破80分了(来自研商区卡塔 尔(阿拉伯语:قطر‎

笔者们能够想转手为什么会晚点?

因为实行了汪洋的失效搜索

可是在进展那么些招来的时候答案已经规定了

故此大家得以加二个近乎于卡时的tot变量

当它高于二个数(笔者获取是4384380,这些数不可能比10^8大)时就淡出

输出当前的最优解就可以

裸的DFS不独有轻便理解,并且代码还短

建个链表,然后爆搜就能够

留神看清一下无用环

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=200001;
 7 void read(int & n)
 8 {
 9     char c='+';int x=0;
10     while(c<'0'||c>'9')
11     c=getchar();
12     while(c>='0'&&c<='9')
13     {
14         x=x*10+(c-48);
15         c=getchar();
16     }
17     n=x;
18 }
19 int n;
20 int ans=0x7ffffff;
21 int a[MAXN];
22 int tot=0;
23 int main()
24 {
25     read(n);
26     for(int i=1;i<=n;i++)
27     read(a[i]);
28     for(int i=1;i<=n;i++)
29     {
30         int bg=i;
31         int now=i;
32         int num=0;
33         while(a[now]!=bg)
34         {
35             tot++;
36             num++;
37             now=a[now];
38             if(num>n+1||num>ans)
39             {
40                 num=0x7ffffff;
41                 break;
42             }
43         }
44         if(tot>4384380)
45         break;
46         ans=min(num+1,ans);
47     }
48     printf("%d",ans);
49     return 0;
50 }

 

音信传送,p2661音信传递 标题汇报有n个同学(编号为1到n卡塔 尔(阿拉伯语:قطر‎正在玩一个讯息传递的游戏。在打闹里每人都有一个恒久的音讯传递对象,...

TAG标签:
版权声明:本文由990888藏宝阁发布于关于计算机,转载请注明出处:p2661信息传递