美团3-30笔试 第五题
第五题做法
直接对着树做会出错,因为有三角恋的情况(环)
tarjan缩点,强连通分量建边,然后用个set存下来新的root
构造了一颗颗树,树木之间相互独立
int dfs(u){
dp[u][0]=1
dp[u][1]=1
枚举边
dp[u][0]*=dfs(j)
dp[u][0]%=mod
return dp[u][0]+dp[u][1]
}
这个是递归函数
下面要枚举树根,树木之间相互独立,
ans=1
ans*=dfs(root)
ans%=mod
样例的解释好像是要减去一个朋友都不邀请的情况,所以输出ans-1
cout<
ac 100%
下面说一下个人看法
我已经退役半年了,很生疏,而且经常笔试迟到半个小时,感觉笔试越来越卷,这个对非竞赛生非常不友好!!!
没必要花大量的时间精力去学这些,性价比太低了,好好准备面试吧!感觉我队友都不一定会写。
错的是这个世界,大家加油吧!
直接对着树做会出错,因为有三角恋的情况(环)
tarjan缩点,强连通分量建边,然后用个set存下来新的root
构造了一颗颗树,树木之间相互独立
int dfs(u){
dp[u][0]=1
dp[u][1]=1
枚举边
dp[u][0]*=dfs(j)
dp[u][0]%=mod
return dp[u][0]+dp[u][1]
}
这个是递归函数
下面要枚举树根,树木之间相互独立,
ans=1
ans*=dfs(root)
ans%=mod
样例的解释好像是要减去一个朋友都不邀请的情况,所以输出ans-1
cout<
ac 100%
下面说一下个人看法
我已经退役半年了,很生疏,而且经常笔试迟到半个小时,感觉笔试越来越卷,这个对非竞赛生非常不友好!!!
没必要花大量的时间精力去学这些,性价比太低了,好好准备面试吧!感觉我队友都不一定会写。
错的是这个世界,大家加油吧!
全部评论
nb,卧槽还有环,感觉用个超级点连树根是不是也行
送花
回复
分享
太恐怖了这题,想混分混不上
送花
回复
分享
秋招专场
官网直投
大佬,第四题要怎么a啊,感觉少了一个优化
送花
回复
分享
确实要先缩点,再树形dp,不能看模板的话,默写不出来
送花
回复
分享
相关推荐
投递哔哩哔哩等公司10个岗位 >
点赞 评论 收藏
转发
04-03 22:32
中国科学技术大学 自动化类 点赞 评论 收藏
转发