题解

洛谷题库 P8868 [NOIP2022] 比赛

本文记号可能稍显凌乱,但都能在题面或者前文中找到定义。

部分分

20 pts\text{20 pts}n,Q3000n,Q\leq 3000

考虑枚举所有 O(n2)\newcommand\bigO{\operatorname{O}}\bigO(n^2) 个区间,预先计算它们本身的答案。记 ga(l,r)=max{ailir}gb(l,r)=max{bilir}\begin{aligned}g_a(l,r)&=\max\{a_i\mid l\leq i\leq r\}\\g_b(l,r)&=\max\{b_i\mid l\leq i\leq r\}\end{aligned},则做前缀和 s(l,r)=i=lrga(l,i)gb(l,i)s(l,r)=\sum_{i=l}^{r}g_a(l,i)g_b(l,i),对于询问 [ql,qr][\text{ql},\text{qr}] 只需回答 i=qlqrs(i,qr)\sum_{i=\text{ql}}^{\text{qr}}s(i,\text{qr}) 即可。

n,Qn, Q 同阶,时空复杂度 O(n2)\bigO(n^2)(更多…)

More
  • 2022年12月8日

这道破题拖了我整整一天。

代数推导

转化为容斥模型

题目所给限制可以表述为,aabb 均为单调不降的序列,长度相等(记为 kk),且 a1=0,ak=n,b1=0,bk=m,i[2,k],ai=ai1bi=bi1a_1=0,a_k=n,b_1=0,b_k=m,\nexists i\in[2,k],a_i=a_{i-1}\land b_i=b_{i-1}

考虑差分序列 ai=aiai1(i[2,k]){a_i}’=a_i-a_{i-1}\quad(i\in[2,k])bi{b_i}’ 同理,它与原序列形成双射。于是不存在 ai=bi=0{a_i}’={b_i}’=0 的差分序列合法。考虑 i=2kai=n\sum_{i=2}^{k}{a_i}’=n,也就是和为 nnk1k-1 元线性方程组的一组非负整数解;bb’ 同理。容易计算“钦定至少有 cc 个位置不合法”的方案数——利用容斥原理即可得到长为 kk 的合法序列对个数为 c=0k2(k1c)(n+(k1)1c(k1)1c)(m+(k1)1c(k1)1c)(1)c\sum_{c=0}^{k-2}\binom{k-1}{c}\binom{n+(k-1)-1-c}{(k-1)-1-c}\binom{m+(k-1)-1-c}{(k-1)-1-c}(-1)^c 答案累加上式结果 ×k\times k(更多…)

More
  • 2022年12月1日

Atcoder ARC149D – Simultaneous Sugoroku

官方题解做法是线性的,在此不再赘述。

考虑对于纸片 X=1,2,,max{Xi}X=1,2,\cdots,\max\{X_i\} 分别计算答案。每次暴力枚举显然不可取,但假若我们知晓对于 XX,在 i=0,1,,Mi=0,1,\cdots,M 次操作以后纸片在数轴上的坐标 x0=X,x1,,xmx_0=X,x_1,\cdots,x_m,其中 pos\text{pos} 是最小的取到 xpos=1x_\text{pos}=-1 的位置,则对于 x0=X=X+1{x_0}’=X’=X+1

  • 如果 pos\text{pos} 不存在,则所有坐标整体向数轴正半轴平移 11 单位;
  • 否则,pos\text{pos} 就将是起始点为 XX’ 的纸片首次到达 00 点的位置,也即题目所求。所有小于 pos\text{pos} 的坐标仍向正半轴平移 11 单位;而 pos\geq \text{pos} 的坐标,由于偏移量 DiD_i 符号翻转,则有 xixi1=(xixi1){x_i}’-{x_{i-1}}’=-(x_i-x_{i-1})。依次考虑每一坐标,就会得到 xi=1xi,posim{x_i}’=1-x_i,\forall \text{pos}\leq i\leq m。 (这里认为当 xpos=0x_\text{pos}=0 时仍然继续执行操作。维护 pos\geq\text{pos} 的坐标位置是为了计算 X>XX”>X’ 的答案。)

这是可以用区间树维护的:我们想要快速求出全局非正数最大值以及首次取到该最大值的位置,同时支持全局加 11、后缀所有数符号翻转×1\times -1)。那么同时维护区间非负数最大值、正数最小值以及首次取到他们的位置,采用延迟标记更新(两种操作对于前述信息是具有结合律的,形成幺半群)即可。

时间复杂度 O(max{Xi}logM)\operatorname{O}(\max\{X_i\}\log M),常数一般。

Submission #36155560 (更多…)

More
  • 2022年11月2日

LibreOJ #138 类欧几里得算法

题意

T1000T \leq 1000 组数据。给定 n,a,b,c[0,109],k1,k2[0,10],k1+k210n, a, b, c\in [0, 10^9], k_1,k_2\in [0, 10], k_1+k_2\leq 10,求取 x=0nxk1ax+bck2 \sum_{x=0}^{n}x^{k_1}\left\lfloor\frac{ax+b}{c}\right\rfloor^{k_2}

部分分——观察性质

k1=0,k2=1k_1=0,k_2=1 时,是为一般类欧几里得算法的模板。上述链接亦给出了 k1=0,k2=2;k1=1,k2=1k_1=0,k_2=2; k_1=1,k_2=1 时的解法。

k2=0k_2=0 时,该式退化为 x=0nxk1\sum_{x=0}^{n}x^{k_1},即 k1k_1 次的等幂求和。有一个模糊的结论:

nn 为正整数。则kk 次的等幂求和,x=0nxk\sum_{x=0}^{n}x^k,是一个关于 nnk+1k+1 次多项式。

该结论来源于 zyw 学姐多项式专题所选题目 BZOJ 3453 – tyvj 1858 XLkxc。之所以说模糊,是因为该多项式的系数是已知的。不过我们仍然可以暴力计算 k+2k+2 个点以插值。

再观察 OI-Wiki 上对于 k1+k22k_1+k_2\leq 2 时的解法。在求取 h(n,a,b,c)=x=0nax+bc2h(n,a,b,c)=\sum_{x=0}^n\left\lfloor\frac{ax+b}{c}\right\rfloor^2时采取了如下转化:

x2=2×x(x+1)2x=2(y=1xy)xx=0nax+bc2=x=0n2(y=1ax+bcy)ax+bc\begin{aligned} x^2&=2\times \frac{x(x+1)}{2}-x\\ &=2\left(\sum_{y=1}^{x}y\right)-x\end{aligned} \quad\begin{aligned} \Longrightarrow\sum_{x=0}^n\left\lfloor\frac{ax+b}{c}\right\rfloor^2=\sum_{x=0}^n2\left(\sum_{y=1}^{\left\lfloor\frac{ax+b}{c}\right\rfloor}y\right)-\left\lfloor\frac{ax+b}{c}\right\rfloor\\ \end{aligned}

这样一来,由于 yy 是一个线性算子,在 ax+bycax+b\geq yc 时都有 yy 向总和贡献,于是我们可以应用类似于 k1=0,k2=1k_1=0,k_2=1 时的方法转化贡献。这个过程对 k2k_2 作了降次。

那么,对于更高次项,有无办法采取同样的办法转化呢?是否可以设计一些转化,使得要求取的函数 f(,k1,k2)f(\cdots,k_1,k_2) 能够由 f(,k1?,k2?)f(\cdots,k_1-?,k_2-?) 推出呢? (更多…)

More
  • 2022年10月13日

形式化题意

给定 A+BA+B 个本质相同的随机变量,在 {1,2,,6}\{1,2,\cdots,6\} 内等概率取值。若两个随机变量 aA,bB,a=ba \in A, b \in B, a=b,则二者相消为 00。求在所有可能的消除完成后,存在 at,aA,t{1,2,,6}a \leq t, a \in A, t \in \{1,2,\cdots,6\} 的概率。对 109+710^9+7 取模。

朴素DP

cic_i 表示随机结果中数值为 iiAA 内变量数;did_i 同理。原题意可以转化为求出 1P(不存在小于等于ta)1-P(\text{不存在小于等于}t\text{的}a)。由概率的定义,我们可以用能造成后者局面的方案总数除以 6A+B6^{A+B} 既是结果。换句话说,原命题的否命题应当满足 i{1,2,,t},cidi\forall i \in \{1,2,\cdots,t\}, c_i \leq d_i

又因为这些随机变量本质相同,则由“可重集的排列数”得,若有确定的 c1,c2,,c6,i=16ci=Ac_{1},c_2,\cdots,c_6, \sum_{i=1}^{6}c_i=A,则掷出对应结果的方案数为 (Ac1)(Ac1c2)(Ai=15cic6)=A!i=16ci!\dbinom{A}{c_1}\dbinom{A-c_1}{c_2}\cdots\dbinom{A-\sum_{i=1}^{5}c_i}{c_6}=\dfrac{\color{blue}A!}{\prod_{i=1}^{6}c_i!} (更多…)

More
  • 2022年9月22日

Educational Codeforces Round 133 F – Bags with Balls

题目中存在高次项的和。则我们分别计算有 p=1,2,,np=1,2,\cdots,n 个袋子选择奇数号球时的方案。对于选择了奇数号球的袋子,每个有 m2\lceil \frac{m}{2} \rceil 种选择;偶数的则有 m2\lfloor \frac{m}{2} \rfloor 种。因此答案为: p=0npk(np)m2pm2np \sum_{p=0}^{n}p^k\dbinom{n}{p}\Big\lceil\frac{m}{2}\Big\rceil^p\Big\lfloor \frac{m}{2} \Big\rfloor^{n-p}

由于 n109n\leq 10^9,这式子看起来非常棘手。但我们注意到,有 k2000k\leq 2000,这提示我们或许应该转变对答案的贡献方式:从高次幂入手,找到 O(polyk)\mathrm{O}(\operatorname{poly} k) 而非 O(n)\mathrm{O}(n) 的算法。 (更多…)

More
  • 2022年8月8日

CodeForces Round #502 Problem G – The Tree

这是lty数据结构专题里唯二自己做出来的题目中的一道。

如果不包含“将 xx 的子树全部染白”的操作,应当怎样处理?

题目所给操作可以这样转述:令 xx 为本次染色操作的节点。若 xx 为白色,则立刻染黑并退出;否则我们找到其子树中的,与 xx 相连的黑色连通块,则对于每个连通块底部节点,若其不是叶子节点,我们将其儿子染黑。

由于本题的树没有特殊性质,且将来加入回退操作,故而难以维护整个连通块以及其叶子节点。因此,我们可以从“在何种情况下,节点 xx 被染黑”的方向考虑。

显然,只有从在 xx 到根的路径上的节点开始的染色操作,才可能波及到 xx。假如最终 xx 被染黑的一瞬,它被包含在了以 comprt\text{comprt} 为根的连通块中。令链 comprt,x\langle\text{comprt}, x\rangle{x1,x2,,xn},x1=comprt,xn=x\left\{x_1,x_2,\dots,x_n \right\},x_1=\text{comprt},x_n=x,那么自然想到,一种一定合法的染色序列是 {y1,y2,,yn}\{y_1,y_2,\cdots,y_n\},其中有 k[1,n]Z,yk{x1,,xk}\forall k \in [1, n] \cap \mathbb{Z},y_k \in \{x_1,\cdots,x_k\},也即我们每一步都在该连通块内部,并将连通块的最大深度推进一层

这种序列确实合法(它是充分条件),但这真的是 xx 被染黑的必要条件么? (更多…)

More
  • 2022年7月16日

洛谷题库 P4770 [NOI2018] 你的名字

本题考查对后缀数组或后缀自动机诸多性质综合、全面的应用,以及利用可持久化数据结构查询历史区间极值的方法。

也就是说,大体思路只花费一小时不到,去掉一个 log\log 却耗了我一天多……

@XZC__Bobby 花了 33 小时不到就用 SA 暴切了!!%%%

“双指针”扫描求串 TT 的每个前缀在 SS 中匹配的最长子串

在任何时刻,SAM 的状态转移函数会将某字符串引向串 SS 中的等价 endpos\mathrm{endpos} 状态。根据 endpos\mathrm{endpos} 和 parent tree 的性质,我们可以对前缀 T[1k],k{1,2,,T}T[1\cdots k], k \in \{1, 2,\cdots, |T|\} 依次求出其最长的作为 SS 的子串出现的后缀。 (更多…)

More
  • 2022年7月9日

一场相当有收获的比赛。比赛链接

A – 石老板举世无双

解法一

尝试观察规律。我们发现,在完成ss次操作以后,左端点的可能取值为xa+(2sx)b2s,x[1,2s]\dfrac{xa+(2^s-x)b}{2^s}, x \in [1, 2^s],右端点的可能取值为xa+(2sx)b2s,x[0,2s)\dfrac{xa+(2^s-x)b}{2^s}, x \in [0, 2^s)。假如现在我们达到最终状态,其l=(x+1)a+(2sx1)b2s,r=xa+(2sx)b2sl=\dfrac{(x+1)a+(2^s-x-1)b}{2^s}, r=\dfrac{xa+(2^s-x)b}{2^s}。那么,在xx的二进制表示中,如果从高到底pos\mathrm{pos}位为11,则在第pos\mathrm{pos}轮中,有check (mid) == 0,向右区间递归;否则向左区间递归。这是很容易解释的:若向右递归,则右端点不变。而在下一层,右端点表示中a,ba, b的所有系数乘22,所以体现为二进制位末尾添一个00。反之,就变成(x+(x+1))/2(x+(x+1))/2,在下一层中体现为2x+12x+1。如果其有popc(x)\operatorname{popc}(x)位为11,则到达该状态的概率为p0popc(x)p1spopc(x)p_0^{\operatorname{popc}(x)}p_1^{s-\operatorname{popc}(x)}

s=3s=3时的状态l=3a+5b8,r=2a+6b8l=\dfrac{3a+5b}{8}, r=\dfrac{2a+6b}{8}为例。22的三位二进制表示为0b010\text{0b010},则推断出在前三轮分别向右、左、右区间递归,到达其的概率为p0p12p_0p_1^2(更多…)

More
  • 2022年5月17日

考虑这个排列是怎样生成的。转述一下题意,可以发现,popcount(PiPi+1mod2n)=K\operatorname{popcount}(P_i \oplus P_{i+1 \mod {2^n}})=K,也即全集msk=2N1\text{msk}=2^N-1的一个大小为KK的子集。

由于这是一个环排列,我们不妨令P0=0P_0=0。这样一来,Pi=j=1iSj,Sj=KP_i=\operatorname{\bigoplus}\limits_{j=1}^{i}S_j, |S_j|=K。结合上文可知,这是一个相邻元素二进制位恰相差KK位的格雷码问题。有K=1K=1时,满足条件的SjS_j恰有NN个,也就是NN位格雷码。

考虑推广。我们发现,如果按照类格雷码的方式生成排列,则所有的SjS_j应构成异或空间,其大小应当恰为2N2^N,并且由线性空间知识可以得到,该线性空间的(基的大小)应当恰为NN。这恰好符合NN位格雷码的构造。因此,只要满足上述条件,就一定能够生成符合题意的排列。

可以证明,除了2K(K=NN>1)2\mid K \lor (K=N \land N>1)以外,总是有满足条件的线性空间生成的。

下述解法的时间复杂度O((NK)+2N)\operatorname{O}\left(\dbinom{N}{K}+2^N\right)(更多…)

More
  • 2022年4月11日