题意描述

洛谷链接

LibreOJ 链接

在一个 \(2\) 维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段 \(\text{AB}\) 和线段 \(\text{CD}\)。lxhgww 在 \(\text{AB}\) 上的移动速度为 \(P\)，在 \(CD\) 上的移动速度为 \(Q\)，在平面上的移动速度 \(R\)。现在 lxhgww 想从 \(\text A\) 点走到 \(\text D\) 点，他想知道最少需要走多长时间。

题意描述

POJ 链接

给定一个数 \(n\)，求斐波那契数列第 \(n\) 项的后四位。

数据范围：\(1 \leq n \leq 10^9\)

题意描述

洛谷链接

LibreOJ 链接

对于任何正整数 \(x\)，其约数的个数记作 \(g(x)\)。例如 \(g(1) = 1\)，\(g(6) = 4\)。

如果某个正整数 \(x\) 满足：\(\forall 0 < i < x\)，都有 \(g(x) < g(i)\)，则称 \(x\) 为反质数。例如，整数 \(1, 2, 4, 6\) 等都是反质数。

现在给定一个数 \(N\)，你能求出不超过 \(N\) 的最大的反质数么？

数据范围：\(1 \leq N \leq 2 \times 10^9\)

题意描述

POJ 链接

给定一个长度为 \(N\) 的序列 \(A\)，要求构造一个长度为 \(N\) 的序列 \(B\)。\(B\) 满足以下条件：

1. \(B\) 非严格单调（单调递增或单调递减都可），

2. 在满足 \(1\) 的条件下，使 \(S = \sum_{i = 1}^{N} | A_i - B_i |\)。

仅需求出最小值 \(S\) 即可。题目数据满足 \(1 \leq N \leq 2000\)。

题意描述

UVa 链接

给定一个 \(n\) 个点 \(m\) 条边的无向图，每条边上都涂有 \(1\) 种颜色。求点 \(1\) 到点 \(n\) 的一条路径，使得经过的边数最少，在此前提下，经过边的颜色序列最小。可能有自环与重边。输入保证至少存在一条连接 \(1\) 和 \(n\) 的道路。

本文仅介绍 GCC 的使用以及在 OI 中使用的技巧，不涉及任何工程项目！

介绍

GCC 不用多说，是指的 GNU 编写的 C  C++ 编译器。包含 gcc、g++、gdb 等软件。

题意描述

洛谷链接

LibreOJ 链接

幼儿园里有 \(N\) 个小朋友，lxhgww 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww 需要满足小朋友们的 \(K\) 个要求。幼儿园的糖果总是有限的，lxhgww 想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

概念

差分约束指的是一种 \(n\) 元一次不等式组。令有 \(n\) 个未知数 \(x_1, x_2, \cdots, x_n\)，\(m\) 个形如 \(x_i - x_j \leq c_k\) 不等式，利用差分约束我们可以求出满足条件的解，或判断无解。

概念

最近公共祖先（英文 Lowest Common Ancestor，简称 LCA）定义为树种两个点的公共祖先里面，离根最远的一个。

概念

树状数组是一种维护线性数组前缀和的特殊方法，使用了类似于快速幂等的二进制分组的优势，对数组进行分段，从而可以快速求出该数组的前缀和的树形数据结构。

这一点与线段树类似。树状数组能干的事情线段树都能干，线段树能干的事情树状数组不一定能干。但树状数组相对线段树代码更短更好写，故在只涉及单点修改的时候树状数组更常用。