2023-03-05 01:39 快手_向量检索平台工程师 发布于上海
发布于上海 关注
第99场双周赛
第三题想并查集去了，没取最大值。
第四题dp以前i个节点、前i个查询、大于等于i个正确查询作为下标都行不通，只能以i节点为根记录正确查询次数了，如果i和j1，j2,...,jni相连，先求dp[j1]，如果[i,j1]在查询中，则dp[i]比dp[j1]的查询正确的次数多1，在求dp[j1]的过程中不能重复考虑i为j1的子节点了，只能考虑 j1为根不包含i的其他子树，最后 dp[i]= sum_{o=1}^{n_i} dp[j_o] + I([i,o] in query)，还要用二次递归求其他节点为根的全树情况
https://mp.weixin.qq.com/s/P_EYQxOEupqdU0BJMRqWsw
https://mp.weixin.qq.com/s/pAD9yv8Fljs6b70EdaScJA
第四题dp以前i个节点、前i个查询、大于等于i个正确查询作为下标都行不通，只能以i节点为根记录正确查询次数了，如果i和j1，j2,...,jni相连，先求dp[j1]，如果[i,j1]在查询中，则dp[i]比dp[j1]的查询正确的次数多1，在求dp[j1]的过程中不能重复考虑i为j1的子节点了，只能考虑 j1为根不包含i的其他子树，最后 dp[i]= sum_{o=1}^{n_i} dp[j_o] + I([i,o] in query)，还要用二次递归求其他节点为根的全树情况
https://mp.weixin.qq.com/s/P_EYQxOEupqdU0BJMRqWsw
https://mp.weixin.qq.com/s/pAD9yv8Fljs6b70EdaScJA
全部评论
相关推荐
投递上海迪士尼等公司10个岗位 > 点赞 评论 收藏
转发