memset0's blog

前提条件，新版 Windows 10 （在有高分屏的机子上装 Win 10 不苛刻吧）。

由于最近经常折腾虚拟机和新电脑， git 也经常要重新安装 / 配置，因此记录一下 git 添加 SSH 公钥的方式。

该死的精度问题让我调了一个小时还没有调出来（事实说明我还是太菜了。）

大概意思就是说平面上给了你一些点然后你要构造一个与 x 轴相切的圆把这些圆都包裹进去。

考虑二分圆的半径，这样就知道了圆心的 y 坐标，根据点在圆内的充要条件——点到圆心的距离小于等于半径计算出圆心的 x 坐标的范围。如果存在两个范围不相交，说明无法构造出一个符合条件的圆心。

需要注意浮点数运算的精度问题，比如计算 x 坐标的范围时这么写：

1

dis = r * r - (r - y) * (r - y);

就容易被卡，而：

1

dis = 2 * r * y - y * y;

就不容易。

一个永远只能在考完后调出 Codeforces 的题的菜鸡厚颜无耻得跑来写题解了。。。

本题要求把树分成的链必须是垂直路径，也就是说不能同时跨越一颗子树的两个根。也就是说每次选中的路径都是到根节点的一串。

所以我们可以通过树上倍增预处理出每个节点 $u$ 如果被选中那么最多可以向上形成长度为 $dp[u]$ 的链。接着跑一遍树上 DP 即可。

预处理时间复杂度 $O(n \log n)$ ，树上 DP 时间复杂度 $O(n)$ 。

貌似因为 D 题比较难调试，做这题的人比较少？反正我这种菜鸡就算考场有时间写了估计也调不出来吧。

这题洛谷的数据太…水，克鲁斯卡尔重构树不连通都可水过。

• 3545: [ONTAK2010]Peaks
• 3551: [ONTAK2010]Peaks加强版

在线算法：克鲁斯卡尔重构树套主席树。

在克鲁斯卡尔重构树上维护 DFS 序（或树链剖分）再套上主席树，维护第 $k$ 大。

当然非加强版由于你是重构树（被针对了）可能要大力卡常。比如加个 fread 以及离散化一下什么的。

$$\sum_{i=1}^{n} \sum_{j=1}^{m} (n \% i) \times (m \% j) \ \ \ (i \not= j)$$

$$= (\sum_{i=1}^{n} n \% i) \times (\sum_{j=1}^{m} m \% j) - \sum_{i=1}^{\min(n, m)} (n \% i) \times (m \% j)$$

可以转化成 $A \times B - C$ 的形式，分别来求。

其中求 $A$ 和 $B$ 的方式是一样的，可以数论分块，也可以直接打表找规律。鉴于这部分不难，笔者写了后者，而描述起来而笔者又非常懒因此忽略求 $A$ 、 $B$ 直接讲求 $C$ 。当然你也可以通过推 $C$ 的方式自己推一下 $A$ 、 $B$ 。

$$C = \sum_{i=1}^{\min(n, m)} (n \% i) \times (m \% i)$$

$$= \sum_{i=1} ^ {\min(n, m)} (n - i \times \lfloor \frac {n} {i} \rfloor) \times (m - i \times \lfloor \frac {m} {i} \rfloor )$$

$$= \sum_{i=1} ^ {\min(n, m)} n \times m - m \times i \times \lfloor \frac {n} {i} \rfloor - n \times i \times \lfloor \frac {m} {i} \rfloor + i ^ 2 \times \lfloor \frac {m} {i} \rfloor \lfloor \frac {m} {i} \rfloor $$

数论分块即可。

询问树上路径第 $k$ 大：二分答案 + 树上查询。查询时用主席树差分 $tree[now] = tree[u] + tree[v] - tree[lca(u,v)] - tree[father(lca(u,v))]$ 即可。

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

由于每个门只会被两个钥匙控制，那么两个钥匙的选或不选就能建立起一种对应关系。即如果门本来是开着的，那么用了一把必须用另一把，不用一把必须不用另一把；如果们本来是开着的，那么不用一把必须用另一把，用了一把必须不用另一把。

Tarjan 跑 2-SAT 随手切，注意 $n$ 和 $m$ 不要搞反。

最小费用最大流。由于一个工人在给一个顾客服务后还能再给一个顾客服务， 所以把每个顾客和每个工人建点显然不能完成任务。

那么我们考虑把第 $i$ 个工人建成 $n$ 个点，表示为 $P(i,j) (i \in [1, m], j \in [1, n])$。把第 $i$ 个顾客表示为 $T(k)$。

把 $T(k)$ 依次向 $P(i,j)$ 连边，流量为 $1$ ，费用为 $w(k,i) \times j$ 。表示第 $k$ 个顾客被第 $i$ 个工人倒数第 $j$ 个服务对答案产生的贡献（即包括在它之后的人的等待时间，而不是这个人自己的花费）。

最后从源点向每个顾客连流量 $1$ ，费用 $0$ 的边，$n \times m$ 个工人向汇点连流量 $1$ ，费用为 $0$ 的边，跑最小费用最大流即可。

到这题为止网络流 24 题也快刷完了呢，还剩下几道码量特大的等着以后有空去浪费时间（逃

这题一眼最小费用最大流，一开始我想了个类似于 NOI2008 志愿者招募 之类的利用满流的方法，但是一直没有调出来。后来怂了，直接连边，最后因为有个 - 1 没有删干净还是调了老半天。orz ，我还是太菜了。

把每一天分成两个节点，一个接受干净的毛巾，一个输出用过的毛巾。直接在这两个点之间连边显然不现实，我们可以分别把这两个点和源点、汇点连边。然后再按照题目条件一一连上对应边。这样最大流肯定能够跑满，求最小费用的话就是这图的最小费用最大流了。

这告诉我们对于不清楚的知识点不要瞎用。

最大流最小割模板题。

想当年第一次打开 BZOJ 做完 A + B 之后看得一脸懵逼的就是这道题，没想到现如今看起来这么简单

不过还是没有秒切，双向边没看到调了好久 QAQ

好了，关于那个连边。这是本人单向边网络流连边：

1
2
3
4
5

inline void add_edge(int u, int v, int w) {
	nxt[tot] = hed[u], to[tot] = v, val[tot] = w, hed[u] = tot++;
	nxt[tot] = hed[v], to[tot] = u, val[tot] = 0, hed[v] = tot++;
	return;
}

这是本人的双向网络流连边（连两遍也是一样的）：

1
2
3
4
5

inline void add_edge(int u, int v, int w) {
	nxt[tot] = hed[u], to[tot] = v, val[tot] = w, hed[u] = tot++;
	nxt[tot] = hed[v], to[tot] = u, val[tot] = w, hed[v] = tot++;
	return;
}

另外 $最大流 = 最小割$ 不必多说了吧，贴个直观的证明（来自：https://jecvay.com/2014/11/what-is-min-cut.html）：

1.最大流不可能大于最小割, 因为最大流所有的水流都一定经过最小割那些割边, 流过的水流怎么可能比水管容量还大呢?

2.最大流不可能小于最小割, 如果小, 那么说明水管容量没有物尽其用, 可以继续加大水流.

那么 SAP + 当前弧优化 + 断层优化 + 反向 BFS 一遍轻松跑过。

今天和自己喜欢的小姐姐聊了天呢，
小姐姐还给了我好多建议呢，
小姐姐还给我加油了呢，
小姐姐还抱抱我了呢。

那个小姐姐是个敲可爱滴男孩纸呢，
好希望能和他面姬啊，
那么 memset0 要加油了呢！

QAQ 写树套树的时候忽然用到。。。

最近忽然发现 BZOJ 的权限题还是很多的（可能是因为以前搜不到就不搜了现在上 DARKBZOJ ），看来还是得众筹买个权限号了（雾

这是一道傻逼数据结构题，由于数据范围小，各种奇葩算法随便过。本菜鸡就写了个普通的树状数组套莫队，各位大佬不要见笑。

题意：

给你个 $1000 \times 1000$ 的矩阵，每次交换任意两个不重合的子矩阵，求最后的结果

如果你是一位数据结构学傻的选手（像我），那么第一感觉肯定是用平衡树做，复杂度 $O(m \times n \log n)$ ，不过不幸的是，由于常数巨大，最后得分甚至可能不如暴力的 memcpy 。

如果你是一个不会高级数据结构的普及选手你说不定就能想到链表。维护一个矩形的链表，然后每次交换就分别把两块矩阵取出再拼接上去。

这道黑题为什么那么水 QAQ
这道题在 BZOJ 上为什么又又又又又是权限题

本题求区间众数，强制在线。

对于每次查询，必定可以分为整块的和非整块的，我们先预处理出第 $i$ 块到第 $j$ 块的众数（ $max[i][j]$ ）和某个数 $i$ 在前 $j$ 个块内的前缀和（ $sum[i][j]$ ）。对于非整块的部分 $O(\sqrt n)$ 暴力加到桶里，加上整块中的个数判断能否更新答案。然后判断 $l$ 与 $r$ 之间的块的众数是否能否更新答案。

预处理的话 $max$ 和 $sum$ 数组全都暴力扫一遍更新，时间复杂度 $O(n \sqrt n)$，详见代码。

时间复杂度：$O(n \sqrt n + m \sqrt m)$

为什么这题的名字这么奇怪？
为什么这题的题解都是分块？

好，我们讲怎么用线段树做：
首先先把 $1$ 和 $2$ 两个操作用线段树维护出来（这很简单），至于排序我们直接统计区间内每个字母的数量（用操作 $1$ ），然后再直接放回去即可（用操作 $2$ ）。

以及这题大小写字母都会出现，无视即可。

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

逐行 DP ，一行一行扫下去，显然之前选择的是那几列不重要，重要的是有多少列已经放了一个棋子，多少列已经放了两个棋子。

用 $f[k][i][j]$ 表示到第 $k$ 行为止，有 $i$ 行放了一个棋子， $j$ 行放了两个棋子的方案数，没放棋子的行数可以由此推出。

给树分块即可，为树上分块 / 树上莫队做铺垫。

给定一个序列，要求兹滋： 区间加数、区间除以数、区间求和、区间求最小值。

其他都很简单，关键在于怎么解决区间除法。

一开始很容易想到之前的 “花神游历各国” ，但是这题并不能这样做（有区间加数），感觉线段树不可做想分块然而分块照样没法解决除法的问题。

正解则是将除法转换为减法，如果当前区间的最大值和最小值与除以除数的数的差值相同，那么把除数变成减数。

复杂度为 $O(n \log^2 n)$ 据称可以用势能分析，但是本蒟蒻太菜了不会，因此略过 QAQ。