夏令营游寄

Day 1

比赛题

T1 P7163

给一个树, 每个点有一个灯, 可能为开或关, 每经过一个点会把灯的状态翻转, 不能停留, 任选起点, 求最短路径把所有灯打开. $n\le 10^5$

尝试构造发现方案不唯一而十分复杂, 考虑dp.

由于起点为自选, 想到换根dp, 发现换根过程很困难, 考虑把换根的信息也放进状态里, 最后设 $f_{u, 0/1, 0/1/2}$ 表示节点 $u$ 的子树内, $u$ 的状态为开或关, 子树内有几个路径端点的情况下让子树内全亮的最短路程, 转移时:

路径拼接时可能会重复走某个点
若走出时发现某个 $v$ 并没有被关闭, 那么就在走到 $v$ 后再走回 $v$ 再走回 $u$ , 会把 $u\to v$ 走两遍.

T2

3d空间内有 $n$ 个块, 每个块都是一个长方体, 第 $i$ 块对角 $(x, y, z)$ 坐标分别为 $(i, 0, 0)$ , $(i+1, a_i, b_i)$ , 要求在这些块内的空间内找到一个最大的长方体

$n\le 2\times 10^5, a_i, b_i\le 10^6$

考虑按 $x$ 分治它, 现在分为两半, 我们选择的长方体左右端点到中间的距离分别为 $l, r$ . 讨论 $a$ , $b$ 最后被哪里限制住, 也就是 $a$ , $b$ 的最小值在哪里取到, 考虑若两者在同一侧取到, 则显然另一边越长越好, $l$ 向左移动的过程 $r$ 显然单调右移, 可以双指针扫出来. 另一种情况为两个限制在两边, 设 $maxa$ 在左边而 $maxb$ 在右边, 另一种情况同理, 则贡献为 $(r-l+1)\cdot maxa\cdot maxb$ , 固定 $r$ , 则 $maxb\cdot (r-l+1)$ 可以看做关于 $l$ 的一次函数, 所以我们扫一遍处理出所有右侧对应的一次函数, 再扫一遍左边对每个放在李超树求最大值即可.

此时复杂度为 $n\log^3 n$ , 考虑取最值的一次函数形成凸壳, 就可以线段树维护凸壳做. 复杂度不变, 但注意到当我们 $l$ 单调递增的时候直线是单调左移的就解决了.

T3

给定长 $n$ 的序列 ${a_i}$ , 代表一棵点数 $\dfrac{(n+1)(n+2)}{2}$ 的树, 其中第 $i$ 层有 $i$ 个节点, 第 $a_i$ 个节点有2个儿子, 其他节点均只有一个儿子, 再按层标号形成的树.

如图为序列{1, 2, 6}.

$q$ 次询问两个点 $x, y$ 的 lca.

$n\le 2\times 10^5$

考虑这个树的性质, 感觉主要有两个, 一个是总分支数是 $n$ , 另一个是深度是 $n$ .

可以看成每个点 $a_i$ 引出一个新的分支, 而其他的都是垂直向下的, 发现我们只要能找出一个点在哪个分支就可以算 lca, 因为总分支数是没问题的, 同时可以把所有分支连成一棵树.

我们找父亲, 儿子是简单的, 就是减去和加上层数, 同时注意对于层 $i$ 所有大于 $a_i$ 的点再找儿子时还要再加一, 这使得我们跨多层找父亲儿子十分困难.

于是利用深度为 $n$ 的性质, 发现我们可以把这个树看成一开始只有根节点1, 每次 $a_i$ 分裂出来一个的结构, 所以用一个可持久化线段树就能维护每一层的形态(插入一个点而已), 但插入一个点后面点的编号怎么变啥的处理复杂, 所以反过来, 最后一层的形态是确定的, 只要从后往前每次删一个点过程容易维护. 而且每个点对应的分支就是这一层时它这个点对应的叶子(由哪个叶子演变而来)的编号.

于是就做完了.

考场上想到做法然而只剩半小时.

Day2

比赛题

T1 Block

给定长度为 $n$ 的序列和 $m$ 个询问, 以B为大小分块后, 若一个询问端点在同一块代价为区间长度, 否则为不算两端点中间的块数加上两端点到各自块端点的距离, 就像分块一样.
$n\le 10^6$ . 提示: 相信自己.

提示让ljc坚信这是个 $\sqrt n$ 的卡常题. 这题方法很多.

法1

首先容易想到一个简单的数论分块做法, 是过不了的, 就是你写出式子后询问 $(l, r)$ 对块大 $B$ 的贡献会化成

$$
\begin{aligned}
&\lfloor\dfrac{r-1}{B}\rfloor-\lfloor\dfrac{l-1}{B}\rfloor+(B-l+B\cdot \lfloor\dfrac{l-1}{B}\rfloor)+(r-B\cdot \lfloor\dfrac{r-1}{B}\rfloor)
\end{aligned}
$$

之类的, 然后拆拆式子, 最后注意要单独给 $l, r$ 在同一块的减去 $B$ . 于是能得到一个绝妙的TLE做法.

wmy神仙对着这个搞出了一个转调和级数的做法, 然而我现在还不会. todo

法2

首先经典调和级数结论告诉我们不同的块个数为 $O(n\log n)$ , 那么考虑对每一块求所有询问对它的贡献. 发现我们只要对两端点都在块内, 都在块外, 一内一外进行讨论就可以把一个询问拆成11个3side静态二维矩形数点问题获得大常数TLE, 令人望而生畏, 但真的有人写了3种不同扫描线的做法啊! . (至于是不是分和数论分块一样多? )

然而有一种更简单的做法, 考虑对每一个块长的答案先加上所有询问区间长度总和, 如果它跨过一块, 就再给贡献减去 $B-1$ . 那么我们只要统计两端点一外一内的即可. 一个树状数组即可.

T2 sbt

给一个长 $n$ 的序列和常数 $k$ , 有 $q$ 次单点修改, 要求在未修改时和每次修改后求出对于序列中所有长度为 $k$ 的滑动窗口中最大值与不严格次大值的和最大为多少.
$n\le 10^6$ , $n\le 10^5$ .

首先你考虑维护滑动窗口没前途的话我们可以套路的枚举每个数是最大值或次大值, 那么此时答案就是它前后 $k$ 个不算自己的最大值和次大值之和, 再考虑有了单点修改后, 如果把数改大只要直接再对修改后的值求一下, 但改小不会做, 于是套路的上一个线段树分治, 看起来2log冲不过去, 但实际上因为修改了的数只有 $q$ 个, 也就是说剩下的数都直接放到了根节点上了, 于是复杂度其实是 $q\log n\log q+n\log n$ .

T3 ntt

见鬼数学题todo.

Day3

比赛题

讲课

LOJ2764 JOIOI塔

给定一个字符串由J, O, I组成, 求能找出多少个不相交的’IOI’, ‘JOI’子序列. $n\le 10^6$

二分答案, 贪心过程中如果碰到J或O就贪心的往已经有的接, 如果已经有的接不上就直接扔, 然后碰到I看当前的子序列个数够不够二分的答案, 不够就作为IOI的I, 否则作为后面的I接上去.

虽说tyy说不二分的都是假的, 但qyc似乎确实从loj上找到了线性的解法啊?

LOJ3666 沙堡 2

给定 $W\times H$ 网格, 每个格子高度为 $A_{i, j}$ , 高度互不相同, 每次只能走到不高于当前格子的相邻格子, 问恰好覆盖一个子矩形的方案数.
$H\cdot W\le 5\times 10^4$

由于高度互不相同, 显然对于一个子矩形, 恰好覆盖它的方案是唯一的. 而能不能成等价于把其中的数排序后相邻两项在图上相邻.

设与当前格子相邻的权值比当前格子大的最小的为后继, 比它小的最大的为它的前驱, 若两个相邻的格子相互为前驱后继, 那么由前驱向其后继连有向边, 此时如果一个矩形能成当且仅当至多一个格子出度为0, 预处理相邻两个格子间是否右边, 注意这里在子矩形边界上的要单独处理.

然后考虑dp, 如果确定了矩阵的上下位置, 那么可以设 $f_{i, 0/1, 0/1, 0/1}$ 表示到 $i$ 列, 第 $i$ , $i-1$ , $i+1$ 列选不选的方案数, 转移可以枚举下一列选还是不选.

因为 $H\cdot W\le 5\times 10^4$ , 所以短的一边一定少于 $\sqrt n$ , 所以只要我们把 $H$ 搞成短边就可以直接做了.

UOJ578 校验码

UOJ280 题目难度提升

给定数列, 求一个顺序, 使得每次按顺序加入一个数后数列中位数不降, 要求字典序最大的方案. 这里偶数个的中位数为中间两个取平均 $n\le 10^5$

为了让中位数不降, 我们要加一个大的一个小的这样, 所以在未加入的数里至少要有一半的比中位数小, 那么考虑:

我们一开始加的必然是全局最小值.
如果当前加入了偶数个, 那么接下来加的数一定要比当前中位数小. 也就是当前最小值.
如果加入了奇数个, 那么只要满足接下来的数和中位数取平均后比原来的大, 可以二分出来.

注意我们这个过程, 因为一开始是全局最小值, 再归纳的看这个过程, 发现每次小于中位数的其实只有一个也就是当前最小值.

cf16-final J Neue Spiel

小 T 有一张 $n\times n$ 的棋盘和很多硬币. 他想把硬币都放到棋盘上, 使得每个格子上恰好有一枚硬币.
每次操作, 小 T 会将一枚硬币放在这些在棋盘外面且与某个格子相邻的位置, 之后按照往棋盘内的方向推硬币, 直到该枚硬币恰好位于格子内为止. 若格子上已经有另外一枚硬币, 则那枚硬币也会被往里推一个格子. 如果有硬币被推出棋盘外则视为失败.
小 T 对每个棋盘外面的位置 $U_i, D_i, L_i, R_i$ 都分别写上了一个非负整数 $U_i, D_i, L_i, R_i$ , 表示在这个位置进行操作的次数. 但在写完数之后, 小 T 发现他并不能很快找出一组合法的方案, 你能帮他找到吗?
无解输出 NO.
$1\le n \le 300$ .

考虑这个挤的过程等价于我们找到第一个不空的位置放上. 那么我们可以先考虑每个硬币是从哪个边界上过来的再去构造方案. 那么每个硬币从哪来的这件事可以简单网络流经典算法, 而安排顺序则比较困难, 每个硬币放的时候要求在它到它的边缘间的所有硬币都已经放上了, 那么如果 $D_i=R_i=0$ 我们可以随便拓扑排序之类的.

但一般情况下, 这种依赖关系会成环, 但如果我们找到这样一个环, 只要把每个环上的硬币对应的边缘换成依赖环上后继(下一个)对应的边缘, 转一下就能把它消掉. 如图, 箭头为从哪条边过来.

考虑如何扫环, $n^2$ 个点和边上找环大概是 $n^4$ 之类的, 这里有一种更好的方式: 我们从某个硬币开始dfs, 如果遍历了它所有依赖仍然没有环那就把处理完这个点了, 否则我们就在找到环后立刻把环消了, 这样的好处时我们花费的总代价是 $n^2+\sum len$ , $len$ 为环长, 而 $\sum len\le n^3$ , 于是就解决了.

UOJ431 time map

给一棵广义线段树, 它维护长 $n$ 的序列 $a$ . 节点 $i$ 的值 $val_i$ 为其所管辖的区间与, 支持:

区间与 $x$

区间或 $x$

区间异或 $x$

询问从 $l, r$ 开始走, 若 $popcount(val_i)&1$ 则走左儿子否则走右儿子, 走到的这条链的权值和.
$n\le 10^6, v\le 10^5$

首先由于区间与的性质, 从任何一个节点出发走都只有 $\log v$ 种不同的取值, 启示我们利用这个性质, 每次走的时候走一条链, 且走的方向是相同的, 那如果我们建一棵正常线段树维护区间与就可以二分倍增找到一段, 而区间与, 或, 异或可以打标记, 标记维护子树所有点都被 $((x \mathrm{and} a) \mathrm{or} b) \mathrm{xor} c$ 的 $a, b, c$ 即可. 由于要二分 $\log$ 次, 每次判定时要 $\log$ 查询区间与所以复杂度 $n\log^3 n$ .

然后考虑由于每次走一条链的过程中有一个端点是不动的, 可以先在线段树上二分到与不变的区间, 之后在链上倍增就是 $O(1)$ 的了, 复杂度 $n\log ^2 n$ .

UOJ425 strings

给定长 $n$ 的 $q$ 个模式串, 每个位置可以是01? , 表示匹配0, 1或者任意字符, 现在求有多少长 $n$ 的字符串可以至少匹配其中的一个.
$n\le 30, q\le 100$

大力暴力, 发现我们至少枚举前26位都爆炸不了. 于是先枚举前24位, 对每场考试预处理一个bitset表示后6位为 $x$ 是否可行, 那么只要直接把前面匹配的字符串对应的bitset并起来, 把对应的bitset并起来求popcount即可. 复杂度 $O(2^(n-6)\dfrac{q}{w})$ .

接着优化, 现在的问题是每次枚举后要对所有考试分别check, 我们维护一个bitset表示当前还有哪些考试是对的, 那么填01时可以直接与上一个什么东西, 接下来要根据这个bitset判断后6位, 方法是每 $\log$ 个分块, 处理每块内的所有可能方案对应的或即可.

UOJ327 去月球

给定一个长 $n$ 序列, 每次询问对于区间 $[l, r]$ 中的数, 若每次可以删除相邻相等的两个数, 最多删多少次.
$n\le 10^5, m\le 2\times 10^6$ . 强制在线.

这玩意居然可差分? !

$[l, r]$ 的答案为 $reverse([1, l-1])*[1, r]-(l-1)$ , 这里乘法指串接起来的答案, 因为把前面那段反过来后就自己和自己消掉了.

而这个等价于问两个前缀的lcp, 于是插到trie上去求lca, 建立trie很简单因为每次相对于上一次插入的地方只可能回到父亲或走到一个儿子.

最后在trie上lca, 复杂度是1log或线性.

Day4

比赛题

T1

给定 $n$ 个点 $(x, y)$ , 距离为曼哈顿距离, 求平面最大生成树.
$n\le 2\times 10^6$ . $\vert x_i \vert , \vert y_i \vert \le 10^8$ .

首先因为是最大生成树, 而对于所有点, 其最远点一定是四个点中的一个, 直接做不好考虑的话可以考虑转化成切比雪夫距离, 那么离每个点最远的就是最上面最下面最左边最右边的四个点中的一个, 如果有多个同为最大任选一个是不劣的, 于是有一种构造方法是每个点只和这四个点连边, 这四个点间两两连边跑 Kruskal.

然而还是较难通过, 考虑Brovka, 看起来仍然是 $n\log n$ , 但实际上如果写了发现其实只会跑两轮, 因为每个点都向那四个点连边, 所以一轮过后其实只剩最多两个连通块.

T2

首先看出是dp, b序列可以看成大小限制, 根据大小关系就可以建出一棵大根笛卡尔树, 这里一定是一棵树在于:

保证有解的偏序关系不可能成环.
对于一条偏序链, 有用的其实是那个最长路, 所以有用的边是以每个点结尾的最长路. 只保留这些边就是树了.

于是在这棵树上dp, 设 $f_{i, j}$ 表示 $i$ 子树根节点为 $j$ 的方案数. 利用前缀和复杂度为 $O(nm)$

此外, 注意到答案是关于 $m$ 的 $O(n)$ 次多项式, 所以再拉插可以做到 $n^2$ .

T3

考虑建出整个字符串的后缀自动机, 那么考虑成为重要节点的标准, 在建出后缀树后:

必然是后缀自动机某节点代表的最长的, 显然.
存在两个以上非空child的一定重要, 因为它child就是包含它的, 每个child出现至少一次所以它的出现次数一定多余自己两个child
只有一个非空child, 只有当它是全局的后缀时才重要, 否则它的出现次数等于孩子的出现次数, 就不变.
没有child, 一定重要, 因为显然只有整个字符串没有child.

我们每次加入一个字符就重判一遍就有了 $n^2$ .

如果数据随机, 那么只要长度超过 $O(\log n)$ , 大概率只会出现一次, 会直接被全串干掉, 所以只维护出现次数超过一次的 $O(n)$ .

对于第一种情况, 我们发现每个节点只会从不重要变成重要一次, 可以直接开个变量维护, 也就是在设置其link的时候顺便看父亲.

接下来考虑正解, 考虑维护parent tree的结构, 考虑新加节点的时候:

我们新建了一个叶子
可能会在clone过程中, 在一个点和它父亲间插入一个新点
反转儿子状态(儿子数 $0\to 1, 1\to 2$ )
查询一个节点到根的路径上1的个数

可以LCT简单解决.

然而LCT跑1e6很困难, 考虑树的形态只有clone时才会变化, 且是把子树深度加1, 看能不能用常数更小的数据结构干, 我们将所有操作反过来做, 这样的好处是我们不需要加点, 而删点只要把这里的点设为0即可, 这样是单点修改区间查询的树剖, 发现我们只在乎从整串跳parent跳到根这条链, 于是就做完了.