A. Italian Cuisine
假设最后切的块是 pi 到 pj,其中菠萝在直线 pipj 的左侧。
枚举 i,则 j 应该在满足菠萝在直线 pipj 左侧的前提下尽可能大(我们认为 pn+i=pi,所以始终有 j>i)。这个 j 要满足的条件具有单调性,并且当 i 增大时,最大的 j 也不降,所以可以用双指针维护这个过程。
算面积时只需求每条边的叉积的和。
时间复杂度 O(n)。
B. Generated String
考虑如果给的都是直接的串而不是一些子串的拼接怎么做。对所有串建立 Trie,则 s 是 t 的前缀当且仅当 t 在 s 的子树中,在 DFS 序上就是 t 在一个区间内。对反串建立 Trie 就可以解决后缀。因此询问给定前缀后缀的串的个数实际上就是一个二维偏序,加上时间维度之后就是三维偏序,可以在 O(nlog2n) 时间内解决。
现在变成给一个子串的拼接,唯一的区别就是没法直接建 Trie。只要我们能够把 Trie 建出来,后面的做法没有区别。事实上建立 Trie 也并不复杂,只需要将所有串按字典序排列,然后求出相邻两个的 LCP 长度,然后类似建虚树的方法,就能建出这些串的压缩 Trie。注意这里排序的时候,如果只是用后缀数组求 LCP 跳过一段,比较复杂度是 O(k+l),其中 k,l 分别是两个字符串的段数,则复杂度仍然可能达到 Ω(n2)。一个解决方法是,使用归并排序,并且递归过程中也计算相邻串的 LCP,然后在归并的过程中,利用已经计算的 LCP 避免重新从头开始比较。另一个解决方法是按照段数从小到大插入排序。在预处理后缀数组,支持 O(1) 求 LCP 的前提下,两种方法的复杂度都是 O(∑kilogn)。
总时间复杂度 O(nlogn+qlog2q+∑kilogq)。
C. Permutation
考虑分治,每次将数列分成两半,然后确定每个数在哪一半。之后递归处理两个区间。
由于这道题的交互器是非适应性的,即排列是预先确定的,所以可以采用随机化。考虑将所有数 shuffle,然后每次询问两个数 x,y,前一半是 x,后一半是 y(区间以外的部分随便用 x 或 y 填充,不会有贡献)。答案有三种可能:
- 答案是 0,说明 x 在后一半,y 在前一半。
- 答案是 1,说明 x,y 在同一侧,但不知道是哪一侧。
- 答案是 2,说明 x 在前一半,y 在后一半。
对于答案是 0,2 的情况,能够直接确定两个数。对于答案是 1 的情况,可以删掉 x,y 的其中一个,用另一个继续进行询问。
分析一下询问次数,因为排列随机,近似可以看成每个数均匀独立在左右之间随机。每次询问有 1/2 的概率确定 2 个数,1/2 的概率确定 1 个数,因此每次期望确定 3/2 个数,故期望询问次数约为 2n/3。
因此总的询问次数大约为 23nlogn。加上一些剪枝(例如当一侧已经满时不继续询问)后,实测 n=1000 时大约需要 6000 次询问。
D. Collect the Coins
二分答案,可以在线性时间内判断能否满足。
考虑按照时间从前往后,维护每个时刻,两个机器人可能的位置集合。事实上,一定可以表示成其中一个机器人在 [l1,r1],另一个在 [l2,r2](不区分两个机器人)。
初始时两个区间都是 [1,109]。对每个事件进行模拟:
- 当时间前进 t 时,两个区间都往两侧扩展 v⋅t。
- 当在位置 c 出现一个硬币时:
- 如果没有区间包含 c,则不可能。
- 如果有一个区间包含 c,则对应区间变成 [c,c]。
- 如果两个区间都包含 c,则任何一个机器人都可以收集硬币,而另一个机器人可能的位置是 [l1,r1]∪[l2,r2]。因为两个区间有交,因此结果还是一个区间。
时间复杂度 O(nlogC)。
E. Normal Friends
不妨设线段树大小为 n+1,且根的分割点为 n。这样做的好处是,对于区间 [1,x] 的翻转操作等价于找到 DFS 序第 x+1 个叶子,然后将其到根的路径上的所有左子树整体翻转(最高的变到最低的,依此类推),并且内部所有左右儿子交换。
这样的操作实际上可以用 LCT 来完成。首先考虑怎么找到这条链,分成两步,分别是找到 DFS 第 x+1 个叶子和对其进行 access 操作。
第一步需要在每条实链上用 splay 额外维护所有点的左/右子树(按照深度),以及哪些点有左/右儿子(当然是通过维护子树内有多少个点有左/右儿子)。这里我们假设每条实链的底端都是叶子。找 DFS 第 k 个叶子的步骤如下:
- 令 L= (所有左子树中叶子个数的和)。
- 如果 k≤L,则在所有左子树中找到第 L 个叶子所在的子树,然后递归。
- 如果 k=L+1,则第 k 个叶子就是这条链的底端。
- 如果 k>L+1,则在所有右子树中找到(自底向上)第 L 个叶子所在的子树,然后递归找其中的第 k−L−1 个叶子。
找到叶子之后,我们需要进行 access 操作,具体步骤如下:
- 我们不对每条链记录它的父亲(因为之后会有翻转操作,父亲没法维护),而是在找叶子的过程中,记录经过的路径,并且找到每条链切换时要接上的父亲。也就是找到链上第 k′ 个有左/右子树的结点。
- 自底向上,如果要把 x 接上 y,首先要将 y 和其目前的儿子 z 断开。在这同时需要将左/右儿子同时分成两部分,对应断开之后的两条链,并把 z 加入左/右儿子的列表(在这里更新 z 的子树叶子数)。
- 将 x 从 y 所在链的左/右儿子列表中删除,将 y 和 x 所在链的左/右儿子列表拼接,并将 x 接到 y 上。
经过上面的两个步骤我们得到了一条链,询问的答案就是链的左子树的个数。下一步就是将链的左子树翻转,这又分成两个部分:
- 首先是将左儿子的列表整体翻转,这可以直接通过打翻转标记实现。
- 对每个左/右儿子,将其子树镜像,这对应着交换它所在链的左/右儿子列表,并且镜像它的所有左/右儿子,同时维护的信息(有多少个点有左/右子树)也需要交换。这里我们采用对链整体打标记,在找叶子的过程中处理标记。
注意翻转左儿子列表的操作会较大影响树的形态,但是 LCT 的 access 次数的分析并不会失效(每次操作只会影响 O(logn) 条轻边)。splay 的复杂度不再能沿用 LCT 的证明,但至少有上界 O(logn),总复杂度不超过 O((n+q)log2n),并且实际表现其实比较快。
F. Triangle
设三个串中字典序最大的为 x,其余两个为 y,z,则显然有 xy>z 和 xz>y,因此只需要满足 yz>x 或 zy>x。我们可以假设 yz≥zy,这等价于 y∞≥z∞,因此只是添加了一维偏序的限制。
现在要求 yz>x,而我们限制了 y≤x,因此 y 一定是 x 的一个前缀。我们可以枚举 x,y,总的枚举次数不会超过总串长。记 x 去掉前缀 y 后的串为 y−1x,则 z 只需要满足以下两个条件:
- z∞≤y∞。
- x≥z>y−1x。
对于后者,可以直接对所有串后缀排序。
对于前者我们需要将所有串按照这个规则排序。注意这里直接比较 yz 和 zy 的大小来排序,总的复杂度可以达到 Ω(n2)。一个复杂度正确的方法是,先判断两个串是否互为前缀,如果不是则可以直接比较,否则通过预处理的 z-函数/后缀数组,可以 O(1) 求出 LCP 然后比较。这样单次比较复杂度是 O(min 而不是 O(|y|+|z|),总复杂度就是正确的 O(\sum|S_i|\log n)。
处理完这两个限制之后,就变成了二维偏序,可以在 O(n\log n) 时间内解决。
需要注意的是,输入中会出现相同的串,所以我们需要记录每个串的出现次数,并且处理好三个串有相同的情况。
总时间复杂度 O(\sum |S_i|\log n)。
G. Stop the Castle 2
将问题转化为放 m-k 个障碍,隔开尽可能多可以互相攻击的车。
只有在一行或者一列相邻的车才能互相攻击,这样的车只有 O(n) 对。在它们之间的任意位置摆放障碍就能防止它们互相攻击。设有 c 对能互相攻击的车之间能摆放障碍。
有的障碍可以阻挡两对车互相攻击(行列各一对),显然我们需要让这样的障碍尽可能多。假设我们能摆放 x 个障碍,每个障碍都能阻挡互不相同的两对车,那么放 m-k 个障碍就能阻挡 \min\{c,m-k+\min\{m-k,x\}\} 对互相攻击的车。
把互相攻击的车看成点,如果一个障碍能阻挡两对车,就在对应的两个点之间连边,会形成一个二分图。x 就是这张图的最大匹配。可以用 Dinic 算法或 Hopcroft-Karp 算法在 O(m\sqrt n) 的时间中求解。
H. Intersection of Paths
如果 k=1,则所求的就是树的直径。当 k 任意时,要求的其实就是只考虑两侧点数都不少于 k 的边时树的直径。
注意所有询问互不相关,因此我们可以将询问按照 k 从大到小的顺序重新排列。当 k 减小时,会陆续加入边,这些边形成一个连通块,如果询问没有修改时,可以直接维护这个连通块的直径。当询问有修改
时有不同的做法,这里介绍其中的两个:
- 由于树的边权几乎不变,我们将询问中修改的边删除,分成两个连通块,分别求出两个连通块的直径,然后合并即可(整棵树的直径端点一定在这两条直径的端点中)。需要支持加点和求子树的直径,在按 DFS 序建立的线段树上合并直径即可。需要 O(1) LCA。
- 直接使用修改边权的动态直径做法。直径等于在欧拉序上依次选 3 个点(可以相同)u,v,w,\mathrm{dep}_u-2\mathrm{dep}_v+\mathrm{dep}_w 的最大值。修改边权对欧拉序上深度的影响就是区间加。用线段树维护这个式子每一段的最大值即可。
时间复杂度 O((n+q)\log n)。
I. Find Yourself
首先注意到,任意的树都是能够确定的:
- 因为树是二分图,所以我们可以黑白染色,先确定怪物所在点的颜色,不妨设和根相同(否则走一步)。
- 假设怪物目前在 x 的子树中且与 x 颜色相同的一个结点(初始 x 为根)。如果 x 是叶子则游戏结束。否则,重复以下过程,直到 x 只剩下一棵子树:
- 询问 x,如果怪物在 x,那么游戏结束。否则,怪物只能走到 x 的子树中,与 x 颜色不同的结点。此时询问 x 的一棵子树,如果怪物不在子树中,就可以删除这棵子树,否则可以删除所有其他子树。此时怪物又可能位于 x 的子树中,未被删除的,和 x 颜色相同的任意结点。
- 当只剩下一棵子树 y 时,询问 x,如果怪物在 x,那么游戏结束。否则令 x\gets y,重复以上过程。
接下来考虑有环的情况。首先要注意到,如果图 H 是不能确定的,则任意包含子图 H 的图都是不能确定的。结合样例和打表观察,可以发现,以下的图都是不能确定的:
- 大小不为 4 的环。
- 四元环,每个点都都和其他点有边。
- 四元环,相邻两个点分别连有长度为 2 的链。
- 四元环,相邻三个点依次连有长度为 2,1,2 的链。
此时可以看出,能确定的图的每一个点双都应该是四元环,或是多条长度为 2、起点终点相同的路径并起来的“纺锤”图。为了进一步地简化图的结构,我们还可以观察到如下性质:
- 如果存在两个二度点 a,b,它们的邻居相同,则可以删除其中的一个和其邻边,而不改变答案。
- 证明:设原图为 G,a,b 的邻居都是 c,d,删掉 b 和其邻边之后的图为 G'。显然如果 G 可以确定,则 G' 可以确定。反过来,如果 G' 可以确定,则使用相同的策略,可以在某一次询问后,确定怪物在 a,b 其中的一个,然后怪物走一步之后只可能在 c,d,因此再询问一下 c 即可确定怪物的位置。
经过上述变换之后,可以发现,能确定的图的每个点双都只能是四元环,且四元环不能有两个点都连有长度为 2 的链,也不能四个点都和其他点有边。
事实上,上述必要条件也是充分的。
证明:满足上述条件的图,一定存在一个点,将这个点作为根时,每个四元环除了根以外的三个点中,至多有两个点连接了一个或多个叶子,另一个点没有和环外的点连边。设环上的点按顺序为 a,b,c,d,其中 a 是根。我们可以先利用树的做法,将问题缩小到在 a 的这个子树内确定怪物的位置。讨论两种情况:
- b,d 分别连有叶子 b',d'(可能多于一个)。先询问 a,如果不在 a,则下一步只可能在 b,d,再询问 b 即可确定。
b,c 分别连有叶子 b',c'(可能多于一个)。先询问 a,如果不在 a,则下一步只可能在 b,d,c'。再询问 b,如果不在 b,则下一步只可能在 a,c,再询问 a 即可确定。
因此满足上述条件的图都能够确定。
图的变换和判断上述条件都可以在 O(n+m) 时间内完成,因此整个题可以在 O(n+m) 时间内解决。
J. Sheriruth
如果一个点有两条出边 u,v,则 u,v 会互相连边。如果 u 或 v 还有出边,会和 u,v 整个连成一个团。以此类推,u,v 可以到达的点都会形成一个团。不断合并这些团,最后整张图的每个连通块只有以下几种可能:
- 内向树。
- 内向基环树。
- 一个团,还有若干内向树,每棵树的根连向了团中的若干个点。
内向树的情况只需要判断祖先后代关系。内向基环树的情况还需要判断点在环上。
大小为 s 的团的方案数就是 \sum_{i=0}^{s-2}(s-2)^{\underline i}。如果是从树根走到团上,要讨论走上来的点是否直接是 v,如果是则只有 1 种方案。这个式子只需要对每个团单独计算,大小总和不超过 n。
总时间复杂度 O((n+m+q)\log n),\log n 在于排序和二分判断是否有某一条边,也可以做到线性。
K. Palindromic Polygon
首先将点复制一遍,变成 2n 个点的序列。相当于可以选一个子序列 i_1< i_2< \cdots< i_k,要求 i_k-i_1< n,且 f_{i_1},f_{i_2},\ldots,f_{i_k} 是回文序列,最大化凸包的面积。
考虑从两侧向中间 DP,设 f(l,r) 是当前回文序列中对应位置是 l,r 的最大面积。转移需要枚举 i,j,满足 l< i\le j< r,f_i=f_j,然后转移到 f(i,j)。这样做时间复杂度是 O(n^4)。
注意到如果 (l,i) 和 (j,r) 之间都有等于 f_i 的点,那么把这两个点选上,面积一定不会变小(相当于凸包上多了两个三角形),因此有用的转移都满足 i 是区间中第一个等于 f_i 的点或 j 是区间中最后一个等于 f_i 的点。这样对于每个区间有用的转移减少到了 O(r-l) 个,时间复杂度 O(n^3)。
L. Cosmic Travel
考虑查 l=r 时如何查询。对所有 a_i 建立 Trie,然后从根开始,如果 l 的对应位为 1 则交换了两棵子树,然后如果 k\le (左子树大小),递归左子树,否则递归右子树。
查询一个区间 [l,r] 时,类似线段树的方式,按对应位分成两个区间,分别递归。我们只需要在 [l,r] 恰好是一个完整的区间时快速回答。即对于每棵子树,对每个 1\le k\le (子树大小),预处理对 j\in [0,2^d),a_i\oplus j 的第 k 小的和,其中 d 是子树的位数。需要预处理的值,每个深度是 O(n) 个,因此总共只有 O(n\log C) 个。每个需要预处理的值都可以通过其孩子的值在 O(1) 时间内得到。
总时间复杂度 O((n+q)\log C)。
M. The Quest for El Dorado
考虑 Dijkstra,将每个点的距离定义为 (i,x),即最早在第 i 轮才能到达,并且第 i 轮至少走了 x 的距离。显然我们希望 i 尽可能小,并且 i 相同的情况下 x 尽可能小。
对于每条边 (v,c,l),如果 a_i=c 且 x+l\le b_i,那么新的距离是 (i,x+l)。
否则,我们需要找到最小的 j>i,满足 a_j=c 且 b_j\ge l,新的距离就是 (j,l)。找这个 j 可以用线段树或者二分 RMQ。
总时间复杂度 O((n+m+k)\log (n+m+k))。