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

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

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

I. Good Partitions

k 是好的当且仅当对于任意 i=1,2,\ldots,n-1,如果 i 不是 k 的倍数,则 a_{i+1}\ge a_i

也就是说,令所有满足 a_{i+1}< a_ii 的 GCD 为 d,如果 d=0k=1,2,\ldots,n 都是好的,否则只有 d 的因子是好的。

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

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

J. Grand Prix of Ballance

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

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

K. Magical Set

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

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

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

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

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

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

时间复杂度 O(n\sqrt {A}+n^3)

L. Recover Statistics

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

M. Two Convex Holes

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

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

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

评论

暂无评论

发表评论

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