NOIWC2023 游记
rui_er
·
·
生活·游记
NOIWC2023 游记
2022.11.19 | 2459903±.5
过审了，早点开坑没啥坏处，于是开坑。
2023.1.12 | 2459957±.5
开幕式。
一个设备开着年级活动，一个设备开着冬令营。
明天还有一天课，也准备这样。
开幕式好看捏。
2023.1.13 | 2459958±.5
感觉双开的话文化课和 OI 都学不好，不双开了，文化课请了个假。看了看课本感觉没啥难的，回头问问同学然后自学一下。
上午第二课堂：叶诗富《矩阵乘法 ＆ 动态 DP》
（之前还写过一个 动态 DP 学习笔记，可参考食用）
易证矩阵乘法满足结合律，我懒得写证明了。又有 $+$ 对 $\min$ 满足分配律，同理可证 $(\min,+)$ 广义矩阵乘法满足结合律。~~好像啥都证了，又好像啥都没证。~~
由于矩阵乘法满足结合律，可以使用矩阵快速幂加速幂运算。矩阵快速幂可用来加速一些线性递推。对于边权都为 $1$ 的图，邻接矩阵的 $k$ 次幂就是两点之间长度为 $k$ 的路径数。
例题一 $f_i=v_i+\sum\limits_{j=1}^mw_{i,j}f_{i-j}$，单点修改，$m\le 5$。
矩阵可以写成 $\begin{bmatrix}f_i & f_{i-1} & \cdots & f_{i-m} & 1\end{bmatrix}$ 的形式，容易设计出转移矩阵。可以使用线段树维护转移矩阵乘法，单点修改和全局询问容易实现。
例题一结束。
例题二 [P4513 小白逛公园](https://www.luogu.com.cn/problem/P4513)
是一道线段树板子题，但是可以用 $(\max,+)$ 矩阵乘法来 DDP。用 $f_i,g_i$ 表示前 $i$ 个数的最大后缀和以及最大子段和，则有 $f_i=\max\{f_{i-1}+a_i,a_i\}$，$g_i=\max\{f_i,g_{i-1}\}$。易得 $(\max,+)$ 广义矩阵乘法递推式：
$$
\begin{bmatrix}g_i & f_i & 0\end{bmatrix}=
\begin{bmatrix}g_{i-1} & f_{i-1} & 0\end{bmatrix}
\begin{bmatrix}0 & -\infty & -\infty \\ a_i & a_i & -\infty \\ a_i & a_i & 0\end{bmatrix}
$$
线段树维护即可。
例题二结束。
例题三 [P4719 【模板】"动态 DP"&动态树分治](https://www.luogu.com.cn/problem/P4719)
经典的单点修改树上最大权独立集问题。
若不带修改，有：
$$
\begin{aligned}
f_{u,0}&=\sum\limits_v\max\{f_{v,0},f_{v,1}\}\\
f_{u,1}&=a_u+\sum\limits_vf_{v,0}
\end{aligned}
$$
其中 $v$ 是 $u$ 的儿子。
但是带修改的话上面的定义并不太好维护。有两个问题：链太多无法维护、矩阵乘法的话儿子大小不一定所以矩阵大小不一定。
对于第一个问题，不难想到采用重链剖分的方式。重链剖分后，把一个点的所有儿子分为重儿子、轻儿子分别处理，矩阵大小变为 $2\times 2$，从而解决了第二个问题。
设 $g_{u,0}$ 表示不取 $u$、$u$ 的所有轻儿子可取可不取的最大权独立集，设 $g_{u,1}$ 表示取 $u$、$u$ 的所有轻儿子都不取的最大权独立集。
$$
\begin{aligned}
g_{u,0}&=\sum\limits_{v\ne ws}\max\{f_{v,0},f_{v,1}\}\\
g_{u,1}&=a_u+\sum\limits_{v\ne ws}f_{v,0}\\
f_{u,0}&=\max\{g_{u,0}+f_{ws,0},g_{u,0}+f_{ws,1}\}\\
f_{u,1}&=g_{u,1}+f_{ws,0}
\end{aligned}
$$
其中 $v$ 是 $u$ 的儿子，$ws$ 是 $u$ 的重儿子。
有矩阵乘法：
$$
\begin{bmatrix}f_{u,0}\\f_{u,1}\end{bmatrix}=
\begin{bmatrix}g_{i,0} & g_{i,0}\\g_{i,1} & -\infty\end{bmatrix}
\begin{bmatrix}f_{ws,0}\\f_{ws,1}\end{bmatrix}
$$
至此，$f$ 可以重链剖分后线段树维护。我们知道重链剖分中一个点到根节点的路径上最多只有 $\Theta(\log n)$ 个轻边，因此每次修改操作只会修改 $\Theta(\log n)$ 的 $g$ 值。因此 $g$ 可以在一开始通过 DFS 预处理出来，之后每次修改操作可以在重链剖分向上跳的时候直接维护。
例题三结束。
有一些简单的习题不写了，还有一些难的习题先咕着。
### ~~下午第二课堂：王晓光《动态规划算法及应用》~~
我还以为求汉诺塔最小步数只是个引子，愣是听了 15min，结果下一题是爬楼梯。。。。
我还是去第一课堂吧，虽然估计听不懂。
### 下午第一课堂：周航锐《题目选讲》
不过题目选讲好像没啥笔记要记。
“这不是 FJOI2022 吗”
“暴戾语言”
## 2023.1.14 | 2459959±.5
### ~~上午第二课堂：翁天东《初等数论》~~
好像很简单，没意思。
### 上午第一课堂：戴江齐《网络流在最优化问题中的应用》
讲网络流算法的时候在第二课堂摸鱼，没听到，好在我之前学过。
但是多项式费用流是啥啊。
一上来就赶上了第一道例题。
### 下午第二课堂：张超《题目选讲》
记录一下洛谷上有的题号：P5536 / P8026 / P5901 / CF1039D。
## 2023.1.15 | 2459960±.5
### 上午
第二课堂太简单了，第一课堂没听说过。
准备 10:00 进一趟第二课堂看看讲到哪了。
### 上午第二课堂：屈运华《树形数据结构及其应用》
跟 zpl 说讲到李超树的时候叫我，结果竟然都 11:10 了。
然后就进来稍微听了会。
然后发现是读课件，而且课件与 OI Wiki 几乎完全一致，我还是以后对着 OI Wiki 自学吧。
### 下午第二课堂：宋新波《计算几何及其应用》
向量加减法和数乘课内刚学过，懒得写。
余弦定理：在 $\triangle ABC$ 中，有 $c^2=a^2+b^2-2ab\cos C$。
向量点积：$\boldsymbol a\cdot\boldsymbol b=|\boldsymbol a||\boldsymbol b|\cos\theta$。点积的结果是标量。
有性质：
- 若 $\boldsymbol a=(x_1,y_1),\boldsymbol b=(x_2,y_2)$，则有 $\boldsymbol a\cdot\boldsymbol b=x_1x_2+y_1y_2$。
- 交换律：$\boldsymbol a\cdot\boldsymbol b=\boldsymbol b\cdot\boldsymbol a$。
- 点积对加法的分配律：$\boldsymbol a\cdot(\boldsymbol b+\boldsymbol c)=\boldsymbol a\cdot\boldsymbol b+\boldsymbol a\cdot\boldsymbol c$。
- 判定两向量垂直：$\boldsymbol a\perp\boldsymbol b\iff\boldsymbol a\cdot\boldsymbol b=0$。
- 判定两向量共线：$\boldsymbol a=\lambda\boldsymbol b\iff|\boldsymbol a\cdot\boldsymbol b|=|\boldsymbol a||\boldsymbol b|$。
- 求两向量夹角：$\cos\theta=\frac{\boldsymbol a\cdot\boldsymbol b}{|\boldsymbol a||\boldsymbol b|}$。
向量叉积：$|\boldsymbol a\times\boldsymbol b|=|\boldsymbol a||\boldsymbol b|\sin\langle\boldsymbol a,\boldsymbol b\rangle$，$\boldsymbol a,\boldsymbol b,\boldsymbol a\times\boldsymbol b$ 满足右手定则。叉积的结果是向量。
在计算几何中，若 $\boldsymbol a=(x_1,y_1),\boldsymbol b=(x_2,y_2)$，则有 $\boldsymbol a\times \boldsymbol b=x_1y_2-x_2y_1$。在下文中，使用计算几何中的常见定义，认为叉积的结果是标量（实际上是向量）。
有性质：
- 反交换律：$\boldsymbol a\times\boldsymbol b=-\boldsymbol b\times\boldsymbol a$。
- $\boldsymbol a\times\boldsymbol b$ 等于 $\boldsymbol a$ 和 $\boldsymbol b$ 组成的三角形的有向面积的两倍。
- 若 $\boldsymbol a,\boldsymbol b$ 共线，$\boldsymbol a\times\boldsymbol b=0$。
- 若 $\theta\in(0,\pi)$，$\boldsymbol a\times\boldsymbol b > 0$。
- 若 $\theta\in(\pi,2\pi)$，$\boldsymbol a\times\boldsymbol b < 0$。
直线的参数表示：设 $\boldsymbol P_0$ 为直线上一点，$\boldsymbol v$ 为方向向量，则直线上所有点 $\boldsymbol P$ 满足 $\boldsymbol P=\boldsymbol P_0+t\boldsymbol v$，其中 $t$ 为参数。
设两直线 $l_1:\boldsymbol P+t\boldsymbol v$ 和 $l_2:\boldsymbol Q+t\boldsymbol w$，交点的参数分别为 $t_1$ 和 $t_2$，设 $\boldsymbol u=\boldsymbol P-\boldsymbol Q$，解方程可得：
$$
\begin{cases}
t_1=\frac{\boldsymbol w\times\boldsymbol u}{\boldsymbol v\times\boldsymbol w}\\
t_2=\frac{\boldsymbol v\times\boldsymbol u}{\boldsymbol v\times\boldsymbol w}
\end{cases}
$$
交点即 $\boldsymbol P+t_1\boldsymbol v$ 或 $\boldsymbol Q+t_2\boldsymbol w$。
设三个点 $\boldsymbol P,\boldsymbol A,\boldsymbol B$ 和直线 $l:\boldsymbol A+t(\boldsymbol B-\boldsymbol A)$，则 $\boldsymbol P$ 到 $l$ 的距离为 $|\frac{(\boldsymbol B-\boldsymbol A)\times(\boldsymbol P-\boldsymbol A)}{|\boldsymbol B-\boldsymbol A|}|$。设点 $\boldsymbol P$ 在 $l$ 上的投影的参数为 $t_0$，设 $\boldsymbol v=\boldsymbol B-\boldsymbol A$，则有 $t_0=\frac{\boldsymbol v\cdot(\boldsymbol P-\boldsymbol A)}{\boldsymbol v\cdot\boldsymbol v}$。点到线段距离只需判点在直线上的投影是否在线段内，然后计算即可。
老师讲得好快，没时间写笔记，以后补。
## 2023.1.16 | 2459961±.5
### 上午第一课堂：张隽恺《题目选讲》
估计听不懂，但没有第二课堂了/hsh
### 下午
没听。
## 2023.1.17 | 2459962±.5
以后更。
## 2023.1.18 | 2459963±.5
分数线 $89,56,24$，可见 WC2023 的阴间。
$25+24+36=85$，离 Au 差 $4$ 分。