抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

比赛地址

A - Consecutive Integers

题意

求在 \(1\)\(N\) 的整数中选择连续的 \(K\) 个整数的方案数。

\(N\le 50\)

题解

显然答案为 \(N-K+1\)

代码

B - RGB Boxes

题意

求有多少非负整数三元组 \((r,g,b)\) 满足 \[Rr+Gg+Bb=N\]

\(N\le 3000\)

题解

枚举其中两个即可。

时间复杂度 \(O(N^2)\)

代码

C - AB Substrings

题意

给定 \(N\) 个字符串 \(s_i\),将这些字符串按任意顺序拼接,求 AB 作为子串的出现次数的最大值。

\(N\le 10^4,|s_i|\le 10\)

题解

先将每个字符串中间的 AB 计入贡献,那么剩余的字符串可以分为 xxxxxABxxBxA 四种。

那么一定是用所有 BxA 和至多一个 xxABxx 拼出 xxABxABxA...BxABxx 这样的字符串,再用剩下的 xxABxxxxABxx 这样的字符串。

注意细节。

代码

D - DivRem Number

题意

给定正整数 \(N\),求有多少正整数 \(m\) 满足 \(\lfloor\frac{N}{m}\rfloor=N\bmod m\)

\(N\le 10^{12}\)

题解

化一下式子,得到 \(\lfloor\frac{N}{m}\rfloor(m+1)=N\)。那么 \(m+1\) 一定是 \(N\) 的因数,枚举即可。

时间复杂度 \(O(\sqrt{N})\)

代码

E - XOR Partitioning

题意

给定序列 \(A_1,A_2,\ldots,A_N\),将该序列划分成若干段,使得每段的异或和相等,求方案数。对 \(10^9+7\) 取模。

\(N\le 5\times 10^5\)

题解

对原序列作前缀和 \(S_i\),假设每段的异或和为 \(x\),那么一个合法的划分方案一定是选择 \(S\) 中一个 \(x\)\(0\) 交替的子序列。

考虑枚举 \(x\),然后 DP。令 \(f_i\) 表示前 \(i\) 个数,强制 \(i\) 选择且 \(S_i=x\) 时合法方案数。那么有 \[f_i=1+\sum_{j=0}^{i-1} f_j(c_i-c_j)\]

其中 \(c_i\) 表示 \(S_1,S_2,\ldots,S_i\)\(0\) 的数量。

最终答案与段数的奇偶性有关,段数为奇数时为 \(f_N\),段数为偶数时为所有 \(f_i\) 的和。段数的奇偶性可以通过 \(S_N\) 是否等于 \(0\) 确定。

用前缀和优化 DP 转移,时间复杂度 \(O(N)\)。注意特判 \(x=0\) 的情况。

代码

F - Edge Ordering

题意

给定一个 \(N\) 个点 \(M\) 条边的简单无向连通图 \(G\),保证前 \(N-1\) 条边构成了 \(G\) 的一个生成树。

你需要给每条边确定一个 \(1\)\(M\) 的整数边权,需要保证边权互不相同。

对于一个确定边权的方案,我们称该方案是好的当且仅当前 \(N-1\) 条边构成的生成树是最小生成树。

求所有好的方案的最小生成树边权和之和。对 \(10^9+7\) 取模。

\(N\le 20\)

题解

假设原图如下图(重绘自官方题解):

This is a picture without description

其中边上的数字为边的编号,黑边为树边,红边为非树边。

我们假设前 \(N-1\) 条边的边权按 \(1\)\(N-1\) 的顺序递增,例如上图中有 \(cost(1) < cost(2) < \ldots < cost(5)\)。为了使这五条边成为最小生成树,我们需要保证其余非树边 \((u,v)\) 的边权需要大于树上 \(u\)\(v\) 路径上最大的边权。例如图中 \(cost(7) > cost(3),cost(9) > cost(4)\)

我们可以根据边权的大小关系建出一个拓扑关系图,例如上图对应的拓扑图如下图所示(来自官方题解):

This is a picture without description

\(a_i\ (1\le i\le N-1)\) 表示上图中 \(i\) 向下的连边数量,即点 \(i\) 向编号大于 \(N-1\) 的点的连边数量。

那么我们可以把问题转化为,有 \(M\) 个有标号的球,你有一个空的序列 \(S\),球会按 \(a_{N-1}\) 个白球,一个黑球,\(a_{N-2}\) 个白球,一个黑球……这样的顺序给你,例如上图对应的球的序列为 \(8,5,9,6,4,7,3,2,1\)。每收到一个球,你可以执行以下操作:

  • 若收到的球是黑球,则在 \(S\) 的最前面插入该球。
  • 若收到的球是白球,则插入到 \(S\) 的任意位置。

求最终得到的所有 \(S\) 序列中黑球的位置编号和之和。

考虑在依次收到球的过程中,维护 \(n\) 表示当前序列 \(S\) 的长度,\(b\) 表示 \(S\) 中黑球的数量,\(c\) 表示不同的序列 \(S\) 的数量,\(s\) 表示所有序列 \(S\) 中黑球的位置编号之和的和。用 \((n,b,c,s)\) 表示当前的状态。

若收到一个黑球,那么新的状态为 \((n+1,b+1,c,s+(b+1)c)\)

若收到一个白球,假设原来的序列中黑球的位置为 \(p_1,p_2,\ldots,p_b\),不妨假设 \(p_0=0,p_{b+1}=n+1\),那么插入该白球时的总变化量(即每个位置的贡献之和)为 \[ \sum_{i=1}^{b+1}(p_i-p_{i-1})(b-i+1)=\sum_{i=1}^{b}p_i \]

所以新的状态为 \((n+1,b,(n+1)c,(n+1)s+s)\),即 \((n+1,b,(n+1)c,(n+2)s)\)

那么加入 \(k\) 个白球后新的状态为 \((n+k,b,\frac{(n+k)!}{n!}c,\frac{(n+k+1)!}{(n+1)!}s)\)

对于原来的问题,我们并没有固定前 \(N-1\) 条边边权的大小关系,所以需要 DP。考虑到上面的问题是按边权从大到小进行转移的,那么这里的 DP 也从大到小确定边权的大小关系。

\(f_S=(n,b,c,s)\)\(S\) 表示该集合中边权的大小关系仍未确定,不在该集合中的边的边权都大于在该集合中的边的边权。\(n,b,c,s\) 的定义与之前类似。转移只需要枚举下一条边,\(c,s\) 的转移与上面问题类似。

实现精细可以做到 \(O(2^NN)\)

代码

评论