2105. [NOIP2015] 信息传递
2024-09-08 10:57:02
★☆ 输入文件:2015message.in
输出文件:2015message.out
简单对比
时间限制:1 s
内存限制:256 MB
【题目描述】
有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 个整数,表示游戏一共可以进行多少轮。
【样例输入】
5
2 4 2 3 1
【样例输出】
3
【提示】
游戏的流程如图所示。当进行完第 3 轮游戏后, 4 号玩家会听到 2 号玩家告诉他自
己的生日,所以答案为 3。当然,第 3 轮游戏后, 2 号玩家、 3 号玩家都能从自己的消息
来源得知自己的生日,同样符合游戏结束的条件。
对于 30%的数据, n ≤ 200;
对于 60%的数据, n ≤ 2500;
对于 100%的数据, n ≤ 200000。
【来源】
在此键入。
Pascal
C
C++
一开始用vector居然还能搞四十分
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<stack>
#include<vector>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int MAXN=;
int n;
struct node
{
vector<int>v;
int num,to,but;
}a[MAXN];
int main()
{
freopen("2015message.in","r",stdin);
freopen("2015message.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i].to),a[i].num=,a[i].v.push_back(i); int ans=;
while()
{
ans++;
for(int i=;i<=n;i++)
{
for(int j=;j<=a[i].num-a[i].but;j++)// i 把知道的所有人的信息跟to说
{
//a[a[i].to].num++;
vector<int>::iterator s=find(a[i].v.begin(),a[i].v.end(),a[i].v[j]);
if(s!=a[i].v.end())
{
a[a[i].to].v.push_back(a[i].v[j]);
a[a[i].to].num++;
a[a[i].to].but++;
} }
//print(i);
for(int j=;j<=a[a[i].to].num;j++)
if(a[a[i].to].v[j]==a[i].to)
printf("%d",ans),exit();
}
for(int i=;i<=n;i++)
a[i].but=;
}
return ;
}
正确做法dfs求最小值
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<stack>
#include<vector>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=;
int n,a[MAXN];
int vis[MAXN];
int ans=0x7ffffff;
stack<int>s;
int dfs(int x)
{
s.push(x);
int num=;
while(!s.empty())
{
int te=s.top();
if(!vis[te])
{
s.push(a[te]);
vis[te]=-;
}
else if(vis[te]==-)
{
s.pop();
vis[te]=;
num++;
while(vis[s.top()]!=)
{
vis[s.top()]=;
s.pop();
num++;
}
s.pop();
while(!s.empty())
{
vis[s.top()]=;
s.pop();
}
}
else if(vis[te]==)
{
while(!s.empty())
{
vis[s.top()]=;
s.pop();
}
}
}
return num;
}
int main()
{
freopen("2015message.in","r",stdin);
freopen("2015message.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]); for(int i=;i<=n;i++)
{
if(!vis[i])
{
int p=dfs(i);
if(p!=)
ans=min(ans,p);
}
}
printf("%d",ans);
return ;
}
最新文章
- 运行错误:error while loading shared libraries: xxx.so.0:cannot open shared object file: No such file or
- ios下fixed回复框bug的解决方案
- torch 入门
- C primer plus 练习题 第七章
- Nodejs解决2分钟限制
- Android 使用Telephony API
- PHP的cURL库:抓取网页,POST数据及其他,HTTP认证 抓取数据
- [iOS基础控件 - 6.10.4] 项目启动原理 项目中的文件
- iOS 获取当前时间以及计算年龄(时间差)
- PHP面向对象概述
- python unicode 字节串转成中文问题
- [ZJOI2016]小星星
- 基于WebGL架构的3D可视化平台—设备管理
- entity framework 上下文对象跟踪相关
- NoSQL简单介绍
- sql 视图 字段条件统计
- linux c++ curl 根据IP地址获得当前网络的所在的地理位置
- Java容器解析系列(3) List AbstractList ListIterator RandomAccess fail-fast机制 详解
- 使用maven-tomcat7-plugins时调试出现source not found解决
- jquery预加载的几种方式
热门文章
- 谈谈hibernate的缓存
- select语句中会影响查询效率的因素
- how to get geometry type of layer using IMapServer3 and IMapLayerInfo? (C#)
- VB.NET+三层 机房收费系统之组合查询
- powershell 的版本号所引起的载入 FSharp 编译器问题
- HDMI信号解析
- Python中flatten用法
- iOS开发——优化篇—— 25个性能优化/内存优化常用方法
- Copy Selected Text from any window
- CPU卡详解【转】