Early's Blog

简介

Link Cut Tree（简称 LCT）是使用 Splay 和实链剖分来维护森林的一个数据结构，它支持以下在线操作：

• 查询 / 修改链上的信息
• 换根
• 动态连边 / 删边
• 查询连通性
• ……

题目链接

题意

给定两个可旋转但不可翻转的环 $x,y$，支持整个环同时增加一个整数，最小化 $\sum_{i=1}^n(x_i-y_i)^2$。

简介

Splay 是二叉查找树的一种，它通过访问节点时将其旋转到根节点，使查找树尽量维持平衡。

题目链接

写在前面

比赛时只想到操作 2 的做法，于是只能写个暴力 60pts+ 只有操作 2 的 20pts 滚粗走人了。

考试结束跟学长一交流，瞬间感觉自己够傻，谨以此篇题解作为纪念。

题意

给定长度为 $n$ 的序列 $a,b$ 和 $m$ 种操作。

每次操作给出 $opt,u,v$，意义如下：

• 当 $opt=1$ 时，可使 $a_u\gets a_u-1,a_v\gets a_v-1$ 或 $a_u\gets a_u+1,a_v\gets a_v+1$；
• 当 $opt=2$ 时，可使 $a_u\gets a_u+1,a_v\gets a_v-1$ 或 $a_u\gets a_u-1,a_v\gets a_v+1$。

每种操作均可实现任意次，问能否把序列 $a$ 转为序列 $b$。

题目链接

题意

一个可重集合 $S$ 的神秘数为最小的不能被 $S$ 任意一子集之和表示的正整数。

给定正整数序列 $a$，每次询问给定 $l,r$，求 $\{a_l,a_{l+1},\dots,a_r\}$ 的神秘数。

题目链接

题意

一个 $(n+2)\times m$ 的矩形由 $1\times1$ 的小矩形构成。

每天第 $2-(n+1)$ 行最左和最右的矩形都有 $\frac ab$ 的概率消失。

问 $t$ 天后大矩形四联通的概率。

对 $10^9+7$ 取模。

题目链接

题意

在本题中，子串是可以通过删去原串若干个字符得到的字符串。特别的，空串也算子序列。

给定一个长度为 $n$ 的字符串 $s$，选出 $k$ 个本质不同的子串，最小化代价。

选择一个长度为 $m$ 的子串的代价为 $n-m$，即删去的字符数量。

题目链接

题意

给定一个长度为 $n$ 的序列 $a$，保证 $i-n\leq a_i\leq i-1$。

要求选出非空集合 $S$，使 $\sum_{i\in S}a_i=0$。

题目链接

题意

给定一棵 $n$ 个点的树，初始全是白点。

要求你做 $n$ 步操作，每一次选定一个与一个黑点有连边的白点，将它染成黑点，然后获得该白点被染色前所在的白色联通块大小的权值（第一次操作可以任意选点）。

求可获得的最大权值。

题目链接

题意

定义长度为 $n$ 的序列 $a$ 的最大前缀和为 $\max(0,\max_{i=1}^n\sum_{j=1}^ia_j)$。

求对于由 $n$ 个 $1$，$m$ 个 $-1$ 组成的所有序列的「最大前缀和」之和是多少。