p站全程，「旧约」与「新约」① 洛谷刷题攻略！

在洛谷刷题的过程中，了解并掌握一些基本的算法和数据结构是非常重要的。在这篇文章中，我们将会介绍“旧约”与“新约”两个部分的洛谷刷题攻略，帮助你轻松提高自己的刷题水平。

旧约

一、基础语言：C++、Python

在旧约部分，掌握基础的编程语言非常重要。一般来说，C++和Python是目前洛谷使用最多的编程语言。C++的优势在于其速度快、流行度广、使用范围广，同时也是比赛中使用得最多的语言之一。而Python则因其易学易用而备受青睐，适合刚开始刷题的新手。

二、基础算法：模拟、搜索、排序、递归与分治

在刷洛谷题目时，我们需要掌握一些基本的算法。这些算法包括：模拟（Simulation）、搜索（Search）、排序（Sort）、递归（Recursion）与分治（Divide and Conquer）。

模拟：如果一个问题可以通过模拟实现，通常可以算作入门题。

搜索：搜索算法是指在一定的规则下朝着目标方向进行试探性地搜索，从而逐步逼近目标。搜索算法有广度优先搜索、深度优先搜索、IDA*搜索、A*搜索等。

排序：常用的排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序等。

递归：递归是指函数在操作过程中调用自己的行为。

分治：将一个大问题分解为几个小问题，递归地解决小问题，最后合并结果得到大问题的解。

三、基础数据结构：数组、链表、栈、队列、堆、哈希表、二叉树

在进行洛谷刷题时，我们需要熟悉一些基础的数据结构。这些数据结构包括：数组（Array）、链表（Linked List）、栈（Stack）、队列（Queue）、堆（Heap）、哈希表（Hash Table）和二叉树（Binary Tree）等。

数组：数组是一组元素的集合，这些元素通过下标进行访问。

链表：每个节点包含数据和指向下一个节点的指针。

栈：栈是一种只能在栈顶进行插入和删除操作的线性数据结构。

队列：队列是一种先进先出（FIFO）的线性数据结构，只允许在队列的末尾插入元素，在队列的头部删除元素。

堆：堆是一种树形数据结构，每个节点都有一个值。

哈希表：哈希表（散列表）是一种具有快速查找性能的数据结构。

二叉树：二叉树是一种树形数据结构，每个节点最多有两个子节点。

新约

一、常用算法：贪心、动态规划、图论

在新约部分，我们需要了解一些更高级的算法。这些算法包括贪心（Greedy）、动态规划（Dynamic Programming）和图论（Graph Theory）。

贪心：在求解最优问题时，每一步都选择当前状态下最优的策略。

动态规划：将一个问题分解成多个子问题，递归地求解子问题，最后得到原问题的解。

图论：图是由节点（vertex）和边（edge）组成的。图论是通过研究节点和边之间的关系，探索图的性质和特征的一门学科。

二、高级数据结构：线段树、树状数组、并查集、哈希集、Trie树

在新约部分，我们还需要了解一些更高级的数据结构。这些数据结构包括线段树（Segment Tree）、树状数组（Binary Indexed Tree）、并查集（Union-Find）、哈希集（HashSet）和Trie树。

线段树：用于快速查询某个区间内的最值或总和，时间复杂度为O(logn)。

树状数组：用于快速查询前N个数的和以及单点修改，时间复杂度为O(logn)。

并查集：主要用于维护一些不相交集合（Disjoint Set），在某些图论问题中使用，时间复杂度为O(alpha(n))。

哈希集：利用哈希函数将元素映射到一个桶中，可以实现常数级别的查找和插入操作。

Trie树：也叫字典树，可用于字符串匹配和前缀查询，时间复杂度为O(k)，k是字符串长度。

总之，掌握这些基础的算法和数据结构对于刷洛谷（LUOGU）题目来说是非常重要的。通过不断地练习和总结，我们可以逐渐提高自己的刷题能力，成为一名优秀的程序员。希望这份攻略能够帮助到你，祝大家在洛谷刷题中取得优异的成绩！