你好,戊戌(LibreOJ Round #8)题解

samzhang 于 2018-02-24 14:42:30 发表,2018-04-15 1:00:33 最后更新

A. Matching

By Snakes,题解 By Snakes

  • 构造找规律
  • 思维难度:提高-
  • 实现难度:普及-

大胆猜结论,就是不证明!

要看证明的话,记得不要被一堆上取整下取整绕晕……

算法一

我会找规律!

考虑 n=1n=1n=1 的情况,显然最优方案是未匹配区间的最左格与最右格匹配,答案为 ∑i=0⌊(m−1)/2⌋(m−1−2i)\sum_{i=0}^{\left\lfloor{(m-1)/2}\right\rfloor}(m-1-2i)i=0(m1)/2(m12i)

考虑 n=2n=2n=2 的情况,kkk 至多为 111,显然最优方案是未匹配区间的左上格与右下格匹配,右上格与左下格匹配,答案为 m+2∑i=0⌊(m−1)/2⌋(m−1−2i)m+2\sum_{i=0}^{\left\lfloor{(m-1)/2}\right\rfloor}(m-1-2i)m+2i=0(m1)/2(m12i)

时间复杂度:O(T)O(T)O(T)
预计得分:101010

算法二

我会暴力!

枚举所有可行方案,计算并更新答案。可行剪枝有要求每次配对的网格 A,BA,BA,B 满足 f(A,B)≤kf(A,B)\leq kf(A,B)k

时间复杂度:O(Tnnm/2mnm/2)O(Tn^{nm/2}m^{nm/2})O(Tnnm/2mnm/2)
预计得分:151515

结合算法一可得 252525 分。

算法三

我会带权带花树!

将网格图转化为带权图,带花树计算其带权最大匹配。

时间复杂度:O(Tn3m3)O(Tn^3m^3)O(Tn3m3)
预计得分:404040

结合算法一可得 505050 分。

算法四

我会构造!

对于 n=mn=mn=mn,mn,mn,m 均为偶数的情况,可以构造的最优方案是将网格图均分为四个区域,左上与右下匹配,右上与左下匹配,此时答案为 n3/2n^3/2n3/2

时间复杂度:O(T)O(T)O(T)
预计得分:181818

结合上述算法可得 686868 分。

算法五

我会大胆猜结论!

注意到算法一中 n=1n=1n=1 的情况 k=0k=0k=0,为了使 kkk 尽量大,可以将匹配方案调整为该行左边 ⌊m/2⌋\left\lfloor m/2\right\rfloorm/2 格与右边 ⌊m/2⌋\left\lfloor m/2\right\rfloorm/2 格从左往右一次匹配,此时答案为 ⌊m/2⌋⌈m/2⌉=⌊m2/4⌋\left\lfloor m/2\right\rfloor\left\lceil m/2\right\rceil=\left\lfloor m^2/4\right\rfloorm/2m/2=m2/4,与算法一中给出的答案相等。

赌一次提交的机会,每行每列都能取得该行或该列的最大答案,则猜想答案为 n⌊m2/4⌋+m⌊n2/4⌋n\left\lfloor m^2/4\right\rfloor+m\left\lfloor n^2/4\right\rfloornm2/4+mn2/4

时间复杂度:O(T)O(T)O(T)
预计得分:100100100

算法六

我会证明!

算法五中给出了在行或列中使 kkk 尽量大的方法,实际上,我们可以构造出一种匹配方案取到猜想中给出的答案。

根据算法四,我们可以将网格图划分为四个区域,使得左上区域与右下区域全等,左下区域与右上区域全等,显然最优的划分方法是:左上区域与右下区域为 ⌊n/2⌋×⌈m/2⌉\left\lfloor n/2\right\rfloor\times\left\lceil m/2\right\rceiln/2×m/2 的矩形,左下区域与右上区域为 ⌈n/2⌉×⌊m/2⌋\left\lceil n/2\right\rceil\times\left\lfloor m/2\right\rfloorn/2×m/2 的矩形。此时答案为:

⌊n/2⌋⌈m/2⌉(⌈n/2⌉+⌊m/2⌋)+⌈n/2⌉⌊m/2⌋(⌊n/2⌋+⌈m/2⌉)=n⌊m2/4⌋+m⌊n2/4⌋\begin{aligned}&\left\lfloor n/2\right\rfloor\left\lceil m/2\right\rceil(\left\lceil n/2\right\rceil+\left\lfloor m/2\right\rfloor)+\left\lceil n/2\right\rceil\left\lfloor m/2\right\rfloor(\left\lfloor n/2\right\rfloor+\left\lceil m/2\right\rceil)\\=\,&n\left\lfloor m^2/4\right\rfloor+m\left\lfloor n^2/4\right\rfloor\end{aligned}=n/2m/2(n/2+m/2)+n/2m/2(n/2+m/2)nm2/4+mn2/4

而此时的 fff(⌈n/2⌉+⌊m/2⌋)(\left\lceil n/2\right\rceil+\left\lfloor m/2\right\rfloor)(n/2+m/2)(⌊n/2⌋+⌈m/2⌉)(\left\lfloor n/2\right\rfloor+\left\lceil m/2\right\rceil)(n/2+m/2),显然有 f≤min(n,m)−1f\leq \min(n,m)-1fmin(n,m)1,当且仅当 n1(mod2)m=nm=nm=nm=n+1m=n+1m=n+1 时取等。

时间复杂度:O(T)O(T)O(T)
预计得分:100100100

B. Matrix

By 613,题解 By 613

  • 博弈、构造找规律
  • 思维难度:提高+
  • 实现难度:普及

出题人也不知道有什么部分分做法 ……

第一小问

引理 1 先手不劣于后手。

先手可以认为是对手先手然后对方随便下了一个位置。

引理 2 对于边长为 1,2,31,2,31,2,3 的矩阵,Alex 无必胜策略。

暴力验证即可。

引理 3 对于边长为 444 的矩阵,Alex 有必胜策略。

暴力验证,或者如第二小问所示构造。

引理 4 对于边长 >4>4>4 的矩阵,Alex 有必胜策略。

第一次操作和 Ball 的第一次操作放在同一行,去掉这一行一列转化为边长少 111 的游戏即可。

第二小问

引理 1 对于边长为奇数的矩阵,Alex 无必胜策略。

由于 Alex 知道的唯一信息是 Ball 上一次放的位置,为了保证确定性,Ball 的每一个位置必然唯一确定 Alex 的位置,从 Ball 的位置向 Alex 的连一条有向边。为了保证操作合法,对应的位置必须唯一且互逆,那么这构成一个完美匹配。然而 nnn 为奇数时不存在完美匹配,故当 n>2n>2n>2 时不存在一种策略保证 Alex 的前两次(Bob 选择一个在 Alice 的策略中既有入边又有出边且二者不同的位置操作一次,再选一个能到达它的位置操作一次)操作都合法;而 n=1n=1n=1 时显然 Alex 无必胜策略。

引理 2 对于边长为 222 的矩阵,Alex 无必胜策略。

暴力验证即可。

引理 3 对于边长为 4,64,64,6 的矩阵,Alex 有必胜策略。

对应的匹配如下(相同标号代表匹配):

(边长为 666 可以随机化搜索,很快就能找到解)

M4=[1156225634773488],M6=[138910111818210213158931431544161112755171112766161714] M_4= \begin{bmatrix} 1 & 1 & 5 & 6 \\ 2 & 2 & 5 & 6 \\ 3 & 4 & 7 & 7 \\ 3 & 4 & 8 & 8 \end{bmatrix} , M_6= \begin{bmatrix} 13 & 8 & 9 & 10 & 1 & 1 \\ 18 & 18 & 2 & 10 & 2 & 13 \\ 15 & 8 & 9 & 3 & 14 & 3 \\ 15 & 4 & 4 & 16 & 11 & 12 \\ 7 & 5 & 5 & 17 & 11 & 12 \\ 7 & 6 & 6 & 16 & 17 & 14 \end{bmatrix} M4=1233124455786678,M6=131815157781884569294561010316171612141111171133121214

引理 4 对于边长为偶数 n(n>3)n(n>3)n(n>3) 的矩阵,Alex 有必胜策略。

证明:按如下伪代码所示构造即可。

function work(n)
{
    if n==4 return M4
    if n==6 return M6
    int a[][]=work(n-4),col=(n-4)*(n-4)/2+4*4/2
    for i=1 to n
        for j=1 to n
        {
            if ((i>n-4) and (j>n-4)) a[i][j] = M4[i-(n-4)][j-(n-4)] + (n-4)*(n-4)/2
            else if ((i>n-4) or (j>n-4) and (i%2=1)) a[i][j]=a[i+1][j]=++col
        }
    return a
}

时间复杂度:O(T)O(T)O(T)
预计得分:100100100

C. MIN&MAX I

By CommonAnts,题解 By fengchanghn

  • 思维难度:提高
  • 实现难度:提高(打表) / NOI(不打表)

算法一

暴力枚举 n!n!n! 种排列,然后暴力枚举统计三元环的数量,按定义计算期望。如果程序时间效率较差可以打表。

时间复杂度:O(n!⋅n3)O(n! \cdot n^3)O(n!n3)
预计得分:151515

算法二

考虑排列 ppp , 将三元环记为 (i,j,k)(i,j,k)(i,j,k) 其中 i<j<ki<j<ki<j<k

容易发现:对于任意三元环 (i,j,k)(i,j,k)(i,j,k) 存在 pj>max(pi,pk)p_j>max(p_i,p_k)pj>max(pi,pk)pj<min(pi,pk)p_j<min(p_i,p_k)pj<min(pi,pk) 成立。

这两种情况是对称的,因此我们只要求 pj>max(pi,pk)p_j>max(p_i,p_k)pj>max(pi,pk) 形式的三元环的期望个数,最后给答案乘 222 即可。

注意到,在一个确定的 ppp 中,每个 jjj 至多对应一个三元环,且存在一个三元环与 jjj 对应当且仅当存在 i<ji<ji<j 满足 pi<pjp_i<p_jpi<pj 且存在 k>jk>jk>j 满足 pj>pkp_j>p_kpj>pk。即 pjp_jpj 既不是前缀最大值也不是后缀最大值。

于是,我们枚举数 jjj 和他所在的位置 iii ,利用组合数计算上述条件的反面来算方案数,参考程序

时间复杂度:O(n2)O(n^2)O(n2)
预计得分:353535

算法三

基于算法二,根据期望的线性性,我们可以对每个 jjj 分别统计期望后求和。

∀j\forall jj,存在一个三元环与 jjj 对应的概率为:1−1j−1n−j+1+1n1-\frac{1}{j}-\frac{1}{n-j+1}+\frac{1}{n}1j1nj+11+n1。这个式子的意义为总概率减去 pjp_jpj 是前缀最大值的概率减去 pjp_jpj 是后缀最大值的概率再加上 pjp_jpj 同时是前缀、后缀最大值的概率(由容斥原理)。

于是,答案为 2⋅(∑j=1n1−1j−1n−j+1+1n)=2⋅(n+1−2⋅∑j=1n1j)2\cdot (\sum_{j=1}^n 1-\frac{1}{j}-\frac{1}{n-j+1}+\frac{1}{n})=2\cdot (n+1-2\cdot \sum_{j=1}^n \frac{1}{j})2(j=1n1j1nj+11+n1)=2(n+12j=1nj1)

x1=(px)(pmodx)(modp) 递推 O(n)O(n)O(n) 求逆元即可。

时间复杂度:O(n)O(n)O(n)
预计得分:757575

算法四

由于 [1,998244352][1,998244352][1,998244352] 中的数互为逆元,且和为 0(mod998244353),故在 998244353−n998244353-n998244353n 较小时求 ∑j=1998244353−ni−1\sum_{j=1}^{998244353-n} i^{-1}j=1998244353ni1 的相反数即可。

时间复杂度:O(p−n)O(p-n)O(pn)
预计得分:151515,结合前述可得 909090

算法五

基于算法三,选定一个值 SSS,对于每个 S∣iS|iSi , 打一个逆元前 iii 个数和的表,这样就可以 O(S)O(S)O(S)(要线性求出一个集合中数的逆元,只要先求出它们的积的逆元以及某种顺序的前缀积,然后依次乘回去算就可以了)求解了。

参考程序

时间复杂度:O(S)O(S)O(S)
预计得分:100100100

算法六

我觉得打表很不优美!能不能不打表?

当然可以啊!利用多项式求解即可(与求阶乘模质数的方法类似,也可以参考中文资料:zzq's Blog)。

所以模数用 998244353998244353998244353 充分证明了出题人的良心。

时间复杂度:O(nlogn)O(\sqrt n \log n)O(nlogn)
预计得分:100100100

D. MINIM

By CommonAnts,题解 By CommonAnts

  • 思维难度:NOI-
  • 实现难度:提高

算法一

暴力搜索、枚举、随机化。

时间复杂度:ω(poly(n,q,li,m))\omega(\mathrm{poly}(n,q,l_i,m))ω(poly(n,q,li,m))
预计得分:000151515(子任务 1)

算法二

NIM 游戏后手必胜当且仅当所有石子堆数量的异或和为 000

所以实际上求的是异或和为 ccc 的最小代价。设计一个 DP:fi(j)f_i(j)fi(j) 表示考虑前 iii 堆异或和为 jjj 的最小代价,暴力转移。

时间复杂度:O(nm2+1)O(nm^2+1)O(nm2+1)
预计得分:353535(子任务 1,2)

算法三

li=2k−1l_i=2^k-1li=2k1 时,一个 ccc 能被如何表示仅和其二进制位数有关。答案是满足 li≥cl_i\ge cliciiiviv_ivi 的最小值。注意特判 000

时间复杂度:O(n+logm+qlogm)O(n+\log m+q\log m)O(n+logm+qlogm)(我们认为范围内的位运算是 O(1)O(1)O(1) 的,下同)
预计得分:202020(子任务 3)

算法四

考虑一个在 [0,a][0,a][0,a] 中的任意整数和一个在 [0,b][0,b][0,b] 中的任意整数异或,可以发现所得结果是一个 [0,c][0,c][0,c] 中的任意整数,其中 ccc 的二进制位中,a,ba,ba,b 最高的共同为 111 的位之后都是 111,之前是 aaabbb 按位或的结果。

那么我们枚举最高的共同二进制位,然后在这一位之前做子集 DP 即可,复杂度为 O(mlog23)O(m^{\log_2 3})O(mlog23)

时间复杂度:O(n+mlog23+q)O(n+m^{\log_2 3}+q)O(n+mlog23+q)
预计得分:555555(子任务 1,2,4)

算法五

考虑算法二的 DP,可以发现它每一层(fif_ifi)的段数期望是常数

证明:考虑最小的一对满足 mmm 以内二进制最高位均为 111li,ljl_i,l_jli,lj,那么这一对可以保证 DPDPDP 数组的任意位置不超过 vi+vjv_i+v_jvi+vj。又根据算法四的分析,每一个权值和不超过 vi+vjv_i+v_jvi+vj 的子集的贡献不超过一段。

由于随机,viv_ivi 的分布是均匀的,故枚举 i,ji,ji,j 计算概率可得期望段数不超过 ∑i≤j2−j∑k=1i+jS(i+j−(k−12),k)=O(1)\sum_{i\le j} 2^{-j} \sum_{k=1}^{i+j} S(i+j-\binom{k-1}{2},k)=O(1)ij2jk=1i+jS(i+j(2k1),k)=O(1)SSS 表示第二类斯特林数)。

对于 mmm 不是 222 的幂的情况,可以分最高位和次高位分别分析,每一位产生的贡献都不超过上述的常数。

故,随机情况下 DP 数组的期望段数是常数。

那么只要记录每一段,暴力转移即可。

时间复杂度:O(n+q)O(n+q)O(n+q)(期望,子任务 4,5)或 O(nlogm)O(n\log m)O(nlogm)(子任务 3)或 O(nm)O(nm)O(nm)(子任务 1,2)
预计得分:100100100

E. MIN&MAX II

By CommonAnts,题解 By CommonAnts

  • 考察平面图染色基础知识。
  • 思维难度:NOI
  • 实现难度:NOI

算法一

枚举所有子区间暴力建图然后暴力算染色数。

时间复杂度:ω(qpoly(n))\omega(q\mathrm{poly}(n))ω(qpoly(n))
预计得分:000101010(子任务 1)

算法二

先考虑怎么求 G(p)G(p)G(p) 的染色数。我们有以下结论:

G(p)G(p)G(p) 是平面图

那么由四色定理 G(p)G(p)G(p) 的染色数不超过 444

通俗而言,令点 iii 对应平面直角坐标系的点 (i,pi)(i,p_i)(i,pi) 并将边连成线段即可。以下均在此平面嵌入的基础上考虑。

G(p)G(p)G(p) 是三角剖分图。(简单地说……对于上述平面嵌入不存在 >3>3>3 条边的“洞”)

考虑 C 题的相关结论即可。另外,也可以得到染色数为 111 的充要条件是区间长度为 111,不超过 222 的充要条件是序列单调。

那么只需判断染色数是否为 333 即可。我们有定理:

平面三角剖分图可以三染色当且仅当不存在一个奇轮子图。奇轮子图包含一个奇环和一个附加点,该点向环上所有点连边。

首先奇轮图显然不能三染色,故只需证明不存在的图一定能三染色。显然可以对每个点双联通分量分别考虑。

利用归纳法证明:一个不存在奇轮子图的点双联通的三角剖分图一定能三染色。

  • 如果点数不超过 333,显然满足。
  • 否则,必然存在一个点使得删去该点后图仍然点双联通:选择边界上的任意一点,若删掉该点后图不点双联通,则过该点必有一条边界上环的弦,递归到弦的一侧即可,最终必然有一个点满足删去该点后图仍然点双联通。
    那么,考虑与这个点相邻的所有点,必然满足隔一个点颜色相同:由于点双联通,对于中间的每个点,与之相邻的所有点颜色相间,又由于不存在奇轮子图,加入新点前点数必然是奇数,故与新点相邻的两侧的点必然同色。则与新点相邻的总颜色数为 222,故能够三染色。

那么暴力枚举区间建图判断即可。

时间复杂度:O(qn3)O(qn^3)O(qn3)
预计得分:252525(子任务 1,2)

算法三

基于算法二:一个排列对应的图含有一个奇轮子图,当且仅当存在一个点满足四个方向都有点(即四种连边条件都有一个点与之满足,该点不是前后缀最值)且度数为奇数。

那么记录一些中间值即可将复杂度优化到 O(n2)O(n^2)O(n2),且可以 O(n)O(n)O(n)G(p)G(p)G(p)

时间复杂度:O(n+qn2)O(n+qn^2)O(n+qn2)
预计得分:555555(子任务 1,2,3,4)

算法四

对于每个左端点,显然右端点向右移动时对应的区间染色数单调不降,故预处理出染色数变化的位置统计答案即可。

时间复杂度:O(n+qn)O(n+qn)O(n+qn)
预计得分:707070(子任务 1,2,3,4,5)

算法五

对询问按左端点排序,用线段树维护算法四即可(也可以用可持久化线段树做到在线算法)

时间复杂度:O((n+q)logn)O((n+q)\log n)O((n+q)logn)
预计得分:100100100

F. 抢红包

By triple_u,题解 By triple_u

首先声明题面中加入 Moejy0viiiiiv 与本人无关。

CommonAnts & samzhang:是我干的 QAQ

由于本题的数据范围在样例造好之后又进行了更改,所以初始时题面中出现了与数据范围不符的样例,如果对您做题产生影响,我深表歉意。

  • 考察选手的生成函数知识和多项式相关算法。
  • 思维难度:NOI
  • 实现难度:NOI

算法一

P(x,y)P(x, y)P(x,y) 为经过 (x,y)(x, y)(x,y) 的概率,则所求即为 ∑x,yP(xD,yD)\sum_{x, y} P(xD, yD)x,yP(xD,yD)

由于 N≤10000N \le 10000N10000,所以直接利用 P(x,y)=A⋅P(x,y−1)+B⋅P(x−1,y)P(x, y) = A\cdot P(x, y - 1) + B\cdot P(x - 1, y)P(x,y)=AP(x,y1)+BP(x1,y) 递推即可。

时间复杂度:O(N2)O(N^2)O(N2)
空间复杂度:O(N2)O(N^2)O(N2),可以使用滚动数组达到 O(N)O(N)O(N)
预计得分:999(子任务 1)

算法二

我们设生成函数 Fz(x)=zi=0P(i,zi)ximod(xD1),那么有 Fz(x)=Fz−1(x)⋅(Bx+A)F_z(x) = F_{z - 1}(x) \cdot (Bx + A)Fz(x)=Fz1(x)(Bx+A)。所求即为 [x0]∑i[iD≤N]FiD(x)[x^0] \sum_{i} [iD \leq N] F_{iD}(x)[x0]i[iDN]FiD(x)。我们可以直接通过枚举 iii 来计算。([xi]f(x)[x^i]f(x)[xi]f(x) 表示 f(x)f(x)f(x)xix^ixi 项系数,其余情况下 [][][] 表示逻辑真值)

时间复杂度:O(ND)O(ND)O(ND)
空间复杂度:O(D+M)O(D+M)O(D+M)(下同)
预计得分:212121(子任务 2,结合算法一)

算法三

FFF 求和可以考虑通过倍增的思想进行。

我们另 H(x)=(Bx+A)Dmod(xD1)SHn(x)=∑i=1nH(x)iSH_n(x) = \sum_{i = 1}^n H(x)^iSHn(x)=i=1nH(x)i

有转移

  • SHn+1(x)=SHn(x)⋅H(x)+H(x)SH_{n + 1}(x) = SH_n(x)\cdot H(x) + H(x)SHn+1(x)=SHn(x)H(x)+H(x)

  • SH2n(x)=SHn(x)⋅H(x)n+SHn(x)SH_{2n}(x) = SH_n(x)\cdot H(x)^n + SH_n(x)SH2n(x)=SHn(x)H(x)n+SHn(x)

时间复杂度:O(D2logN)O(D^2 \log N)O(D2logN)
预计得分:484848(子任务 2,3,结合算法一)

算法四

现在考虑有坑的情况。

在计算 [x0]∑iFiD(x)[x^0] \sum_{i} F_{iD}(x)[x0]iFiD(x) 时,我们可以对一段连续的不包含坑的 x+yx + yx+y 的值的区间 [l,r][l, r][l,r] 计算贡献。

如果我们能快速求出 Fl(x)F_l(x)Fl(x),那么就能将问题转化为无坑的情况了。

我们设 Gz(x)=∑i=0zP(i,z−i)⋅xiG_z(x) = \sum_{i = 0}^z P(i, z - i)\cdot x^iGz(x)=i=0zP(i,zi)xi

如果能得到 Gl(x)G_l(x)Gl(x),就可以通过在原 Fl(x)F_l(x)Fl(x) 的对应位置上减去相应的值得到有坑情况下的 Fl(x)F_l(x)Fl(x)

可以发现 GGG 的转移与 FFF 相同。

又由于所有坑 x≤Mx \leq MxM,所以只用维护 G(x)modxM

使用与算法二类似的朴素计算方法。时间复杂度

时间复杂度:O((D+M)N)O((D + M)N)O((D+M)N)
预计得分:565656(子任务 2,4,结合算法一、三)

算法五

在算法三、四的基础上考虑如何快速计算 Gz(x)G_z(x)Gz(x)

可以发现对于无坑区间 [l,r][l, r][l,r]Gr(x)=Gl(x)(Bx+A)rlmodxM[xi](Bx+A)m=(mi)BiAm−i[x^i](Bx + A)^m = \binom{m}{i} B^i A^{m - i}[xi](Bx+A)m=(im)BiAmi

可以通过一次多项式乘法进行转移。

时间复杂度 O(K(DlogD+Mlog2M)logN)O(K(D \log D + M \log^2 M) \log N)O(K(DlogD+Mlog2M)logN)

空间复杂度 O(D+M)O(D + M)O(D+M)

预计得分:100100100

共 6 条回复

kczno1
kczno1

C题打表可以O(S)

liu_cheng_ao

就是枚举 i,ji,ji,j 算概率……那个斯特林数就是假定分布均匀的情况下,和不超过 i+ji+ji+j 的子集个数 ……

lastans7

萌新求助D题算法5中期望段数公式的推导过程。。。@CommonAnts

samzhang

@Xenoacid,应该是压缩了的表。

Xeonacid

C题那个打出来的表是smg啊QAQ