From c074a8668c59a87b7e776fdcd3ff25a81800acc6 Mon Sep 17 00:00:00 2001 From: Ir1d Date: Tue, 23 Apr 2019 15:55:18 +0800 Subject: [PATCH] fix: update oj links and other minor fixes --- docs/basic/divide-and-conquer.md | 4 +--- docs/basic/expression.md | 2 +- docs/basic/greedy.md | 2 +- docs/basic/prefix-sum.md | 4 +--- docs/dp/interval.md | 4 ++-- docs/dp/memo.md | 2 +- docs/dp/number.md | 6 +++--- docs/dp/optimizations/convex-hull-optimization.md | 10 ++++----- docs/dp/optimizations/monotonous-queue-stack.md | 4 ++-- docs/ds/bit.md | 9 ++++---- docs/ds/dsu.md | 2 +- docs/ds/index.md | 4 ++-- docs/ds/monotonous-stack.md | 2 -- docs/ds/persistent-in-bit.md | 6 +++--- docs/ds/persistent-trie.md | 2 +- docs/ds/segment.md | 2 +- docs/ds/splay.md | 4 ++-- docs/ds/treap.md | 8 +++---- docs/geometry/distance.md | 12 +++-------- docs/geometry/half-plane-intersection.md | 2 +- docs/graph/flow.md | 26 ++--------------------- docs/graph/flow/node.md | 2 +- docs/graph/heavy-light-decomposition.md | 10 ++++----- docs/graph/shortest-path.md | 2 +- docs/intro/common-tricks.md | 4 ++-- docs/math/crt.md | 2 +- docs/misc/largest-matrix.md | 2 +- docs/misc/mo-algo.md | 4 ++-- docs/misc/random.md | 2 +- docs/string/sa.md | 5 ++--- 30 files changed, 58 insertions(+), 92 deletions(-) diff --git a/docs/basic/divide-and-conquer.md b/docs/basic/divide-and-conquer.md index 4e9851f2..3a338aa8 100644 --- a/docs/basic/divide-and-conquer.md +++ b/docs/basic/divide-and-conquer.md @@ -183,9 +183,7 @@ LeetCode 有递归专题练习，[点这里去做题](https://leetcode.com/explo ### 递归优化 -先来一道例题：[三连击](https://www.luogu.org/problemnew/show/P1618)。 - -这道题朴素的递归写法只能得到 25 分，因为递归次数太多，所以超时。 +比较 naive 的递归实现可能递归次数太多，容易超时。 怎么优化呢？详见[搜索优化](/search/optimization)和[记忆化搜索](/dp/memo/)。 diff --git a/docs/basic/expression.md b/docs/basic/expression.md index 8b90746a..efe2a945 100644 --- a/docs/basic/expression.md +++ b/docs/basic/expression.md @@ -86,6 +86,6 @@ int calc(const std::string &s) { // 计算转换好的后缀表达式 ## 习题 -1. [表达式求值（NOIP2013）](https://www.luogu.org/problemnew/show/P1981) +1. [表达式求值（NOIP2013）](https://vijos.org/p/1849) 2. [后缀表达式](https://www.luogu.org/problemnew/show/P1449) 3. [Transform the Expression](https://www.spoj.com/problems/ONP/) diff --git a/docs/basic/greedy.md b/docs/basic/greedy.md index 32887ca6..27103f61 100644 --- a/docs/basic/greedy.md +++ b/docs/basic/greedy.md @@ -25,7 +25,7 @@ 有些题的排序方法非常显然，如 [Luogu P1209 [USACO1.3]修理牛棚 Barn Repair](https://www.luogu.org/problemnew/show/P1209) 就是将输入数组差分后排序模拟求值。 -然而有些时候很难直接一下子看出排序方法，比如 [Luogu P1080 国王游戏](https://www.luogu.org/problemnew/show/P1080) 就很容易凭直觉而错误地以 $a$ 或 $b$ 为关键字排序，过样例之后提交就发现 WA 了 QAQ。一个~~众所周知的~~常见办法就是尝试交换数组相邻的两个元素来 **推导** 出正确的排序方法。我们假设这题输入的俩个数用一个结构体来保存 +然而有些时候很难直接一下子看出排序方法，比如 [NOIP 2012 国王游戏](https://vijos.org/p/1779) 就很容易凭直觉而错误地以 $a$ 或 $b$ 为关键字排序，过样例之后提交就发现 WA 了 QAQ。一个~~众所周知的~~常见办法就是尝试交换数组相邻的两个元素来 **推导** 出正确的排序方法。我们假设这题输入的俩个数用一个结构体来保存 ```cpp struct { diff --git a/docs/basic/prefix-sum.md b/docs/basic/prefix-sum.md index a98d3bfb..2527af10 100644 --- a/docs/basic/prefix-sum.md +++ b/docs/basic/prefix-sum.md @@ -114,11 +114,9 @@ int main() { 具体怎么搞？譬如使 $[l,r]$ 每个数加上一个 $k$ ，就是 $b_l \leftarrow b_l + k,b_{r + 1} \leftarrow b_{r + 1} - k$ 。 最后做一遍前缀和就好了。 -~~对于多维差分，自己手推一下就好了。（逃~~ - ### 习题 -- [P3368【模板】树状数组 2](https://www.luogu.org/problemnew/show/P3368)（需要掌握树状数组） +- [树状数组 3 ：区间修改，区间查询](https://loj.ac/problem/132) ## 树上差分 diff --git a/docs/dp/interval.md b/docs/dp/interval.md index a8f2aa53..834d182e 100644 --- a/docs/dp/interval.md +++ b/docs/dp/interval.md @@ -46,8 +46,8 @@ for (len = 1; len <= n; len++) ## 几道练习题 -[洛谷 P1063 能量项链](https://www.luogu.org/problemnew/show/P1063) +[NOIP 2006 能量项链](https://vijos.org/p/1312) -[洛谷 P1005 矩阵取数游戏](https://www.luogu.org/problemnew/show/P1005) +[NOIP 2007 矩阵取数游戏](https://vijos.org/p/1378) [洛谷 P4767\[IOI2000\]邮局](https://www.luogu.org/problemnew/show/P4767) diff --git a/docs/dp/memo.md b/docs/dp/memo.md index dbf859bb..97f9f2df 100644 --- a/docs/dp/memo.md +++ b/docs/dp/memo.md @@ -4,7 +4,7 @@ ## 记忆化搜索是啥 -好，就以[「Luogu P1048」采药](https://www.luogu.org/problemnew/show/P1048)为例，我不会动态规划，只会搜索，我就会直接写一个粗暴的 [DFS](/search/dfs): +好，就以[NOIP 2005 采药](https://vijos.org/p/1104)为例，我不会动态规划，只会搜索，我就会直接写一个粗暴的 [DFS](/search/dfs): - 注：为了方便食用，本文中所有代码省略头文件 diff --git a/docs/dp/number.md b/docs/dp/number.md index 3e2ed3a5..9f472467 100644 --- a/docs/dp/number.md +++ b/docs/dp/number.md @@ -2,7 +2,7 @@ 数位 DP 问题往往都是这样的题型，给定一个闭区间 $[l,r]$ ，让你求这个区间中满足 **某种条件** 的数的总数。 -??? note " 例题[洛谷 P2657\[SCOI2009\]windy 数](https://www.luogu.org/problemnew/show/P2657)" +??? note " 例题 [SCOI2009 windy数](https://www.lydsy.com/JudgeOnline/problem.php?id=1026)" 题目大意：给定一个区间 $[l,r]$ ，求其中满足条件 **不含前导 $0$ 且相邻两个数字相差至少为 $2$ ** 的数字个数。 首先我们将问题转化成更加简单的形式。设 $ans_i$ 表示在区间 $[1,i]$ 中满足条件的数的数量，那么所求的答案就是 $ans_r-ans_{l-1}$ 。 @@ -54,9 +54,9 @@ int solve(int x) { [BZOJ 3679 数字之积](https://www.lydsy.com/JudgeOnline/problem.php?id=3679) -[洛谷 P2602\[ZJOI2010\]数字计数](https://www.luogu.org/problemnew/show/P2602) +[ZJOI2010 count 数字计数](https://www.lydsy.com/JudgeOnline/problem.php?id=1833) -[洛谷 P4127\[AHOI2009\]同类分布](https://www.luogu.org/problemnew/show/P4127) +[Ahoi2009 self 同类分布](https://www.lydsy.com/JudgeOnline/problem.php?id=1799) [洛谷 P3413 SAC#1 - 萌数](https://www.luogu.org/problemnew/show/P3413) diff --git a/docs/dp/optimizations/convex-hull-optimization.md b/docs/dp/optimizations/convex-hull-optimization.md index d7fa042b..afe63f38 100644 --- a/docs/dp/optimizations/convex-hull-optimization.md +++ b/docs/dp/optimizations/convex-hull-optimization.md @@ -1,6 +1,6 @@ ## 斜率优化 -??? note " 例题[「Luogu P3195」「HNOI2008」玩具装箱 TOY](https://www.luogu.org/problemnew/show/P3195)" +??? note " 例题[「HNOI2008」玩具装箱 TOY](https://www.lydsy.com/JudgeOnline/problem.php?id=1010)" 令 $f_i$ 表示前 $i$ 个物品，随意分组装在任意多个容器里所能得到的最小费用。 写出 **状态转移方程** ： $f_i=max\{f_j+(pre_i-pre_j+i-j-1-L)^2\}$ ，其中 $pre_i$ 表示前 $i$ 个数的前缀和。 @@ -21,14 +21,14 @@ ### 几道练习题 -[「Luogu P4072」「SDOI2016」征途](https://www.luogu.org/problemnew/show/P4072) +[「SDOI2016」征途](https://www.lydsy.com/JudgeOnline/problem.php?id=4518) -[「Luogu P2120」「ZJOI2007」仓库建设](https://www.luogu.org/problemnew/show/P2120) +[「ZJOI2007」仓库建设](https://www.lydsy.com/JudgeOnline/problem.php?id=1096) -[「Luogu P3628」「APIO2010」特别行动队](https://www.luogu.org/problemnew/show/P3628) +[「APIO2010」特别行动队](https://www.lydsy.com/JudgeOnline/problem.php?id=1911) [「BZOJ 4709」「JSOI2011」柠檬](https://www.lydsy.com/JudgeOnline/problem.php?id=4709) [「Codeforces 311B」Cats Transport](http://codeforces.com/problemset/problem/311/B) -[「Luogu P4027」「NOI2007」货币兑换](https://www.luogu.org/problemnew/show/P4027) +[「NOI2007」货币兑换](https://www.lydsy.com/JudgeOnline/problem.php?id=1492) diff --git a/docs/dp/optimizations/monotonous-queue-stack.md b/docs/dp/optimizations/monotonous-queue-stack.md index 5adc493b..1cb4ec3e 100644 --- a/docs/dp/optimizations/monotonous-queue-stack.md +++ b/docs/dp/optimizations/monotonous-queue-stack.md @@ -32,6 +32,6 @@ [「Luogu P1886」滑动窗口](https://www.luogu.org/problemnew/show/P1886) -[「Luogu P2254」「NOI2005」瑰丽华尔兹](https://www.luogu.org/problemnew/show/P2254) +[「NOI2005」瑰丽华尔兹](https://www.lydsy.com/JudgeOnline/problem.php?id=1499) -[「Luogu P2569」「SCOI2010」股票交易](https://www.luogu.org/problemnew/show/P2569) +[「SCOI2010」股票交易](https://www.lydsy.com/JudgeOnline/problem.php?id=1855) diff --git a/docs/ds/bit.md b/docs/ds/bit.md index 7244082e..56be7aaf 100644 --- a/docs/ds/bit.md +++ b/docs/ds/bit.md @@ -1,7 +1,5 @@ ## 简介 -* * * - 树状数组和下面的线段树可是亲兄弟了，但他俩毕竟还有一些区别： 树状数组能有的操作，线段树一定有； 线段树有的操作，树状数组不一定有。 @@ -96,5 +94,8 @@ int getsum(int x) // a[1]……a[x]的和 ## 例题 -[传送门](https://www.luogu.org/problemnew/show/P3374) -[传送门 2](https://www.luogu.org/problemnew/show/P3368) +- [树状数组 1 ：单点修改，区间查询](https://loj.ac/problem/130) +- [树状数组 2 ：区间修改，单点查询](https://loj.ac/problem/131) +- [树状数组 3 ：区间修改，区间查询](https://loj.ac/problem/132) +- [二维树状数组 1：单点修改，区间查询](https://loj.ac/problem/133) +- [二维树状数组 3：区间修改，区间查询](https://loj.ac/problem/135) diff --git a/docs/ds/dsu.md b/docs/ds/dsu.md index 4e4cfc96..5379b2f5 100644 --- a/docs/ds/dsu.md +++ b/docs/ds/dsu.md @@ -115,7 +115,7 @@ void unionSet(int x, int y) { [「JSOI2008」星球大战](https://www.lydsy.com/JudgeOnline/problem.php?id=1015) -[「NOI2001」食物链](https://www.luogu.org/problemnew/show/P2024) +[「NOI2001」食物链](http://poj.org/problem?id=1182) [「NOI2002」银河英雄传说](https://www.luogu.org/problemnew/show/P1196) diff --git a/docs/ds/index.md b/docs/ds/index.md index 3bc1a1a8..55b84c1d 100644 --- a/docs/ds/index.md +++ b/docs/ds/index.md @@ -11,9 +11,9 @@ - A ：算法竞赛中，数据结构的考察主要分为两类： - ​ 1.考察对于特定信息的检索与维护和对特定操作的支持，例如[「SCOI2010」序列操作]() + ​ 1.考察对于特定信息的检索与维护和对特定操作的支持，例如[「SCOI2010」序列操作](https://www.lydsy.com/JudgeOnline/problem.php?id=1858) - ​ 2.使用合适数据结构加速信息检索，优化算法复杂度，例如[「APIO2012」派遣]() + ​ 2.使用合适数据结构加速信息检索，优化算法复杂度，例如[「APIO2012」派遣](https://www.lydsy.com/JudgeOnline/problem.php?id=2809) - Q ：有没有一种完美的数据结构可以搞定所有事情啊？ diff --git a/docs/ds/monotonous-stack.md b/docs/ds/monotonous-stack.md index fdea068e..78a6f32f 100644 --- a/docs/ds/monotonous-stack.md +++ b/docs/ds/monotonous-stack.md @@ -32,6 +32,4 @@ sta.push(x) ??? note "[POJ3250 Bad Hair Day](http://poj.org/problem?id=3250)" 有 $N$ 头牛从左到右排成一排，每头牛有一个高度 $h_i$ ，设左数第 $i$ 头牛与「它右边第一头高度 $≥h_i$ 」的牛之间有 $c_i$ 头牛，试求 $\sum_{i=1}^{N} c_i$ 。 - （可以左转 [洛谷 P2866](https://www.luogu.org/problemnew/show/P2866)） - 比较基础的应用有这一题，就是个单调栈的简单应用，记录每头牛被弹出的位置，如果没有被弹出过则为最远端，稍微处理一下即可计算出题目所需结果。 diff --git a/docs/ds/persistent-in-bit.md b/docs/ds/persistent-in-bit.md index a360e7ee..57806d64 100644 --- a/docs/ds/persistent-in-bit.md +++ b/docs/ds/persistent-in-bit.md @@ -1,10 +1,10 @@ -[静态区间 k 小值](https://www.luogu.org/problemnew/show/P3834)的问题可以用[主席树](/ds/persistent-seg/)在 $O(n\log_2 n)$ 的时间复杂度内解决。 +[静态区间 k 小值 (POJ 2104 K-th Number)](http://poj.org/problem?id=2104)的问题可以用[主席树](/ds/persistent-seg/)在 $O(n\log_2 n)$ 的时间复杂度内解决。 如果区间变成动态的呢？即，如果还要求支持一种操作：单点修改某一位上的值，又该怎么办呢？ -??? note " 例题[洛谷 P3380【模板】二逼平衡树（树套树）](https://www.luogu.org/problemnew/show/P3380)" +??? note " 例题[洛谷 P3380【模板】二逼平衡树（树套树）](https://loj.ac/problem/106)" -??? note " 例题[洛谷 P2617 Dynamic Rankings](https://www.luogu.org/problemnew/show/P2617)" +??? note " 例题[ZOJ 2112 Dynamic Rankings](http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1112)" 如果用[线段树套平衡树](/ds/balanced-in-seg/)中所论述的，用线段树套平衡树，即对于线段树的每一个节点，对于其所表示的区间维护一个平衡树，然后用二分来查找 $k$ 小值。由于每次查询操作都要覆盖多个区间，即有多个节点，但是平衡树并不能多个值一起查找，所以时间复杂度是 $O(n\log_2^3 n)$ ，并不是最优的。 diff --git a/docs/ds/persistent-trie.md b/docs/ds/persistent-trie.md index 96501d1f..fe7d6b09 100644 --- a/docs/ds/persistent-trie.md +++ b/docs/ds/persistent-trie.md @@ -2,7 +2,7 @@ 大部分的可持久化 Trie 题中，Trie 都是以 01-Trie 的形式出现的。 -??? note " 例题[洛谷 P4735 最大异或和](https://www.luogu.org/problemnew/show/P4735)" +??? note " 例题[最大异或和](https://www.lydsy.com/JudgeOnline/problem.php?id=3261)" 对一个长度为 $n$ 的数组 $a$ 维护以下操作： diff --git a/docs/ds/segment.md b/docs/ds/segment.md index a76a15dd..41ba07e5 100644 --- a/docs/ds/segment.md +++ b/docs/ds/segment.md @@ -322,7 +322,7 @@ int main() { ### LUOGU P3373【模板】线段树 2 -[传送门](https://www.luogu.org/problem/show?pid=3372) +[传送门](https://www.luogu.org/problem/show?pid=3373) 代码： diff --git a/docs/ds/splay.md b/docs/ds/splay.md index 6a7309be..7a2205eb 100644 --- a/docs/ds/splay.md +++ b/docs/ds/splay.md @@ -418,7 +418,7 @@ int main() { 以下题目都是裸的 $\text{Splay}$ 维护二叉查找树。~~（直接套板子即可）~~ -- [【模板】普通平衡树](https://www.luogu.org/problemnew/show/P3369) +- [【模板】普通平衡树](https://loj.ac/problem/104) - [\[HNOI2002\]营业额统计](https://www.lydsy.com/JudgeOnline/problem.php?id=1588) - [\[HNOI2004\]宠物收养所](https://www.lydsy.com/JudgeOnline/problem.php?id=1208) @@ -426,7 +426,7 @@ int main() { [luogu P4402 \[Cerc2007\]robotic sort 机械排序](https://www.luogu.org/problemnew/show/P4402)/[bzoj 1552（权限题）](https://www.lydsy.com/JudgeOnline/problem.php?id=1552) -[luogu P3380【模板】二逼平衡树（树套树）](https://www.luogu.org/problemnew/show/P3380) +[二逼平衡树（树套树）](https://loj.ac/problem/106) [bzoj 2827 千山鸟飞绝](https://www.lydsy.com/JudgeOnline/problem.php?id=2827) diff --git a/docs/ds/treap.md b/docs/ds/treap.md index 32646560..f8dd4529 100644 --- a/docs/ds/treap.md +++ b/docs/ds/treap.md @@ -285,12 +285,12 @@ int main() { ## 练习题 -[luogu P3369【模板】普通平衡树](https://www.luogu.org/problemnew/show/P3369) +[普通平衡树](https://loj.ac/problem/104) -[luogu P3391【模板】文艺平衡树（Splay）](https://www.luogu.org/problemnew/show/P3391) +[文艺平衡树（Splay）](https://loj.ac/problem/105) -[luogu P2596\[ZJOI2006\]书架](https://www.luogu.org/problemnew/show/P2596) +[\[ZJOI2006\]书架](https://www.lydsy.com/JudgeOnline/problem.php?id=1861) -[luogu P2042\[NOI2005\]维护数列](https://www.luogu.org/problemnew/show/P2042) +[\[NOI2005\]维护数列](https://www.lydsy.com/JudgeOnline/problem.php?id=1500) [CF 702F T-Shirts](http://codeforces.com/problemset/problem/702/F) diff --git a/docs/geometry/distance.md b/docs/geometry/distance.md index 4311b404..e7016d08 100644 --- a/docs/geometry/distance.md +++ b/docs/geometry/distance.md @@ -40,7 +40,7 @@ $$ \end{gathered} $$ -[NOIP2017 提高组 奶酪](https://www.luogu.org/problemnew/show/P3958) 就运用了这一知识，可以作为欧氏距离的例题。 +[NOIP2017 提高组 奶酪](https://loj.ac/problem/2317) 就运用了这一知识，可以作为欧氏距离的例题。 以此类推，我们就得到了 $n$ 维空间中欧氏距离的距离公式：对于 $\vec A(x_{11}, x_{12}, \cdots,x_{1n}) ,~ \vec B(x_{21}, x_{22}, \cdots,x_{2n})$ ，有 @@ -114,9 +114,7 @@ $$ ### 例题 1 -[Luogu P5098](https://www.luogu.org/problemnew/show/P5098) - -~~（不要被难度吓住，是假的）~~ +[USACO2004OPEN Cave Cows 3 洞穴里的牛之三](https://www.luogu.org/problemnew/show/P5098) 根据题意，对于式子 $|x_1-x_2|+|y_1-y_2|$ ，我们可以假设 $x_1 - x_2 \geq 0$ ，根据 $y_1 - y_2$ 的符号分成两种情况： @@ -340,8 +338,4 @@ $d(L_m) = (|x_1-x_2|^m+|y1-y2|^m)^{\frac{1}{m}}$ 我们可以简单的认为对两个串进行异或运算，结果为 1 的数量就是两个串的汉明距离。 ------- - -上面这两种距离在 OI 中并不常用，有兴趣的话可以深入了解一下。 - -部分内容搬运自[浅谈三种常见的距离算法](https://www.luogu.org/blog/xuxing/Distance-Algorithm)，感谢作者 [xuxing](https://www.luogu.org/space/show?uid=32139) 的授权。 +部分内容搬运自[浅谈三种常见的距离算法](https://www.luogu.org/blog/xuxing/Distance-Algorithm)，感谢作者 xuxing 的授权。 diff --git a/docs/geometry/half-plane-intersection.md b/docs/geometry/half-plane-intersection.md index 90e59851..7b9b1802 100644 --- a/docs/geometry/half-plane-intersection.md +++ b/docs/geometry/half-plane-intersection.md @@ -144,5 +144,5 @@ t[r+1]=its(q[l+1],q[r]);//再求出新的交点 [POJ 1279 Art Gallery](http://poj.org/problem?id=1279) 求多边形的核 -[洛谷 P4196 [CQOI2006]凸多边形](https://www.luogu.org/problemnew/show/P4196) +[[CQOI2006]凸多边形](https://www.lydsy.com/JudgeOnline/problem.php?id=2618) diff --git a/docs/graph/flow.md b/docs/graph/flow.md index 79b5b493..21fb1c90 100644 --- a/docs/graph/flow.md +++ b/docs/graph/flow.md @@ -30,27 +30,5 @@ ## 网络流 24 题 -- [「Luogu 1251」餐巾计划问题](https://www.luogu.org/problemnew/show/P1251) -- [「Luogu 2754」家园](https://www.luogu.org/problemnew/show/P2754) -- [「Luogu 2756」飞行员配对方案问题](https://www.luogu.org/problemnew/show/P2756) -- [「Luogu 2761」软件补丁问题](https://www.luogu.org/problemnew/show/P2761) -- [「Luogu 2762」太空飞行计划问题](https://www.luogu.org/problemnew/show/P2762) -- [「Luogu 2763」试题库问题](https://www.luogu.org/problemnew/show/P2763) -- [「Luogu 2764」最小路径覆盖问题](https://www.luogu.org/problemnew/show/P2764) -- [「Luogu 2765」魔术球问题](https://www.luogu.org/problemnew/show/P2765) -- [「Luogu 2766」最长不下降子序列问题](https://www.luogu.org/problemnew/show/P2766) -- [「Luogu 2770」航空路线问题](https://www.luogu.org/problemnew/show/P2770) -- [「Luogu 2774」方格取数问题](https://www.luogu.org/problemnew/show/P2774) -- [「Luogu 2775」机器人路径规划问题](https://www.luogu.org/problemnew/show/P2775) -- [「Luogu 3254」圆桌问题](https://www.luogu.org/problemnew/show/P3254) -- [「Luogu 3355」骑士共存问题](https://www.luogu.org/problemnew/show/P3355) -- [「Luogu 3356」火星探险问题](https://www.luogu.org/problemnew/show/P3356) -- [「Luogu 3357」最长k可重线段集问题](https://www.luogu.org/problemnew/show/P3357) -- [「Luogu 3358」最长k可重区间集问题](https://www.luogu.org/problemnew/show/P3358) -- [「Luogu 4009」汽车加油行驶问题](https://www.luogu.org/problemnew/show/P4009) -- [「Luogu 4011」孤岛营救问题](https://www.luogu.org/problemnew/show/P4011) -- [「Luogu 4012」深海机器人问题](https://www.luogu.org/problemnew/show/P4012) -- [「Luogu 4013」数字梯形问题](https://www.luogu.org/problemnew/show/P4013) -- [「Luogu 4014」分配问题](https://www.luogu.org/problemnew/show/P4014) -- [「Luogu 4015」运输问题](https://www.luogu.org/problemnew/show/P4015) -- [「Luogu 4016」负载平衡问题](https://www.luogu.org/problemnew/show/P4016) +https://loj.ac/problems/tag/30 + diff --git a/docs/graph/flow/node.md b/docs/graph/flow/node.md index e91815ee..ecb5fa5a 100644 --- a/docs/graph/flow/node.md +++ b/docs/graph/flow/node.md @@ -14,7 +14,7 @@ ![](./images/node2.png) -## 例题[luogu P4568\[JLOI2011\]飞行路线](https://www.luogu.org/problemnew/show/P4568) +## 例题[\[JLOI2011\]飞行路线](https://www.lydsy.com/JudgeOnline/problem.php?id=2763) 题目大意：有 $n$ 个结点， $m$ 条边， $k$ 张旅行券，可以使用一张旅行券使得经过该边的边权除以二向下取整，求从结点 $s$ 到 $t$ 的最短路的长度。 diff --git a/docs/graph/heavy-light-decomposition.md b/docs/graph/heavy-light-decomposition.md index c249427f..35f55ce0 100644 --- a/docs/graph/heavy-light-decomposition.md +++ b/docs/graph/heavy-light-decomposition.md @@ -276,14 +276,14 @@ int querymax(int x, int y) { [「luogu P3379」【模板】最近公共祖先（LCA）](https://www.luogu.org/problemnew/show/P3379)（树剖求 $lca$ 无需数据结构，可以用作练习） -[「JLOI2014」松鼠的新家](https://www.luogu.org/problemnew/show/P3258)（当然也可以用树上差分） +[「JLOI2014」松鼠的新家](https://www.lydsy.com/JudgeOnline/problem.php?id=3631)（当然也可以用树上差分） -[「HAOI2015」树上操作](https://www.luogu.org/problemnew/show/P3178) +[「HAOI2015」树上操作](https://www.lydsy.com/JudgeOnline/problem.php?id=4034) [「luogu P3384」【模板】树链剖分](https://www.luogu.org/problemnew/show/P3384) -[「NOI2015」软件包管理器](https://www.luogu.org/problemnew/show/P2146) +[「NOI2015」软件包管理器](https://www.lydsy.com/JudgeOnline/problem.php?id=4196) -[「SDOI2011」染色](https://www.luogu.org/problemnew/show/P2486) +[「SDOI2011」染色](https://www.lydsy.com/JudgeOnline/problem.php?id=2243) -[「SDOI2014」旅行](https://www.luogu.org/problemnew/show/P3313) +[「SDOI2014」旅行](https://www.lydsy.com/JudgeOnline/problem.php?id=3531) diff --git a/docs/graph/shortest-path.md b/docs/graph/shortest-path.md index cb718b8c..2a491109 100644 --- a/docs/graph/shortest-path.md +++ b/docs/graph/shortest-path.md @@ -283,7 +283,7 @@ for (i = 1; i <= n; i++) { 事实上，这个 DP 就相当于把每个结点拆分成了 $k+1$ 个结点，每个新结点代表使用不同多次免费通行后到达的原图结点。换句话说，就是每个结点 $u_i$ 表示使用 $i$ 次免费通行权限后到达 $u$ 结点。 -### 模板题：[\[JLOI2011\]飞行路线](https://www.luogu.org/problemnew/show/P4568) +### 模板题：[\[JLOI2011\]飞行路线](https://www.lydsy.com/JudgeOnline/problem.php?id=2763) 题意：有一个 $n$ 个点 $m$ 条边的无向图，你可以选择 $k$ 条道路以零代价通行，求 $s$ 到 $t$ 的最小花费。 diff --git a/docs/intro/common-tricks.md b/docs/intro/common-tricks.md index 9cd40bee..2dfa19ad 100644 --- a/docs/intro/common-tricks.md +++ b/docs/intro/common-tricks.md @@ -1,7 +1,5 @@ 本页面主要分享一下在竞赛中的小技巧。 -注：本页面部分内容最初发表于[洛谷日报 #86](https://studyingfather.blog.luogu.org/some-coding-tips-for-oiers)，由原作者整理并搬运至此，略有删改。 - ## 利用局部性 局部性是指程序倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身。局部性分为时间局部性和空间局部性。 @@ -203,3 +201,5 @@ inline Node* newnode(){ } ``` + +注：本页面 [部分内容](https://github.com/24OI/OI-wiki/commit/e9fa69af9d7f1583cb5ddad837c04bb1b03d7939) 最初发表于[洛谷日报 #86](https://studyingfather.blog.luogu.org/some-coding-tips-for-oiers)，由原作者整理并搬运至此，略有删改。 diff --git a/docs/math/crt.md b/docs/math/crt.md index 594ca0d8..7760909e 100644 --- a/docs/math/crt.md +++ b/docs/math/crt.md @@ -147,4 +147,4 @@ $$ [\[TJOI2009\]猜数字](https://www.luogu.org/problemnew/show/P3868) -[\[SDOI2010\]古代猪文](https://www.luogu.org/problemnew/show/P2480) +[\[SDOI2010\]古代猪文](https://www.lydsy.com/JudgeOnline/problem.php?id=1951) diff --git a/docs/misc/largest-matrix.md b/docs/misc/largest-matrix.md index a54ccf42..dd976bb8 100644 --- a/docs/misc/largest-matrix.md +++ b/docs/misc/largest-matrix.md @@ -60,4 +60,4 @@ for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) [luogu P1578 奶牛浴场](https://www.luogu.org/problemnew/show/P1578) -[luogu P1169 \[ZJOI2007\]棋盘制作](https://www.luogu.org/problemnew/show/P1169) +[\[ZJOI2007\]棋盘制作](https://www.lydsy.com/JudgeOnline/problem.php?id=1057) diff --git a/docs/misc/mo-algo.md b/docs/misc/mo-algo.md index 21260be6..4b4710d3 100644 --- a/docs/misc/mo-algo.md +++ b/docs/misc/mo-algo.md @@ -361,7 +361,7 @@ dfs 一棵树，然后如果 dfs 到 x 点，就 push_back(x),dfs 完 x 点， 这样的话，我们就把一棵树处理成了序列。 -例题是[\[WC2013\]糖果公园](https://www.luogu.org/problemnew/show/P4074), 这题是带修改树上莫队 +例题是[\[WC2013\]糖果公园](http://uoj.ac/problem/58), 这题是带修改树上莫队 题意是给你一棵树，每个点有颜色，每次询问 @@ -574,7 +574,7 @@ int main() { - 每个节点都要属于一个块 - 编号相邻的块之间的距离不能太大 -了解了这些条件后，我们看到这样一道题[\[SCOI2005\]王室联邦](https://www.luogu.org/problemnew/show/P2325) +了解了这些条件后，我们看到这样一道题[\[SCOI2005\]王室联邦](https://www.lydsy.com/JudgeOnline/problem.php?id=1086) 在这道题的基础上我们只要保证最后一个条件就可以解决分块的问题了 diff --git a/docs/misc/random.md b/docs/misc/random.md index ea650bbc..07f4d3ec 100644 --- a/docs/misc/random.md +++ b/docs/misc/random.md @@ -93,7 +93,7 @@ int main() { ## Example I -先来看一道网络流题：[「TJOI2015」线性代数](https://www.luogu.org/problemnew/show/P3973)。 +先来看一道网络流题：[「TJOI2015」线性代数](https://www.lydsy.com/JudgeOnline/problem.php?id=3996)。 我们并不想写网络流，于是开始偷税。建模？不存在的。 diff --git a/docs/string/sa.md b/docs/string/sa.md index c81f162e..ae2edfc1 100644 --- a/docs/string/sa.md +++ b/docs/string/sa.md @@ -423,7 +423,7 @@ $$ 某些题目求解时要求你将后缀数组划分成若干个连续 LCP 长度大于等于某一值的段，亦即将 $h$ 数组划分成若干个连续最小值大于等于某一值的段并统计每一段的答案。如果有多次询问，我们可以将询问离线。观察到当给定值单调递减的时候，满足条件的区间个数总是越来越少，而新区间都是两个或多个原区间相连所得，且新区间中不包含在原区间内的部分的 $h$ 值都为减少到的这个值。我们只需要维护一个并查集，每次合并相邻的两个区间，并维护统计信息即可。 -经典题目： [luogu P2178 「NOI2015」品酒大会](https://www.luogu.org/problemnew/show/P2178) +经典题目： [「NOI2015」品酒大会](http://uoj.ac/problem/131) ### 线段树 @@ -433,8 +433,7 @@ $$ 有些题目让我们求关于一个位置与之前所有位置的 LCP 的长度情况。利用 $LCP_{i,j}=\min\{h_{i+1},h_{i+2},...,h_j\}$ 的性质，我们发现这个 $LCP$ 的值是单调递减的。那么我们可以用一个单调栈来维护这些 LCP 值: 在新加入元素 $h_{i}$ 时，我们先把所有大于等于 $h_i$ 的值弹出，统计其个数，并将 $h_{i}$ 压入单调栈，个数为弹出的值的总个数加 $1$ 。 -经典题目有 [luogu P4248 「AHOI2013」差异](https://www.luogu.org/problemnew/show/P4248) 和 [luogu P3181 「HAOI2016」找相同字符](https://www.luogu.org/problemnew/show/P3181) 。 - +经典题目有 [「AHOI2013」差异](https://www.lydsy.com/JudgeOnline/problem.php?id=3238) 和 [「HAOI2016」找相同字符](https://www.lydsy.com/JudgeOnline/problem.php?id=4566) 。 ## 习题 -- 2.11.0