历届真题 小朋友崇拜圈【第九届】【省赛】【C组】——【C++】【C】【Java】【Python】四种语言解法

简介: 历届真题 小朋友崇拜圈【第九届】【省赛】【C组】——【C++】【C】【Java】【Python】四种语言解法

整个题目:


资源限制


内存限制:256.0MB   C/C++时间限制:1.0s   Java时间限制:3.0s   Python时间限制:5.0s


 班里N个小朋友,每个人都有自己最崇拜的一个小朋友(也可以是自己)。

 在一个游戏中,需要小朋友坐一个圈,

 每个小朋友都有自己最崇拜的小朋友在他的右手边。

 求满足条件的圈最大多少人?


 小朋友编号为1,2,3,...N

 输入第一行,一个整数N(3<N<100000)

 接下来一行N个整数,由空格分开。


 要求输出一个整数,表示满足条件的最大圈的人数。


 例如:


输入格式


 9

 3 4 2 5 3 8 4 6 9


 则程序应该输出:

 4


 解释:

 如图所示,崇拜关系用箭头表示,红色表示不在圈中。


image.png

 显然,最大圈是[2 4 5 3] 构成的圈



 再例如:


输入格式


 30

 22 28 16 6 27 21 30 1 29 10 9 14 24 11 7 2 8 5 26 4 12 3 25 18 20 19 23 17 13 15


 程序应该输出:

 16


 资源约定:

 峰值内存消耗(含虚拟机) < 256M

 CPU消耗 < 1000ms



 请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。


 所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。

 不要使用package语句。不要使用jdk1.7及以上版本的特性。

 主类的名字必须是:Main,否则按无效代码处理。


简单分析:

查长度,那么可以认为是dfs搜索,搜完了比每条线的长度就可以了。所以,难度还是可以的。


C++

#include<iostream>
#include<algorithm>
using namespace std;
int vis[100009];
int ans;
int indug[100009];
int vis1[100009];
void dfs(int n,int qi,int l)
{
  if(vis[n]==qi)
  {
  ans=max(ans,l); 
  return;
  }
  vis1[vis[n]]=1;
  dfs(vis[n],qi,l+1);
}
int main()
{
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
  cin>>vis[i];
  indug[vis[i]]++;
  }
  for(int i=1;i<=n;i++)
  {
  if(vis1[i]==0&&indug[i]!=0)
  {
    vis1[i]=1;
    dfs(i,i,1);
  }
  }
  cout<<ans;
  return 0;
}

C

#include<stdio.h>
#define MAX 100005
int state[MAX];
int arr[MAX];
int ans;
void dfs(int k,int step){
  if(state[arr[k]]!=0){
  if(step-state[arr[k]]+1>ans)ans=step-state[arr[k]]+1;
  return;
  }
  state[k]=step;
  dfs(arr[k],step+1);
}
int main()
{
  int n;
  scanf("%d",&n);
  int i;
  for(i=1;i<=n;i++)scanf("%d",&arr[i]);
  for(i=1;i<=n;i++)dfs(i,1);
  printf("%d",ans);
  return 0;
}

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class Main {
  public static void main(String[] args) throws IOException {
  n = nextInt();
  isWorship = new boolean[n+1];
  a = new int[n+1];
  for(int i = 1;i <= n;i++) {
    int x = nextInt();
    isWorship[x] = true;
    a[i] = x;
  }
  for(int i = 1;i <= n;i++) {
    if(isWorship[i]) {
    start = i;
    dfs(i,0);
    }
  }
  System.out.println(max);
  }
  private static void dfs(int x, int s) {
  if(x > n) return;
  if(x == start && s != 0) {
    max = Math.max(s, max);
    return;
  }
  if(!isWorship[x]) {
    return;
  }
  isWorship[x] = false;
  dfs(a[x],s+1);
  }
  static int nextInt() throws IOException {
  st.nextToken();
  return (int) st.nval;
  }
  static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  static int start,a[],n,max;
  static boolean[] isWorship;
}

Python

from collections import defaultdict
n=int(input())
l=[0]+list(map(int,input().split()))
vis=defaultdict(int)
ans=0
for i in range(1,n+1):
  if not vis[i]:
    now=l[i]
    k=1
    vis[i]=k
    while not vis[now]:
      k+=1
      vis[now]=k
      now=l[now]
    ans=max(ans,k-vis[now]+1)
print(ans)
相关文章
|
2月前
|
算法框架/工具 C++ Python
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角(Euler Angles)之间的相互转换,以及python和C++代码实现
111 0
|
8天前
|
Java Linux Python
Linux环境下 代码java调用python出错
Linux环境下 代码java调用python出错
22 3
|
19天前
|
机器学习/深度学习 人工智能 安全
python和Java的区别以及特性
Python:适合快速开发、易于维护、学习成本低、灵活高效。如果你需要快速上手,写脚本、数据处理、做点机器学习,Python就是你的首选。 Java:适合大型项目、企业级应用,性能要求较高的场景。它类型安全、跨平台能力强,而且有丰富的生态,适合更复杂和规模化的开发。
19 3
|
21天前
|
SQL JavaScript 前端开发
用Java、Python来开发Hive应用
用Java、Python来开发Hive应用
22 6
|
21天前
|
NoSQL JavaScript Java
Java Python访问MongoDB
Java Python访问MongoDB
19 4
WK
|
1月前
|
机器学习/深度学习 Java 程序员
为什么Python比C++慢很多?
Python相较于C++较慢主要体现在:动态类型系统导致运行时需解析类型,增加开销;作为解释型语言,逐行转换字节码的过程延长了执行时间;自动内存管理和垃圾回收机制虽简化操作但也带来了额外负担;全局解释器锁(GIL)限制了多线程性能;尽管Python库方便灵活,但在性能上往往不及C++底层库。然而,Python在某些领域如数据分析、机器学习中,凭借其高级别抽象和简洁语法仍表现出色。选语言需依据具体应用场景和需求综合考量。
WK
39 1
|
2月前
|
Unix C语言 C++
Python调用C/C++
Python调用C/C++
19 2
|
2月前
|
搜索推荐 JavaScript 前端开发
简单实用,Python代码调试利器/java代码的设计和解读
尽管有许多高级调试工具,但在多数情况下,`print()`仍是便捷之选。`icecream`库则将`print()`调试法发挥到极致,简化变量检查与信息输出,提升调试效率。无论是基本变量还是复杂数据结构,`icecream`都能轻松应对,并支持自定义输出格式,让你的调试工作更高效。下面,让我们一起探索`icecream`的更多实用功能吧!
17 0
|
2月前
|
运维 Java API
探索Java中的Lambda表达式自动化运维的魔法:如何利用Python脚本提升效率
【8月更文挑战第29天】Lambda表达式是Java 8中引入的一个新特性,它允许我们将功能作为方法参数,或者代码作为数据来处理。在这篇文章中,我们将深入探讨Java中的Lambda表达式,包括它的语法、使用场景以及如何在实际编程中应用它。我们将通过一些简单的示例来演示Lambda表达式的强大功能和灵活性,让你更好地理解和掌握这一新特性。
|
2月前
|
PHP C++ Python
右手坐标系,空间点绕轴旋转公式&程序(Python和C++程序)
右手坐标系,空间点绕轴旋转公式&程序(Python和C++程序)
26 0
下一篇
无影云桌面