首先我们把原来的距离数组 $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 题比较难调试，做这题的人比较少？反正我这种菜鸡就算考场有时间写了估计也调不出来吧。
阅读全文…这题洛谷的数据太…水，克鲁斯卡尔重构树不连通都可水过。
在线算法：克鲁斯卡尔重构树套主席树。
在克鲁斯卡尔重构树上维护 DFS 序（或树链剖分）再套上主席树，维护第 $k$ 大。
当然非加强版由于你是重构树（被针对了）可能要大力卡常。比如加个 fread 以及离散化一下什么的。
这题的规律是很好找的，难的就是需要用高精度进行计算。
于是我…厚颜无耻地逃避了高精度，用 Python 打了个表：
1 | def locate(x): |
$$\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 | inline void add_edge(int u, int v, int w) { |
这是本人的双向网络流连边（连两遍也是一样的）：
1 | inline void add_edge(int u, int v, int w) { |
另外 $最大流 = 最小割$ 不必多说了吧，贴个直观的证明（来自：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$ 行放了两个棋子的方案数，没放棋子的行数可以由此推出。
阅读全文…