【WC 2026】 游记

食堂伙食不赖的。被骂低素质了。

AI 课

一节课讨论教育，一节课说造 AI，好像也就是那些东西。

lhx 数据结构

treap：期望深度 \(3\log_2\)。

  • 应用：后缀平衡树，类似重量平衡树去给每个节点赋权值，这样每次插入新后缀时，我们可以容易地和某个原有后缀比较大小：
    • 先比较第一位字符。
    • 若相等比较去掉第一个字符的大小，这两个后缀在平衡树中已经存在。
  • 有交合并：
    • 按照较大的根对另一棵树进行切割，对于切出来的分别与左右子树合并。
    • 不妨设 \(siz_1\le siz_2\)，一般情况下，这个复杂度是 \(O(siz_1\times \log (\frac{siz_1+siz_2}{siz_1}))\)。
    • 合并 \(m\) 个 treap，总大小为 \(n\)，合并总复杂度为 \(O(n\log n)\)，可以用于树上合并。
    • 对于一棵平衡树，split 后 unite，均摊 \(O(n\log n\log V)\)。

WBLT：\(\alpha\) 取 \(\frac{1}{4}\) 可以避免浮点数运算。

  • 好像没写过 merge/split 版本的。

全局平衡：

  • 重剖+线段树：重剖往上跳轻边子树大小翻倍，我们希望在线段树中也有这个性质。
    那么将线段树按照轻子树大小和比例进行加权，复杂度 \(\log\)。
  • 点分+分治：令 \(u\) 的分治深度按照分治时的 \(siz_u\) 加权，复杂度 \(\log\)。
  • 带权分治（集合）：
    • 合并果子，但是复杂度 \(\log_{\varphi}\)。
    • 将比例下降到 2 的整数幂，合并果子，复杂度 \(\log_2\)。
  • 带权分治（序列）：
    • 划分为两部分，保证差最小。复杂度 \(\log_\varphi\)。
    • 将比例下降到 2 的整数幂，使用栈维护：
      • 若栈顶两个都比 \(r_i\) 小，合并栈顶，重复执行。
      • 若栈顶小于等于 \(r_i\)，则合并栈顶和 \(i\)。插入 \(i\)。
      • 复杂度 \(\log_2\)。

UOJ960【USsR #1】程序校验

UOJ1017 【ULR #3】程序校验 II

多树二分：

P5314 [Ynoi2011] ODT
直接重剖，维护轻儿子平衡树，这样是 \(O(m\log ^2n)\)。
分 $k=0,1,2\dots $ 级重儿子，其中 \(k\) 级重儿子有 \(2^{2^k}\) 个。

莫队与等价类分治：

  • 莫队：\(B=\frac{n}{\sqrt q}\)。
  • 等价类分治：
    • 按照 \(B\) 分块，分治处理每个块。
    • 复杂度 \(O(\frac{n}{B}(q+T(B)))\)，其中 \(T(m)=2T(\frac{m}{2})+O(f(m))\)。

qoj14685 Epilogue of Happiness

lhf 交互、通信

IOI practice

AT_agc044_d [AGC044D] Guess the Password
密码长度可以问 \(L\times (\mathtt{a+b+c+d+}\dots)\)。
注意到可以判定子序列。在确定密码长度后，我们可以知道每个字符的出现次数，最后归并排序。

P13614 [IOI 2018] highway 高速公路收费

CF1764G3 Doremy's Perfect DS Class (Hard Version)

P13535 [IOI 2025] 纪念品（souvenirs）
第一次问 \(p_0-1\)。若某次购买了 \(S\) 集合内的商品，且花费了 \(sum\) 元，则我们下一次购买 \(\frac{sum-1}{|S|}\)，这样最后一定可以得到 \(p_n\)。
那么可以递归子问题了。

QOJ10182 진화 2

  • finger search：在长度为 \(n\) 的 01 序列里找到所有的 \(m\) 个 \(1\)，\(m\) 已知，交互。
    • 每次尝试往前跳 \(\frac{n}{m}\)，若存在 1 就去二分。
    • 复杂度 \(O(m\log \frac{n}{m})\)。

UOJ751 【UNR #6】神隐
考虑求出任意两个点之间边编号的 \(\mathrm{and,or}\)，若相等说明这是边。
我们获得一个询问次数 \(2\log n\)，复杂度 \(O(n^2)\) 的做法。

CF2164G Pointless Machine

P6837 [IOI 2020] 数蘑菇

IOI2025 Practice
由于 \(LIS\times LDS \ge n\)，我们传其中一个就好。使用删除数量区分两种。

P10434 [JOIST 2024] 间谍 3 / Spy 3

P13539 [IOI 2025] 恐龙大迁徙（migrations）

题目评讲

考号 GD-057
T1 二进制/binary

  • 两个数最后一步操作一定不一样。
  • 只有最后一个 \(\times 2\) 操作和可能接很多 \(+1\) 操作。
  • 只有一个数会进行 \(\times 2\) 操作。

考虑 \(2^k\times x\le y<2^{k+1}\times x\)，那么 \(x\) 若变成 \(2^{k+1}x\) 则答案为 \(2^{k+1}x-y+k+1\)。
否则，考虑我们给 \(y\) 加上 \(O(\log V)\) 大小的一个数，让他末尾 \(k\) 位 1 尽量少。
即 \(\left\lfloor\frac{y+i}{2^k}\right\rfloor-x+k+i+\operatorname{pop}((y+i)_{[0,k)})\)。

考虑最后 6 位，要么全部加成 0，要么不填完。这可以预处理 \(2^6\) 的表，\(O(1)\) 回答。

T2 game
治疗计划，然后限制是二维的，我们可以扫描线优化建图。
考虑这是 \(k\) 条点不交路径，费用流处理。

T3 paint

zc 欧洲题

P11354 [eJOI 2023] Tree Search
边分治，二分。\(\log_{\frac{3}{2}} n=28\)。

P13804 [SWERC 2023] In-order
考虑根若有 2 个儿子，那么我们可以确定他们分别是谁。否则这个儿子可以是左儿子或右儿子。同时我们可以递归，那么只有 \(\deg=1\) 的点有 2 的贡献。

对于你确定了根的中序遍历时，你确定的区间中若有 \(\deg=1\) 的点，他就被确定了。
若确定的不是根，找到中序遍历确定的最浅点 \(u\)，他的祖先的 \(\deg=1\) 点需要确定往左/右，会对 \(u\) 的中序遍历位置产生影响，可以组合数计算。

problem AB3_gpus
考虑一定可以调整，使得每秒执行的任务数量不降。
从小到大枚举完工时刻，然后新增的这个时刻我们把人物先排满，然后从贵的开始删除。

P13695 [CEOI 2025] theseus
将边定向为编号较小指向编号较大。那么 0/1 的标签可以让这条边反转/不反转。
那么找出一棵生成树，则一定可以到达。

考虑先按照最短路分层。我们可能走一些同层之间的边，这些边算入 \(C=O(\log n)\) 中。我们希望，这些边只会走 \(O(\log n)\) 次。
\(\color{Red}\mathtt \Gamma\)

CF2018C Tree Pruning
设 \(mx_u\) 表示 \(u\) 子树内最深的节点深度。
若保留深度 \(i\)，则 \(u\) 可以被保留，要求：

  • \(dep_u\le i,mx_u\ge i\)。

所以 \(u\) 可以贡献到 \([dep_u,mx_u]\)。

P13340 [EGOI 2025] Dark Ride / 黑暗乘车
考虑二进制的那些东西。
设我们需要找到的位置是 \(a,b\)。
检测每个包含 \(2^i\) 的开关，若返回偶数说明 \((a\oplus b) _i=0\)，否则 \(=1\)。
\(\color{Red}\mathtt \Gamma\)

展览 瑞士 SOI 2023/2024

cxy 欧拉数

  • 对于序列 \(p\)，设 \(asc(p)=\sum_{i=1}^{n-1} [p_i<p_{i+1}]\)。
  • 定义欧拉数 \(\left\langle^n_k\right\rangle\) 表示有多少个 \(n\) 阶排列满足 \(asc(p)=k\)。
  • 一种递推方式：考虑插入 \(n\)，则 \(A_{n,k}=(k+1)A_{n-1,k}+(n-k)A_{n-1,k-1}\)。

QOJ5448 另一个欧拉数问题（\(O(n^2)\) 做法）
考虑每次插入最大值构造 \((n,\alpha)\) 阶排列，只能选择一个空插入所有 \(n\)。
类似上面进行递推就好。

  • 另一种欧拉数递推方式：每次在末尾添加一个元素。这样我们需要记录最后一个元素的排名：\(A_{n,k,x}=A_{n-1,k-[y<x],y}\)，可以前缀和优化。\(O(n^3)\)

QOJ5532 CEOI 2016 kangaroo（\(O(n^2)\)）
。

  • 容斥计算欧拉数：
    • 形式化描述容斥：\(w(a)=\prod_i (p_i[f_i(a)=0]+q_i[f_i(a)=1])\)。
    • 我们需要求 \(\sum_{a\in A}w(a)=\sum_{a\in A}\prod_i (p_i+(q_i-p_i)[f_i(a)=1])=\sum_{a\in A}\sum_{S} \prod_{i\not\in S} p_i\prod_{i\in S} (q_i-p_i)\mathrm{cnt}(S)\)，其中 \(cnt(S)=\sum_{a\in A} \prod_{i\in S} [f_i(a)=1]\)。
    • 带入 \(p_i=1,q_i=x\)：\(\sum_{S} (x-1)^{|S|}cnt(S)\)，考虑求 \(cnt(S)\)。
    • \(\left\langle^n_m\right\rangle \sum_{i=0}^{n-m} i^n \binom{n+1}{m+i+1}(-1)^{n-i+m}\)。
    • \(\left\langle^n_m\right\rangle=[\frac{x^n}{n!}y^m]\sum_{k\ge 0} (x-1)^k (e^y-1)^{n-k}\)。

LOJ575 「LibreOJ NOI Round #2」不等关系
\([a>b]=1-[a<b]\)。
枚举上一个 1 在哪里：\(f_i=\sum_{1\le j\le i}f_{j-1}\frac{(-1)^{c_i-c_{j}}}{(j-i+1)!}[s_i=[a>b]]\)。

QOJ9651 又一个欧拉数问题

AT_abc267_g [ABC267G] Increasing K Times

CTT2024 DAY 3 比赛

QOJ17203 谜题 II

fsz 数学

群论

  • 定义 \((G,\cdot)\)：封闭性、结合律、单位元、逆元。
    • 单位元唯一、逆元唯一、逆元自反性。
  • 陪集：对于群 \((G,\cdot)\) 子群 \(H\) 和 \(g\in G\)，定义 \(gH\) 是 \(H\) 的陪集。
    • \(\forall g\in G,|gH|=|H|\)。
    • \(\forall g\in G,gH=H\Leftrightarrow g\in H\)。
    • \(\forall g_1\)，要么 \(g_2\in G,g_1H=g_2H\)，要么 \(g_1H\cap g_2H=\varnothing\)。
  • 定义簇 \(G/H\) 表示 \(\{gH\mid g\in G\}\)。当 \(G\) 有限时，有 \(|G/H|\cdot |H|=|G|\)。
  • 群作用：\(G\times X\rightarrow X\)。
  • 轨道：定义 \(x\in X,\operatorname{orbit}(x)=Gx=\{g\star x\mid g\in G\}\)。
  • 稳定子：定义 \(x\in X,\mathrm{Stab}(x)=\{g\mid g\in G,g\star x=x\}\)。
    • \(\mathrm{Stab}(x)\) 是 \(G\) 的子群。
    • 可以定义 \(G/\mathrm{Stab}(x)\)。
  • 轨道-稳定子定理：\(|\mathrm{Stab}(x)|\cdot |\mathrm{orbit}(x)|=|G|\)。
    • 证明：考虑双射 \(\varphi: G/\mathrm{Stab}(x)\rightarrow\mathrm{orbit}(x)\)。
    • \(g\mathrm{Stab}(x)\mapsto gx\)，设有 \(g_1\mathrm{Stab}(x)=g_2\mathrm{Stab}(x)\)，则存在 \(g\in\mathrm{Stab}(x),g_1g=g_2\)。
    • 故有 \(g_2\star x=(g_1g)\star x=g_1\star( g\star x)=g_1\star x\)。
  • Burnside 引理：设群 \(G\) 作用在集合 \(X\)，记 \(X/G\) 表示 \(\{Gx\mid x\in X\}\)，\(X^g\) 表示 \(\{x\in X\mid g\star x=x\}\)。则 \(|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|\)。
    • 证明：\(|X/G|=\sum_{x\in X}\frac{1}{|Gx|}=\sum_{x\in X} \frac{|\mathrm{Stab}(x)|}{|G|}=\frac{1}{|G|}\sum_{x\in X}\sum_{g\in G}[g\star x=x]=\frac{1}{|G|}\sum_{g\in G}|X^g|\)。
  • 置换群：设 \(X\) 是一个非空集合，对于双射 \(f:X\rightarrow X\)，他和 \(X\) 构成群 \((X,f)\)，记作 \(Sym(X)\)。当 \(X=\{1,2,3,\cdots,n\}\) 时，可以记作 \(S_n\)。
  • Polya 定理：\(n\) 个元素，每个元素都可以染上 \(m\) 中颜色之一。置换群 \(S_n\) 的子群 \(G\)，方案书是 \(\frac{1}{|G|}\sum_{g\in G}m^{\mathrm{cyc}(g)}\)。

图同构计数
把边的存在性改成完全图黑白染色。考虑边之间的映射关系 \((x,y)\rightarrow (p_x,p_y)\)，则考虑两个不同的、大小分别是 \(a,b\) 的点置换环，他们之间的边形成 \(\gcd(a,b)\) 个等价类。而一个点置换环内部的边则形成 \(\frac{a}{2}\) 个等价类。
我们可以暴力枚举每种置换环的个数。
\(p(19)=500,p(60)=10^6,p(100)=2\times 10^8\)。

线性规划
呜哇摆烂。

概率题目

  • 停时期望：设 \(F(x)\) 表示停时的 PGF，有 \(F(1)=1,F'(1)=E(T)\)。也可以定义 \(G(x)\) 表示未停时的 PGF，有 \(G(1)=E(T)\)。

P4548 [CTSC2006] 歌唱王国
考虑在一个未停时状态后面接上 \(s\)，那么所有的 border 处可能产生停时。
即 \((\frac{z}{m})^nG(z)=\sum_{j\in Bd(s)}(\frac{z}{m})^{n-j} F(z)\)，带入 \(z=1\)。

AT_agc038_e [AGC038E] Gachapon
考虑枚举哪个数是最后取到的，那么其他的满足 \(\ge b_j\)，而他恰好是 \(b_j\)。
写出停时的 PGF：
\(1+(\mathcal{L}(\sum_{i=1}^n \frac{a_i^{b_i-1}z^{b_i-1}}{S^{b_i-1}(b_i-1)!}\prod_{j\ne i}(\exp(\frac{a_iz}{S})-\sum_{0\le k<b_j} \frac{a_j^kz^k}{S^k k!})))'(1)\)
其中 \(\mathcal{L}\) 表示拉格朗日算子，将 EGF 转为 OGF。\(S=\sum a\)。
考虑这个函数写成 \(\sum_{p,q} A_{p,q}z^p e^{\frac{qz}{S}}\)，可以背包求系数。
考虑 \(\mathcal{L}(z^pe^{qz})=\frac{z^pp!}{(1-qz)^{p+1}}\)。

P5326 [ZJOI2019] 开关
设 \(F\) 表示第一次停时的 PGF，\(G\) 表示某次停时后的停时 PGF，\(H\) 表示停时的 PGF。
有 \(F(z)G(z)=H(z)\)。
求 \((\frac{H}{G})'(1)=\frac{GH'-HG'}{G^2}(1)\)。

分别看 \(G\) 和 \(H\) 怎么求。
对于 \(\hat G(z)=\prod_{i=1}^n \frac{e^{\frac{p_iz}{S}}+e^{\frac{-p_iz}{S}}}{2}\)，\(\hat H(z)=\prod_{i=1}^{n} \frac{e^{\frac{p_iz}{S}}+(-1)^{s_i}e^{\frac{-p_iz}{S}}}{2}\)。

可以使用 \(O(nS)\) dp 求出 \(\sum a_ie^{\frac{iz}{S}}\) 的形式。
\(G(z)=\sum_{i\ge 0} \frac{a_iS}{S-iz},G'(z)=\sum_{i\ge 0} \frac{ia_iS}{(S-iz)^2}\)。

\[\begin{aligned} \frac{GH'-HG'}{G^2}(1)&=\frac{\sum_{i,j}(\frac{ja_ib_jS^2}{(S-iz)(S-jz)^2}-\frac{ia_ib_jS^2}{(S-iz)^2(S-jz)})}{\sum_{i,j} (\frac{a_ia_jS^2}{(S-iz)(S-jz)})}(1)\\ &=\frac{\sum_{i}(\frac{a_ib_SS^3}{S-i}-\frac{a_Sb_iS^3}{S-i})}{a_S^2S^2}\\ &=\frac{S}{a_S^2}\sum_i \frac{a_ib_S-a_Sb_i}{S-i} \end{aligned} \]

posted @ 2026-02-08 08:51  TallBanana  阅读(22)  评论(0)    收藏  举报