2023.2 做题记录

yanchengzhi · 2023-03-02 21:34:27 · 个人记录

部分题解

首先，不难想到一个简单 dp，设 f_i 表示消灭怪兽 i 的最小体力消耗，假设普通攻击体力消耗为 a_i，魔法攻击体力消耗为 b_i，可以得到状态转移

f_u=\min(b_u,a_u+\sum_{u\rightarrow v}f_v)

但是，有一个很明显的问题，这张图并不是 DAG，不能够直接拓扑排序。

不过，由于 f_u\geq 1,a_u\geq 1，因此一定存在一个终止的位置，也就是说，转移的顺序一定满足 DAG 的结构。

不难发现，如果对于任意的 v，都有 f_v>f_u，那么当前状态下 f_u 已经转移完成了。

因此，可以开一个维护最小的 f_u，每次从堆中取出的元素一定是完成了转移的，它就可以作为一个终止位置对其它点产生贡献，然后类似拓扑排序的方法，如果一个点的入度为 0 了，它就转移完成了，再把它加入堆中即可。

很有启发性。

把询问离线，放到一棵线段树上，然后题目中修改操作相当于全局加，全局乘，全局特殊加，区间取 \min 或 \max。

发现全局特殊加不好维护，但是可以观察到一个性质：进行操作后，答案的相对大小不会发生改变。

因此可以把初始值排序，最大值和最小值一定在端点处取到，这样全局特殊加就可以用标记维护了。

考虑把 a_i 不降的那个限制去掉，转化成：

求每个数的取值范围为 [0,M]，且异或和为 X 的方案数。

因为如果存在 i 满足 a_i=a_{i+1}，把这两个数删掉不会有影响，因此可以考虑在最后枚举删了多少对相同的数。

设 g_i 表示 i 个互不相同的数满足如上限制的方案数，最后的答案是

\sum_{i=0}^{\lfloor\frac{n}{2}\rfloor}\frac{g_{n-2i}}{(n-2i)!}\binom{M+i}{M}

钦定了 i 个数互不相同，不好计算，考虑容斥，先用数位 dp 算出长度为 i 的合法序列个数（不限制元素互不相同），用 f_i 表示。

这部分时间复杂度 \mathcal{O}(n^3\log V)。

那么

g_l=f_l-\sum_{i=0}^{l}\sum_{j=0}^{l-1}\sum_{k=0}^{l}\binom{l}{i}\text{odd}_{i,j}g_j\text{even}_{l-i,k}(M+1-j)^{\underline{k}}

其中 i 表示所有出现次数为奇数的数的总数，j 表示出现次数为奇数的数的种类数，k 表示出现次数为偶数的数的种类数，\text{odd}_{i,j} 表示把 i 个不同的元素划分成 j 个不可区分的集合且集合大小是奇数的方案数，\text{even}_{i,j} 同理。

这部分可以通过预处理做到 \mathcal{O}(n^3)。

因此总复杂度 \mathcal{O}(n^3\log V)。