jiangly的博客

博客

The 3rd Universal Cup. Stage 10: West Lake 题解

2024-10-04 22:24:42 By jiangly

A. Italian Cuisine

假设最后切的块是 pipj,其中菠萝在直线 pipj 的左侧。

枚举 i,则 j 应该在满足菠萝在直线 pipj 左侧的前提下尽可能大(我们认为 pn+i=pi,所以始终有 j>i)。这个 j 要满足的条件具有单调性,并且当 i 增大时,最大的 j 也不降,所以可以用双指针维护这个过程。

算面积时只需求每条边的叉积的和。

时间复杂度 O(n)

B. Generated String

考虑如果给的都是直接的串而不是一些子串的拼接怎么做。对所有串建立 Trie,则 st 的前缀当且仅当 ts 的子树中,在 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(区间以外的部分随便用 xy 填充,不会有贡献)。答案有三种可能:

  • 答案是 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 时,两个区间都往两侧扩展 vt
  • 当在位置 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= (所有左子树中叶子个数的和)。
  • 如果 kL,则在所有左子树中找到第 L 个叶子所在的子树,然后递归。
  • 如果 k=L+1,则第 k 个叶子就是这条链的底端。
  • 如果 k>L+1,则在所有右子树中找到(自底向上)第 L 个叶子所在的子树,然后递归找其中的第 kL1 个叶子。

找到叶子之后,我们需要进行 access 操作,具体步骤如下:

  • 我们不对每条链记录它的父亲(因为之后会有翻转操作,父亲没法维护),而是在找叶子的过程中,记录经过的路径,并且找到每条链切换时要接上的父亲。也就是找到链上第 k 个有左/右子树的结点。
  • 自底向上,如果要把 x 接上 y,首先要将 y 和其目前的儿子 z 断开。在这同时需要将左/右儿子同时分成两部分,对应断开之后的两条链,并把 z 加入左/右儿子的列表(在这里更新 z 的子树叶子数)。
  • xy 所在链的左/右儿子列表中删除,将 yx 所在链的左/右儿子列表拼接,并将 x 接到 y 上。

经过上面的两个步骤我们得到了一条链,询问的答案就是链的左子树的个数。下一步就是将链的左子树翻转,这又分成两个部分:

  • 首先是将左儿子的列表整体翻转,这可以直接通过打翻转标记实现。
  • 对每个左/右儿子,将其子树镜像,这对应着交换它所在链的左/右儿子列表,并且镜像它的所有左/右儿子,同时维护的信息(有多少个点有左/右子树)也需要交换。这里我们采用对链整体打标记,在找叶子的过程中处理标记。

注意翻转左儿子列表的操作会较大影响树的形态,但是 LCT 的 access 次数的分析并不会失效(每次操作只会影响 O(logn) 条轻边)。splay 的复杂度不再能沿用 LCT 的证明,但至少有上界 O(logn),总复杂度不超过 O((n+q)log2n),并且实际表现其实比较快。

F. Triangle

设三个串中字典序最大的为 x,其余两个为 y,z,则显然有 xy>zxz>y,因此只需要满足 yz>xzy>x。我们可以假设 yzzy,这等价于 yz,因此只是添加了一维偏序的限制。

现在要求 yz>x,而我们限制了 yx,因此 y 一定是 x 的一个前缀。我们可以枚举 x,y,总的枚举次数不会超过总串长。记 x 去掉前缀 y 后的串为 y1x,则 z 只需要满足以下两个条件:

  • zy
  • xz>y1x

对于后者,可以直接对所有串后缀排序。

对于前者我们需要将所有串按照这个规则排序。注意这里直接比较 yzzy 的大小来排序,总的复杂度可以达到 Ω(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,它们的邻居相同,则可以删除其中的一个和其邻边,而不改变答案
    • 证明:设原图为 Ga,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 会互相连边。如果 uv 还有出边,会和 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=cx+l\le b_i,那么新的距离是 (i,x+l)

否则,我们需要找到最小的 j>i,满足 a_j=cb_j\ge l,新的距离就是 (j,l)。找这个 j 可以用线段树或者二分 RMQ。

总时间复杂度 O((n+m+k)\log (n+m+k))

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。