这篇文章受密码保护，输入密码才能阅读

## 斜率优化 斜率优化的核心思想是将转移方程变为形如 $y = kx +b$ 的形式，这样我们就需要解决 $n$ 个线性规划问题。在第 $i$ 个线性规划问题当中，我们的点集是 $S$，同时有斜率 $k_i$，假设这个线性规划的最小答案（截距）为 $b_i$ 则会向点集中添加一个新点 $(x_i, f(b_i))$，$f$ 是一个因题而异的函数。…

点分治 解决的问题 常用于解决树上大规模的路径问题。 基本思想 由于树上所有的路径都可以转化为经过重心的路径和没有经过重心的路径，对于前者可以直接 $O(n)$ 处理，对于后者则可以递归子树处理。 时间复杂度是 $O(n \log n)$。 算法步骤 寻找树的重心，将其作为根。 求出所有端点是根的路径。 求解问题，并递归子树回到第一步。 细节 找重…

这次的难度是真的上去了，我在一开始的时候还想着能不能冲一下一道题目的高分，结果被狠狠打脸。在考场上很难切题，只能打部分分，但是打部分分就完完全全的暴露了我思维不够严密和代码准确度不高的问题，经常因为一些漏判条件和其他没有注意到的地方而失分。对于每次比赛的 T2 和 T3 基本上对于我来说是不可做的水平，补也很难补，于是就放弃了，我把大量的时间花在了…

hehezhou 杂题选讲 XXI Open Cup, Grand Prix of Korea C. Economic One-way Roads 考虑类似耳分解的结构，每次加入一个耳。 很显然可以先预处理出答案的下界，然后将边权于最小值做差，得到边 $(i, j)$ 不同方向的权值差。 考虑进行状态压缩，考虑将找强连同分量的过程转化为从一个环出发…

这篇文章受密码保护，输入密码才能阅读

解决的问题 博客 洛谷专栏 矩阵乘法在图论中常用于(定长/限制类)路径统计和最短路问题。此类型题目的时间复杂度往往是 $O(n^3 \log k)$，故此类题目的点数不应过大。 OI-wiki 一些代码技巧 struct Mat { int n; vector<VI> A; vector<int>& operator…

这篇文章受密码保护，输入密码才能阅读

比赛补题 ABC 350 C 题最开始因为一个变量在操作间不经意被修改吃了一发罚时，后怀疑自己方法有误，联想到了之前做过的一道排序题，敲完之后上交发现还是 WA 了。回到最开始的代码，检查了一下，发现了错误。虽然题目过了，但还是浪费了很多时间。或许不应该对自己的方法过早产生质疑。 F 题是一个非常经典的递归题（括号序列），这道题预计时间只有 30 …

如果 Latex 挂了多刷新awa。 UVA1099 Sharing Chocolate 这道题最开始读题的时候并没有理解题意，读题十分重要！之后并没有想到可以将长宽转换成面积和长，也没有想到新状态的面积与长的整除关系，这道题完全挂了。 AC code UVA1252 Twenty Questions 这道题最开始思路想复杂了，但是应该能写的出来，…