+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-08(82)

2019-09(116)

2019-10(8)

2019-11(8)

2019-12(12)

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

发布于2019-09-11 13:29     阅读(1141)     评论(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
在这里插入图片描述
所以提交无法通过所有测试案例
在这里插入图片描述



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

作者:23dh

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

来源: python黑洞网

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

23 0
收藏该文
已收藏

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