本计划根据 Menci 博客 题解时间顺序排列。
CodeVS 和 COGS 的部分题出于某些原因不打算做（主要是没有账号）。
部分未完成且正准备做的题目可能会给出链接（优先级：洛谷 > BZOJ > LOJ > UOJ）。

zhouyuheng2003 学长一天打完 CF 后给我做的一道他说是简单题的题，然而炒鸡难！！！

考虑暴力，每个炸弹向能引爆炸弹的连边，总数是 $n^2$ 级别的。之后跑 tarjan 缩点，并在 DAG 上统计答案。统计是，考虑合并来的点所对应的情况可能会有重点，因此需要开桶去重。这样的时空复杂度都是 $O(n^2)$ 的。

考虑优化，通过观察可以发现，能引爆的炸弹一定是连续的一整段区间。那么我们可以用线段树优化建边，统计答案是不需要开桶统计，而是统计能够炸掉的最左端的点和最右端的点。时间复杂度 $O(n \log n)$ ，空间复杂度 $O(n)$。

当然这并不是最优的做法，zhouyuheng2003 学长的博客中给出了一种时空复杂度均为 $O(n)$ 的做法。见 https://blog.csdn.net/zhouyuheng2003/article/details/83278984 。

第一次参加 NOIP 提高组，有紧张，有失落，也有惊喜。无论最后结果如何，这次奋力拼搏我永不会忘记。

配置编译系统

新建编译系统并粘贴入以下命令，保存为 G++.sublime-build 或其他你喜欢的名称。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

{
    "shell_cmd": "g++ \"${file}\" -o \"${file_path}/${file_base_name}\" -Wall",
    "file_regex": "^(..[^:]*):([0-9]+):?([0-9]+)?:? (.*)$",
    "working_dir": "${file_path}",
    "selector": "source.c, source.c++",
    "variants":
    [
        {
            "name": "compile",
            "shell_cmd": "g++ \"${file}\" -o \"/tmp/${file_base_name}\" -Wall -O2 && echo 'Compile finished.'"
        },
        {
            "name": "run",
            "shell_cmd": "'/tmp/${file_base_name}' && echo '=============\nRun finished.'"
        },
        {
            "name": "compile & run",
            "shell_cmd": "g++ \"${file}\" -o \"/tmp/${file_base_name}\" -Wall -O2 && /tmp/${file_base_name} && echo '=============\nComplie & run finished.'"
        }
    ]
}

配置编译运行快捷键

把以下代码粘贴到你的快捷键配置文件中，表示 F9 编译， F10 运行， F11 编译并运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

{
	"keys": ["f9"], "command": "build",
	"args": {
		"variant": "compile"
	}
},
	{
		"keys": ["f10"], "command": "build",
		"args": {
			"variant": "run"
		}
},
	{
		"keys": ["f11"], "command": "build",
		"args": {
			"variant": "compile & run"
		}
}

其他注意事项

Mac OS 下默认用 Clang 编译 G++ 代码。因此不支持使用万能头文件（bits/stdc++.h），解决方案：

1. 手动复制 bits/stdc++.h 文件到对应目录中

2. 手动安装 g++4.9 并把上面编译命令中的 g++ 替换为 g++-4.9

本题大概是一个基环树上带修改边权的最短距离。可以把他看做一棵树，把多的那条边拎出来，树剖维护距离，分类讨论即可。大概是你谷蓝题难度吧。

由于树剖只需要查询 dfs 序上区间最小值，可以考虑树状数组维护常熟较小。目前不卡常的情况下你谷效率 rk1 。（如果我被超了私信窝一下 qwq…）

首先我们把原来的距离数组 $p$ 差分为数组 $a$。原题可以等同为在 $a$ 数组中选择 $k$ 个不相邻的数使得总和最小。

假设我们已经选择了 $a_i$ ，那么 $a_{i-1}$ 和 $a_{i+1}$ 要么同时选择，要么同时没有被选择。同时，如果我们同时选择，需要的花费即 $V_{a_{i+1}} + V_{a_{i-1}} - V_{a_i}$ 。我们维护一个堆和双向链表，每次从小根堆选择堆顶，把 $a_i$、 $a_{i-1}$ 和 $a_{i+1}$ 同时删除，再新建一个价值为 $V_{a_{i+1}} + V_{a_{i-1}} - V_{a_i}$ 的节点，扔到堆里，重复 $k$ 次就能得到答案。

前提条件，新版 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 以及离散化一下什么的。

这题的规律是很好找的，难的就是需要用高精度进行计算。

于是我…厚颜无耻地逃避了高精度，用 Python 打了个表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def locate(x):
    a = [1, 3]
    for i in range(2, x):
        a.append(a[-1] + a[-2])
    # print(a)
    return a[x - 1]

def solve(x):
    t = locate(x)
    if x % 2 == 1:
        return t ** 2
    else:
        return t ** 2 - 4

n = int(input())
print(solve(n))

$$\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 写树套树的时候忽然用到。。。