「QuestOJ」盛大的庆典 – 题解

主要思路

狗屎状压题。

看到度数不超过 \(10\) 就知道需要状压儿子的信息。考虑处理一个 neck 数组来表示子树内节点到当前子树根下面的节点编号,然后我们每一次往上跳的时候我们都可以对这个数组进行调整,然后 DP 的时候就会比较愉快了。

处理 \(m\) 个请求的时候,我们把对应的 neck 提取出来,然后做标记,按标号小的进行 DP。

继续阅读「QuestOJ」盛大的庆典 – 题解

P3349:[ZJOI2016]小星星 – 题解

主要思路

怎么毫无头绪啊?(wtcl)不过有一说一,题目是真的挺好。

有一种接近正解的方式是设置 DP,设 \(dp[u][i][stat]\) 为当前在点 \(u\)、编号为 \(i\) 且被用过的编号集合为 \(stat\),然后做一个树形 DP。不难分析出这个东西的复杂度是 \(\Theta(n^3 3^n)\)。

这个肯定过不了的,考虑进行玄学优化。假设转移时能去掉第三个限制就好了。我们考虑抛弃这个第三维。抛弃之后必须要面对的一个问题就是非法状态。我们可以考虑硬点一个点集,使得整个 DP 的时候只能选点集内的编号。发现这样答案的意义是至少有 \(i\) 个重叠选择的点的方案数,所以我们可以愉快的套一个 \((-1)^{n – |S|}\) 系数就可以的出恰好为 \(0\) 个重叠选择的方案数了。

继续阅读P3349:[ZJOI2016]小星星 – 题解

LibreOJ#3124. 「CTS2019 | CTSC2019」氪金手游 – 题解

主要思路

首先,\(n – 1\) 个二元组代表着这颗树形有向图的形状。我们先考虑外向树的情况:子树根的时间戳要早于所有的子节点,所以可以考虑直接用背包的方法进行合并。如果有反向边,那么我们可以考虑进行容斥,枚举反向关系数再乘上一个容斥系数 \(-1\) 即可。

继续阅读LibreOJ#3124. 「CTS2019 | CTSC2019」氪金手游 – 题解