数据结构

我们可以将莫队算法从一维扩展到更高维度。

考虑正在维护 kk 维结构的信息,且每一维的大小分别为 n1,n2,,nkn_1,n_2,\cdots,n_k。为了下文叙述方便,我们将维度大小序列复制一份,得到 nk+1,,n2k(ni=nik)n_{k+1},\cdots,n_{2k}\quad(n_i=n_{i-k})。我们同时维护 2k2k 个指针,第 i  (ik)i\ \ (i\leq k) 个指针维护第 ii 维左端点,第 i  (k<i2k)i\ \ (k<i\leq 2k) 个指针维护第 iki-k 维右端点。按询问处理顺序依次移动到每个询问对应的位置上。 (更多…)

More
  • 2023年1月24日

又来了,要不然差临门一脚要不然是编译器出锅悬置指针导致了看似非常不合理的 undefined behavior。这已经不是简单的 frustration 了,要是考场上遇到这种根本没办法查出来的语言相关问题,不就三年 OI 一场空了么?

不过,正是因为考试前从没“用过”悬置指针,才会诱发这样的问题。这再次提醒我们,考场上千万不要使用不熟悉的语法糖,使用平时经大量验证的写法,纵使排版稍欠美观、或代码量增长少许,也是稳定而完备的。

不得不说,这几场“主题模拟赛”的题面中,唯这一场是最上心的。既将足球相关术语用平易近人的方式融合进题面里,又不使其过分冗长而消磨选手耐心。 (更多…)

More
  • 2023年1月23日

这是原论文中证明的简化版本,但不失其正确性。

mxx\newcommand\mx{\text{mx}}\mx_xxx 子树中最大值,smxx\newcommand\smx{\text{smx}}\smx_xxx 子树中严格次大值,fa(x)\newcommand\fa{\operatorname{fa}}\fa(x)xx 的父亲。称节点 xx关键点,当且仅当 xx 是根节点,或 mxfa(x)mxx\mx_{\fa(x)}\neq \mx_x。设变量 Φ\Phi 表示目前线段树上关键点个数。 (更多…)

More
  • 2023年1月23日

洛谷题库 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},(1lrn)0otherwisegb(l,r)={max{bilir},(1lrn)0otherwise\begin{aligned}g_a(l,r)&=\begin{cases}\max\{a_i\mid l\leq i\leq r\},&(1\leq l\leq r\leq n)\\0&\text{otherwise}\end{cases}\\g_b(l,r)&=\begin{cases}\max\{b_i\mid l\leq i\leq r\},&(1\leq l\leq r\leq n)\\0&\text{otherwise}\end{cases}\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日

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

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日