link

T1 摆花

Problem

给出一个整数 nn 和 mm 个区间 [li,ri][l_i,r_i]，要求往长度为 nn 的序列 aia_i 中填数 x(0≤x≤n−1)x(0\leq x\leq n-1)，其中 xx 可以重复，求一种方案最大化 mex⁡[ali,ari]\operatorname{mex} [a_{l_i},a_{r_i}]，输出这个最大值。

100%→n,m≤105,1≤li≤ri≤n100\% \rightarrow n,m\leq 10^5,1\leq l_i\leq r_i\leq n

1s/512MB1\text{s}/512\text{MB}

Solution

答案为 min⁡(ri−li+1)\min (r_i-l_i+1)，因为对于每一个区间来说最优方案肯定是从 00 到 ri−li+1r_i-l_i+1。

时间复杂度 O(m)\mathcal{O}(m)。

Summary

题面看成 xx 不可以重复了，然后写的区间交，30pts30\text{pts}。

T2 打饭

Problem

给出一个整数 kk 和一个长度为 nn 的序列 aia_i，构造出一组该序列的排列最小化 ∑i=1n−k∣ai−ai+k∣\sum_{i=1}^{n-k}|a_i-a_{i+k}|，输出这个最小值。

30%→n≤1030\% \rightarrow n\leq 10

100%→n≤3×105,k≤min⁡(n−1,5000),−109≤ai≤109100\% \rightarrow n\leq 3\times 10^5,k\leq \min(n-1,5000),-10^9\leq a_i\leq 10^9

1s/512MB1\text{s}/512\text{MB}

Solution

问题等价于将这 nn 个数分成 kk 个组，找出排列最小化每个组的 max⁡−min⁡\max - \min 之和，如下图是 n=8,k=3n=8,k=3 时的分组情况：

GroupDivision

那么将有 n mod kn\bmod k 个组会被分到 nk+1\frac{n}{k}+1 个数（下文称为种类 1），k−n mod kk-n\bmod k 个组会被分到 nk\frac{n}{k} 个数（下文称为种类 2）。

那么将原序列排个序，若要使 max⁡−min⁡\max - \min 最小，那么每一个组的数必定会在排序后的序列中为连续的一段。

那么设 g1=n mod k,g2=k−n mod k,p1=nk+1,p2=nkg_1=n\bmod k,g_2=k-n\bmod k,p_1=\frac{n}{k}+1,p_2=\frac{n}{k}，设 fi,jf_{i,j} 为种类 1 的组已经分了 ii 个，种类 2 的组已经分了 jj 个的最小答案。

那么便有转移：

i<g1→fi+1,j=min⁡fi,j+ap1(i+1)+p2j−ap1i+p2j+1j<g2→fi,j+1=min⁡fi,j+ap1i+p2(j+1)−ap1i+p2j+1i < g_1\rightarrow f_{i+1,j}=\min f_{i,j}+a_{p_1(i+1)+p_2j}-a_{p_1i+p_2j+1}\\ j < g_2\rightarrow f_{i,j+1}=\min f_{i,j}+a_{p_1i+p_2(j+1)}-a_{p_1i+p_2j+1}

答案显然为 fg1,g2f_{g_1,g_2}，时间复杂度 O(nlog⁡n+k2)\mathcal{O}(n\log n+k^2)。

Summary

暴力都还比预期少 1010 分，20pts20\text{pts}。

T3 小象砍树

Problem

给出一棵 nn 个节点的无根树，每次可以选择一个度数为 11 的点并删掉，问多少种不同的方案可以将树删到只剩一个点，两种方式不同当且仅当至少有一步被删除的节点不同，方案数对 998244353998244353 取模。

10%→n≤1010\% \rightarrow n\leq 10

100%→n≤105100\% \rightarrow n\leq 10^5

1s/512MB1\text{s}/512\text{MB}

Solution

设 fif_i 为以 ii 为根的方案数。

显然，对于一个根来说，根节点一定最后删除，且一定在子节点都被删除之后，设以 ii 为根的子树大小为 sizisiz_i，根节点的删除次序肯定比 sizisiz_i 要大，由于根节点的儿子节点删除起来无序，所以等价于 sizi−1siz_i-1 中选 sizjsiz_j 个数，然后再把剩下的数留给下一个儿子节点。

又因为方案顺序是有序的，所以还要乘上对应的 fjf_j，总的来说转移方程为：

fi=∏j∈sonifjCsizi−cnt−1sizjf_i=\prod_{j\in son_i}{f_jC_{siz_i-cnt-1}^{siz_j}}

换根转移：

fj=fiCn−1n−sizjCn−1sizjf_j=\frac{f_iC_{n-1}^{n-siz_j}}{C_{n-1}^{siz_j}}

答案为 ∑i=1nfi\sum_{i=1}^{n}f_i，时间复杂度 O(nlog⁡n)\mathcal{O}(n\log n)。

Summary

暴力，赛时想的换根转移组合推炸了，10pts10\text{pts}。

T4 路径计数

Problem

给出一棵 nn 个节点的完全二叉树并另外加了 mm 条边，问图上有多少条不同的简单路径，答案对 109+710^9+7 取模。

简单路径指一条没有多次经过同一个点的路径（只有一个点的路径也是简单路径），两条路径不同当且仅当经过的边集不同或经过边的顺序不同，重边也算不同的边。

15%→m=015\% \rightarrow m=0

100%→n≤109,m≤10100\% \rightarrow n\leq 10^9,m\leq 10，数据随机生成。

5s/512MB5\text{s}/512\text{MB}

Solution

二叉树不用直接建边，然后直接 DFS 即可。

WHY? 仅考虑 mm 条边经过的顺序和方向，有 m!2mm!2^m 种方案，而实际需要建出的节点数为 mlog⁡nm\log n，故时间复杂度为 O(m!2m(mlog⁡n)2)\mathcal{O}(m!2^m(m\log n)^2)，可以通过本题。

Summary

直接输出 n2 mod (109+7)n^2\bmod (10^9+7)，15pts15\text{pts}。

T5 博物馆

Problem

给出一个 nn 个点的边带权完全图，对于每一个点 xx 来说，定义一条合法的路标（一些边），当且仅当所有点都能通过此路标到达 xx，代价为（每个点到 xx 的最小边权值）之和。对于每一个点，最小化代价。

20%→n≤820\% \rightarrow n\leq 8

100%→n≤3000,1≤wi,j≤109100\% \rightarrow n\leq 3000,1\leq w_{i,j}\leq 10^9

1s/512MB1\text{s}/512\text{MB}

Solution

将所有边的边权减去最小的边权，将问题转化为求一条链上的代价和，对于一条路径来说，若权值出现递增且后面有富余的边，那么合并成一条显然更优，那么仅需跑一遍 Dijkstra 即可，为防止出现递增而没有富余的边的情况，需提前初始化 disti=min⁡2gi,jdist_i=\min 2g_{i,j}。

时间复杂度 O(n2)\mathcal{O}(n^2)。

Summary

暴力，20pts20\text{pts}，考得太烂了。