NOIP 2015 信息传递

时间：2024-10-13 14:20:01浏览次数：9

标签：同学游戏 NOIP Ti 信息传递编号 2015

描述

有 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

样例输出 1

提示

数据范围与提示

对于 30%的数据， n≤200；
对于 60%的数据， n≤2500；
对于100的数据，

标签：同学,游戏,NOIP,Ti,信息,传递,编号,2015
From： https://blog.csdn.net/YYX_YYJ/article/details/142898072

NOIP 2015 推销员
描述阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有N家住户，第i家住户到入口的距离为Si米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依......
神奇的幻方 NOIP 2015 题解
描述幻方是一种很神奇的 N×N 矩阵：它由数字 1,2,3,⋯⋯,N×N 构成，且每行、每列及两条对角线上的数字之和都相同。当 N 为奇数时，我们可以通过下方法构建一个幻方：首先将 1 写在第一行的中间。之后，按如下方式从小到大依次填写每个数 K(K=2,3,⋯,N×N) ：若 (K−1)......
『模拟赛』多校A层冲刺NOIP2024模拟赛06
Rank比较还行A.小Z的手套（gloves）签。最大值最小，一眼二分答案。双指针check一下就完了，复杂度$\mathcal{O(n\logn)}$。点击查看代码#include<bits/stdc++.h>#definefo(x,y,z)for(registerint(x)=(y);(x)<=(z);(x)++)#definefu(x,y,z)for(regis......
多校A层冲刺NOIP2024模拟赛06
A.小Z的手套（gloves）明现的二分，我们先排序，假定$a$数组个数少，我们就对每一个$a_i$找一个$b_i$使其差不超过二分的值，然后贪心来讲，肯定找相差最大的那组但差不超过二分值的那个数最优，且先找比他小的那组（因为排过序了），然后套个$multiset$就过了，虽然$n{log_n}^2$......
[赛记] 多校A层冲刺NOIP2024模拟赛06
小Z的手套（gloves）100pts最大值最小，考虑二分答案；首先排序，然后每次找出数量较少的那个数组中的每个数$x$在另一个数组中有没有值在范围$[x-mid,x+mid]$的（其中$mid$为二分的答案），其实只需找$x-mid$就行，最后判断一下所有数是否合法即可；因为已经升序排序，所以......
多校A层冲刺NOIP2024模拟赛06
多校A层冲刺NOIP2024模拟赛06$T1$A.小Z的手套（gloves）$100pts/100pts$容易发现将选出的左右手套各升序排序后，同一个位置上的两只手套的尺码差距一定在答案的候选集合里，画个数轴分讨一下就证完了。部分分$20\%$：因为$n=m$所以不用管谁选谁不选的问题，故\(......
多校 A 层冲刺 NOIP2024 模拟赛 06
多校A层冲刺NOIP2024模拟赛06T小Z的手套（gloves）签到题答案显然具有单调性，排序后二分答案即可。T小Z的字符串（string）签到题注意到$n$较小，可以使用$O(n^3)$的算法，直接上大$DP$。设计状态$f_{i,j,k,0/1/2}$表示从左往右填到$i$位，已经填了$j$个\(0......
[赛记] 多校A层冲刺NOIP2024模拟赛05
这场数数好数（number）100pts找三个数的和，而且允许$\Theta(n^2)$，那么我们可以维护出两个数的和，然后每次顺序遍历找这个数减去前面的某个数在任意两个数的和中有没有出现过，这个也是$\Theta(n^2)$的；所以时间复杂度：$\Theta(n^2)$，如果带$\log$会过不去，要用桶维护；点击......
多校A层冲刺NOIP2024模拟赛04
02表示法直接递归即可，稍微写个高精。点击查看代码#include<bits/stdc++.h>usingnamespacestd;//#defineint__int128constintN=1e4;strings;intb[N],c[N],len;inta[N],tot;intread(){ intf=1,s=0;charch=getchar(); while(ch<'0'||ch>'9......
NOIP 模拟赛：2024-10-12
T1：break忘了写，于是-20pts离散化，若一个段被$\ge3$个线段覆盖，无解；否则答案为$2^{cnt}$，$cnt$为连通块个数。T2：推式子题，注意轮数$\le\logn$即可。T3：T4：一种新的树的生成方式。这个数据范围，一眼状压。考虑一颗以$u$为根的树$T$怎么生成：枚举$u$的......