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」氪金手游 – 题解