美团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%

下面说一下个人看法
我已经退役半年了,很生疏,而且经常笔试迟到半个小时,感觉笔试越来越卷,这个对非竞赛生非常不友好!!!
没必要花大量的时间精力去学这些,性价比太低了,好好准备面试吧!感觉我队友都不一定会写。
错的是这个世界,大家加油吧!
全部评论
nb,卧槽还有环,感觉用个超级点连树根是不是也行
3
送花
回复
分享
发布于 03-30 21:26 四川
太恐怖了这题,想混分混不上
2
送花
回复
分享
发布于 03-30 21:26 日本
秋招专场
校招火热招聘中
官网直投
大佬,第四题要怎么a啊,感觉少了一个优化
1
送花
回复
分享
发布于 03-30 21:38 北京
确实要先缩点,再树形dp,不能看模板的话,默写不出来
点赞
送花
回复
分享
发布于 03-30 22:02 浙江

相关推荐

3 2 评论
分享
牛客网
牛客企业服务