2020.11 月赛题解

Once edited 4 年，1 月前

Problem A 选择题

First to solve: hangyesheng

二分题。

枚举 $d_i$，求出有多少个人的出生年份小于 $d_i$（假设有 $x$ 个），求出有多少个人的奖项的设立年份 $\le d_i$（假设有 $y$ 个），那么能出的选择题数量就是 $x\times y\times \binom{n-y}{3}$。

时间复杂度 $O(n+m\log_2n)$。

Problem B 辗转相除法

First to solve: Chirography_11

6 10 15是各位选手使用最多的一组反例。

Problem C 爆炸吧现充

First to solve: Renatus

集合题。
$$
F(Q) = \sum_{S\cup T=Q}\max(A(S),B(T))
$$
做一下子集前缀和：设 $\hat{F}(Q) = \sum_{S\subseteq Q}F(S)$。则有

$$\hat{F}(Q) = \sum_{S\cup T\subseteq Q}\max(A(S),B(T)) = \sum_{S\subseteq Q}\sum_{T\subseteq Q}\max(A(S),B(T))$$

这个很好算。求出 ${A(S) \mid S\subseteq Q}$ 和 ${B(S) \mid S\subseteq Q}$。把两个长度为 $2^{|Q|}$ 的序列分别排序，然后在归并的过程中统计贡献即可。

由于 $a_i\le 2^7$，因此 $A(S),B(S)\le 2^7n$，所以用桶排序即可。

时间复杂度 $O(2^{n+7}n)$。

有关高维前缀和（子集前缀和）的内容可以见此。

Problem D 傲娇

First to solve: LiuRunky

性质题。

考虑什么样的 $a’$（$a$ 的排列）能最大化 $F$。考虑 $a’$ 中最小值的位置。先假设 $a’$ 的最小值唯一且为 $a’_i$。那么 $i=1$ 或者 $i=n$ 是最大化 $F$ 的充要条件。

证明：因为 $a_i’$ 是最小值，对于任意 $l\le i\le r$，有 $w(l,r)=a_i’$。因此我们希望满足 $w(l,r)=a_i’$ 的区间 $[l,r]$ 尽可能少。而当且仅当 $i=1$ 或者 $i=n$ 时 $[l,r]$ 的个数能取到最小值。

如果 $a’$ 有多个相等的最小值，不难证明，最小值放开头或者末尾是最大化 $F$ 的充要条件。也就是说，$a’$ 中除了最小值之外的其他数一定构成一个连续区间 $[L,R]$（也就是说 $[1,L-1],[R+1,n]$ 放的都是最小值）。

如果 $a’$ 中有 $x$ 个最小值，那么放最小值的方案数就是 $x+1$（所有数都相同的情况例外）。

考虑完放最小值的方案后，剩下的就是子问题了。

时间复杂度 $O(n\log_2n)$（需要排序）。

Problem E 布尔表达式

First to solve: MAOooo

构造题。

由于 SPJ 复杂度原因，本题是不让你写括号的，相当于是提示了你做法。

举个例子：如果要求 $a_1=1,a_2=1,a_3=0$ 时 $f(a_1,a_2,a_3)=1$，那么我令 $f=a_1\wedge a_2\wedge \neg a_3$ 就行。

如果我要求 $f(1,1,0)=f(0,1,1)=1$，那么我令 $f=a_1\wedge a_2\wedge \neg a_3\lor \neg a_1\wedge a_2\wedge a_3$即可。

也就是说，逻辑与和逻辑非操作用于描述一个二进制状态，而逻辑或把所有状态都并起来。

复杂度 $O(n2^n)$。

Comment

cubercsl Once ：这是主析取范式。

Problem F 天桥

First to solve: Renatus

DP 题。

定义一个序列的贪心括号序列是用栈模拟得到那个括号序列。

栈模拟：如果遇到相同颜色，就分别标为左右括号，然后弹栈。否则就圧栈。

显然，括号序列有树的结构，每个结点代表一个匹配。

设 $f_i$ 表示长度为 $2i$ 的合法染色序列个数。设 $g_i$ 表示长度为 $2i$，且该序列的贪心括号序列中最外层括号的颜色不为某个特定色的方案数。

最外层括号：如 ((()))(()) 中的最外层括号是 (____)(__)。

不为某个特定色：可以理解为，不为第 $1$ 种颜色。也可以理解为，只有 $k-1$ 种可选的颜色。

$g$ 是用于辅助 $f$ 的转移。

则有 $g_i=(k-1)\sum_{j}g_jg_{i-1-j}$，$f_i=k\sum_j g_jf_{i-1-j}$。

$f$ 的转移可以理解为，枚举贪心括号序列中第一对括号的匹配位置，然后计算染色方案数。

一个染色序列对应唯一的贪心括号序列。因此正确性有保证。

时间复杂度 $O(n^2)$。

Comments

钟兆雄

4 年，1 月前

没有代码的答案吗

回复 0 0

Once

4 年，1 月前

所有选手代码都已公开。

回复 1 0

MAOoo

4 年前

C题的复杂度是不是还需要增加一个$\, O(3^n) \,$用于枚举出所有的$\, A(S \subseteq Q) \,$和$\, B(S \subseteq Q) \,$加到桶里面。至少我看到所有的AC代码都有枚举子集这一步。

回复 0 0