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

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日

CodeForces CF356E – Xenia and String Problem

这是一种不需要任何数据结构和处理字符串的工具,但细节繁多的做法。

设全串为 s1ns_{1\dots n}。不难发现,Gray string 的串长必然是 2w1(w1)2^w-1\quad (w\geq 1) 的形式。若其长为 2w12^w-1,我们称其为 w1w-1 阶 Gray string。

同时用归纳法可以证明,设一个 ww 阶 Gray string 的起始位置为 x+1x+1(其终到位置为 x+2w+1x+2^{w+1}),那么必然有 k{0,1,,w},sx+2k=sx+2k+2k+1=sx+2k+2×2k+1==sx+2k+(2wk1)2k+1i,j,0i<jw,sx+2isx+2j \forall k\in\{0,1,\cdots,w\},s_{x+2^k}=s_{x+2^k+2^{k+1}}=s_{x+2^k+2\times 2^{k+1}}=\cdots=s_{x+2^k+(2^{w-k}-1)2^{k+1}}\\ \forall i,j,0\leq i<j\leq w,s_{x+2^i}\neq s_{x+2^j} 成立。例如一个 33 阶 Gray string 可以被描述为 abacabadabacaba\mathtt{abacabadabacaba}(更多…)

More
  • 2023年1月5日

AGC058D – Yet Another ABC String

A,B,C\mathtt{A,B,C} 换成 0,1,20,1,2。记 a,b,ca,b,c 是题面中 A,B,C\mathtt{A,B,C} 的数量,n=a+b+cn=a+b+c。我们称位置 ii 不合法,当且仅当 Si2+2Si1+1Si(mod3)S_{i-2}+2\equiv S_{i-1}+1\equiv S_i\pmod 3。将其视为两条边 (i2,i1),(i1,i)(i-2,i-1),(i-1,i),那么所有不合法的位置造成的连边将会形成若干条链。

考虑容斥。直接钦定指定数量的位置不合法,其方案是难以计算的。又因为容斥系数是 (1)c(-1)^ccc 为钦定的非法位置数量,那么将整个串分成若干个部分分别计算方案,带上容斥系数相乘后累加,结果不变。故而尝试从上文的链入手:易得对于固定长度的一条链,能够连成它的非法位置集合不变。设 f(l,0)f(l,0) 表示“大小为偶数,且能够连成长度恰为 ll 的链”的非法位置集合数量;f(l,1)f(l,1) 则是大小为奇数。染色方案位置集合方案是独立的;则设整个串按顺序被分成了链 (l1,l2,,ls)(l_1,l_2,\cdots,l_s)(此处的“链”长度均不小于 33),答案即为 (l1,,ls)染色方案数((l1,,ls))i=1s((1)f(li,1)+f(li,0))\sum_{(l_1,\cdots,l_s)}\operatorname{染色方案数}\left((l_1,\cdots,l_s)\right)\prod_{i=1}^s\left((-1)f(l_i,1)+f(l_i,0)\right) (更多…)

More
  • 2022年12月16日

NOIP+?准省选难度?已经到了能力的边缘么?

但有点奇怪的是,这三道题的思考方向全部正确,T1 甚至只差临门一脚了;可惜部分分给得不那么让人舒服。

另外,这种“为了卡常而卡常”的时间限制着实令人不适;尤其是当 CWOI 的评测机本身配置落后的情况下。不过这也反过来使得我重新开始关注更底层的常数优化。

简略题解

A – 种花

(更多…)

More
  • 2022年12月16日

洛谷题库 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日

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

代数推导

转化为容斥模型

题目所给限制可以表述为,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日

T1 的 Hack 数据提醒我,尽管时间复杂度没有变化,但所有想到剪枝和常数优化在时限不充裕的题目中仍是必要的。

T2 没有认真读题,忽略了“恰执行一次”的要求。

T3 里面没有使用自己熟悉的存边方式,时间趋紧的情况下代码实现出错。这再次告诫我应以求稳为重。

简单题解

A – 跳棋

(x,y)(x,y) 跨步跳能够跳到 (x±2,y),(x,y±2)(x\pm 2,y),(x,y\pm 2),以及 (x+k,y+k),k=±2(x+k,y+k),k=\pm 2。可以发现 x,yx,y 奇偶性均不变。我们只需要考虑所有存在棋子的格子及其邻居。它们形成若干连通块,在这些连通块上 BFS 即可。

若采用 std::map 存储,时间复杂度为 O(7nlogn)\newcommand\bigO{\operatorname{O}}\bigO(7n\log n)。需要采纳“避免遍历不存在的连通块”之类的优化。 (更多…)

More
  • 2022年11月23日

仍然是中规中矩的一场模拟赛。前两题正解,第三题暴力,第四题不会。

简略题解

A – 激光

考虑是否有两条及以上双向连边,若是则无解,若有一条则枚举要将哪一侧的发射器旋转到哪一方向。简单模拟即可。

B – 碰撞

这类数轴上带标号小球相撞的题目都有一个经典套路:两球相撞调转方向时,我们不认为是球本身转向,而认为两球仍然保持原方向运动,而其编号交换(更多…)

More
  • 2022年11月20日