10.2 总结

$ABC373D$

第一反应是 $Topo$ 排序，然而如果直接 $Topo$ 的话会出现如下情况：

初始会钦定 $val_1=val_3=0,$ 但这样无法算出 $val_2.$

于是考虑建双向边然后 $Dfs.$ 本题保证有解，不过无解也很好判断。

$ABC373E$

起初有一个思路：

先对原序列进行排序。求出前缀和 $s_i=\sum_{j=1}^i a_j.$

枚举 $i\in[1,n],$ 二分 $q\in[0,k-s_n]$ 并进行判断。判断时取最大的 $m$ 个不含 $i$ 的 $a$ 中元素，记为 $b_1,…,b_m.$ 设其中有 $p$ 个满足 $b_p>a_i+q,$ 则若 $q$ 满足题意，需 $\sum_{j=p+1}^m (a_i+q-b_j)+q\le k-s_n.$ 左侧的求和式可以转化为前缀和的形式，因为 $b$ 是由 $a$ 从大到小取值的，尽管去除了 $i$ 本身。实际处理时 $p$ 要通过二分求解，记得和 $min(m,i-1)$ 取 $min.$ 另外，如果无法取出 $m$ 个元素构成序列 $b_1,…,b_m,$ 则必然合法。

$ZR-3018-10\ pts$

昨天想的 $dp$ 算法实现起来有诸多困难。由于 $2^n$ 和 $n!$ 在 $n\le 10$ 时都较小，所以可以直接枚举排列。时间复杂度 $O(n!n).$

$ZR-3020$

题目默认 $\forall\ i\in [1,n],p_i\in[1,n].$

那么 $\forall i\in[k+1,n],p_i\in [k+1,n],$ 方案数即为 $(n-k)^{n-k}.$

$[1,k]$ 暴力搜索进行判断，最劣时间复杂度为 $8^{10},$ 理论过不了，实际不超过 $600\ ms.$ 这样吧。