jiangly的博客

博客

The 3rd Universal Cup. Stage 15: Chengdu 题解

2024-11-07 19:41:12 By jiangly

A. Arrow a Row

一个串能通过操作得到的必要条件包括:

  • > 开头。
  • >>> 结尾
  • 至少有一个 -

而事实上上述条件也是充分的。如下是一个可能的构造:

  • 当目标串不以 ->>> 结尾时,重复操作 (n4,5),这样可以视作删除了最后一个字符。最终目标串一定是以 ->>> 结尾。
  • 枚举 i1n4,如果 si- 则不操作,否则令 ji 之后第一段连续的 - 的结尾位置,操作 (i,ji+4)

操作次数显然不超过 n,时间复杂度也为 O(n)

B. Athlete Welcome Ceremony

先求出有 xaybzc 的好序列,然后做一个三维前缀和,即可在 O(1) 时间内回答询问。

dp(x,y,z,ch) 表示有 xaybzc,且以 ch 结尾的好的前缀个数。因为前缀长度就是 x+y+z,枚举下一个字符即可 O(1) 转移。

时间复杂度 O(n3+Q)

C. Chinese Chess

对状态集合(状态为 (位置,类型))进行搜索,枚举询问的格点,然后根据距离分成若干个子集。实现后可以发现,即使对于全部位置都可行的情况,也只需要 3 步即可确定类型。因此总的搜索节点数不超过 903,如果速度还是很慢,可以考虑打表 3 步的所有决策,这样只需要搜索 2 步以内的情况。搜索的时候可以顺便记录每个状态的决策。

实现时注意每种棋子的移动方式。

D. Closest Derangement

注意到当 pii 时,ni=1|pii|n

n 是偶数时,最小值可以取到 n,且只在排列 2,1,4,3,,n1 取到。

n 是奇数时,根据奇偶性,最小值为 n+1。可以在排列 ,2k+2,2k+3,2k+1,,2k+3,2k+1,2k+2, 取到(前后的部分和偶数时一样,相邻数两两对换)。这样的排列共 n1 个,现在我们要找到 pq1,pq2,,pqn 的字典序第 k 小,只需快速实现比较两个排列,然后调用 nth_element 即可。

比较两个排列 p1,p2 只需找到最小的 i 使得 p1,qip2,qi。注意到对于任意两个不同的好的排列,对应不同的位置一定是一个区间加上边界的 O(1) 个零散点,只需在 q1 上 RMQ,然后暴力统计零散点即可。

时间复杂度 O(nlogn)O(n)

E. Disrupting Communications

要求的是和 uv 的路径相交的连通块数。考虑用总的连通块数减去和 uv 的路径不相交的连通块数。

l=LCA(u,v),则和 uv 的路径不相交的连通块有以下两种:

  • 完全在 l 的子树外部。
  • 完全在 l 的子树内部,且连通块的根不在 uv 的路径上。

f(x),g(x) 分别表示以 x 为根的连通块数和 x 子树内的连通块数,则转移如下: f(x)=ych(x)(1+f(y))g(x)=f(x)+ych(x)g(y) 同理,令 fo(x),go(x) 表示删除 x 的子树,且以 x 的父亲为根的树对应的答案。注意这里计算 fo(x) 不能使用除法(可能会有除以 0 情况),而应该预处理前后缀乘积。

再令 sumf(x)x 到根的路径上的所有点 yf(y) 的和,则答案为 g(1)go(l)g(l)+sumf(u)+sumf(v)2sumf(l)+f(l) 时间复杂度 O(n+qlogn)

F. Double 11

对于一个分组方案,设每组的个数和总和分别为 cisi。要在 mi=1kisi1 的前提下最小化 mi=1ciki,一定有每组的 d(ci/ki)d(kisi) 是相等的,即 ki 正比于 cisi。令 S=mi=1cisi,则 ki=ci/siSmi=1ciki=mi=1cisiS=S2。因此题目所求的答案就是 S

注意到确定每个分组的大小之后,每个系数 ci 就确定了,因此一定是把较小的数分到较大的组。因此我们可以将数组排序,从而每一组一定是一个区间。

考虑排序后的三个区间 (c1,s1),(c2,s2),(c3,s3)s1/c1s2/c2s3/c3)。事实上我们有如下不等式: (c1+c2+c3)(s1+s2+s3)+c2s2(c1+c2)(s1+s2)+(c2+c3)(s2+s3) 一个证明如下:

  • 移项,变为 (c1+c2+c3)(s1+s2+s3)(c1+c2)(s1+s2)(c2+c3)(s2+s3)c2s2
  • c1c1+c2,s1s1+s2,这不会改变作为前提的不等关系,只需证 (c1+c3)(s1+s3)c1s1(c2+c3)(s2+s3)c2s2
  • ai=si/cifi(x)=(ci+x)(si+a3x)x=a3(1+2x)+ai2(1+x)(ai+a3x),则上述不等式等价于 c30f1(x)dxc30f2(x)dx,只需证明对任意 x0 都有 f1(x)f2(x)。再次求导会发现 fi(x)ai(0,a3) 上恒为负,因此命题得证。

因此转移函数是 Monge 的,可以用 WQS 二分 + 决策单调栈在 O(nlognlogϵ1) 的时间内求解。二分时需要注意精度问题,应当需要 long double。

G. Expanding Array

考虑序列中相邻的两个数 x,y。首先通过插入两个数的 XOR 可以得到序列 x,y,xy,x,y,也就是可以无限复制一对相邻的数,使得操作时不会将其消耗掉,因此我们可以把操作看成选中一对数 (x,y),将 (x,xopy)(xopy,y) 加入可能的相邻数的集合。不断重复这样的操作,最后就能得到所有可能出现的相邻数对,自然就能算出可能出现的不同数的个数。

接下来分析一下这样的数对的个数,序列中本身有 n1 对相邻的数,可以看作是独立的。对于相邻的两个数 x,y,因为进行的都是位运算,所以运算得到的任何一个数都可以看作两个位的一个函数 f(x,y),其中 x,y,f(x,y){0,1},且 f(0,0)=0,因此至多有 23=8 种可能。数对的数量自然不会超过 82n。事实上,打表可以发现这 8 种可能的数都是可以产生的,因此直接枚举然后去重即可。

时间复杂度 O(n)O(nlogn)

H. Friendship is Magic

先考虑如何计算一个 f(x)。当分割点向右移时,显然左侧单调递增,右侧单调递减。考虑找到最后一个左侧小于右侧的位置。即把 x 划分为 l,m,r,其中 m 是一个数位,满足 10l+mrl<m10|r|+r,则 f(x)=min{10l+mr,m10|r|+rl}

现在考虑求 f(x) 的和,枚举 m,|r|,然后枚举 f(x) 取哪边,例如取 10l+mr,则有限制 0lL0rR10l+mrl<m10|r|+r10l+mrm10|r|+rl(l,r) 放到平面上,则这些限制都是半平面,且斜率只有 0,,10,1,112 这几种,通过分类讨论可以求出半平面交中所有点的 l,r 之和,进而计算出答案。也可以直接枚举 l 的奇偶性,使得斜率都是整数,然后找到半平面的所有交点并分段,每一段中固定 l 的答案都是关于 l 的二次函数,进而通过插值求总和。

时间复杂度 O(|Σ|log|Σ|n),其中 |Σ|=10,且常数较大,需要精细实现。

I. Good Partitions

k 是好的当且仅当对于任意 i=1,2,,n1,如果 i 不是 k 的倍数,则 ai+1ai

也就是说,令所有满足 ai+1<aii 的 GCD 为 d,如果 d=0k=1,2,,n 都是好的,否则只有 d 的因子是好的。

单点修改会导致一些 i 被插入或删除,可以使用线段树维护 GCD,并且预处理每个数的因子个数来快速回答询问。

时间复杂度 O((n+q)logn)

J. Grand Prix of Ballance

按照题意模拟即可。注意忽略掉非当轮比赛和消息和每位选手第二条及以后的消息。

时间复杂度 O(n+mlogm+q)

K. Magical Set

Ω(x) 表示 x 的质因子数量(计算重数)。设初始集合为 S,结束集合为 T,则总的操作次数不会超过 xSΩ(x)xTΩ(x) 而只要每次恰好除掉一个质因子,这个上界就是能够达到的。而事实上,只要 ST 存在一个完美匹配(xS 匹配 yT 当且仅当 yx),就一定存在达到这个上界的操作序列。具体来说,我们可以通过如下方法构造这个操作序列:

  • 对于 xS,设 M(x) 是完美匹配中和 x 匹配的 T 中的数。如果对于任意 xSM(x)=x,则构造完成。否则找到 M(x)x 的最小的 x,令 px/M(x) 的任意一个质因子,然后重复以下过程:

    • 如果 x/pS,则将 x 变为 x/p,这就完成了一次操作。
    • 如果 x/pS,则说明 M(x/p)=x/pM(x)x/p,我们可以交换 M(x)M(x/p),然后令 x/p 成为我们考虑的 x,重复这个过程。

      由于这个过程中 x 不断变小,因此一定会终止。

因此,问题变成了为 S 中的每个数 x 选择一个因子 y,使得这些因子互不相同,且最小化它们的 Ω(y) 的和。我们找到每个数的所有因子,如果因子超过 n 个,我们事实上只需要保留 Ω(y) 最小的 n 个(即使有 n1 个被其他数选择,还会剩下一个),然后在 xSyT 之间连一条边。

最终我们形成了一个左部 n 个点,右部不超过 n2 个点,不超过 n2 条边的二分图,要找一个左部完美匹配,使得右部选择的点的 Ω(y) 之和最小。可以将右部的所有点按照 Ω(y) 从小到大排列,然后用匈牙利算法寻找匹配。这个算法的正确性来自于拟阵。而只要在未找到匹配时,不初始化算法中的 vis 数组,算法的复杂度就是 O(|M||E|),其中 |M| 是匹配大小,|E| 是边数。

时间复杂度 O(nA+n3)

L. Recover Statistics

只需构造 n=100 个数,前 50 个数为 a,第 5195 个数为 b,第 9699 个数为 c,第 100 个数为 c+1 即可。

M. Two Convex Holes

注意到多边形的投影实际上只是多边形进行了平移和缩放,进行一些坐标变换后可以转化为两个多边形分别做匀速直线运动。进一步可以转化成多边形 P2 的速度为 0P1 的速度为 (0,1)

我们可以将多边形的面积以所有顶点的 x 坐标分成 O(n) 段,则每一段中多边形的上下边界都是线段。进一步容斥成 (上边界 下边界),则只需要计算形如 min{ax+b+t,cx+d} 的函数的积分。这个函数可以按照 t 分成三段,每段都是二次函数。因此面积可以表示成 O(n) 段的分段函数,每一段都是二次函数。再预处理一下每一段的前缀和,询问时只需二分出端点所在的段,然后加上边界部分即可。

时间复杂度 O((n+q)logn)

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{|y|,|z|}) 而不是 O(|y|+|z|),总复杂度就是正确的 O(|Si|logn)

处理完这两个限制之后,就变成了二维偏序,可以在 O(nlogn) 时间内解决。

需要注意的是,输入中会出现相同的串,所以我们需要记录每个串的出现次数,并且处理好三个串有相同的情况。

总时间复杂度 O(|Si|logn)

G. Stop the Castle 2

将问题转化为放 mk 个障碍,隔开尽可能多可以互相攻击的车。

只有在一行或者一列相邻的车才能互相攻击,这样的车只有 O(n) 对。在它们之间的任意位置摆放障碍就能防止它们互相攻击。设有 c 对能互相攻击的车之间能摆放障碍。

有的障碍可以阻挡两对车互相攻击(行列各一对),显然我们需要让这样的障碍尽可能多。假设我们能摆放 x 个障碍,每个障碍都能阻挡互不相同的两对车,那么放 mk 个障碍就能阻挡 min{c,mk+min{mk,x}} 对互相攻击的车。

把互相攻击的车看成点,如果一个障碍能阻挡两对车,就在对应的两个点之间连边,会形成一个二分图。x 就是这张图的最大匹配。可以用 Dinic 算法或 Hopcroft-Karp 算法在 O(mn) 的时间中求解。

H. Intersection of Paths

如果 k=1,则所求的就是树的直径。当 k 任意时,要求的其实就是只考虑两侧点数都不少于 k 的边时树的直径。

注意所有询问互不相关,因此我们可以将询问按照 k 从大到小的顺序重新排列。当 k 减小时,会陆续加入边,这些边形成一个连通块,如果询问没有修改时,可以直接维护这个连通块的直径。当询问有修改

时有不同的做法,这里介绍其中的两个:

  • 由于树的边权几乎不变,我们将询问中修改的边删除,分成两个连通块,分别求出两个连通块的直径,然后合并即可(整棵树的直径端点一定在这两条直径的端点中)。需要支持加点和求子树的直径,在按 DFS 序建立的线段树上合并直径即可。需要 O(1) LCA。
  • 直接使用修改边权的动态直径做法。直径等于在欧拉序上依次选 3 个点(可以相同)u,v,wdepu2depv+depw 的最大值。修改边权对欧拉序上深度的影响就是区间加。用线段树维护这个式子每一段的最大值即可。

时间复杂度 O((n+q)logn)

I. Find Yourself

首先注意到,任意的树都是能够确定的:

  • 因为树是二分图,所以我们可以黑白染色,先确定怪物所在点的颜色,不妨设和根相同(否则走一步)。
  • 假设怪物目前在 x 的子树中且与 x 颜色相同的一个结点(初始 x 为根)。如果 x 是叶子则游戏结束。否则,重复以下过程,直到 x 只剩下一棵子树:
    • 询问 x,如果怪物在 x,那么游戏结束。否则,怪物只能走到 x 的子树中,与 x 颜色不同的结点。此时询问 x 的一棵子树,如果怪物不在子树中,就可以删除这棵子树,否则可以删除所有其他子树。此时怪物又可能位于 x 的子树中,未被删除的,和 x 颜色相同的任意结点。
  • 当只剩下一棵子树 y 时,询问 x,如果怪物在 x,那么游戏结束。否则令 xy,重复以上过程。

接下来考虑有环的情况。首先要注意到,如果图 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 的团的方案数就是 s2i=0(s2)i_。如果是从树根走到团上,要讨论走上来的点是否直接是 v,如果是则只有 1 种方案。这个式子只需要对每个团单独计算,大小总和不超过 n

总时间复杂度 O((n+m+q)logn)logn 在于排序和二分判断是否有某一条边,也可以做到线性。

K. Palindromic Polygon

首先将点复制一遍,变成 2n 个点的序列。相当于可以选一个子序列 i1<i2<<ik,要求 iki1<n,且 fi1,fi2,,fik 是回文序列,最大化凸包的面积。

考虑从两侧向中间 DP,设 f(l,r) 是当前回文序列中对应位置是 l,r 的最大面积。转移需要枚举 i,j,满足 l<ij<r,fi=fj,然后转移到 f(i,j)。这样做时间复杂度是 O(n4)

注意到如果 (l,i)(j,r) 之间都有等于 fi 的点,那么把这两个点选上,面积一定不会变小(相当于凸包上多了两个三角形),因此有用的转移都满足 i 是区间中第一个等于 fi 的点或 j 是区间中最后一个等于 fi 的点。这样对于每个区间有用的转移减少到了 O(rl) 个,时间复杂度 O(n3)

L. Cosmic Travel

考虑查 l=r 时如何查询。对所有 ai 建立 Trie,然后从根开始,如果 l 的对应位为 1 则交换了两棵子树,然后如果 k (左子树大小),递归左子树,否则递归右子树。

查询一个区间 [l,r] 时,类似线段树的方式,按对应位分成两个区间,分别递归。我们只需要在 [l,r] 恰好是一个完整的区间时快速回答。即对于每棵子树,对每个 1k (子树大小),预处理对 j[0,2d)aij 的第 k 小的和,其中 d 是子树的位数。需要预处理的值,每个深度是 O(n) 个,因此总共只有 O(nlogC) 个。每个需要预处理的值都可以通过其孩子的值在 O(1) 时间内得到。

总时间复杂度 O((n+q)logC)

M. The Quest for El Dorado

考虑 Dijkstra,将每个点的距离定义为 (i,x),即最早在第 i 轮才能到达,并且第 i 轮至少走了 x 的距离。显然我们希望 i 尽可能小,并且 i 相同的情况下 x 尽可能小。

对于每条边 (v,c,l),如果 ai=cx+lbi,那么新的距离是 (i,x+l)

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

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

The 3rd Universal Cup. Stage 9: Xi'an 题解

2024-09-10 21:31:13 By jiangly

A. An Easy Geometry Problem

Ai=Aiik2,则对于 ir 是好的半径当且仅当 Ai+rAir=b

用线段树或树状数组维护正反两个方向的哈希值,询问时二分长度然后比较哈希值即可。

时间复杂度 O(n+qlog2n)

B. Counting Multisets

考虑 p(S) 是奇数的条件,设 cnt(x)xS 中的出现次数,则 p(S)=n!xcnt(x)!。根据 Lucas 定理,p(S) 是奇数当且仅当所有 cnt(x) 在二进制下相加没有进位。因此,合法的可重集就是对于 n 的二进制中每个 2i,任意选择一个 x 重复 2i 次。

现在还要解决 ORxSx=y 的条件。可以通过容斥将条件改写为 xS,bin(x)bin(y)x 的二进制中的 1y 的子集)。

因此,对于固定的 y,只需要计算对于每个 2ibin(n),2jbin(y),可以选或不选 2i+j,总和等于 x 的方案数。这可以通过数位 DP 解决,即 f(i,j) 表示确定最低 i 位,目前进位为 j 的方案数,时间复杂度 O(logxlognpcnt(y))

总时间复杂度 O(2pcnt(y)pcnt(y)logxlogn)

C. Counting Strings

(复读官方题解)

首先把条件改写成 gcd(r,rl)=1。建出 SAM,对于每个 rl,假设保留所有 gcd(r,rl)=1r 对应的结点,这样的串的个数就是这些结点到根的路径的并中深度为 rl 的点数。如果我们把这些结点按 DFS 序排序,则容易维护这些路径的并。

考虑通过搜索枚举 rl 包含质因子的集合来优化这个算法。在加入一个素数 p 时,要删除所有 prr 对应的结点,这样的删除对路径并的变化是删除一条链,可以用链表维护前驱后继,求两次 LCA 就能找到这条路径。回溯时撤销修改即可。为了统计答案,我们维护每个深度的点数,修改的影响是区间加,查询是单点求值,可以用 O(1) 修改 O(n) 查询的分块维护。

接下来只需要分析这样搜索时需要修改的次数 F(n)。实测在 n=105 时,修改的次数不超过 2107。具体的分析是,修改次数等于 n1x=1[μ(x)0]nmaxp(x),其中 maxp(x)x 的最大素因子。

时间复杂度 O(F(n)+nn)

D. Bracket Sequence

考虑 DP 计算一个给定字符串 s 的方案数。f(i,j) 表示 S[0:i] 中等于 ()[0:j] 的子序列的方案数,则答案就是 f(|s|,2k)

K=max{k}。对于第 1 类区间询问,我们可以把这个 DP 写成 vMlMl+1Mr,其中 Misi 的转移矩阵。由于矩阵的特殊性质,可以在 O(K2) 的时间内计算一个矩阵乘上 Mi,因此只需要预处理 M1M2Mi(M1M2Mi)1,就可以在 O(K) 时间内回答一个询问。

对于第 2 类区间询问,首先可以添加一个 DP 状态,表示还没有进入子串,同时预处理 M1M2Mi 的前缀和即可。

总时间复杂度 O(nK2+qK)

E. Dominating Point

S(u)={v(u,v)Eu=v}。点 u 是支配点当且仅当不存在 vu 满足 S(u)S(v)

把所有点按度数从大到小排序,依次检查是否存在这样的 v。显然我们只需要检查已经确定是支配点的 v,而找到三个支配点后就可以直接返回,因此对于每个 u 只需检查 O(1) 个点,每次检查 O(n)

总时间复杂度 O(n2)

F. An Easy Counting Problem

因为 p 是素数,由 Lucas 定理可知组合数是 p 进制下每一位组合数的乘积。0ba<p 的组合数分布可以 O(p2) 暴力计算。

求出一位的组合数分布后,我们要计算其在 i,jijmodp 卷积意义下的 k 次幂。通过找一个原根并将下标取离散对数的变换,我们可以将其转化为普通的循环卷积,可以用 FFT 优化。

时间复杂度 O(p2+plogplogk)

G. An Easy Math Problem

我们加上 gcd(p,q)=1 的限制,不同的 (p,q) 就对应了不同的 r。考虑计算这样的 (p,q) 的方案数。显然方案数是积性的,即每个素数独立,且 pk 的方案数是 2k+1(1,1),(pi,1),(1,pi))。分解 n 之后直接计算即可。

可以预处理素数来加速分解,时间复杂度 O(N+qNlogN)

H. Elimination Series Once More

我们对每个 i,和每个 j=1,2,,n,来计算 i 能不能赢下第 j 轮,也就是能不能让 ai 变成其所在的大小为 2j 的子树的最大值。

只需要判断两个条件:

  • 所在子树中大于 ai 的不超过 k 个。每次最多只能把一个换出去。
  • ai2j。这是为了保证有足够多小的数放进子树。

这个条件可以在归并排序的过程中快速判断,时间复杂度 O(n2n)

I. Max GCD

我们枚举 gcd=d,看是否能用 d 的倍数满足条件。显然对于固定的 ji 应该越大越好,k 在满足 kjji 的前提下越小越好。

考虑从大到小枚举 j,找到对应的 iki 可以直接找到,但 k 并不单调。然而如果 i 更小的时候 k 更大,这样的三元组一定是不优的,因此仍然是只需要让 k 单调下降。令 A=max{ai}d(A)1A 中约数个数的最大值,则可以在 O(nd(A)) 的时间中找到所有的三元组。

询问就是简单的二维偏序,为了平衡复杂度,可以使用 O(1) 修改、O(n) 查询的分块,总时间复杂度 O(nd(A)+qn)

J. Graph Changing

考虑在 G1 中,两点有边当且仅当 |u,v|k,如果 u,v 可达,则最短路径长度一定不超过 3u1nv)。因此如果 k>3G2 开始就是空图。

k=3 时,显然当 n 足够大时 G2 开始也是空图。

k=2 时,显然当 n 足够大时 Gi+1Gi 的反图。

k=1 时,显然 G1 开始就是完全图。

因此只需要预处理 n 小的情况(例如 n<10),特判 k=1,2,3,剩余的情况分类讨论答案是 1,2,3 即可。

K. Penguins in Refrigerator

先求方案数,考虑从大到小插入数。首先大于 M/2 的数相对顺序不改变,对于不超过 M/2 的每个数 ai,找到左右第一个大于 Mai 的数,则 ai 只能插入到这个区间中。注意到这些区间形成一棵树形结构,因此方案数就是每个数插入的方案数相乘。

再求字典序最小的方案数。大于 M/2 的数相对顺序不改变,可以连一条链。对于不超过,对于不超过 M/2 的每个数 ai,找到左右第一个大于 Mai 的数,只需要它们之间的相对顺序不改变即可(因为其他的顺序关系都通过链确定了)。之后用堆维护,求字典序最小的拓扑排序即可。

时间复杂度 O(nlogn)

L. Prism Palace

所求的就是随机旋转一个角度,有一条边在 y 轴上的投影是整个凸包的概率。对于相邻的两个内角 a,b,这条边满足条件的角度范围是 max{0,πab}。对这些角度求和然后除以 2π 即可。时间复杂度 O(n)

M. Random Variables

考虑对每个 k 计算每种数出现次数不超过 k 的方案数。其等于 n![xn](ki=0xii!)m 注意由于模数不一定是素数,所以不一定有阶乘逆元,但 EGF 的卷积只需要乘上组合数。

考虑容斥,即把 ki=0xii! 写成 exi=k+1xii!。如果能够预处理所有 (i=kxii!)m,就能够在 O(n2logn) 时间内计算答案(因为 mkn)。

这里 m 的范围是 nk,按照 k 从大到小预处理,每次只需给内部的式子加上一项,展开后是 O(m) 项已知的式子求和。因此可以在 O(nk=1n3k2)=O(n3) 时间内预处理所有的值。对于每组数据,还要对 0in 计算 m\choose i,可以通过快速幂计算 (1+x)^m\bmod x^{n+1}O(n^2\log m) 的时间内计算。因此总复杂度是 O(N^3+\sum n^2(\log n+\log m))

对于整数 B,我们只预处理 k\ge B 的值,复杂度是 O\left(\frac{n^3}{B}\right)。对于 k< B,我们要计算的是一个短多项式的幂,可以通过 ODE(f'g=mg'f)来计算,注意 EGF 的求导就是移位,所以不需要除法,复杂度是 O(nk)。总时间复杂度 O\left(\frac{N^3}{B}+\sum n B^2+\sum n^2(\log n+\log m)\right)

官方题解里有 O(\sum n^2\log n) 的做法。

N. Python Program

外层循环直接模拟,内层循环用等差数列求和。

时间复杂度 O(|a-b|)

The 3rd Universal Cup. Stage 7: Warsaw 题解

2024-08-25 21:10:44 By jiangly

A. Bus Analysis

不妨将价格除以 2,变为 13,最后将答案乘 2 即可。

先考虑对于给定的 t_1,t_2,\ldots,t_n,如何计算最小代价。

\mathrm{dp}(i,j) 表示用 j 的代价覆盖了前 i 个点,最多还能覆盖多长的距离。设覆盖前 i 个点的最小代价为 x,则只有 f(i,x),f(i,x+1),f(i,x+2) 的值有用。这是因为在如果前 i 个点花费了至少 x+3 的代价,一定不比“花费 x 的代价覆盖前 i 个点,然后再买一张 3 元的票”优。

于是,在 DP 的过程中我们只需要记录 x,f(i,x),f(i,x+1),f(i,x+2) 这些值。现在变为计数问题,只需要将这些值记在状态里面。并且注意到,我们只需要求代价的和,所以不需要将 x 计入状态,只需在代价变大时统计进答案。

时间复杂度 O(n\cdot 75^3)。实际上,状态数的常数非常小,有用的三元组 (a,b,c) 都满足 0\le a\le a+20\le b\le b+20\le c\le 75

B. Missing Boundaries

首先,对于已经确定两个端点的区间,它们一定不能相交。

对于已经确定一个端点的区间,确定的端点一定不能包含在已经确定的区间里面,且互不相同。

剩下的区间可以任意填,我们可以计算出最小和最大的可能区间数量,判断输入的区间数量是否在范围内即可。

最大的区间数量就是(L- 两端点确定的区间的长度和 - 一个端点确定的区间个数)。

最小的区间数量就是相邻且差大于 1 的右端点和左端点的对数(包括开头和结尾)。

时间复杂度 O(N\log N)

C. Price Combo

考虑最终方案中每个物品是在商店 A 购买还是商店 B 购买。注意到如果 a_i>a_jb_i< b_j,那么在商店 A 购买物品 i 、商店 B 购买物品 j 一定是不优的(交换之后一定不劣)。因此,假设我们把一个物品看做点 (a_i,b_i),那么一定存在一条右上到左下的折线,折线上以及左上方的物品在商店 A 购买,折线右下方的物品在商店 B 购买。我们对这条折线进行 DP。

不妨设 a_i,b_i 互不相同。我们考虑从右上到左下确定折线,当折线向左的时候,加入折线上方的 a_i 产生的贡献;折线向下的时候,加入折线右方的 b_i 产生的贡献。注意因为是买一送一,因此只有第 1,3,5,\ldots 个会产生贡献。

显然我们只需要将 (a_i,b_i) 作为折线的关键点。为了方便起见,我们可以加入 (+\infty,+\infty),(-\infty,-\infty)

\mathrm{dp}(i,p,q) 是折线走到了 (a_i,b_i),选择的 a 个数奇偶性是 pb 个数奇偶性是 q 的最小代价。那么假设 (a_i,b_i)(a_j,b_j) 转移来(a_i< a_j,b_i< b_j),则需要加上的贡献是 a_i< a_k< a_jb_k>b_j)和 b_i< b_k< b_ja_k>a_i),以及 a_i 的贡献。

考虑按照 a_i 从大到小扫描线,用线段树维护转移。线段树以 b 作为下标,维护 DP 值加上 a_k 的贡献的最小值。对于 a_k 的贡献,只需在扫描线时在线段树上做前缀加(b_j< b_k)。注意这里的加法标记实际上是(0 位置加上的值,1 位置加上的值,加的数的个数)三元组。对于 b_k 的贡献,考虑直接在线段树上维护,即每个结点维护 \mathrm{dp}(j) 加上小于 b_jb 的贡献后的最小值,以及 b 的贡献。这里 b 的贡献本质上和 a_k 的加法标记一样。合并时,DP 值应当是左区间的 DP 值以及(右区间的 DP 值加上左区间 b 的贡献)的较小值。这样,要求 \mathrm{dp}(i),只需要在线段树上查询后缀 (b_i,+\infty)

时间复杂度 O(N\log N)

D. Data Determination

不妨设 a_1\le a_2\le \cdots\le a_n

k 是奇数时,需要存在 i,满足 a_i=m,i-1\ge\frac{k-1}{2},n-i\ge\frac{k-1}{2}

k 是偶数时,需要存在 i< j,满足 a_i+a_j=2m,i-1\ge \frac{k}{2} -1,n-j\ge\frac{k}{2}-1。注意对于相同的 (a_i,a_j)ij 离得越近越好,这样的 (i,j) 只有 O(n) 对。

时间复杂度 O(n\log n)

E. Express Eviction

解法 1

最小割。注意到存在路径当且仅当不存在左下区域到右上区域、每个格子都有居民、且相邻格子行列差都不超过 2 的路径。我们认为左下边界和左下区域是相邻的,右上边界和右上区域是相邻的。

因此我们可以对每个有居民的格子建两个点 (a_u,b_u),如果它是左下边界则连边 (S,a_u,+\infty),右上边界则连边 (b_u,T,+\infty),同时连边 (a_u,b_u,1) 代表可以花费 1 的代价删除这个格子。对于行列差都不超过 2 的每对格子 u,v,连边 (b_u,a_v,+\infty)。这个图的最小割即为答案。

时间复杂度 O(\mathrm{Maxflow}(HW,HW))

解法 2

最短路。考虑普通的最短路在什么时候会得不到最优解。

.#....
....#.
...#..
###...
###..#
###...

如这个例子,只需删除第三行的第四个格子。我们注意到这样的路径实际上是经过了一个格子相对的两个角,但我们的状态中并没有记录经过的格子,所以导致重复计算代价。

考虑所有经过两次的格子,如果一个有居民的格子 u 的两次经过在另一个格子 v 的两次经过之间,我们不如额外花费 1 的代价直接穿过格子 v。因此可以假设没有这样的两个格子 (u,v)。在这个前提下,我们可以发现路径上的每一个点至多在两个格子的两次经过之间(路径的两侧各一个),通过在状态中记录这两个格子,我们可以做到 O(H^3W^3) 的时间复杂度。

进一步地,假设我们依次经过了格子 u,v,那么下一步一定是从 v 走到格子 u 的对角。并且如果在下一次经过 u 之前我们花费了额外的代价,也是不如直接穿过 u 的。因此我们只需要记录一个之前经过的格子,并加一种额外的转移,即当前位置是 x,经过了 v,对于 v 的每个对角相邻的点 w,如果 x 可以不花费额外代价到达 w,则可以直接转移到位置 w,经过了 x。转移可以通过从每个点 BFS 预处理。

时间复杂度 O(H^2W^2)

F. Fibonacci Fusion

不妨设 a_1\le a_2\le \cdots\le a_n

枚举 j,则 a_j< a_i+a_j\le 2a_j,满足这样条件的斐波那契数只有至多两个,假设我们能求出这两个斐波那契数,就只需要求某个数的出现次数。

由于 a_i 非常大,对应的斐波那契数也非常大,所以我们计算斐波那契数对大素数取模的值(避免碰撞),同时需要估算对应的数的下标。

因为 F_n=\frac{1}{\sqrt5}\left(\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right)\approx \frac{1}{\sqrt 5}\left(\frac{1+\sqrt5}{2}\right)^n ,所以可以用 n\approx \log_{\frac{1+\sqrt 5}{2}}{\sqrt 5a_i} 来估算。

时间复杂度 O(n\log n+\sum\log a_i)

G. Game of Geniuses

答案等于 \max_i\min_j a_{ij}

设答案为 x,答案大于等于 x 是平凡的,先手可以删除除最小值等于 x 的行以外的其余行。

要证明答案小于等于 x,我们只需要证明每轮后,后手都能保证每行都有小于等于 x 的数。不妨设先手删除了第一行,则后手找到剩余 n-1 行中各一个小于等于 x 的数,标记其所在列,然后删除未被标记的列即可。

时间复杂度 O(n^2)

H. Henry the Plumber

因为每个水管都必须立即转弯,所以答案至少是 2

而答案不超过 4,因为可以分别连平行于 z 轴的水管,到同一个 z 之后垂直于 z 轴连接起来(如果两点连线平行于 z 轴则直接连)。

分类讨论:

  • 如果 (x_1,y_1,z_1)-(x_2,y_2,z_2) 垂直于 (p_1,q_1,0)(p_2,q_2,0),则答案为 2
  • 否则答案至少为 3。答案为 3 当且仅当存在一个中间点 P,和 (x_i,y_i,z_i) 的连线垂直于 (p_i,q_i,0)。即 P 在经过 (x_i,y_i,z_i) 且垂直于 (p_i,q_i,0) 的平面上。
  • 如果这两个平面平行,则答案为 4
  • 否则找到这两个平面的交,设为 (x_0,y_0,z)(一条平行于 z 轴的直线)。现在要确定 z 的值,使得 P 的夹角为直角,即 (x_0-x_1,y_0-y_1,z-z_1)(x_0-x_2,y_0-y_2,z-z_2) 的点积为 0
  • 如果 (x_0,y_0) 和某个 (x_i,y_i) 重合,则满足条件的 P 就是 (x_i,y_i,z_{j}),如果 z_1\ne z_2 则答案为 3,否则答案为 4(因为水管长度不能为 0)。
  • 否则,条件是一个关于 z 的二次方程,只需判断判别式是否大于等于 0。大于等于 0 则答案为 3,否则答案为 4

时间复杂度 O(1)

I. ICPC Inference

枚举获得金银铜牌的队伍。铜牌一定是通过了一个题目,且罚时尽量大。金牌一定是通过了尽量多的题目,且罚时尽可能小。

我们可以将分数设为 M\cdot \mathrm{num}-\mathrm{penalty},其中 M 是一个非常大的数。则分数越大的人排名越高。

考虑银牌可能的分数,因为铜牌只通过一个题,银牌分数应当在不小于铜牌的前提下尽可能小,因此有用的分数只有通过一个题的情况以及通过两个题且罚时最大。设这些可能的分数是 s_1< s_2< \ldots< s_k,则满足 s_i<\mathrm{bronze}\le\mathrm{gold}< s_{i+1} 的金铜牌是不合法的(当然还有小于 s_1 和大于 s_k 的情况)。

我们可以在 O(\log N) 的时间里面对每一个区间计算答案,但是区间的数量可以是 O(N^2) 的。注意到罚时 K=20 比较小,而可能的罚时都形如 t_i+K\cdot c0\le c< i),因此可能的罚时可以写成 O(N) 个段,每个段以 K 为周期。对于跨段的区间我们可以 O(\log N) 计算。而对于段内我们可以抽象成 O(K) 个以下询问:

  • 有多少对 (\mathrm{bronze},\mathrm{gold}) 满足 \mathrm{bronze}\bmod K=il\le \mathrm{bronze}\le r\mathrm{gold}-\mathrm{bronze}\le j

这样的 (\mathrm{bronze},\mathrm{gold}) 也只有 O(NK) 对,预处理之后可以 O(\log N) 回答询问。

注意金银铜牌必须互不相同,因此需要做一些容斥。

时间复杂度 O(NK\log N)

J. Juliet Unifies Ones

数据范围很小,所以做法很多。

一个线性的做法是分成三段,分别是 0,1,0,设 \mathrm{dp}(i,j) 表示考虑 i 个字符,目前在第 j 段,至少要删几个字符。

K. Routing K-Codes

如果 K(b)=\left\lfloor\frac{K(a)}{2}\right\rfloor 则我们将边定向为 a\to b。因为所有 K(x) 互不相同,因此每个点的出度都不超过 1,入度不超过 2,且图中不存在环,因此只可能是内向二叉树。因此如果 m\ne n-1 则无解。

假设确定了根,则根的值为 01(度数小于 2 则为 0,等于 2 则为 1),深度不超过 3231,每个孩子的值是 2K(x)2K(x)+1。最小的代价和可以通过 DP 求出。使用换根 DP 即可求出每个点作为根的答案。

时间复杂度 O(n+m)

L. Random Numbers

注意到长度为 k 的区间的和的期望是 k\cdot \frac{n+1}{2},因此当 k 距离 \frac{n}{2} 较近时才有较大的概率存在合法区间。当 k 较小的时候,因为总的组合数量不多,因此也有一定的概率存在合法区间。

因此只需设置常数 B,枚举所有长度在 [1,B]\left[\frac{n}{2}-B,\frac{n}{2}+B\right] 中的区间检查即可。

时间复杂度 O(nB)。例如 B500 可以通过此题。

M. Mathematics Championships

答案等于前 2^i0\le i\le k)大数和的最大值。排序后即可计算。

时间复杂度 O(n2^n)

The 3rd Universal Cup. Stage 6: Osijek 题解

2024-08-11 21:35:44 By jiangly

A. Coprime Array

注意到我们只关心 s\bmod x 的值(答案绝对值要求在 10^9 以内,但是任何一组解都可以通过调整符合这个范围,所以可以忽略这个限制),将 x 分解后,只需要求出每个 p^k 的解,就能通过 CRT 合并出 x 的解。

显然答案等于 1 当且仅当 \gcd(s,x)=1

剩下的情况,除了 s 是奇数且 x 是偶数的情况,都能构造出长度为 2 的解。

s 是奇数且 x 是偶数的情况可以先分出一个 1,因此可以构造出长度为 3 的解。

实现时其实可以利用随机避免分解和 CRT,随机到一个解的概率至少是 \prod_{p|x}\frac{\max\{1,p-2\}}{p}

B. Square Locator

因为点 Ay 轴上,所以点 A 的坐标可以直接算出。枚举 ABCD 是逆时针还是顺时针,设点 B 的坐标是 (x,y),则可以通过点 B 和点 C 到原点的距离列出两个方程,从而直接解出 x,y 并判断。

C. -is-this-bitset-

对于深度 d\le 11 的点 i,将 a_i 设为 2^{20-d}。因为树是二叉树,所以至多改变 2^{12}-1=4\,095 个点的 a_i

改变之后,每条链上的前 12 个点就可以凑出 [0,2^{21}) 中所有 2^9=512 的倍数。因此对于 d>11 的点,只需要考虑模 512 的每种余数能凑出的最小的数,可以在 O(512) 的时间 DP 求出。

为了进一步减小空间消耗,注意到每条链上 DP 的改变量不会超过 \max\{b_i\} < 2^{21},因此只需记录 DP 数组发生的改变,回溯时撤销即可。

V=\max\{b_i\},k=5\,000,则时间复杂度为 O(nV/k),空间复杂度为 O(n+V)

D. Cycle Game

我们认为最外圈边界都是白格子,则存在一个内部非空的环当且仅当存在一个格子,将这个格子视为白格子后白格子的八连通块至少有两个(即存在一个白格子和边界不连通)。

加入一个黑格子后,如果存在这样的格子,那么其中的一个一定与新加入的格子相邻。因此只需使用线段树分治和可撤销并查集维护连通性,在每个时刻枚举周围的所有格子并判断这次操作是否应该进行。

时间复杂度 O(nm\log ^2 (nm))

E. Sum of Squares

F. Alternating Cycle

G. Touching Grass

如果询问的是直线,则问题可以转化为直线和点集的上凸包是否相交,只需在凸包上二分。

线段询问可以通过线段树转化为直线询问,即按 x 排序建线段树,对线段树上的每个区间都求凸包。

这样的空间复杂度是 O(n\log n+m),采用类似分治的方式离线回答询问可以优化为 O(n+m)

将线段按斜率排序后可以避免二分,改用双指针,总时间复杂度 O((n+m)\log n)

H. Game Design

ip_i 连边,可以看作每个点入度和出度都是 1 的有向图。设 f(i,j) 为考虑前 i 个点,有 j 条入边和出边的另一端还未确定(大于 i)。

考虑 i 的连边,有如下四种转移。

  • 入边和出边都向后,转移到 j+1,方案数 1
  • 入边向后,出边向前,转移到 j,方案数 j
  • 入边向前,出边向后,要求 s_i=1,转移到 j,方案数 j
  • 入边和出边都向前,要求 s_i=1,转移到 j-1,方案数 j^2

时间复杂度 O(n^2)

I. Geometry Hacking

J. Non-Interactive Nim

The 3rd Universal Cup. Stage 5: Moscow 题解

2024-07-28 13:15:20 By jiangly

A. Counting Permutations

对于所有满足条件的排列,二元组序列 (a_{p_i}\bmod m_1,a_{p_i}\bmod m_2) 一定是相同的,也就是按 a_i\bmod m_1 为第一关键字,a_i\bmod m_2 为第二关键字升序排序。

如果这个序列不合法则无解,否则方案数为每个 (a_i\bmod m_1,a_i\bmod m_2) 二元组出现次数的阶乘乘积。

时间复杂度 O(n\log n)

B. Bookshelf Tracking

如果只有 E 操作,则维护每本书的位置,就可以 O(1) 进行交换。

如果有 R 操作,注意到 R 操作的本质是将位于前一半的书按编号降序排序,后一半的书按编号升序排序。因此,在最后一次 R 操作之前,只需维护每本书是在前一半还是后一半。排序后再处理最后的一段 E 操作即可。

时间复杂度 O(n+q)

C. Painting Fences

最优解一定是从一个极大全黑矩形开始扩展。这样的矩形共有 O(nm) 个,可以通过枚举底端然后笛卡尔树求出。

考虑求从一个矩形扩展到全部的步数。显然两维是独立的,因此只需要考虑 [l,r] 扩展到 [0,n] 的最少步数。

如果 l=0 或者 r=n,显然最优解是长度每次翻倍。

对于一般情况,枚举 l=0r=n 哪个先满足。不妨设 l=0 先满足。设初始时 d=\left\lceil \frac{l}{r-l}\right\rceil,则至少需要 \left\lceil\log_2{(d+1)}\right\rceil 步。但是一直向左对称可能会导致一些浪费。事实上,最优解是:第 i 轮,如果 d 的二进制从低到高第 i 位是 1,则向左对称,否则向右对称。

因此从一个矩形开始扩展的最小步数可以在 O(\log nm) 甚至 O(1) 的时间内求出。

总时间复杂度 O(nm\log nm)O(nm)

D. Function with Many Maximums

首先要注意到,假设 a_i 是降序排序,则 f(a_i)=\sum_{j=1}^ia_j+ia_i。如果不考虑 a_i 必须是整数的条件,令 a_i=\frac{1}{i(i+1)} 可以使所有 f(a_i) 相同。

考虑找一个大数 M(大约为 Cn^4 级别),然后令 a_i=\left\lfloor \frac{M}{i(i+1)}\right\rfloor,然后对其进行调整。我们希望使得 f(a_{n}),f(a_{n-2}),f(a_{n-4}),\ldots,f(a_{n-2(b-1)}) 是最大值,因此对于 i< n-2(b-1),只需令 a_i=a_{i+1}+1。注意这时 a_1 也就是 a_i 的最大值不超过 O(Cn^2),符合题目要求。

对于后面部分的调整,首先需要将 f(a_i) 调整成递增,这只需将函数值下降位置的 a_i 增加 O(n) 的值。这是因为原来相邻函数值的差是 O(n) 的,所以调整后累计的差是 O(n^2),而将 a_i 增加 1 会使得 f(a_i) 增加 i+1

调整后,相邻函数值的差仍然是 O(n) 的,而相邻 a_i 的差是 \Theta(Cn),因此将 a_{2i+1} 的值减少 f(a_{2i+2})-f(a_{2i}) 就能使得 f(a_{2i+2})=f(a_{2i})

E. Building a Fence

分类讨论。不妨设 w\le h

  • 如果 s\le w\le h,那么从一个角开始贪心铺放,不可能出现一个 s 被分成三段的情况,因此答案可以取到下界 \left\lceil \frac{2(w+h)}{s}\right\rceil
  • 如果 w\le h< s,那么答案可能是 2,34
    • 要答案为 2,只可能是两个 s 都被分成了两段,即 w+h=s
    • 要答案为 3,肯定有 ks 恰好拼了 k+1 条边。
      • k=1,即 2w=s2h=s
      • k=2,即 2w+h=2s2h+w=s
      • k=3,即 2(w+h)=3s
    • 否则答案为 4
  • 如果 w< s\le h
    • 如果 2w+h\ge 2s,那么可以先拿两个 s 分出两个 w,剩下部分拼到同一个长边,然后从这条边开始贪心,能取到下界 \left\lceil \frac{2(w+h)}{s}\right\rceil
    • 否则答案为 34,分析同上,但因为大小关系的限制只可能 k=3,即 2(w+h)=3s

F. Teleports

注意到经过任意的操作后,我们都知道可能的宝藏位置是一个区间。设 f(l,r) 是已知宝藏在第 l 个到第 r 个箱子时,找到宝藏的最小代价。

转移如下。

  • 枚举选择的传送器 x,则新的可能的宝藏范围是 [2x-r,2x-l]
    • 如果 1\le 2x-r\le 2x-l\le n,则 f(l,r)\le f(2x-r,2x-l)
    • 如果 2x-r< 1,则 [2x,r] 中的宝藏无法传送,f(l,r)\le \max\{f(1,2x-l),f(2x,r)\}
    • 如果 2x-l>n,则 [l,2x-n-1] 中的宝藏无法传送,f(l,r)\le \max\{f(2x-r,n),f(l,2x-n-1)\}

注意到转移图是一个关于区间长度 r-l 的分层图,每一层中只有第一类转移。因此可以从小到大枚举 r-l,执行所有的第二、三类转移,然后使用 Dijkstra 进行第一类转移。这里是稠密图所以可以使用 O(n^2) 的 Dijkstra(当然堆优化的 Dijkstra 也很快)。

时间复杂度 O(n^3)

G. Exponent Calculator

因为只有加法、减法和乘法,因此不考虑牛顿迭代。考虑用 e^x=\sum_{n=0}^\infty \frac{x^n}{n!} 来逼近。但是这样在 |x| 较大时收敛较慢。因此考虑先将 x 除以 2^B,然后展开到 x^T 项,最后将结果平方 B 次。实验可以发现 T=7,B=10 时较优,可以在 x=20 时达到 10^{-12} 以下的相对精度。

H. Ancient Country

考虑所有城市的顶点,不可能出现 i < j < k < l 满足 P_iP_k 在同一个城市,并且 P_jP_l 在同一个城市(否则 P_iP_kP_jP_l 就会相交或是在国家范围之外)。因此这些城市的顶点形成一个树形结构。即设包含最小顶点的城市的顶点为 P_{i_1},P_{i_2},\ldots,P_{i_k},那么剩余的城市顶点一定分布在 [i_1+1,i_2-1],[i_2+1,i_3-1],\ldots,[i_k+1,n] 这些区间中。

因此我们可以设计区间 DP,即 f(l,r) 表示只是用下标在 lr 的顶点,所构造城市的最大保护级别。转移如下。

  • 假设 P_l 不属于某个城市,则 f(l,r)\gets f(l+1,r)

  • 否则我们要选一个包含 P_l 的凸包,然后用凸包的权值加上凸包顶点间的区间的 f 值之和来更新 f(l,r)。这一步也可以用 DP 进行。

    • 首先枚举 i 连的第一条边 P_iP_s,然后令 g(j,k) 表示凸包最后一条边是 P_jP_k 的最大权值。转移是枚举下一条边 P_kP_e,然后转移到 g(k,e)。最后检查一下连回 l 是否合法并更新答案。需要枚举第一条边是因为要检查 P_kP_iP_s 这个角是否合法。注意这里判断凸包只需要相邻三个点的夹角,因为下标递增,必然是不会自交的。

具体实现时,可以从大到小枚举 l,然后进行 DP。枚举 l,s 后,DP 的复杂度是 O(n^3)。注意到转移可以用极角序优化,即枚举 k,e,可以转移到 g(k,e)i 是极角序上的一段。事实上,我们不需要记录极角序,因为下标递增,每个点所连出的边按下标排序就是极角序,因此枚举 k,e 后,可以转移的 i 是一个前缀,用双指针维护即可。

总时间复杂度 O(n^4)

I. Marks Sum

如果长度小于 2\,000,可以直接返回 d=info=0

如果长度大于等于 2\,000,我们一定能找到一个前缀,使得剩余字符数小于 2\,000,且总和是 2\,000 的倍数或其加 1。我们令 info=2x+y0\le y\le 1)表示前缀的总和等于 2\,000x+y。因为字符串长度不超过 10^6,因此 x< 1\,000,是足够的。

第二次时只需根据 info 计算出前缀的总和,在加上输入串的总和即可。

J. Prefix Divisible by Suffix

枚举选择最短的后缀。如果后缀有前导 0,则去掉之后仍然满足条件。因此满足条件的最短后缀长度不超过 7(如果大于 7 则前缀小于后缀)。

因为我们钦定枚举的后缀是最短的一个,需要枚举更短的一些进行容斥。若干后缀都满足的数形如 km+a,可以用扩展欧几里得算法求出。

时间复杂度 O(10^7\cdot 2^7\cdot \log n)。但是注意到在后缀较长时,对于很多的集合,满足条件的数的大小都超过了 n。我们在枚举的时候对这种情况直接剪枝,总枚举次数实际上远小于这个上界。

K. Train Depot

首先可以把所有列车转化为 s_it_i 的路径(t_is_i 的祖先),价值为 c_i,然后选择若干条点不相交的路径使得总价值最大。

f(x) 为在 x 的子树里面选择路径的最大价值。如果 x 不是某条路径的顶端则 f(x)\gets \sum_{y\in ch(x)}f(y)

如果选择了 x\to y 的路径,那么 yx(不包括 x)的路径上的每一个点的兄弟以及 y 的所有孩子 z 会贡献 f(z)。反过来考虑,每个点 x 会对底端是 x 的父亲或 x 的兄弟子树中的点的路径有贡献,在 DFS 序上即 [in_{parent_x},in_x)[out_x,out_{parent_x}) 这两个区间。使用线段树或树状数组维护这个贡献即可。

时间复杂度 O((n+\sum k_i)\log n)

L. Array Spread

二分答案 x,如果有一种序列满足每个区间的总和在 [1,x] 中,说明答案不大于 x

s_i 是前 i 个数的和,则限制为 s_i\ge s_{i-1}1\le s_{r_i}-s_{l_i-1}\le x,显然是差分约束的形式。离散化之后点数和边数都是 O(m),因此判断负环的时间复杂度是 O(m^2)。这里也可以看出答案是分子和分母不超过 O(m)(分母不超过简单环长度也就是图中点数,分子不超过图中除 x 外的边权和)的分数。因此二分次数是 O(\log m),二分之后可以根据实数值还原答案。也可以直接对这 O(m^2) 个分数二分。

总时间复杂度 O(m^2\log m)

事实上,我们可以去掉二分。将边权为 x 的边称为特殊边,剩下的是普通边。令 f(i,v) 表示从任意点开始,经过恰好 i 条特殊边,到达 v 的路径的普通边边权和的最小值。则答案等于 \max_v\min_{i=0}^{n-1}\frac{f(i,v)-f(n,v)}{n-i}

其中 n 是顶点数。

证明见此论文

M. Uniting Amoebas

每次将最大值和相邻的合并就可以做到 \sum_{i=1}^n a_i-\max_{i=1}^n\{a_i\}

显然这是最优解,因为每次花费 v 的代价至多使得最大值增加 v

The 3rd Universal Cup. Stage 0: Trial Contest 题解

2024-06-02 14:46:11 By jiangly

A. Arrested Development

动态规划,f(i,j) 表示考虑前 i 个任务,第一个人总时间为 j 时,第二个人总时间的最小值。

时间复杂度 O(n^2\max\{a_i,b_i\})

B. Champernowne Substring

讨论以下情况:

  • 对于位置不超过 100\,000 的情况暴力判断,以下都假设串中出现的都至少是五位数。

  • 特判串中出现 10^k10^k-1 的情况,以下都假设串中所有数的长度相等。

  • 串中只包含一个数。问号一定贪心填 0(首位是 1),如果首位是 0 还需要在前面补 1

  • 串中包含超过一个数。枚举这个数的开始位置和长度,以及进位的位数(因为串长不超过 25 且都至少是五位数,因此至多有一次进位)。那么进位的部分全部填 09,前一位枚举 09,再之前的位每个数都一样,问号同样贪心填 01。对于每种可能性都检查一遍。

C. Comparator

首先注意到,表达式只有两个输入,我们可以直接枚举这两个输入后求表达式的值。从而,每条语句的效果都可以拆分为不超过 4 条:如果 x 的第 a 位为 uy 的第 b 位为 v,则返回 r。当两条语句的 (a,u,b,v) 四元组相同时,靠后的语句实际上没有任何效果,因为它所能作用的输入已经全部返回了。因此,我们实际上只需要考虑不超过 4k^2 条语句,每条语句的效果可以在 O(2^{2k}) 的时间内暴力处理。

当我们得到了所有 f(x,y) 的值后,就可以统计答案。前两个答案都可以暴力统计,最后的答案枚举 x,y 后使用 bitset 优化即可。

时间复杂度 O\left(\sum|expr|+k^22^{2k}+2^{3k}/w\right)

D. Dihedral Group

二面体群的操作对应到字符串其实就是翻转和循环移位,只需要判断未翻转/翻转的 d+d 是否包含 t 作为子串。

时间复杂度 O(n)

E. House Deconstruction

1. n=m 的情况

首先考虑 n=m 的情况,即人的数量和房子的数量一样多时,如何求最小代价。对于一个方案,设 c_i 表示经过了 ii+1 这条边的人数(这里模 x 相等的下标表示同一个位置,例如 x+1 代表 1)。如果是从 i+1ic_i 是经过人数的相反数,显然最优解中不会有一条边两个方向都有人经过。则方案对应的代价是 \sum_{i=1}^x|c_i|,需要满足的限制如下:

  • 如果 i 位置是人,则 c_i=c_{i-1}+1
  • 如果 i 位置是房子,则 c_i=c_{i-1}-1
  • 如果 i 位置是空,则 c_i=c_{i-1}

容易发现,c_i 序列几乎是确定的,除了可以整体加上一个任意整数。设一个合法的序列是 c_i',则最小代价为对于任意 k\sum_{i=1}^x|c_i+k| 的最小值。这个函数关于 k 是下凸的,因此可以用三分求出答案。(事实上,k 一定是 c_i 的中位数的相反数。)

2. n< m 的情况:最优解

延续 n=m 的思路,我们可以稍微修改 c_i 的定义,即如果 i 位置是房子,c_i 可以等于 c_{i-1}-1c_{i-1}(表示该房子未被选择)。我们可以猜测以下的引理:

引理 1g(k)c_x=k 时的最优解,则 g(k) 是下凸函数。

有了引理 1 之后,对于 n< m 的情况我们同样可以三分 k,之后只需解决固定 c_x 之后的问题,即可求出最优解。

引理 1 的证明 只需证明 2g(k)\le g(k-1)+g(k+1)。设 k-1k+1 对应的序列分别为 c_i^{(k-1)}c_{i}^{(k+1)}。则令 c_i^{(k)}=\frac{c_i^{(k-1)}+c_i^{(k+1)}}{2}。该序列几乎满足我们的需求,包括 c_x^{(k)}=k 以及相邻 c_i 之间的关系,并且因为三角形不等式 |a+b|\le |a|+|b|,该序列的代价不超过 \frac{g(k-1)+g(k+1)}{2}。唯一有问题的地方是当某一处房子只在 k-1k+1 中的一个方案中被选择时,我们会算出 c_i=c_{i-1}-1/2。然而,对于每一个极长的小数部分为 1/2 的连续段,整体加上或减去 1/2 就是合法的序列,且其中的一种不会使得代价变大(只需比较正数和负数的数量)。从而我们证明了 2g(k)\le g(k-1)+g(k+1)\blacksquare

对于证明中存在小数部分的调整,事实上,即使我们把 i 位置是房子时的限制改为 c_i\in[c_{i-1}-1,c_i],最优解仍然会在所有数都是整数时取到。(提示:仍然可以考虑调整,也可以直接把原问题写成费用流,这样也能得到原问题的凸性。)

接下来只需要考虑固定 k 时如何求最优解。我们可以使用 DP。

f(i,j) 表示考虑了前 i 个位置,c_i=j 的最小代价。初始值为 f(0,k)=0。转移如下:

  • 如果 i 位置是人,则 f(i,j)= f(i-1,j-1)+|j|
  • 如果 i 位置是房子,则 f(i,j)= \min \{f(i-1,j+1),f(i-1,j)\}+|j|。这里代表房子可选可不选。
  • 如果 i 位置是空,则 f(i,j)=f(i-1,j)+|j|

最终的答案即为 f(x,k)

注意到 f(i,j) 对于固定的 i,关于 j 是下凸的,很容易维护。实现中,为了方便,可以把状态改为 f(i,j) 表示前 i 个位置选了 j 个房子的最小代价,这时最小值的位置一定是单调不降的,可以用差分维护最小值之后的斜率,对于房子只需插入一个 0 的斜率。

把空的位置一起处理,就能做到 O(m) 的时间复杂度。

因此,我们可以在 O(m\log n) 的时间内求出最优解。

3. n< m 的情况:方案数

为了计算方案数,我们还需要以下的引理:

引理 2 一个全局最优解 S 只会在唯一的 k 处取到最优解。

证明 注意到对于一个全局最优解的匹配方案,每个未选择的房子 i 都应该满足 c_i=0,即没有匹配经过该房子,否则用该房子替换这个匹配中的房子,代价严格变小。如果一个全局最优解 S 在两个不同的 k 处取到最优解,那么一定有一个 k 使得某个未选择的房子 i 满足 c_i\ne 0,矛盾。因此, 一个全局最优解 S 只会在唯一的 k 处取到最优解。\blacksquare

根据引理 2,我们只需对每个 g(k) 取到最小值的 k 分别计算方案数并求和即可。

我们还需要以下引理:

引理 3 至多有两个 k 满足 g(k) 是最小值。

证明 采用反证法,假设 g(k-1),g(k),g(k+1) 都是最小值。根据引理 1 的证明过程,g(k)=\frac{g(k-1)+g(k+1)}{2} 的必要条件是 c_i^{(k-1)}\cdot c_i^{(k+1)}\ge 0(否则三角形不等式严格不等),以及对于每个极长的小数部分为 1/2 的连续段,正数的个数等于负数的个数(从而无论加还是减 1/2,都不会改变代价)。因此不妨设 k-1\ge 0k+1\le 0 是对称的),找到最小的 j 满足 c_j^{(k-1)}\ne c_j^{(k+1)}-2,则 j 位置是房子。这样的 j 一定存在,否则两个方案对应相同的 S,根据引理 2,一定不是全局最优解。此时 c_j^{(k-1)}=c_j^{(k+1)}-3c_j^{(k-1)}=c_j^{(k+1)}-1,且 c_j^{(k-1)}\ge 0。无论如何,我们都可以令 c_{j}^{(k)}=c_{j-1}^{(k)}>0,同时调整极长的连续段。但是因为 j 是未选择的房子,所以这一定不是全局最优解。因此至多有两个 k 满足 g(k) 是最小值。\blacksquare

根据引理 3,我们只需要对至多两个 k 分别计算方案数并求和。因此这不会增加我们的复杂度。

至于计算方案数,可以在 DP 的过程中同时进行。我们维护 DP 取到最小值的位置,并且最小值至多有两个。最小值之后的部分的方案数只需进行一个平移。因为最小值的位置单调不降,方案数也很容易维护,时间复杂度仍然为 O(m)

综上,我们可以在 O(m\log n) 的时间复杂度内解决该问题。

F. Magic Bean

我们只需要构造出能够交换两个环内的豆子的操作,之后每次找到 a 环内的 b 豆子,和 b 环内非 b 的豆子交换,即可在不超过 30 次交换内完成复原。

构造的操作如下:把 a 环内要交换的豆子移至 1b 环内要交换的豆子移至 4a 环转到 b 环,b 环逆时针转一格,b 环转到 a 环。

G. Manhattan Walk

由于每个格子的状态是均匀独立随机的,并且到一个格子之前无法得知该格子的状态,因此可以看做到每个格子时再均匀随机状态。

f(i,j) 表示从 (i,j) 开始,到达终点的期望最小时间。如果 i=rj=c,则可以直接转移,否则设两个方向的 f 值分别为 aba\le b)。

讨论两种情况:

  • b\ge a+p,那么无论如何都会选择 b,期望为 a+p/4
  • b < a+p,那么只有当离能走 a 还有超过 b-a 的时间才会选择走 b,期望为 (p-b+a)/2p\cdot b+a/2+(b-a)/2p\cdot (a+b)/2。(三项分别代表选择走 b、可以走 a 时走 a、等待后走 a 的期望。)

时间复杂度 O(rc)

H. MountainCraft

注意到斜线的长度等于横向覆盖的长度乘以 \sqrt 2。而横向覆盖的长度就是所有 [x-y,x+y] 的并。使用线段树维护即可(维护区间最小值和最小值个数;或者因为减法只是加法的撤销,维护每个结点的覆盖次数)。

时间复杂度 O(q\log q)

I. Not Another Constructive!

我们可以在字符 A 的位置计算贡献,也就是前缀中 N 的数量和后缀中 C 的数量的乘积。因此设 f(i,N,C,k) 表示考虑了长度为 i 的前缀,前缀中 N 的数量为 N,后缀中 C 的数量为 C,是否能恰好有 k 个 NAC 子序列。可以用 bitset 优化。

时间复杂度 O(n^3k/w)

J. Passport Stamps

i 趟旅行可能无法进行的条件是 p\le \sum_{j=1}^{i-1}c_j+i\cdot (c_i-1),也就是在前面每个章之间留恰好 (c_i-1) 的间隔。

时间复杂度 O(n)

注意,直接计算可能会超过 long long 的范围,需要使用 __int128 或改用除法。

K. Shadow Line

注意到要判断是否只有一片影子,只需要知道每个端点在墙上的位置的相对关系。而这些相对关系只会有 O(n^2) 次变化,也就是在两两的连线与 x 轴交点的位置。算出这些变化的位置之后就可以进行模拟。

只有一片影子的充要条件是对于每个真前缀,下端点的数量大于上端点的数量。因为每次都是交换位置相邻的端点,因此这个条件可以在 O(1) 时间内维护。

要注意的细节包括在有三点共线时的交换顺序,以及 x 轴上的下端点应该始终排在上端点之前。

时间复杂度 O(n^2\log n)

L. Square of Triangles

M. Training, Round 2

f(i,j,k) 表示考虑前 i 个题,是否能恰好加 j 次实现水平和 k 次思维水平。注意这里当某个 (j,k) 能达到时,之后都能达到。因此我们对每个 j 维护两个集合:已经能达到的 k 的集合以及已经更新过的 k 的集合。对于每个问题,我们只需找到矩形中能达到但还未被更新过的 (j,k),将 (j+1,k)(j,k+1) 都加入能达到的集合。因为每个 (j,k) 只会被更新一次,所以时间复杂度是 O(n^2\log n)

【PR #2】史莱姆 更优秀的解法

2022-04-09 18:52:35 By jiangly

回顾对于给定递增序列 a_1\le a_2\le \cdots\le a_n 求答案的过程:

  • 找到最小的 i 使得对所有的 j\le ia_i\ge a_j-a_1-a_2-\cdots-a_{j-1}+k
    • 注意如果 i 满足条件,则 i+1 也满足条件。
    • 只有这些满足条件的 i 才可能在吃掉 1,2,\ldots,i-1 后继续吃掉 i+1;同时,如果无法继续吃掉 i+1,则 i+1 一定可以依次吃掉 1,2,\ldots,i
    • 如果不存在满足条件的 i,根据上述性质,只有 n 可能获胜。
  • x=i,枚举每个史莱姆 j=i+1,\ldots,n,如果当前 x 能够吃掉 ja_1+a_2+\cdots+a_{j-1}\ge a_j+k),那么吃掉 j,否则 1,2,\ldots,j-1 都不可能获胜,因此令 x=j
  • 能够获胜的史莱姆即为 x,x+1,\ldots,n

考虑利用值域 [2^j,2^{j+1}) 分段的技巧优化上述过程。

对于第一步,只有每一段中的第一个数可能是 a_j-a_1-a_2-\cdots-a_{j-1}+k 的前缀最大值,因此先判断每一段的最后一个数是否满足条件,如果满足,则二分出第一个满足条件的数。

如果找不到满足条件的 i,容易判断最后一个数是否能够获胜(如果能获胜,它一定是所在段中的唯一一个数)。

接下来我们从 i 所在的段开始,枚举每一段,先判断能否吃掉这一段中的第一个数 y_1,如果可以,则可以吃掉这一段中的所有数(因为 (2^j+k)+2^j=2^{j+1}+k);否则,令 xy_1,注意此时不一定能吃掉所有数,因此还要判断是否能吃掉第二个数 y_2(如果存在),如果不能,则令 x=y_2,此时就一定可以吃掉这一段的所有数了。

注意最开始 i 所在的段已经有一些数被吃掉了,但处理的方式完全类似于后面的段。

需要支持的操作是区间求值域段中的最小值、次小值、最大值,以及区间后继。每次询问需要 O(\log W) 次 RMQ 和一次后继查询,因此可以做到 O((n+q)(\log n+\log W)) 的复杂度。

共 8 篇博客