123456' blog

Blog

"Libre" Round 1 Div.2题目题解

2021-11-13 09:10:59 By 123456

A. Albiduria [Div.2 Only]

直接 BFS 即可。

B. Blastula [Div.2 Only]

答案即为卡特兰数 $C_n$.

C. Caucasoid

假设串长为 $m$,每一段极长相同字符长度为 $x_i$,那么我们记 $f(m)=m^2- \sum x_i^2 =2n$。

$x_i=1$ 时 $f(m)$ 取到最小值 $m(m-1)$。我们找到最小的 $m$ 使得 $m(m-1)\geq 2n$,考虑构造一个长度为 $m$ 的串。

将 $m(m-1)/2$ 视为 $f(m)/2$ 的初始值,那么对于一个 $x_i=k$,它会使 $f(m)/2$ 减小 $k(k-1)/2$。而我们总共需要减小 $m(m-1)/2-n$。由于 $(m-1)(m-2)/2 < n$,那么这个值最多为 $m-2$。

接下来我们直接贪心,每次取一个尽量大的 $k$。

由于 $k=3$ 时 $k\leq k(k-1)/2$,$k=2$ 时 $k(k-1)/2=1$,并且 $k=2$ 最多出现 $2$ 次,因此 $\sum x_i \leq m$。

时间复杂度 $O(t\sqrt n)$

D. Dialysate

结论: 存在一种最优方案使得每次操作的区域是上一次的子集且颜色与上一次相反.

考虑归纳证明, 记 $S$ 为当前所有操作区域的并, $T$ 为接下来一步的操作区域, 我们有:

  1. $T$ 与 $S$ 有交的情况一定可以转化成 $T$ 被 $S$ 包含的情况.

  2. $T$ 与 $S$ 交集为空时, 可以找一个连接 $S$ 和 $T$ 的集合 $M$ 并操作 $S \cup T \cup M$,并将之前的所有操作连接到更外的层以及外层的连接部分同时操作, 特殊处理最外层和第二层的情况.

  3. $T$ 被 $S$ 包含时, $T$ 落在某个完整区域内时等价于情况二, 否则一定连接若干个同色块, 这些块可以同时处理, 步数一定不会更劣.

知道这个结论就比较好做了, 我们可以枚举最后被修改的区域, 这时答案就是将同色边边权当作 $0$, 异色边边权当作 $1$ 后距离这个点最远的黑色点的距离, 对所有点取最小值即可.

E. Exilarch

问题相当于统计每个 $(p, S)$($1 ≤ p ≤ p + |S| − 1 ≤ m$),在多少个 $(x, y)$($1 ≤ x ≤ y ≤ n$)中使得:$∃z ∈ [x, y], \{A_{z,p}, A_{z,p+1}, \cdots, A_{z,p+|S|−1}\} = S$,然后求和。

先考虑 $p = 1$ 时的情况,将矩阵建出一棵 trie,每个结点用 set 保存对应 $S$ 出现的行集合。

每次将 $p$ 加 1,只需将根的所有孩子合并,作为新根。两个行集合合并时直接把小的加入大的。$O(nm \log^2 n)$。

F. Feuillant [Div.1 Only]

不会做

G. Glycoside [Div.1 Only]

不会做

Yuhao Du Contest 7 的题解博客怎么被删除了

2021-10-14 09:56:54 By 123456

为啥 404 了

Best university in California

2021-09-22 22:39:57 By 123456

Our OI Oriented Open Archive 账户分享!

2021-03-09 16:15:06 By 123456

$\color{red}{\huge{\mathrm O_4\mathrm A \text{已永久停止下载服务,其所有数据迁移到了 QOJ::FTP。}}}$

拥有 FTP 权限的用户可以在 QOJ::FTP 上下载。


每个账户有 20 GB 每月的下载流量配额,大家合理使用!

username password
public1 rR2q67hrW3B57O
public2 893eu6nj'Z;Y(T
public3 @tTG.VV5RhjE[7
public4 Px0Pb2FLQ:yRMA
public5 1}k1pQr(EbpF0{
public6 Z8H[?AnFDJQ.]r
public7 jJ2Eh4bmJXJuEg
public8 h!qy]f1Wj,2Zfc
public9 TNhh]ax!tYkz[u
public10 [email protected]:6b4.ZrRE
public11 ;$u0,(j>Fq,Z4.
public12 'l[xE1xkJ][email protected]
public13 }Dt5:W))Xw1&]r
public14 @Y5hZnT1HspoFd
public15 3<}[email protected]&XH
public16 aiyWq>DSAlN)hm
public17 o(0Y2wFA;o0kD[
public18 6OSZK8J(z9bmc{
public19 J'CyD{V&[email protected]
public20 >7n{;z44'sG.Tl

大家好,我是123456

2021-03-09 15:16:42 By 123456

大家早上好!

123456 Avatar