20260429 测试 笔记

T2

对于一个二元组 $(p,q)$，其中 $p,q$ 都是长度为 $n$ 的排列，小 Z 定义其权值为 $\sum _{i=1}^{n}max(p_i,q_i)$。

请你对 $k=1,2,\dots ,n\times n$ 求出，一共有多少对 $(p,q)$ 满足其权值为 $k$。

由于答案可能很大，所以答案请对输入的模数 $P$ 取模。

$1\le n\le 100,{10}^8\le P\le {10}^9+7$。

显然可以固定 $p_i=i$，最后给答案 $\times n!$。接着考虑按顺序放 $q_i$，但是把 $q_i$ 放到 $r$（定义 $l<i<r$）的位置的情况难以 DP，因为有后效性，考虑设计一种没有后效性的 DP。只考虑 $1\dots i$ 和 $q_{1\dots i}$，发现共有以下五种情况。

 i   |  l'    i   |  l'    i  |  i   |  i
q[i] | q[i]  q[l] | q[i]  ___ | q[l] | ___

设 $f_{i,j,s}$ 表示考虑把 $q_{1\dots i}$ 放进 $1\dots i$，还有 $j$ 个数没放进去，权值为 $s$ 的方案数。

对于第一种情况：

$$f_{i,j,s+i}\leftarrow f_{i-1,j,s}$$

对于第二种情况，可以在前面 $j$ 个 $l^{\prime }$ 中任选一个放 $q_i$，也可以任选一个没放的 $q_l$ 放进 $i$。

$$f_{i,j-1,s+2i}\leftarrow f_{i-1,j,s}\times j^2$$

对于第三、第四种情况，一个是把 $q_i$ 放到前面去，本位留空等后面的放进来；另一个是把前面没放的 $q_l$ 放进 $i$，$q_i$ 留到后面再放。两种本质和贡献均相同，一起计算。

$$f_{i,j,s+i}\leftarrow f_{i-1,j,s}\times 2j$$

对于第五种情况，就是 $q_i$ 以后再放，$i$ 等后面的放到前面来。

$$f_{i,j+1,s}\leftarrow f_{i-1,j,s}$$

状态数 $O(n^4)$，转移 $O(1)$，时空复杂度 $O(n^4)$。

T3

小 Z 所在的班级一共有 $n$ 个人，他们正在准备组织团建活动。根据调查，第 $i$ 个人可以参加团建的时间为区间 $[l_i,r_i]$。

由于可能不存在所有人都有空的时间，大家决定把人分成 $k$ 组。每一个人会被分到恰好一个组，每个组有至少一个人。团建要求所有人都能参加，所以对于同一个组，要求存在至少一个时间点满足所有人都能参加团建。

一般来说，团建时间越长，能获得的快乐度也就越多。对于一个组，团建所能获得的快乐度，等于所有人都能参加团建的整数时间点个数。一次团建的快乐度等于每个组的快乐度之和。

小 Z 希望最大化团建的快乐度，但是现在小 Z 还不能确定要把所有人分成多少组。所以，请你对 $k=1,2,\dots ,n$ 求出，所有合法的分组方案中，快乐度的最大值是多少。特别的，如果不存在合法的方案，输出 $-1$。

$T\le 10,1\le n\le 6\times {10}^3,\sum n\le 1.2\times {10}^4,1\le l_i\le r_i\le {10}^9$。

由特殊性质启发，考虑包含了别人的区间，容易发现这些人除非独立成组，否则他们直接加入被包含的人所在的组，对那一组团建时长无影响。

因此先不管包含别人的区间，是一个简单的 DP，设 $f_{i,j}$ 表示按 $l_i$ 顺序考虑前 $i$ 个人，划分成 $j$ 组的方案数，则有

$$f_{i,j}\leftarrow \underset{k=1}{\overset{i-1}{max}}\{f_{k,j-1}+r_k-l_i\}$$

状态数 $O(n^2)$，转移 $O(n)$，时间复杂度 $O(n^3)$，无法通过。

这种按顺序的区间拆分，联想到 四边形不等式优化，恰好 $r_k-l_i$ 作为 $w(k,i)$ 是能够 $O(1)$ 计算的代价函数，使用二分队列即可做到 $O(n^2)$。

最后考虑包含别人的那些人，如果让他们独立成组，显然让区间最长的那些人独立成祖贡献最大，枚举有多少个人独立成组，即和 DP 结果做 $(max,+)$ 卷积即可。