UOJ Logo liu_cheng_ao的博客

博客

UOJ Σ* Round #1 题解

2025-04-13 23:37:58 By liu_cheng_ao

UOJ Σ* Round #1 题解

写在前面

由于第二题原本的题目描述并不对应解法,且原本的题目表述是更为困难的问题,第二题题面应该进行修改。然而,发现这一点时比赛时间已经接近结束(我在复核题解证明的时候发现的错误),因此我们不得不遗憾地宣布,由于这一问题,我们现在对第二题的题目描述进行修改,并且本场比赛将不会计分(unrated)。

最开始的第二题游戏规则是这样的,没有现在这样的多轮操作:

首先艾莉芬在棋盘上放置一些带颜色的积木。然后蔡德仁可以对棋盘进行任意次操作,然后交给艾莉芬再进行任意次操作,之后棋盘会进行左、下两次操作把所有积木收拢到左下角。

这是我没有做足够的验证和数学证明中的失误造成的错误,再次向各位参赛选手深表歉意。

彩色括号

  • 题意、题面、题解:liu_cheng_ao
  • 标程、数据:WeLikeStudying

思路

问题研究对象是满足条件的括号序列:整体合法且删掉每种单个颜色之后都合法,那么考虑怎么判断一个括号序列是否满足条件。

括号序列合法当且仅当:

  1. 左右括号个数相等
  2. 所有前缀和非负(将 () 分别视为 $+1,-1$)

分别考虑:

  1. 由于整体左右括号个数相等且删掉红色之后左右括号个数还是相等,作差可以得到红色左右括号个数相等。同理每个颜色都如此。
  2. 考虑某个位置 $i$ 的前缀和,设红绿蓝的前缀和分别是 $a,b,c$,那么 $a+b,a+c,b+c,a+b+c\ge 0$。可以发现当 $a+b,a+c,b+c\ge 0$ 同时成立时,全部相加可得 $2(a+b+c)\ge 0$。所以 $a+b+c\ge 0$ 这个条件不用单独考虑。

所以总的条件是:

  1. 每种颜色左右括号个数都相等。
  2. 删掉每种颜色得到的前缀和分别非负。

这是判断条件。现在我们再考虑如何用最少的修改次数让一个括号序列合法,发现:

  • )( 一定是前若干个 )() 一定是最后若干个 (。可以调整证明。
  • 所以可以贪心:如果某种括号多,那么先改那种括号到数量平衡。然后从外往里每次将第一个 ) 和最后一个 ( 一起修改,直到前缀和全部非负为止。这就是最小修改次数。

加上颜色限制后,每种颜色内部还是符合这个条件。所以我们不妨先把每种颜色都改到数量平衡,设这样改完后的整个序列是 $a'$。

然后设 $x_1,x_2,x_3$ 分别表示三种颜色从外往里多改了多少对括号。我们目标是最小化 $\sum x_i$。

考虑合法性对 $x_i$ 的约束,现在的约束只剩下删掉每种单个颜色时每个前缀和都必须 $\ge 0$。

对于前缀 $j$ 来说,颜色 $i$ 增加的前缀和是 $\min(x_i,A_{i,j},B_{i,j})$,其中 $A_{i,j}$ 是前缀 $a'[1,j]$ 中 ) 个数,而 $B_{i,j}$ 是后缀 $a'[j+1,n]$ 中 ( 个数。另外设 $C_{i,j}$ 表示一开始颜色 $i$ 在 $a'$ 的前缀和。

可以列出不等式组:

$$ (\forall k, j) \sum_{i\ne k} (C_{i,j}+\min(x_i,A_{i,j},B_{i,j}))\ge 0 $$

将 $\min(\cdot,\cdot)\ge 0$ 拆开成 $\cdot \ge 0\land \cdot \ge 0$ 的形式,全部整理完以及合并同类项后可以得到一个不等式组:

$$ (\forall S\subsetneq U, S\ne\emptyset) \sum_{i\in S} x_i\ge C_S $$

其中 $U$ 表示所有颜色的集合 $\{1,2,3\}$,$C_S$ 是一个算出来的由 $S$ 决定的常数。

所以整个问题就是在这个约束下最小化 $\sum x_i$。因为颜色很少,三维空间上每个限制是一个平面,直接在每个面上都双指针枚举判定其它限制下的最优解即可。当颜色数更大时可以当成较一般的整数规划问题。

三种颜色的约束是在这个图的形状上求离原点曼哈顿距离最近的点:

图

算法

按照思路所说,先做让每种颜色左右括号数量平衡必要的修改得到 $a'$,然后枚举前缀算出 $A,B,C$ 数组,合并算出不等式组。

三种颜色的情况下,可以看成三个形如 $x_1\ge \cdot\land x_2\ge \cdot\land x_1+x_2\ge \cdot$ 的三段折线的二维偏序约束进行合并。两两枚举用双指针算出它们相交的折线,然后第三个约束在折线上的效果是约束折线只能取前一半。枚举所有折线上的点更新答案即可,一共 $O(n)$ 个。

或者你可以直接把它当成实数线性规划手算答案公式然后向上取整,在本题三种颜色的特殊情况下这是对的。

时间复杂度:$O(n)$

扩展

根据思路,显然我们可以做更多颜色的情况。设颜色数为 $k$,复杂度则为 $O(nk+ILP(k,2^k-2))$,其中 $ILP$ 是整数规划复杂度。枚举约束子集的朴素暴力算法复杂度不超过 $O(nk+2^{(2^k)})$。

本题考虑出四种颜色的情况,但鉴于选手的体验并没有这么做。

部分分

如果你没有发现不等式组,可以用双指针和区间数据结构算出每两种颜色的约束。(没有不等式组不容易发现约束只有三段,但至少可以发现是二维偏序上的阶梯型)

然后仍然可以 $O(n)$ 合并三个二维偏序约束算出答案。

时间复杂度:$O(n\log n)$

如果你只发现了一部分性质,可以做更前面的部分分。

积木对战

  • 题意、题面、题解、锅:liu_cheng_ao
  • 标程、数据:Yanami

思路

问题给了一个上下左右的操作方式,我们要研究它。不妨用 $LRUD$ 的序列表示操作过程。

观察问题并手玩一些例子,发现:

  • 显然相邻的 $L,R$ 会抵消,相邻的 $U,D$ 也会抵消。抵消之后操作序列中 $LR$ 和 $UD$ 只能交替出现。奇数位置和偶数位置是两个子序列,分别只有 $LR$ 和 $UD$。
  • 另外,形如 $RDR$ 或者 $RUR$ 这种片段,第二个 $R$ 没有效果(一个 $R$ 之后只要没有 $L$ 所有积木都是靠最右的),可以消掉。同理,$L,U,D$ 都如此。
  • 所以可以推出消到最简的操作序列按下标 $\pmod 4$ 恰好分别是 $L,R,U,D$ 四种操作。实际上,长的操作序列只能是不断重复“顺时针转圈” $LURD$ 或者“逆时针转圈” $LDRU$。

那么一个操作序列的基本效果是 $LURD$ 的不断重复。可以发现,在操作两步之后,所有积木都到了角落,之后如果只考虑积木的存在而不考虑颜色,那么所有有积木的位置是确定的(以下用“形状”来称呼所有积木的位置集合)。我们记每行积木个数的数组为 $\{r_i\}$,每列积木个数的数组为 $\{c_j\}$,那么 $LRUD$ 依次是给这两个数组中的一个升序/降序排序而另一个不变。而一旦积木堆积到了角落里,之后无论怎么操作积木都只能堆积在角上了,这种情况下知道了 $\{r_i\},\{c_j\}$ 就能唯一确定形状。

加上颜色之后,转一圈总的效果就是在积木之间进行一个置换,对于固定的角上堆积的形状来说,置换是确定的,设为 $P$,可以算出。顺时针($URDL$)和逆时针($RULD$)对应的置换恰好互为逆。

(到这里我们可以解决 [ROI 2024] 2026 (Day 1) 这一问题。)

我们会发现,只要积木已经堆到了角落,那么后续它怎么操作都能逆回去。所以堆积在左下角的方案数是置换 $P$ 作用于最终状态所能得到的所有不相等的状态种类数,也就是 $\lvert \langle P \rangle (A)\rvert$,其中 $A$ 表示最终的棋盘状态。这可以算出置换然后每个置换环上颜色列的最小正周期(复制一倍然后KMP求最大border)算出环的周期再求最小公倍数(筛法求出每个质因子次数)来得到。

然后我们要考虑不到一个周期的情况。要保证无论蔡德仁如何操作艾莉芬都能操作,所以一个必要条件是初始局面 $LD$ 和 $DL$ 两种操作得到的形状必须相同。

可以得到以下条件:

引理 1 一个矩阵 $LD$ 和 $DL$ 形状相同,当且仅当存在一行或一列为全空或全满,且删去这行/列之后的子矩阵的 $LD$ 和 $DL$ 形状相同。

  • 充分性:通过操作的定义证明原来的结果等于删去这行/列后子矩阵的操作结果加上这行/列的结果,然后归纳。
  • 必要性:假如不存在,那么每行每列都既有空也有积木,则 $LD$ 后第一列必定全满,$DL$ 后第一行必定全空,左上角这一格矛盾,必然形状不同。

然而,在此基础上,满足这个条件的局面在 $LD/DL$ 操作后得到的颜色分布有可能不同,且不能通过 $P$ 置换互换。所以不能直接用形状的方案数和颜色置换的方案数相乘!

反例:

010     100     100
234 [LD]200 [DL]300
050     534     254

计算出 $P$ 可以发现第二行第一个和第三行第二个位置是不会变的,所以不能通过 $P$ 互换两者,这说明该矩阵不是后面两个矩阵的合法解!

一开始的做法给这一点做了伪证,并且没有做足够的暴力验证。

做法认为:

一个初始局面是符合题目要求的,当且仅当:

  • 它可以通过不断删去当前全空或全满的行/列删到空。(形状条件)
  • 它在 $LD$ 之后得到的颜色分布可以被最终状态的置换生成。(颜色条件)

所以认为原问题答案等于形状的方案数乘以颜色的方案数。具体来说,形状的方案数等于 $\{r_i\},\{c_j\}$ 数组重新排序能得到的不同数组的数量,颜色的方案数如前文所述。

因此,实际上题目应该这样安排游戏规则:艾莉芬先操作一次,再让蔡德仁染色。但这样仍然需要给答案增加一些分类讨论和常数系数,因此被迫修改成现在的题面。对于现在的题意来说,这个做法是对的。

然而,原问题的困难性也没有得到证明,并且可以发现在 $LD/DL$ 之后的颜色分布可通过 $P$ 置换的情况是有一定规律的,原问题未必就没有做法。

算法

(对于没改之前的题面是假的)

形状的方案数:先算出 $\{r_i\},\{c_j\}$ 数组,然后根据数组里每种数的数量组合数计算。

颜色的方案数:算出最终状态上 $URDL$ 作用的置换 $P$ 然后求每个置换环上颜色列的最小正周期(复制一倍然后KMP求最大border),算出环的周期,再求最小公倍数(筛法求出每个质因子次数)。

两者相乘即为答案。

时间复杂度:$O(n^2)$

程序校验

题意、题面:OldDriverTree, liu_cheng_ao

题解、标程、数据:OldDriverTree

算法 1

每次暴力模拟,总时间复杂度 $O(nm)$,空间复杂度 $O(n)$。

期望得分 5 分。

算法 1.5

考虑对暴力算法进行极限卡常,但是本题操作本质串行,无法使用指令集优化。

这里介绍一种对指令集的通用攻击手段:计算连续访问数组的 L1 缓存缺失量。

强制在线会导致遍历数组时发生大量的 L1 缓存缺失。

为了卡常到极限,利用取模生效次数很少的性质,可以将 $a$ 数组和 $l$ 数组预处理的时候进行合并,这样对于每个位置,只会进行 3​ 次 ​8​ 字节的数组访存。

评测机的 CPU 的 L1 缓存行大小为 32B 的数据缓存和 32B 的指令缓存,每个核心的 L1 缓存总大小为 32KB 的数据缓存和 32KB 的指令缓存。L1 缓存命中时需要约 $4\sim5$ 时钟周期,缺失时需要约 $12\sim14$ 时钟周期。(这段是问 deepseek 的,该数据大致复合正常 CPU 的表现)

如果暴力算法可以通过,则 1s 处理遍历数组时发生的 L1 缓存缺失次数为 $10^5\times 5\times10^5\times 3\times 8/32/10=3.75\times10^9$,由于 CPU 的频率是固定的,所以对时钟周期进行计算可以发现该数据远远超过 CPU 访存极限。

不过对于数据范围较小的测试点,有优化后的暴力算法获得了非平凡的分数。

期望得分 5~15 分。

算法 2

针对 $d_i=0$ 的情况,观察发现取模最多进行 $O(\log v)$ 次,因为每次取模都会导致 $v$ 减半。

考虑每次使用数据结构高效找到接下来第一次该数会发生取模的位置,等价于给定 $x,v$,求 $x$ 后面最近的一个区间,使得区间包含了 $v$。

这个问题可以倒着从后往前维护持久化值域线段树,维护每个值最近被覆盖的时刻,每次加入一个区间的时候做区间染色。

于是对每个位置 $i$,我们有一个持久化值域线段树,支持给定 $v$,查询从 $i$ 开始 $v$ 第一次被覆盖到的时刻。

总时间复杂度 $O(n\log v+m\log^2v)$,空间复杂度 $O(n\log v)$。

期望得分 15 分。

算法 3

如果所有询问的 $R$ 都等于 $n$,有一种持久化平衡树做法。

先考虑简化的,没有 $l_i,r_i$ 限制,并且 $d_i=0$ 的问题。

倒着维护每个后缀的函数复合结果,$f[i][j]$ 表示从 $i$ 开始,初始是 $j$,经过函数复合后到 $n$ 位置的值是多少。

初始是 $f[n][i]=i$ 的恒等映射,使用所谓的 “整体DP” 的思路,还是从后往前倒着维护,每次在原函数复合结果 $f[i+1]$ 前加一个新的函数复合得到 $f[i]$ 时做一个区间复制。注意到这里需要将一个区间变成另一个区间复制多次,这个可以用倍增合并的方法实现单次 $O(\log v)$。

特别需要注意的是,对于持久化 treap 来说,区间复制 $k$ 次的倍增合并是 $O(\log^2v)$ 的,而对于其他拥有更加优秀性质的平衡树(如 WBLT,AVLT),该操作是 $O(\log v)$ 的。

图

这样可以 $O(n\log v)$ 预处理出每个后缀的持久化平衡树,支持每次 $O(\log v)$ 查询给定 $x$ 和 $l$,求 $x$ 经过 $[l,n]$ 区间函数复合后的结果。

再考虑如果有 $l_i,r_i$ 的限制,并且 $d_i\neq 0$ 该怎么办。可以发现持久化平衡树功能非常强大,区间的限制可以通过每次对 $f[i]$ 只修改其 $[l_i,r_i]$ 部分,其他部分保持不变来实现。$d_i\neq 0$ 可以通过每次对 DP 数组做一个区间平移操作实现,可以用持久化平衡树的操作简单实现。

针对 $R=n$ 的情况,总时间复杂度 $O(n\log v+m\log v)$,空间复杂度 $O(n\log v)$。

期望得分 35 分。

算法 4

回顾算法 2,持久化值域线段树功能受限无法进行区间平移和复制操作,考虑将其换成持久化平衡树来支持更强的操作。

于是倒着从后往前维护持久化平衡树,维护每个点最近被覆盖的时刻,每次的操作有区间染色,区间复制,分裂合并等,都是持久化平衡树支持的操作。

对每次查询,使用预处理好的数据结构每次 $O(\log v)$ 找到最近一次取模的位置,需要取模 $O(\log v)$ 次。

总时间复杂度 $O(n\log v+m\log^2v)$,空间复杂度 $O(n\log v)$。

期望得分 55~75 分。

算法 5

我们发现对于 $R=n$ 我们可以每次 $O(\log v)$ 查询出答案,所以可以对序列分治建立线段树,对线段树的每一层,问题变成 $L=1,R=n$ 的子问题。

每次查询需要按顺序找到 $[L,R]$ 区间的 $O(\log n)$ 个线段树结点,将 $v$ 依次代入得到经过区间函数复合后的结果。

这个方法可以顶层分块,底层分块,将线段树变成多叉线段树来极大地减少常数。

顶层分块:可以发现线段树的根结点的没有用的,只有 $L=1,R=n$ 的查询才会用,所以可以不建立。继续分析可以发现线段树的最上面几层如果拆掉后,会减少预处理复杂度,少量增加查询复杂度。

底层分块:可以发现线段树的叶子结点是没有用的,如果建立的持久化平衡树,则每次查询是 $O(\log v)$ 的,还不如暴力。于是可以底层区间很小时直接暴力计算答案。

多叉线段树:可以发现线段树加上底层分块和顶层分块后二叉就不优了,于是将线段树改为多叉的。

利用右儿子:可以发现线段树结点可以直接从其右儿子处继承过来持久化平衡树,然后只需要将左儿子的部分插入即可。

图

利用左侧查询的优势:可以发现询问的部分如果是某个线段树结点的后缀,则可以不用暴力,而是用持久化平衡树的一次查询代替。

图

总时间复杂度 $O(n\log v+m\log^2v)$,空间复杂度 $O(n\log^2 v)$。

这个算法没有利用取模的特性,所以不优,在其他没有好的性质的题中是已知的最优做法。

利用以上技巧极限卡常后,期望得分推测为 55~85 分。

算法 6

我们考虑使用 “全局平衡” 的思想,类似于树链剖分套线段树的那种问题,每次查询如果需要在 $O(\log n)$ 个子问题上花费 $O(\log n)$ 的代价二分,导致复杂度是 $O(\log n) \times O(\log n)=O(\log^2n)$,如果将两种二分的结构套起来,构造出一种常数层减半的结构,就可以做到 $O(\log n) + O(\log n)=O(\log n)$。

我们在这个问题上,尝试将一开始的持久化平衡树的做法进行拓展,使得其可以进行区间查询,并且将第二,四种暴力做法的思想结合进去,即利用每次只会发生 $O(\log v)$ 次取模的特性。

图

我们在持久化平衡树上维护每条边的边权,有两种颜色的边,分别是红色和黑色。红色的边的含义是下方结点是某次取模导致的区间复制复制产生的,黑色的边的含义是正常持久化平衡树的边。

每个叶子结点到根结点的路径上最多只有 $O(\log v)$ 条红色的边,因为每走一次红色的边相当于找到了一次发生取模的事件,取模的性质保证只能发生 $O(\log v)$ 次取模。同时由于持久化平衡树是平衡树,所以可以保证每个叶子结点到根结点的路径上最多有 $O(\log v)$ 条黑色的边。

具体实现的时候,我们需要对每条红色的边记录下这条边是序列上哪个位置产生的,持久化平衡树的重新平衡(如旋转)仅限于对黑色的边,对红色的边是不做重新平衡的。平衡操作可以看做是产生新的边,以及将原本两条新的边压缩为一条边。由于我们是通过红色的边来找到每次取模的位置的,所以重新平衡的时候对红色的边做平衡操作会使得找取模位置的时候少找了一些,只能对黑色的边做操作。

每次查询 $[l,r]$ 区间,输入 $v$ 时,先在 $l$ 位置的持久化平衡树根结点上开始查询 $v$,在查询的过程中每次走一条红色的边则意味着发生了一次取模,走黑色的边则是为了保证持久化平衡树的深度所必须走的。这样我们可以用 $O(\log v)+O(\log v)=O(\log v)$ 的时间复杂度找到 $[l,r]$ 区间查询时所发生的所有取模事件。在递归查询的过程中如果发现走到了一条时间 $>r$ 的红色的边,则不需要继续递归了。

其实可以进一步解释本题做法,我们需要维护一个 DAG 结构,使得从任何点出发,该 DAG 深度是 $O(\log v)$ 的。虽然暴力的计算图的 DAG 深度是 $O(n)$ 的,但是我们只关心取模的位置,所以对于不是取模的操作可以将其合并在一起来减少 DAG 的深度。利用持久化平衡树深度以及取模次数的性质,可以构造出一个满足我们要求的 DAG 结构,每次查询本质上是在预处理好的深度 $O(\log v)$ 的 DAG 结构上进行 DFS。

本做法对于其他持久化平衡树做法有显著优势,因为其他做法需要多次查询持久化平衡树,本做法只需要一次查询,虽然本做法的平衡树由于“全局平衡”的性质所以常数比正常平衡树大。

总时间复杂度 $O((n+m)\log v)$,空间复杂度 $O(n\log v)$。

期望得分 100 分。

UOJ Σ* Round #1 公告

2025-04-02 16:41:39 By liu_cheng_ao

UOJ $\Sigma^\ast$ Round #1 将于 4 月 13 日星期日晚上 17:00 举行!比赛将进行 5 个小时,共三道题,和 UOJ NOI Round 赛制相同。

这是 UOJ 第一场 UOJ $\Sigma^*$ Round,NOI 难度,欢迎大家来玩!

UOJ $\Sigma^\ast$ Round 是 LCA 主办的系列比赛,希望大家参赛愉快。

在形式语言中,$\Sigma^*$ 表示“所有”字符串的集合,你能从无数字符的海洋中找到问题的答案吗?

比赛链接:http://uoj.ac/contest/96

出题人:liu_cheng_ao et al.

参加本次比赛将有机会获得 LCA 的神秘礼品!前三名均可获得礼品。

除此之外特殊获奖条件的 SHA256 码是 48405573d9ac7a841e4860fab6036961bd8a2e7404027595e7a84b47c7771b6b,比赛结束后将公布条件。

附启:你可以加入 LCA 的教学研究 QQ 群 435253885


赛后结果更新

特殊获奖条件公布:三道题得分均大于0的选手中总分最低的,如有并列就取最后一次提交最晚的。

比赛消息更新

由于第二题原本的题目描述并不对应解法,且原本的题目表述是更为困难的问题,第二题题面应该进行修改。然而,发现这一点时比赛时间已经接近结束(我在复核题解证明的时候发现的错误),因此我们不得不遗憾地宣布,由于这一问题,我们已经对第二题的题目描述进行修改,并且本场比赛将不会计分(unrated)。

这是我没有做足够的验证和数学证明中的失误造成的错误,再次向各位参赛选手深表歉意。

礼品仍然按照原成绩进行发放。

fa025fd8c420225402faf6e7df41ed2e

LCA的省选NOI长训公告(第二期)

2024-12-07 07:59:47 By liu_cheng_ao

LCA的省选NOI长训公告(第二期)

LCA 的 OI 课堂开课辣!

fa025fd8c420225402faf6e7df41ed2e

2024 年 12 月 11 日起,LCA 的第一届省选 NOI 长训(第二期)将在山东省青岛市举行。也可选择 12 月 18 日开始参与。

本次长训以线下全日制集训形式进行,每年一届分为四期,每期约两个月。由LCA实际主讲,并且有lxl等多名跳蚤国神秘嘉宾担任命题、助教和教务等工作。其中,部分节假日或比赛前会有短期集训,期间会有更多高水平旅客讲课和紧凑的模拟赛。


目前,在 NOIP 以上的省选、NOI 水平的学习过程中,同学主要通过大量刷题、模拟赛训练来提升实力。在遇到困难和瓶颈时,缺乏科学的方法去分析具体的知识、学习情况和应对策略,往往只能粗略地增加某一类型的刷题数量,或者尝试在自学和同学交流的过程中自行领悟一些算法和数学方法。

仅有的几个省选 NOI 长训,也是基于这些传统的讲课、刷题、模拟赛、同学自学交流开展的,缺少具体的教学方法帮助选手高效发现问题和提升深层次的理解和解题能力。

不过,近几年的 OI 同学们已经发展和引入了不少一般性的算法知识理论和教学方法。我们也有幸为 OI 社区的学习资源做出一些贡献,用学术方法改进 DP、字符串等知识的深入理解,引入组合模型和计算理论等提高同学们研究和解决算法问题的能力,尝试题解补全、算法数学练习、问题改编研讨等新的教学技术和形式,并在近年山东、河北、江苏各省省队集训等课程中得到初步验证。

因此今年起我们计划开展长训课程,邀请全国各地达到一定水平并计划冲击省队 NOI 的选手进行更为科学的长线训练。


一些教学研究的笔记 https://loj.ac/d/4518

299f518daea1adc6d8518d47e59dda3a

测试

本期入营名额按照 NOIP 实际成绩等标准分配,参加过上期集训的同学也可优先。之前的测试赛内容均已在洛谷公开。

教学改进

省选/NOI 难度 传统教学 本次教学
学科体系 零散的算法知识点和题目 基于数学和算法科学的体系,带学生理解问题的实质和研究方法
教学内容 只有算法模板、变体和数学概念、例题 还包括描述和研究问题的数学模型、算法设计方法等
教学方式 讲课+刷题+模拟赛+答疑 还包括多种系统性解决问题的数学思维练习和研讨,如问题改编等
解题方式 以题感为主,方法靠自学领悟 理解数学方法,稳定记录和推进对问题的认识
作业题单 - 尽量覆盖各种OI中的技巧和应用
模拟赛 - 有编审对题目质量和难度进行把控,保证每场训练的有效性,避免低效题目如思维难度低的大代码毒瘤题、超纲的偏题怪题等。每个月有公开原创月赛。

日常训练采用讲练结合的模式,全日制上课,有理论课、交流研讨课、晚自习(有答疑老师),并安排体育活动,劳逸结合。

课后作业除了常规训练题单外,增加了算法数学练习。

交流研讨课注重算法数学练习题讲解讨论,鼓励学生进行好题分享、算法想法分享和解题交流等,另外还会开展题目研讨课,对题单或模拟赛题目进行深入研究,通过改编等方式探究各种问题的一般性推广,并讲解相关 OI 应用和学术拓展知识,增进学生对知识的理解和问题模型的研究能力。

基本信息

  • 时间 2024 年 9 月 24 日到 2025 年 7 月中旬,按照NOIP-省选-NOI时间分为四期,每期约两个月,两期之间根据正式比赛时间休息约 1 到 2 周。每周三到周一下午上课,周一晚上和周二休息。本期(第二期)上半部分时间为 12 月 11 日(可选择 18 日开始参与)到 1 月 13 日,下半部分将在过年后到联合省选前举行,具体时间待联合省选时间和学生具体省份安排为准。

  • 地点 山东省青岛市某中学,线下全日制集训。

  • 教学团队 刘承奥(蔡德仁/LCA/CommonAnts)主讲,另有多名 NOI 水平助教参与工作。此外,有多名 NOI 金银牌高水平同学共同学习。

090e2a2d7d61c6f49554018d16bb117d

招生信息

  • 招生范围 招收全国 NOIP 300 分以上或同等水平的同学,以及 NOIP 成绩在自己省份有较大希望进入省队的同学,并且家庭和学校支持接受全日制线下集训。

  • 招生人数 总人数不超过30人。

  • 报名方式 按期报名,一期起报。有意向同学可以填写问卷:问卷链接

  • 学习费用 按期收取,根据不同基础成绩享受不同优惠,多人团体报名另有优惠。详情请在填写问卷之后咨询。

  • 补贴 参与互测等任务的同学可按工作内容标准获得现金补贴。

  • 奖学金 根据 2024 年 NOIP 和 2025 年省选/NOI/IOI 成绩设有奖学金。详情见下文附录。

  • 教学基金 勰码和刘承奥均已出资成立教学基金,专项补贴部分有经济压力的同学顺利完成营地训练计划,可用于缴纳学费、住宿费、承担生活费等在营期间的学习、生活基本支出。受资助同学需要承担部分建设 OI 社区公开学习资源任务和教学任务(教学可选在退役后进行),以推动 OI 发展以及营地教研、积累教学经验。具体细则和申请流程详见联系方式。

报名&联系方式

  • 报名请填写问卷 问卷链接 https://www.wjx.cn/vm/QsK1X7K.aspx

  • QQ咨询教学详情 1913272728 (蔡德仁/刘承奥/LCA/CommonAnts)(主要咨询教学内容,关于管理、报名和费用等请填问卷后等待专人联系)

c8b63adf03f91528f709f7bc8bbd2bb6

蔡德仁随笔:~一些 OI 教学研究的故事~

2024-09-14 21:51:12 By liu_cheng_ao

蔡德仁随笔:~一些 OI 教学研究的故事~

问题求解

知识点不只有算法

2017 年,距今七年之前——当时省选的主流 OJ,BZOJ 因故暂停服务,我作为一个学生参与 LibreOJ 的创建。在起初添加题目标签系统时,我们感觉到“OI 中似乎有两类不同的知识点”,然而,谁也说不清楚两者到底是什么,只好草草归结为“一般的理论或思想”和“具体的有模板题的知识点”,这就是 LibreOJ 玫红色和草绿色两种标签的由来。

时过境迁。大学二年级起,我们学习了一般的算法设计、计算理论。许多曾经模糊的、玄之又玄的思想和理论渐渐有了它清晰的面貌和数学上明确的表达与应用。那时,我意识到 OI 中确实存在两类不同的知识点——但不是什么宽泛和具体的对立,这二者的分野对研究算法和解决问题没什么意义。OI 中真正的区别在于组合模型与算法,也就是问题研究对象的结构和算法问题本身的性质。

例如这个经典例子:一个长为 $n$ 的序列 $\{a_i\}$ 每一项是 $1\dots m$ 之间的整数,给定若干个限制,每个限制的形式是 $l,r,u,v$ 表示 $a_{l\dots r}$ 这一段的最大值必须在 $[u,v]$ 内,问方案数。

这个问题的形式是统计方案数。最基本的做法是尝试判定一个特定的方案是否满足条件。这里,我们研究的是数学对象是序列上一些区间的最值。序列区间最值的结构是笛卡尔树——因此我们在笛卡尔树上的 LCA 处检查限制。于是,我们就找到了一种按照遍历笛卡尔树的顺序逐位判定某个方案是否满足条件的算法。直接对这个判定算法过程的状态压缩就可以得到一个递推(DP)算法统计方案数。也就是 $f(i,j,k)$ 表示区间 $a_{i\dots j}$ 最大值为 $k$ 的方案数,转移顺序表示最值结构(笛卡尔树的形状),再进行优化。

这里,问题求解有几个步骤: - 问题研究的组合对象:序列区间最值结构→笛卡尔树 - 根据笛卡尔树容易得到朴素的判定算法 - 问题形式-计数:从判定到计数→DP的基本方法 状态机-状态压缩 - 算法优化:经典的DP优化方法,状态合并、数据结构(前缀和等)

可以看到,这里存在两个知识点:“笛卡尔树”刻画序列区间最值结构,“递推/DP DP优化”在之后解决计数问题。换言之,OI中存在刻画问题的组合对象以及算法形式两个主要任务,它们是不同的。

问题在于,传统的OI训练完全是以算法形式(算法模板、模式、优化技巧)来组织的——因为只有算法会有模板题,组合对象在传统教学中不存在。除了笛卡尔树等少数,绝大多数的组合知识点尽管重要,却完全被忽略,只能在所谓的“杂题选讲”,DP/贪心/构造题单中寻得只鳞片爪。更严重的是,表示、推导、研究组合模型性质结构的方法几乎没有任何系统学习的意识。大半的NOI金银牌在半天内做不出任何有三、四个引理的组合推导问题(比如这样的)。对于那些没能从同学交流或自学组合数学悟出道理的多数同学来说,七年前和今天都是如此。

除了组合,一切没在算法模板题和经典教科书注册了位置的的数学也都如此被忽略。例如 OI 中这个常见的推导:最大化绝对值和 $\max(\sum \lvert x_i-y_i\rvert)$。

$$ \begin{aligned} &\max(\sum \lvert x_i-y_i\rvert)\\ =&\max(\sum \max(x_i-y_i,y_i-x_i))\\ =&\max(\sum \sigma_i(x_i-y_i))\\ \end{aligned} $$

将绝对值(或者曼哈顿距离、方差等类似的东西)写成参数最值,然后利用最值方向的一致性通过变量分离等简化最优化权值的范围/形式。本来,这个出现次数不少的技术也应当是一个知识点,但传统教学中学生很难意识到这一点。这导致不管是自己做题,还是题单、选讲等课程都很难避免学习中遗漏和忽略这类方法。

因此,在教学中传达这些现代数学的研究意识是必要的。任何的关键点、难点都应该被研究。例如 OI知识点的字段和类型 所写的。为了达到这一点,一些笔头的算法数学的练习、研讨也是必要的。

数学语言与一句话题解

《西江月·证明》 ——佚名

即得易见平凡,仿照上例显然。

留作习题答案略,读者自证不难。

反之亦然同理,推论自然成立。

省去过程QED,由上可知证毕。

每个 OIer 大概都有过对着题解抓狂的时刻。面对“单调性一下就行了”“注意到可以二分图染色并给白色权值异或1”……种种一句话题解,如同见到了一座精致的牙雕,但是谁又能想象出生长它的大象的样子呢。

对于个人笔记,一句话题解记录的是问题中的关键认识。表面上看,一句话题解看不懂可能有数学符号的含义没有标明,跳过表述等原因。但更多的问题在于,这个性质的前因后果是什么?(谁具有这个性质?哪里用到这个性质?)它的数学目的是什么?(能解决什么问题?没有为什么不行?有/无这个性质的区别是什么?)它能否推广到其它的情况?(改条件还成立吗?对于其它模型、问题能否诱导出类似的?)

这些是研究数学问题的一般方法。我们希望自己能通过一点例子举一反三,那么不妨试一试从这个例子中的关键点开始研究。

在今年的江苏省队集训(有四五个 NOI 金牌的同学参加)中,我出了自认为难度接近的 3 道题目,但实际结果却有些出乎预料。3 道题中有一道好几个同学会做,但另外 2 题却没人得出正确的思路。和同学讨论了想法和做法的细节后,我注意到这样一个事实:我们研究问题的思维方式是不同的。同学们做题的时候,往往找到问题的一个大概的模型(比如二维点、树上路径、二分图、生成函数等某个比较宽泛的对象)之后,根据自己的解题经验观察和尝试该模型上适用的算法模式/技巧(比如对于树上路径来说,尝试按LCA分类/启发式合并、树上差分、分治、倍增等手段),将其套入问题看是否能够满足条件和性质或联想做过的类似问题算法做些调整。

这一做法的问题是,对问题研究对象本身没有稳定的刻画,在不断尝试过程中,之前推导的性质观察往往被浪费。一次又一次地“重做”这道题,直到某个幸运时刻猜对了大体的做法,然后利用题感和经验完成细节工作。这对于整体不太经典(即使每个部分的推导都很常规)的问题就很难做了——甚至很多处理方法相当直接的问题都被称为 Ad-hoc。

举一个例子。有一排 $n$ 条鱼体型为正整数 $\{a_i\}$,可以让一条鱼吃掉另一条相邻的,体型不大于自己的鱼,并且体型加上被吃的鱼的体型。每次问一个范围,问里面哪些鱼能吃光范围内的其他所有鱼。

首先,容易发现,任何时候一条鱼的状态对应一个区间。然后,只有那些“极大”的,也就是无法继续吃掉左右相邻鱼的区间是有用的。到这里,我们作为“题感”选手迅速发现了一个事实:每次从极大区间跳到一个更大的极大区间,区间和(鱼大小)至少翻了一倍,容易得到总的层数是 $\log a$ 的。

到此为止——我们可以轻易用倍增、线段树等算法配合 $\log a$ 的势能来在可接受的时间复杂度内解决问题。然后 AC,下一题。

然而,等等。这时候我们对问题的认识足够充分吗?

想想一般方法。我们应该刻画问题的研究对象,并且不断加深对它的认识。对于这个问题来说,上面我们已经得到了刻画问题的关键是极大区间的结构。而我们容易证明:不能有两个极大区间在相交的同时互不包含。否则,假设有 $[a,c)$ 和 $(b,d]$ 两个极大区间满足这点且 $a\le b\le c\le d$,那么 $[a,c)\ge b\gt (b,d]\ge c\gt [a,c)$(这里的不等式比较的是对应的鱼体型总和),矛盾。极大区间一定满足它相邻两侧的数字比自己的区间和还要大,这会导致矛盾。

所以这是嵌套集,可以用一棵有根树的每个子树(对应的DFS序区间)来表示。上面的性质也对应了树高不超过 $\log a$ 等等。更重要的是——当我们想进一步研究这个问题时,只要研究这棵树就行了。显然,找到这棵树比起只是套用倍增、线段树解决特定问题,我们的认识深刻得多。

在一开始就刻画问题的研究对象,并不断推进认识——而不是直接尝试套用各种技巧。这是不那么依赖题感和灵感的一般方法。想想自己如果要打表找规律,该对谁打表(问题研究的关键数学对象),用什么格式输出(表示和刻画它的可能手段)。

题感做题就像盲人摸象,反复探索各个部位,不同局部性质难以联系,尝试很多次才能逐渐得到整体认知。而如果先知道了象的大致形态(问题的研究对象和可能的表示),再对具体的部位做研究逐步填充,局部之间是有联系的,自然探索起来事半功倍。

一句话题解令人迷惑,也往往是因为我们并不知道在问题中要刻画什么,因此缺乏目的。没有主语只有谓语,自然是读不懂文章的。反过来说,能把一句话题解的数学逻辑补全,也是一种可行的练习方式。

举一反三的计算理论

计算理论是另一个竞赛传统教学未曾意识到的部分。

问题类、归约、计算复杂性、计算模型——现在 OI 算法已经发展到了需要这些一般理论和思想的地步。具体到各类具体的算法,更一般的算法设计思想也很重要。OI 正在逐渐习惯基于组合结构的算法复杂性分析,或者基于自动机、等价类等的字符串研究(就像IOI2024D2T1)。生成函数云云更不可能被人力禁止。总之,OI 开始需要一些研究能力——而不只是学会一些经典算法和应用然后局部改编。

最近某位同学的一个问题可以作为例子:

问:有这么一个问题:删边加边MST(最小生成树),离线。使用线段树分治的前提下,存在一种并查集做法:在一个节点上,下传下来一些边,表示可能在MST里面(它们都已经完全覆盖这个节点),在这个节点上,忽略子树边,把所有完全覆盖的边掏出来,如果不在MST就永远没用。把子树边全加入,再把完全覆盖的掏出来,如果在MST就永远有用。后者缩点,前者删除,剩下的下传。

这个算法似乎有些反直觉。这个东西是否有拓展或者可能源于更加本质的某个事物??

(思考了一段时间之后)

这里面,是否:问题的核心在于保证递归到一个节点时候的有效点/边数量? 我想说,这个算法并不容易归结为最基本的mst方法和线段树分治的简单结合,而是有一点它自己的东西。它的牛逼之处在于对于复杂度的保证。 而这一点,是否有推广?或者说,就可以把它当作一道孤题,不再细究?

这位同学实际上已经注意到了问题的关键。学术上,这是数据结构的一个非常基本的思想。为了解释这个问题,我们可以考虑把它推广到MST以外的其他问题上并做一个比较。

答:这个怎么推广——感觉找到一些和MST有类似性质的东西还是不难的——比如二维偏序极值(有一堆区间,要求插入区间删除区间,用线段树分治处理,维护所有不被其他区间包含的区间组成的序列,也就是所谓动态单调栈或者说动态前缀最值)。

把维护MST换成维护二维偏序极值,这个技巧还适用,但可能需要更复杂的均摊。

具体来说就是得按子树内涉及到的操作参数对数轴进行分段(值域压缩/离散化),然后把上面继承下来的潜在的极值序列坐标同属一段的缩起来处理。每一段要么同时不是极值,要么同时是极值。

核心点在于,线段树分治的一个 $m$ 大小的节点的子树内可能涉及到的操作数是最多不超过 $m$ 的(或者有些问题 $m\log m$)。而在很多问题中,$m$ 个操作实际上最多也就只能区分出 $m$ 组本质不同的信息。 就像在长为 $n$ 的序列上做 $m$ 次区间加也可以分段缩点(值域压缩/离散化)把序列规模缩小到 $O(m)$。

而MST也满足这个条件(图里只有 $m$ 条边待考虑时,图待定最小生成树的规模也可以缩到 $O(m)$ 表示),所以也可以这么做。这实际上在组合对象里是非常常见的性质,并不是MST特殊的。

所以其实大部分线段树分治都可以这样处理。这也是数据结构的一个标准方法,操作少的时候,就是可以按“能否被不同操作区分”对原来的组合对象进行缩点,使得总规模变成和数据结构操作有关的。

当然,也有不满足这个的。比如动态增删物品的背包。因为只要达到 $\log V$ 个物品信息量就是 $\Theta(V)$ 的。

这位同学很快发现了其他应用。

有一个应用:P7361 拜神

首先这个题有一个显然的3log做法:二分,然后看区间max lcp,这个东西可以掏出来1log个支配对 ,再来一个log是线段树之类的。这是粗略的分析。当然实际上本题有一个优点:因为修改是1log,而查询没有log,那么二分的那个log正好补上来。所以这实际是2log。

另一种算法:整体二分。然而整体二分导致了按理来讲必须是3log。它加入支配区间,然后其实就是覆盖了一个阶梯,是二维偏序极值问题。查询本质上查询前缀最值。

然而注意到其实,询问有一个端点是不变的,所以可以在每一层的时候根据询问不变的那个端点来缩段,然后暴力维护前缀max。

分析复杂度:首先,所有节点总共本质不同的段是只有1log的。然而本来就有1log的支配对,一搭配线段树分治/(或者说整体二分,本质差不多), 已经自带2log了,即便是O(1)操作,复杂度无可避免的依然是2log。

当然,这也并不是完全没用,如果询问的q改成nlogn级别,那么正常算法的二分加持久化就会导致复杂度和整体二分一样变成3log。然而这个做法复杂度依然是2log。

只要理解了数学上准确的例子,从算法设计的一般思想中受益也并不困难。

前面几节,我们讨论的是如何在例题上举一反三——而在这一节,我们展示了学习算法时计算理论的意义——在算法设计上举一反三。当例子足够时,我们总会走向一般的理论。

天涯若比邻

OI 的研究和改进是站在计算机科学基础上,许多同学和老师们在 OI 社区中无私贡献的成果。

感谢他们。而对于我来说,有一些人是特别记得的。

感谢我的朋友 ljt12138,tqyaaaang,sys.,还有 Shilling.X,以及许多人。

感谢 EI 的所有工作。

感谢 Qingyu 的所有工作。

感谢 fjzzq,command_block,YeahPotato,skc,dXqwq,xht,undefined,Menci,rxz 和许多其它同学对更科学的 OI 学习资源和技术做出的贡献。(感谢小粉兔——如果那篇归约课件已经做完了的话。)

感谢蒋炎岩老师,您提出的问题总给我们指出道路。

感谢 cxm,xudyh,wls,vfk,jiry,lrj 和其它许多前辈带我接触 OI 教研。

感谢勰码团队和 lethalboy 对教学实践的支持。

感谢我在信息之路上重要的刘老师,董老师,陈老师,段老师,姚老师。

仍然,最后引用蒋老师的话来结尾:

大部分同学都没能迈过从 “业余选手” 到 “职业选手” 的门槛——给你更多的时间,能解出非常困难的题目。如果你接受过一点理论计算机科学的训练,就会发现竞赛作为一种 “竞技体育”,其实是性价比极低的。 ——蒋炎岩 Yanyan's Wiki (jyywiki.cn)

祝各位都能从题感走向严肃、科学的研究方法,成为算法设计和计算机科学技术的“职业选手”!

更多讨论

我们一般在公开 OJ 和各大 OI 群里讨论问题,不过,有时我一些内测的课件文件和讨论放在这里:

d50760233cabb11c112b77f707fc7b18

拓展阅读(示例)

LCA的省选NOI长训和测试赛公告

2024-09-12 04:09:01 By liu_cheng_ao

LCA的省选NOI长训和测试赛公告

LCA 的 OI 课堂开课辣!

fa025fd8c420225402faf6e7df41ed2e

2024 年 9 月 24 日起,LCA 的第一届省选 NOI 长训将在山东省青岛市举行。

本次长训将会以线下全日制集训形式进行,每年一届分为四期,每期约两个月。由LCA实际主讲,并且有多名跳蚤国神秘嘉宾担任命题、助教和教务等工作。其中,部分节假日或比赛前会有短期集训,期间会有更多高水平旅客讲课和紧凑的模拟赛。


目前,在 NOIP 以上的省选、NOI 水平的学习过程中,同学主要通过大量刷题、模拟赛训练来提升实力。在遇到困难和瓶颈时,缺乏科学的方法去分析具体的知识、学习情况和应对策略,往往只能粗略地增加某一类型的刷题数量,或者尝试在自学和同学交流的过程中自行领悟一些算法和数学方法。

仅有的几个省选 NOI 长训,也是基于这些传统的讲课、刷题、模拟赛、同学自学交流开展的,缺少具体的教学方法帮助选手高效发现问题和提升深层次的理解和解题能力。

不过,近几年的 OI 同学们已经发展和引入了不少一般性的算法知识理论和教学方法。我们也有幸为 OI 社区的学习资源做出一些贡献,用学术方法改进 DP、字符串等知识的深入理解,引入组合模型和计算理论等提高同学们研究和解决算法问题的能力,尝试题解补全、算法数学练习、问题改编研讨等新的教学技术和形式,并在近年山东、河北、江苏各省省队集训等课程中得到初步验证。

因此今年起我们计划开展长训课程,邀请全国各地达到一定水平并计划冲击省队 NOI 的选手进行更为科学的长线训练。


一些教学研究的笔记 https://loj.ac/d/4518

299f518daea1adc6d8518d47e59dda3a

测试赛

本次长训测试赛将于 9 月 15 日、9 月 16 日进行,所有同学均可直接报名参加。测试赛分为两场,NOIP+ 难度和省选难度各一,可根据自己水平自由选择参加其中一到两场。

测试赛成绩可以作为认定入营水平资格的标准。请保证参赛公平。请勿在测试赛期间与人讨论、上网搜索题目或用 AI 辅助写程序等。一旦发现违规行为即失去资格。

教学改进

省选/NOI 难度 传统教学 本次教学
学科体系 零散的算法知识点和题目 基于数学和算法科学的体系,带学生理解问题的实质和研究方法
教学内容 只有算法模板、变体和数学概念、例题 还包括描述和研究问题的数学模型、算法设计方法等
教学方式 讲课+刷题+模拟赛+答疑 还包括多种系统性解决问题的数学思维练习和研讨,如问题改编等
解题方式 以题感为主,方法靠自学领悟 理解数学方法,稳定记录和推进对问题的认识
作业题单 - 尽量覆盖各种OI中的技巧和应用
模拟赛 - 有编审对题目质量和难度进行把控,保证每场训练的有效性,避免低效题目如思维难度低的大代码毒瘤题、超纲的偏题怪题等。每个月有公开原创月赛。

日常训练采用讲练结合的模式,全日制上课,有理论课、交流研讨课、晚自习(有答疑老师),并安排体育活动,劳逸结合。

课后作业除了常规训练题单外,增加了算法数学练习。

交流研讨课注重算法数学练习题讲解讨论,鼓励学生进行好题分享、算法想法分享和解题交流等,另外还会开展题目研讨课,对题单或模拟赛题目进行深入研究,通过改编等方式探究各种问题的一般性推广,并讲解相关 OI 应用和学术拓展知识,增进学生对知识的理解和问题模型的研究能力。

基本信息

  • 时间 2024 年 9 月 24 日到 2025 年 7 月中旬,按照NOIP-省选-NOI时间分为四期,每期约两个月,两期之间根据正式比赛时间休息约 1 到 2 周。每周三到周一下午上课,周一晚上和周二休息。

  • 地点 山东省青岛市某中学,线下全日制集训。

  • 教学团队 刘承奥(蔡德仁/LCA/CommonAnts)主讲,另有多名 NOI 水平助教参与工作。此外,有多名 NOI 金银牌高水平同学共同学习。

090e2a2d7d61c6f49554018d16bb117d

招生信息

  • 招生范围 招收全国 NOIP 250 分以上或同等水平的同学(可参加入营测试,不要求过往比赛成绩),并且家庭和学校支持接受全日制线下集训。

  • 招生人数 总人数不超过30人。

  • 报名方式 按期报名,一期起报。有意向同学可以填写问卷:问卷链接

  • 学习费用 按期收取,根据不同基础成绩享受不同优惠,多人团体报名另有优惠。详情请在填写问卷之后咨询。

  • 奖学金 根据 2024 年 NOIP 和 2025 年省选/NOI/IOI 成绩设有奖学金。详情见下文附录。

  • 教学基金 勰码将出资成立教学基金,专项补贴部分有经济压力的同学顺利完成营地训练计划,可用于缴纳学费、住宿费、承担生活费等在营期间的学习、生活基本支出。受资助同学需要承担部分建设 OI 社区公开学习资源任务和教学任务(教学可选在退役后进行),以推动 OI 发展以及营地教研、积累教学经验。具体细则和申请流程将于近期公布,可关注社区/OJ公告。

报名&联系方式

c8b63adf03f91528f709f7bc8bbd2bb6

liu_cheng_ao Avatar