首页 > 小 Q 与构造
开通博客写题解
头像 范艺杰
发表于 2021-04-23 23:23:04
首先，k=1我们发现没有合法的。其次，对于k>=2的情况，我们可以分成若干链进行求解，链长很短。如果没有q的限制，则很显然记录最后一个选不选就行了。由q的限制，则记录最后q个数选的情况。看起来复杂度是2^q的，但是按照不能相邻来剪枝，状态不超过200个。进行dp即可。 #include < 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 折花有时亦有时
发表于 2021-05-03 20:51:10
一个很标准的淀粉质题。 题目所给的式子，我们可以看做一个树的重心，然后周围点与这个重心的贡献和，然后继续找这个重心的子树的重心，重复上述过程，就是淀粉质了。 但是我们需要注意一点，如果我们在计算贡献时，没有对所给式子的第一项进行从小到大的排序的话，时间复杂度是要退化为N^2的。关于贡献的求法，就是一 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”