ABC 312

SFlyer / 2023-07-30 / 原文

纪念一次(赛后补完)赛时 ABCDFGH 的比赛。

submissions

过会补。

A,B

可以直接暴力打表。B 题也可以 这样。

C

二分答案。

D

可以 dp,\(dp_{i,j}\) 表示前 \(i\) 个,现在 () 多多少。(\(\ge 0\))。\(dp_{i,j}=dp_{i-1,j-1}(if \ can\ '(')+dp_{i-1,j+1}(if \ can \ ')')\)

E

啊!感觉是最难的一题。首先所有的长方体体积之和 \(\le 100^3=10^6\)。可以把两个长方体面重合 \(<=>\) 他们中有 \(1\times 1\) 的小正方体面重合。然后就可以暴力。

F

枚举 pull-tab 选几个,二分 regular can 最多还可以选一个。(当然,先按 happiness 从大往小排,求前缀和)。

editorial 是 \(O(N)\) 的,kl。

G

我的方法好烦啊。

最简单的方法是:\(ans=\binom{n}{3}+\binom{n}{2}-\sum_i\sum_j dis_{i,j}\)。可以一个 dfs 解决。1。

我赛时的方法是:\(dp_{v}\) 表示以 \(v\) 为根的子树的答案。\(f_{v}\)\(v\) 为根,可以和 \(fa_v\) 组成一种方法的选两个节点的方法数。\(sz_v\) 是子树大小。以下 \(g\) 为儿子。

\(dp_v=\sum_{(a,b,c)\in g_v} sz_a\cdot sz_b\cdot sz_c+sum_{u\in g_v} (n-sz_u)\cdot dp_u+\sum_{u\in g_v} dp_u\)

\(f_v=\sum_{u\in g_v}f_u+\frac{\sum_{u\in g_v}sz_u\cdot (sz_v-sz_u-1)}{2}\)

2。