是的，你没有看错，我又来山东集训了。
Day 1
这几天讲课的居然是 yaoxi 哎。
- P1527 [国家集训队] 矩阵乘法。
yaoxi：大家觉得什么才是基础算法呢？
我们考虑整体二分。每次，我们把 \([l, r]\) 取中点 \(mid\)，然后我们二分到 \([l, mid - 1]\) 和 \([mid + 1, r]\)。
接下来我们更改一下判定方法，我们把所有 \(x < k\) 的都设置为 \(1\)，剩下的 \(k \le x\) 的设置为 \(0\)，接下来我们使用双层树状数组来进行维护前缀和，剩下的每次在操作函数后面撤销即可。
上来就是紫题
- P2619 [国家集训队] Tree I。
我们考虑 wqs 二分。
wqs 二分，用一句话概括，就是这个玩意儿是个单调的，我们每次在 \([l, r]\) 中进行二分，二分到 \(mid\) 作为斜率，然后找这个类似函数的玩意儿的切点。接下来考虑如何判断切点。
我们把横坐标设置为 \(k\)，纵坐标设为 \(ans\)。很明显，当且仅当 \(ans - mid \times k\) 最小的时候 \(k\) 就是切点。这里 \(ans\) 表示答案，\(k\) 表示白色点的个数。我们这才发现，这里和把所有的白色点的权值减掉 \(mid\) 是一致的。
所以，我们算法的流程就是，先二分斜率，然后进行最小生成树的计算，同时记录下此时的 \(k\) 的值，就可以了。
yaoxi 自信一交，先CE，后WA，然后WA，还是WA，依旧WA，仍然WA，终于，yaoxi：先下课，要是我没调出来就下一题。
-
P4383 [八省联考 2018] 林克卡特树。
貌似不难。
容易发现，答案具有单调性。我们不妨考虑 wqs 二分。我们直接就二分斜率，然后我们发现这不就是个树形 dp 吗，所以这就出来了。 -
P3199 [HNOI2009] 最小圈。
简单，二分，然后判个负环就行。 -
P3509 [POI 2010] ZAB-Frog。
简单简单。我们容易发现，对于一个 \(i\) 一一定可以维护一个长度为 \(k\) 的区间 \([l, r]\)，所以这样我们就可以找到每个 \(i\) 所对应的 \(j\)。然后就是典的倍增了。 -
P3216 [HNOI2011] 数学作业。
yaoxi：像这种矩阵快速幂只能做一次的错误思想我们一定要摒弃。
我们可以发现，设 \(f_i\) 表示答案，我们考虑 \(f_i = (f_{i - 1} \times 10^{\lg i + 1} + i) \mod k\)。
然后我们做 \(18\) 次矩阵快速幂即可。
-
P4159 [SCOI2009] 迷路。
我们容易发现 \(w_i \le 9\)，我们不妨轻松地把一个点拆成 \(w_i\) 个，然后做 \(T\) 次矩阵快速幂即可。 -
P2151 [SDOI2009] HH 去散步。
典。见山东暑假集训 I的第一题。这还是伟大的 xby 老师讲的。