+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-08(82)

2019-09(116)

2019-10(8)

2019-11(6)

B站笔试真题之[编程题]小A最多会新认识的多少人

发布于2019-09-11 13:29     阅读(1012)     评论(0)     点赞(23)     收藏(2)


前言

这道题连着踩了两个坑,一个是不支持numpy,另一个是matlab的矩阵计算较为耗时,发出来供大家避免这种错误。

题目

链接:https://www.nowcoder.com/questionTerminal/1fe6c3136d2a45fa8ef555b459b6dd26
来源:牛客网

小A参加了一个n人的活动,每个人都有一个唯一编号i(i>=0 & i<n),其中m对相互认识,在活动中两个人可以通过互相都认识的一个人介绍认识。现在问活动结束后,小A最多会认识多少人?

输入描述:

第一行聚会的人数:n(n>=3 & n<10000);
第二行小A的编号: ai(ai >= 0 & ai < n);
第三互相认识的数目:
m(m>=1 & m < n(n-1)/2);
第4到m+3行为互相认识的对,以’,'分割的编号。

输出描述:

输出小A最多会新认识的多少人?

示例1
输入

7
5
6
1,0
3,1
4,1
5,3
6,1
6,5

输出

3

分析

显然可以转化为图的连通问题,判断某点与其他点之间的可达性,所以用矩阵的幂求可达性矩阵,然后用可达性矩阵与原矩阵相减就可以得到结果了。

代码

python

提交的时候才发现牛客网的系统不支持numpy,要真是在笔试的时候才发现这得多难受啊。

import numpy as np
n=int(input())
ai=int(input())
m=int(input())
A = np.identity(n)
for i in range(0, m):
	line = input()
	strs = line.split(",")
	x=int(strs[0])
	y=int(strs[1])
	A[x, y]=1
	A[y, x]=1
# A = A + A.T - np.diag(A.diagonal()) # 对称阵,也可以
P = A
item = A
for i in range(2, A.shape[0]+1):
	item = item.dot(A)
	P = P + item  # 这里不可用P += item
res = np.sign(P)[ai, :].sum()-A[ai, :].sum() # 最后总共认识的人数减去原来认识的人数
print(int(res))
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

不过本地还是能运行的
在这里插入图片描述

matlab

修改修改原来的python程序,matlab的就写好了,虽然能够运行但是还是输给了时间。

n=input('');
ai=input('');
m=input('');
A=eye(n);
for i = 1:m
    line=input('','s');
    strs = strsplit(line, ',');
    x = str2num(strs{1});
    y = str2num(strs{2});
    A(x+1,y+1)=1;
    A(y+1,x+1)=1;
end
item=A;
R=A;
for j = 2:length(A)
    item = item*A;
    R=R+item;
end
P=sign(R);
res=sum(P(ai+1,:))-sum(A(ai+1,:));
disp(res);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

仅仅是示例1的计算就用了139ms
在这里插入图片描述
所以提交无法通过所有测试案例
在这里插入图片描述



所属网站分类: 技术文章 > python文章

作者:23dh

链接: http://www.pythonheidong.com/blog/article/107154/

来源:python黑洞网 www.pythonheidong.com

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

23 0

赞一赞 or 踩一踩

收藏该文
已收藏

评论内容:(最多支持255个字符)

相似文章

  为什么不返回`none'而不是tkinter.Entry对象?

  结合python flask和express.js

  带有多个应用程序的Django静态文件

  递归grep使用python

  将16位整数转换为32位浮点

  使用PIL和win32clipboard将图像写入python中的Windows剪贴板吗?

  更改每个视图的数据库并访问每个视图的多个数据库

  有任何适用于Python的pdf417条形码库吗?

  当它永远不会被实例化时,在python中创建一个类有意义吗?

  如何停止将回车符添加到Python的文件输出中?

优质资源排行榜

 python经典电子书大合集下载 下载次数 8117

 零基础java开发工程师视频教程全套,基础+进阶+项目实战(152G) 下载次数 7548

 零基础前端开发工程师视频教程全套,基础+进阶+项目实战(共120G) 下载次数 7442

 零基础大数据全套视频400G 下载次数 7005

 零基础php开发工程师视频教程全套,基础+进阶+项目实战(80G) 下载次数 6893

 零基础软件测试全套系统教程 下载次数 6503

 全套人工智能视频+pdf 下载次数 6440

 IOS全套视频教程 基础班+就业班 下载次数 4680

 编程小白的第一本python入门书(高清版)PDF下载 下载次数 3216

10  effective python编写高质量Python代码的59个有效方法 pdf下载 下载次数 3102

11  Python深度学习 pdf下载 下载次数 3070

12  python项目开发视频 下载次数 3001

13  python从入门到精通视频(全60集)python视频教程下载 下载次数 2999

14  使用python+pygame开发的小游戏《嗷大喵快跑》源码下载 下载次数 2998

15  黑马2017年java就业班全套视频教程 下载次数 2992

16  python实战项目 平铺图像板系统源码下载,适用于想要保存,标记和共享图像,视频和网页的用户 下载次数 2987

17  利用python实现程序内存监控脚本 下载次数 2987

18  树莓派Python编程指南 pdf下载 下载次数 2985

19  老男孩python自动化视频 下载次数 2980

20  老王python基础+进阶+项目视频教程 下载次数 2973

21  尚硅谷Go学科全套视频 下载次数 2972

22  Python基础教程 pdf下载 下载次数 2971

23  某硅谷Python项目+AI课程+核心基础视频教程 下载次数 2968

24  Web前端实战精品课程 下载次数 2967

25  [小甲鱼]零基础入门学习Python 下载次数 2962

26  tron python小游戏 下载次数 2962

27  老男孩python全栈开发15期 下载次数 2958

28  2017最新web前端开发完整视频教程附源码 下载次数 2948

29  笨办法学python pdf下载 下载次数 2937

30  最新全套完整JAVAWEB2018开发视频 下载次数 2926

31  Python算法教程_中文版 pdf下载 下载次数 2925

32  Python Cookbook第三版中文PDF下载高清完整扫描原版 下载次数 2920

33  Spring boot实战视频6套下载 下载次数 2909

34  python全套视频十五期(116G) 下载次数 2904

35  Python项目实战 下载次数 2885

36  python全自动抢火车票教程-python视频教程下载 下载次数 2883

37  30个小时搞定Python网络爬虫 含源码 下载次数 2882

38  尚硅谷大数据之Hadoop视频 下载次数 2876

39  简明python教程 (A Byte of Python)pdf下载 下载次数 2875

40  Python高性能编程 pdf下载 下载次数 2870

41  Python A~B~C~ python视频教程下载 下载次数 2865

42  利用Python进行数据分析 pdf下载 下载次数 2863

43  数据结构与算法视频(小甲鱼讲解-全) 下载次数 2863

44  web小程序表白天数倒计时源码下载 下载次数 2862

45  python基础视频教程 下载次数 2862

46  go语言全套视频 下载次数 2854

47  流畅的Python PDF下载高清完整扫描原版 下载次数 2850

48  清华学霸尹成Python爬虫视频-ok 下载次数 2846

49  黑马前端36期最全视频和代码 下载次数 2842

50  2018最新全套web前端视频教程+源码下载 下载次数 2841