首页 > 魔法树
开通博客写题解
头像 Alka_Tale
发表于 2023-10-20 21:21:23
C题： gcd大于1时，mex不超过1; mex大于1时，gcd为1； 因此答案要么来源于整个序列（mex最大化），要么来源于两个相邻数且其中一个为0（gcd最大化且mex为1）。 D题： 只考虑模2^20意义下的数，因此只有2^20个点，bfs预处理答案即可。 E题： n<7时，答案为-1。 展开全文
去ta的博客 赞 (13) 回复(0) 收起
头像 keduoli
发表于 2023-10-21 00:18:47
G 魔法树 这题第一感觉就是树形DP 但是这里面的状态蛮多的，不太好下手。 其实可以分情况讨论 全是奇数 全是偶数 这样的话，dfs中需要维护的状态反而少了。 还有一点就是，这题的核心是边 也就是边的选择/不选决定了方案数 只有理解这点，才能理解下面的转移方程 全是奇数连通分量 每个 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 itoshiki_Treap
发表于 2023-10-21 16:34:55
计数类树形 DP 的常用思路之一为决策边，将点或点所在连通块状态放在主状态的附加维中。例如CF461B，NOIP2022 T3都可以用这个思路解决。 回到本题，决策边的提示已经挂脸上了，考虑状态设计：注意每个点所在的连通块可以通过是否和儿子连边从而和儿子合并成一个大连通块来改变奇偶性，但是答案中整体 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”