``` \documentclass[UTF8]{ctexart} \usepackage{geometry} \usepackage{fancyhdr} \usepackage{graphicx} \usepackage{array} \newcommand{\PreserveBackslash}[1]{\let\temp=\#1\let…

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

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

j在某个寂静的机房里，小P正专注地编写代码，周围的机器低声运转，仿佛在伴奏他的编码乐章。经过一段时间的密集工作，他决定暂时放松一下，于是戴上耳机，打算让音乐洗净内心的疲惫。谁料，当耳机插入之后，他的思绪却被一阵突如其来的音响震撼了。犹如一阵突如其来的雷鸣，令他惊慌失措。 “这是何等的声音！”他发现，此刻耳机已经化身为扬声器，系统音量竟然达到了100…

今天，小 Y 兴致勃勃的告诉我们他买来了鲱鱼罐头，但作为井底之蛙的我理所应当不知道鲱鱼罐头是什么，当然我肯定也不知道作为鲱鱼罐头的开启者会有怎样的后果。 最开始，他们只是拿出来了一个看起来很像地雷的鲱鱼罐头，而且密封也做的相当不错。只见他们拿出一个螺丝刀开始疯狂的向那个鲱鱼罐头输出，当然我肯定也不知道为什么一个普普通通的地雷罐头密封要做的那么严实，…

点分治 解决的问题 常用于解决树上大规模的路径问题。 基本思想 由于树上所有的路径都可以转化为经过重心的路径和没有经过重心的路径，对于前者可以直接 $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…