A. Arrow a Row
一个串能通过操作得到的必要条件包括:
- 以
>
开头。 - 以
>>>
结尾 - 至少有一个
-
。
而事实上上述条件也是充分的。如下是一个可能的构造:
- 当目标串不以
->>>
结尾时,重复操作 (n−4,5),这样可以视作删除了最后一个字符。最终目标串一定是以->>>
结尾。 - 枚举 i 从 1 到 n−4,如果 si 为
-
则不操作,否则令 j 为 i 之后第一段连续的-
的结尾位置,操作 (i,j−i+4)。
操作次数显然不超过 n,时间复杂度也为 O(n)。
B. Athlete Welcome Ceremony
先求出有 x 个 a
、y 个 b
、z 个 c
的好序列,然后做一个三维前缀和,即可在 O(1) 时间内回答询问。
令 dp(x,y,z,ch) 表示有 x 和 a
、y 个 b
、z 个 c
,且以 ch 结尾的好的前缀个数。因为前缀长度就是 x+y+z,枚举下一个字符即可 O(1) 转移。
时间复杂度 O(n3+Q)。
C. Chinese Chess
对状态集合(状态为 (位置,类型))进行搜索,枚举询问的格点,然后根据距离分成若干个子集。实现后可以发现,即使对于全部位置都可行的情况,也只需要 3 步即可确定类型。因此总的搜索节点数不超过 903,如果速度还是很慢,可以考虑打表 3 步的所有决策,这样只需要搜索 2 步以内的情况。搜索的时候可以顺便记录每个状态的决策。
实现时注意每种棋子的移动方式。
D. Closest Derangement
注意到当 pi≠i 时,∑ni=1|pi−i|≥n。
当 n 是偶数时,最小值可以取到 n,且只在排列 2,1,4,3,…,n−1 取到。
当 n 是奇数时,根据奇偶性,最小值为 n+1。可以在排列 …,2k+2,2k+3,2k+1,… 和 …,2k+3,2k+1,2k+2,… 取到(前后的部分和偶数时一样,相邻数两两对换)。这样的排列共 n−1 个,现在我们要找到 pq1,pq2,…,pqn 的字典序第 k 小,只需快速实现比较两个排列,然后调用 nth_element 即可。
比较两个排列 p1,p2 只需找到最小的 i 使得 p1,qi≠p2,qi。注意到对于任意两个不同的好的排列,对应不同的位置一定是一个区间加上边界的 O(1) 个零散点,只需在 q−1 上 RMQ,然后暴力统计零散点即可。
时间复杂度 O(nlogn) 或 O(n)。
E. Disrupting Communications
要求的是和 u 到 v 的路径相交的连通块数。考虑用总的连通块数减去和 u 到 v 的路径不相交的连通块数。
令 l=LCA(u,v),则和 u 到 v 的路径不相交的连通块有以下两种:
- 完全在 l 的子树外部。
- 完全在 l 的子树内部,且连通块的根不在 u 到 v 的路径上。
令 f(x),g(x) 分别表示以 x 为根的连通块数和 x 子树内的连通块数,则转移如下: f(x)=∏y∈ch(x)(1+f(y))g(x)=f(x)+∏y∈ch(x)g(y) 同理,令 fo(x),go(x) 表示删除 x 的子树,且以 x 的父亲为根的树对应的答案。注意这里计算 fo(x) 不能使用除法(可能会有除以 0 情况),而应该预处理前后缀乘积。
再令 sumf(x) 为 x 到根的路径上的所有点 y 的 f(y) 的和,则答案为 g(1)−go(l)−g(l)+sumf(u)+sumf(v)−2sumf(l)+f(l) 时间复杂度 O(n+qlogn)。
F. Double 11
对于一个分组方案,设每组的个数和总和分别为 ci 和 si。要在 ∑mi=1ki⋅si≤1 的前提下最小化 ∑mi=1ciki,一定有每组的 d(ci/ki)d(ki⋅si) 是相等的,即 ki 正比于 √cisi。令 S=∑mi=1√cisi,则 ki=√ci/siS,∑mi=1ciki=∑mi=1√cisiS=S2。因此题目所求的答案就是 S。
注意到确定每个分组的大小之后,每个系数 √ci 就确定了,因此一定是把较小的数分到较大的组。因此我们可以将数组排序,从而每一组一定是一个区间。
考虑排序后的三个区间 (c1,s1),(c2,s2),(c3,s3)(s1/c1≤s2/c2≤s3/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。
- 令 c1←c1+c2,s1←s1+s2,这不会改变作为前提的不等关系,只需证 √(c1+c3)(s1+s3)−√c1s1≥√(c2+c3)(s2+s3)−√c2s2。
- 令 ai=si/ci,fi(x)=∂√(ci+x)(si+a3x)∂x=a3(1+2x)+ai2√(1+x)(ai+a3x),则上述不等式等价于 ∫c30f1(x)dx≥∫c30f2(x)dx,只需证明对任意 x≥0 都有 f1(x)≥f2(x)。再次求导会发现 ∂fi(x)∂ai 在 (0,a3) 上恒为负,因此命题得证。
因此转移函数是 Monge 的,可以用 WQS 二分 + 决策单调栈在 O(nlognlogϵ−1) 的时间内求解。二分时需要注意精度问题,应当需要 long double。
G. Expanding Array
考虑序列中相邻的两个数 x,y。首先通过插入两个数的 XOR 可以得到序列 x,y,x⊕y,x,y,也就是可以无限复制一对相邻的数,使得操作时不会将其消耗掉,因此我们可以把操作看成选中一对数 (x,y),将 (x,xopy) 和 (xopy,y) 加入可能的相邻数的集合。不断重复这样的操作,最后就能得到所有可能出现的相邻数对,自然就能算出可能出现的不同数的个数。
接下来分析一下这样的数对的个数,序列中本身有 n−1 对相邻的数,可以看作是独立的。对于相邻的两个数 x,y,因为进行的都是位运算,所以运算得到的任何一个数都可以看作两个位的一个函数 f(x,y),其中 x,y,f(x,y)∈{0,1},且 f(0,0)=0,因此至多有 23=8 种可能。数对的数量自然不会超过 82⋅n。事实上,打表可以发现这 8 种可能的数都是可以产生的,因此直接枚举然后去重即可。
时间复杂度 O(n) 或 O(nlogn)。
H. Friendship is Magic
先考虑如何计算一个 f(x)。当分割点向右移时,显然左侧单调递增,右侧单调递减。考虑找到最后一个左侧小于右侧的位置。即把 x 划分为 l,m,r,其中 m 是一个数位,满足 10l+m≥r 且 l<m⋅10|r|+r,则 f(x)=min{10l+m−r,m⋅10|r|+r−l}。
现在考虑求 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_i 的 i 的 GCD 为 d,如果 d=0 则 k=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) 而只要每次恰好除掉一个质因子,这个上界就是能够达到的。而事实上,只要 S 和 T 存在一个完美匹配(x\in S 匹配 y\in T 当且仅当 y\mid x),就一定存在达到这个上界的操作序列。具体来说,我们可以通过如下方法构造这个操作序列:
对于 x\in S,设 M(x) 是完美匹配中和 x 匹配的 T 中的数。如果对于任意 x\in S,M(x)=x,则构造完成。否则找到 M(x)\ne x 的最小的 x,令 p 为 x/M(x) 的任意一个质因子,然后重复以下过程:
- 如果 x/p\notin S,则将 x 变为 x/p,这就完成了一次操作。
如果 x/p\in S,则说明 M(x/p)=x/p 且 M(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_S 和 y_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,第 51 到 95 个数为 b,第 96 到 99 个数为 c,第 100 个数为 c+1 即可。
M. Two Convex Holes
注意到多边形的投影实际上只是多边形进行了平移和缩放,进行一些坐标变换后可以转化为两个多边形分别做匀速直线运动。进一步可以转化成多边形 P_2 的速度为 0,P_1 的速度为 (0,1)。
我们可以将多边形的面积以所有顶点的 x 坐标分成 O(n) 段,则每一段中多边形的上下边界都是线段。进一步容斥成 (上边界 - 下边界),则只需要计算形如 \min\{ax+b+t,cx+d\} 的函数的积分。这个函数可以按照 t 分成三段,每段都是二次函数。因此面积可以表示成 O(n) 段的分段函数,每一段都是二次函数。再预处理一下每一段的前缀和,询问时只需二分出端点所在的段,然后加上边界部分即可。
时间复杂度 O((n+q)\log n)。