题意 题目链接 给出一个正方形区域，其中有一些点是障碍。每次询问给出两个球的初始位置，询问至少需要改变几次重力才能使两球相遇。 解析 首先我们发现，实际上仅有障碍周围（包括地图边界）上的点是有意义的（因为任何位置的球经过一次操作一定会到这些点，显然一次操作是可以枚举的）。我们定义每一组有意义的 $(x,y)$ 为一个状态，显然最多状态数为 $200…

题意 题目链接 给定 $n$ 个点，求一个由若干个点连接成的凸多边形，所包含的点数最多，输出点数。 解析 先说解法：将所有边按照 atan2(y,x) 的值排序， 然后枚举凸多边形起点，再遍历排序后的边进行 dp 转移，复杂度为 $O(n^3)$。 大致思路与已有题解相同，但是我在这里想要阐述一个困惑我许久的点：为什么是 atan2 ？ 搜索百度百…

大概是要开一个文化课专题了，最近文化课有点崩，所以可能要抽点时间偶尔整理一些文化课的东西（基本都是错题）。 题面 设 $\vec{a},\vec{b},\vec{c}$ 为平面向量，$\vert \vec{a} \vert=\vert \vec{b} \vert=2,(2\vec{c}-\vec{a})\cdot(\vec{c}-\vec{b})=…

非常有意思的一道题（虽然确实容易想不出来）。 题意 题目链接 维护一个 $0 \sim 2^n-1$ 的序列，支持两个操作：将下标为偶数的数按序提前，将下标为奇数的数按序后置；将下标为偶数的数按序后置，将下标为奇数的数按序提前。 解析 我们考虑两种操作的实质。 第一种操作（偶前奇后）：对于下标为 $x$ 的数，若 $x$ 为偶数，则它的新下标为 $…

题意 题目链接 树上的棋子博弈，每个点有权值。你可以添加一条边以试图反败为胜，不同的加边方法根据权值有一个代价，需要最小化这个代价。 解析 我们首先定义一个结点先手必败是 lose，先手必胜是 win，容易发现，叶子结点一定是 ​lose，然后对于每一个非叶子结点，只要它有一个儿子是 ​lose，它就是 win，否则，该结点也是 lose。一遍 d…

本来没打算写这玩意儿，结果学习了之后觉得吉老师线段树真的很有意思，所以就决定简单写一下学习笔记。 本博客参考：echo 的 博客 与 代码启示，jiry_2 的 课件。 但是个人感觉该博客对于 pushdown 部分还是有点难以理解，所以决定用自己的语言写一篇博客阐述一下。 吉老师线段树 吉如一(jiry_2)的 PDF 见博客上方博客参考部分。 …

博客版本 参考：hsfzLZH1 的 博客 及代码启示 左偏树 模版题：Luogu3377。 由于朴素堆的合并操作可能会退化到 $O(n)$，所以我们需要通过一些方式维护合并操作，左偏树就是其中之一。 一些定义 该部分改编自 hsfzLZH1 的 博客 外结点 ：左儿子或右儿子是空结点的结点（首先左偏树是一个堆，堆是一棵二叉树）。 距离 ： 一个结…

题目链接 解析 题意就不多阐述了，看原题就够了。个人觉得这是一道练归并排序性质的好题（虽然动规/堆维护等方法似乎也可行，但我认为最朴素的方法才是最美丽的）。 再发觉贪心不可行时，我们考虑分治维护每一轮比赛可能获胜的人。假设我们以及维护好了左区间（即上一轮比赛）哪些人可能能在上一轮获得胜利（也就是能活到当前这轮）以及右区间的这个信息，我们考虑如何合并…

博客参考：学委 的 博客 及 代码启示 暴力最大流 模板题：Luogu3376 在学习 Dinic 之前，必须先要知道暴力最大流的写法。 首先理解何为网络最大流。一张网络就是一张带权有向图，源点可以输出无限的流量，但是每一条边都有一个容量，需要满足这条边上的流量不能超出其容量（可以理解为输水系统），最后所有流量都会被汇点接收。我们需要求出这个网络运…

题目链接 题意 给定一个二分图，二分图上的每个点都有一个权值。如果一个左部点的权值和一个右部点的权值的 $\gcd$ 大于 $1$，则这两点之间有一条边。求二分图最大匹配。 解析 首先我们发现，如果暴力建边的话，我们可能会建 $n^2$ 条边，在 $100$ 组数据的情况下，非常容易 TLE。 我们考虑优化。对于一个左部点的权值和一个右部点的权值的…