寂静山林

原创 对书稿的不定期更新……

书稿算是完成了第一版的定稿了，已经转成PDF供有需要的朋友免费使用，还请多多提出意见，以便进一步完善。以下是底稿更新的记录，适当的时候再放出第二版的定稿。

原创 我写的书：《C++，挑战编程——程序设计竞赛进阶训练指南》

这是我写的书《C++，挑战编程——程序设计竞赛进阶训练指南》的初稿，欢迎大家提出意见。本书的读者对象为计算机专业（或对ACM/ICPC竞赛感兴趣的其他专业）学生以及编程爱好者。可以作为ACM/ICPC竞赛训练的辅助参考书。本书不是面向初学者的C++语言教程，要求读者已经具备一定的C或C++编程基础，有一定的英语阅读能力，了解基本的数据结构，已经掌握了初步的程序设计思想和方法，具备相应的算法分析...

原创 《挑战编程:程序设计竞赛训练手册》- 题解（全）

PC = Programming Challenges （http://www.programming-challenges.com/）UVa = University of Valladolid Online Judge（http://uva.onlinejudge.org/）《挑战编程:程序设计竞赛训练手册》PDF下载地址（英文版）：http://acm.cs.buap.mx

原创 《挑战编程:程序设计竞赛训练手册》- 题解（第一章 - 第八章）

PC = Programming Challenges （http://www.programming-challenges.com/）UVa = University of Valladolid Online Judge（http://uva.onlinejudge.org/）《挑战编程:程序设计竞赛训练手册》PDF下载地址（英文版）：http://acm.cs.buap.mx/do

原创 UVa 10045 Echo

秒），却仍难以通过，因此可以考虑使用记忆化技巧，即将搜索过程中遇到的状态的结果进行记录，在下一次遇到时，不必重复搜索，而是直接返回结果，这样会大幅提高效率（这个技巧与动态规划中的备忘技巧很相似，同样可以应用该技巧的题目是。题目中给出了两个条件，一个是“回显”的条件，该条件说的是对于输入的每个字符，均可以在字符串中找到一个相同的字符与之对应，注意，这里是一一对应，不能两个字符对应同一个字符，如果满足该条件，则称之为满足“回显”条件。，但由于被截断，因此不满足“回显”的条件，只满足“缓存长度为。

原创 UVa 12916 Perfect Cyclic String

如果是逐个字符比较，可能会超时，将字符串散列后，可以快捷的获取某个子串的散列值，以此散列值来进行比对会大大提高效率。由于需要确定最小的周期字符串，那么对于长度为。本题可以通过字符串散列来予以解决。个字符一组进行比对，检查。，则从第一个字符开始，每。的字符串来说，可以从。

原创 UVa 12897 Decoding Baby Boos

题目给定一系列的替换规则以及最终的字符串，要求解题者按照规则替换字符串，显然，对于每个字符逐一根据规则逆向还原会超时，因此需要考虑更高效的方法。个大写字母在逆向应用规则后与哪个字母相对应，确定对应关系后，则可以直接输出。考虑到是按照顺序逆向应用规则，那么只需确定在最终给出的字符串中。注意，不需要考虑替换结果的逻辑性，因为本题并不存在合理的逻辑。的字母所对应的字母即可，也就是说，根据规则，反向确定。本题是一道模拟题目。

原创 UVa 11400 Lighting System Design

是类似的，属于重复的子问题，因此可以使用动态规划中的备忘技巧（将递归中已解决子问题的结果使用表格予以记录，当再次遇到此子问题时，直接查表获得结果），使用递归予以解决。显然，电压最高的灯泡必须选择，因为没有其他灯泡可以代替它们。那么对于不是最高电压的灯泡，可以选，也可以不选，如果不选，可以使用更高电压的灯泡来替换。题目允许使用具有更高适配电压的灯泡来替换较低适配电压的灯泡，直觉就是先将灯泡按照适配电压的高低递增排列，然后进行选择。类灯泡，可以选择或者不选，假定在第。类灯泡中，最后一次选择的是第。

原创 字符串散列

当两个不同的字符串依据上述方法转换得到的散列值相同时，称之为冲突（collide），为了尽量减少冲突出现的概率，可以使用两组（甚至多组）基数和模数，得到两个不同的散列值，将之配对来表示字符串的映射值，这样冲突的概率非常小。字符串散列（string hash，又称字符串哈希）是指在字符串和数值之间建立对应关系，相当于为字符串创建“指纹”。存在非常多的散列算法，下面介绍通过模运算实现的一种简易散列算法。有时并不需要获取整个字符串的散列值，而只需获取字符串某一部分的散列值，那么可以通过类似于前缀和的技巧来获取。

原创 UVa 12445 Happy 12

广度优先搜索 双向搜索

原创 UVa 11523 Recycling

的类型相同的物品过程中，遇到了一个不可回收的物品，那么此时不必再继续向右扫描，可以终止，因为无法将不可回收的物品放到回收桶中，后续的物品移除过程可以单独作为动态规划的一个子任务看待。来说，如果它不是一个可回收物品，那么不需考虑，只需继续考虑区间。及其右侧同类型的可回收物品一并移除，此时最少操作次数为。右侧的若干可回收物品，等待出现一个类型与最左侧物品。内的可回收物品所需的最少操作次数，那么对于区间。类似，可以说是该题的简化版本。移除，此时最少操作次数为。，而是先闲置，转而移除。时，选择将最左侧物品。

原创 UVa 10571 Products

使用回溯法解决挑战编程题目：UVa 10571 Products。

原创 UVa 12208 How Many Ones Needed?

如果问题能够分解为一系列的子问题而且子问题互不重叠，那么这往往提示可以应用动态规划思想，而上述分析中，问题符合这一性质。的个数然后求和，显然，这是低效的做法，对于题目所给定的测试数据规模，无法获得。的个数，可以应用前述的规律予以分解进行求和。内的整数，可以将其分成两个区间来统计其二进制表示中。的个数，问题是类似的，继续按照前述方法继续分解即可。的二进制表示，从左往右计数，除了第。的二进制表示，从左往右计数，除了第。的二进制表示，从左往右计数，除了第。，将其转换为二进制表示，假设为：；

原创 UVa 12870 Fishing

根据题意，捕鱼的过程和喂鱼的过程是相对独立的，互不影响，因此可以对捕鱼和喂鱼分别进行动态规划，然后枚举可能的捕鱼和喂鱼组合，确定最大的收益。利用动态规划可以确定。应用动态规划思想解题。次时的最大可能收益。

原创 我编写的书已经出版

第一卷：程序设计竞赛训练营：基础概念与数学第二卷：程序设计竞赛训练营：算法与实践

原创 UVa 10747 Maximum Subsequence

分类讨论加贪心解题。（1）读入数据，将其存放到数组 A 和 B 中。// Maximum Subsequence// UVa ID: 10747// Verdict: Accepted// Submission Date: 2021-11-12// UVa Run Time: 0.020s//// 版权所有（C）2021，邱秋。metaphysis # yeah dot net#include <bits/stdc++.h>using namespace std;in

原创 UVa 12911 Subset Sum

由于本题中 NNN 最大为 404040，生成所有子集显然不可行，需要适当变通。实际上，我们可以将数组分成两个数组 AAA 和 BBB，其大小只相差 111，分别生成 AAA 和 BBB 的所有子集和，由于 NNN 最大为 404040，则 AAA 的大小最大为 202020，AAA 中不同的子集和最多有 2202^{20}220 个，这是可行的。然后对于数组 AAA 的每个子集和 sss，在数组 BBB 的子集和中查找 T−sT - sT−s 是否存在，若存在，则将数组 AAA 中子集和 sss 的数量

原创 UVa 10707 2D-Nim

题目大意：给定两个网格图，是否能够对两个网格图的连通块建立一个映射（一一对应），使得左侧网格图中的任意一个连通块都可以通过镜像、旋转、平移操作的组合使得与右侧与之对应的连通块重合。原题解 https://lzsy01-xzy-blog.blog.luogu.org/solution-uva10707 存在问题，反例如下（由 lxyzxzy 给出）：14 4 50 2 1 0 1 1 1 2 2 20 1 1 0 1 1 1 2 2 1 正确输出“NO”，原题解输出“YES”。本题并不是判定图

原创 回复读者提问：位标记在素数筛中的应用

在编程竞赛中，如果要求确定某一范围内的素数，一个常用的方法是使用素数筛。在使用素数筛的过程中，需要记录某个数是否是素数，常见的方法是使用一个整数数组来记录，例如：const int MAXN = 10000010;int primes[MAXN], cnt;void sieve(){ for (int i = 2; i < MAXN; i++) { if (primes[i]) continue; primes[cnt++] = i; for (int j = i + i;

原创 如何高效地使用 UVa OJ 来进行练习？

由于UVa OJ的创建者Miguel Ángel Revilla教授已于2018年4月去世，而且UVa OJ过于老旧，兼之又是国外网站，打开非常缓慢，导致练习时阅读题目非常不便。不过由于国内IOI和ACM/ICPC的逐渐普及，有许多手段可以缓解这种情况，以下介绍三种方法。（1）UVa Arena（https://github.com/dipu-bd/UVA-Arena）。一款由编程爱好者Sudipto Chandra Dipu开发的软件，专门用来支持UVa OJ，可以通过此软件一次性下载UVa OJ上的所

原创 高斯消元法

原创 关于半平面交问题

原帖地址。先说点题外话。因为我是学医的（我专业是临床医学而不是计算机科学），在大三（有可能是大四，具体由于时间比较久，记不清楚了）的时候，老师教授《病理生理学》，这门课的目的是了解人体在疾病状态下组织和细胞所呈现的形态。但奇怪的是，老师在最初的几周并不给我们看疾病状态的组织和细胞的切片，而是反复给我们看正常情形下人体组织的细胞切片（比如肝细胞、上皮细胞等）。我们很纳闷，不禁向老师提出疑问。老师解释说，给你们看正常情形下的切片是为了让你们熟悉正常情况下人体的细胞是什么样子，当你们对正常情况的细胞是什么样子了

原创 第10章 图算法 10.5 网络流问题

原创 第2章 数据结构：2.11.1 线段树

原创 第3章 字符串：3.5.5 最长重复子串

原创 第3章 字符串：3.5.4 最长公共子串

原创 第3章 字符串：3.5.3 后缀数组

原创 第3章 字符串：3.5.2 Aho-Corasick算法

原创 UVa 10689 Yet Another Number Sequence

题目定义如下的序列：f(0)=af(0)=af(0)=a f(1)=bf(1)=bf(1)=b f(n)=f(n−1)+f(n−2),n>1f(n)=f(n-1)+f(n-2),n>1f(n)=f(n−1)+f(n−2),n>1如果 a=0a=0a=0，b=1b=1b=1，则序列为斐波那契序列（Fibonacci Sequence），如果 aaa 和 bbb 为其他值，则可以得到其他的序列。你的任务是在给定 aaa 和 bbb 的值之后，确定 f(n)f(n)f(n) 的最后 mmm

原创 第6章 组合数学：6.7.1 斐波那契数

原创 第13章 几何：13.6.5 最小圆覆盖

原创 第3章 字符串：3.5.1 Trie

原创 第14章 计算几何：14.5 凸包

原创 第14章 计算几何：14.5 坐标离散化

原创 11990 Dynamic Inversion（动态逆序对）

UVa 11990 Dynamic Inversion（动态逆序对）给定 {1，2，3，…，n}\{1，2，3，…，n\}{1，2，3，…，n} 的一个排列，从排列中每次删除一个数字，共删除 mmm 个数字，在每次删除数字之前输出该排列的逆序对数。数组 AAA 的逆序对数定义为二元组（iii，jjj）的数量：i<ji<ji<j 且 A[i]>A[j]A[i]>A[j]A[i]>A[j]。输入输入包含多组测试数据。每组测试数据的第一行包含两个整数 nnn 和 m（1≤

原创 第二章 数据结构：2.10 二叉树

原创 第一章 入门：1.3 格式化输出

原创 第一章 入门：1.2 格式化输入

原创 第一章 入门：1.1 基本数据类型

原创 第二章 数据结构：2.1.4 约瑟夫问题