发布于2019-09-11 13:29 阅读(1754) 评论(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
显然可以转化为图的连通问题,判断某点与其他点之间的可达性,所以用矩阵的幂求可达性矩阵,然后用可达性矩阵与原矩阵相减就可以得到结果了。
提交的时候才发现牛客网的系统不支持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))
不过本地还是能运行的
修改修改原来的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的计算就用了139ms
所以提交无法通过所有测试案例
作者:23dh
链接:https://www.pythonheidong.com/blog/article/107154/64a80384f0de80705de0/
来源:python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 python黑洞网 All Rights Reserved 版权所有,并保留所有权利。 京ICP备18063182号-1
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!