1.9k 字 2 分钟

题目集总目录 # 01 - 复杂度 1 最大子列和问题 (20 分) 本题链接 是本次课最后讲到的 4 种算法的实验题，属于基本要求，一定要做； # 代码 #include <iostream>using namespace std;int n, x, nowsum, maxsum;int main() { cin >> n; for(int i = 0; i < n; ++i) { cin >> x; nowsum += x; if (nowsum > maxsum) {...
4k 字 4 分钟

# 一、Fibonacci 博弈 # 描述 基本的斐波那契博弈（Fibonacci Game）描述如下： 有一堆石子，两个顶尖聪明的人玩游戏，先取者可以取走任意多个，但不能全取完，之后每次可以取的石子数至少为 1，至多为对手刚取的石子数的 2 倍。约定取走最后一个石子的人为赢家，求必败态。 # 结论 当且仅当总石子数为斐波那契数时，先手必败。 # 证明 证明如下，转自大佬证明 用到了 Zeckendorf 定理（齐肯多夫定理）：任何正整数可以表示为若干个不连续的 Fibonacci 数之和。 # 二、Bash 博弈 # 描述 基本的巴什博弈（Bash Game）描述如下： 有一堆 n...
2k 字 2 分钟

原博指路：MOOC 浙大数据结构课后题记录 ——PTA 数据结构题目集 (全) 本博客是为了记录学习数据结构时做的题集，若代码有疏漏欢迎指出！ 也相当于是一个数据结构的总结了～ ps：因为已经学过 c 了所以都用 c 写了，但也有很多 c 语言的东西。 MOOC 传送门 # 第一周 —— 最大子列和算法、二分查找 代码及其思路指路博客：PTA 数据结构题目集 第一周 —— 最大子列和算法、二分查找 # 01 - 复杂度 1 最大子列和问题 (20 分) # 01 - 复杂度 2 Maximum Subsequence Sum (25 分) # 01 - 复杂度 3 二分查找 (20 分) #...
7.5k 字 7 分钟

上周末的蓝桥杯省模拟赛时最后一题是一道最小生成树的题目，因为恰好在慕课上刚看到这个地方，所以现学了 Prim 算法，解决了这个题目 (大概)，赛后就打算多琢磨琢磨这一类题目。题目链接 最小生成树问题，是指给定无向图 G=(V,E)，连接 G 中所有点，且边集是 E 的子集的树称为 G 的生成树 (Spanning Tree)，而权值最小的生成树称为最小生成树 (Minimal Spanning Tree，MST)。 # 一、Kruskal 算法 Kruskal 算法易于编写，且效率很高 紫书 p356 描述如下： Kruskal...
6.1k 字 6 分钟

2020 蓝桥杯模拟省赛模拟赛题目及代码记录，若有错误欢迎指正！ 因为赛后没分数啥的也不知道哪道题对哪道题不对，只能靠做的时候的感觉所以可能会有疏漏。 # 1. 填空题 易知为 2018 # 2. 填空题 因为有两个字母重复，所以答案为 7！/ 2 = 2520 # 3. 填空题 4 对括号，可以枚举共有 14 种情况，也可以递归 #include <iostream>#include <vector>using namespace std;typedef long long ll;ll n,ans,total;//total...
4.1k 字 4 分钟

记录一下慕课学习的笔记，以及例题代码 # 一。递归到动规的一般转化方法 递归函数有 n 个参数就定义一个 n 维的数组， 数组的下标是递归函数参数的取值范围。 这样就可以从边界值开始逐步填充数组，相当于计算递归函数值的逆过程。eg：例题 1 数字三角形 # 二。动规解题的一般思路 # 1. 将原问题分解为子问题 将原问题分解为若干个子问题，与原问题的形式相同或类似，只不过规模小了。 子问题都解决，原问题即解决。 子问题的解一旦求出就会被保存，所以每个子问题只要求解一次。 # 2....
6.8k 字 6 分钟

# 一、图 # 1. 什么是图 表示 “多对多” 的关系，包含了： 一组顶点：通常用 V (Vertex) 表示顶点集合 一组边：通常用 E (Edge) 表示边的集合 无向边是顶点对：(v，w) ∈ E，其中 v，w∈V 有向边 <v,w> 表示从 v 指向 w 的边 (单行线) 不考虑重边和自回路 # 抽象数据类型定义 类型名称：图 (Graph) 数据对象集：G (V,E) 由一个非空的有限顶点集合 V 和一个有限边集合 E 组成。 操作集：对于任意图 G ∈ Graph, 以及 v ∈ V，e ∈ E Graph Create ():...
3.9k 字 4 分钟

# 一、堆 # 1. 堆是什么 堆（Heap), 是一个可以被看做一棵完全二叉树的数组对象，有以下性质： 任意节点的值是其子树所有结点中的最大值 / 最小值（有序性） 堆总是一棵用数组表示的完全二叉树。 # 2. 最大堆的操作函数 定义 typedef struct HeapStruct *MaxHeap;struct HeapStruct { ElementType *Elements;// 存储堆元素的数组 int Size;// 当前元素个数 int Capacity;// 最大容量};# (1) 空最大堆的创建 (Create...
10k 字 9 分钟

上篇说到 RMQ 问题可以用 ST 表算法处理，但需要在线修改的时候，线段树是更好的选择。 如图，很明显线段树是个二叉搜索树 要注意的点如下： 线段树用数组存储，数组空间简单的就一般开到原数组的 4*n 倍（准确的说是将 n 向上扩充到 2 的幂次方然后乘 2，如 5->8->16） 线段树数组存储中，某个结点的编号为 n，则其左子结点编号为 2 n（表示成 n << 1）, 右子节点编号为 2n+1 (表示为 n << 1 | 1) 规定根节点为 1 #...
8.1k 字 7 分钟

# 一、二叉搜索树 # 1. 二叉搜索树是什么 二叉搜索树（BST，Binary Search Tree), 又称二叉排序树或二叉查找树，是一棵二叉树，可以为空，当不为空时满足以下性质： 非空左子树的所有键值小于其根结点的键值 非空右子树的所有键值大于其根结点的键值 左、右子树都为二叉搜索树 # 2. 二叉搜索树的操作函数 # (1) 二叉搜索树的查找操作 Find 要查找的值为 X 从根结点开始查找，若树为空，则返回 NULL 若搜索树非空，则将 X 与根节点的键值进行比较并进行以下处理 若 X 小于根结点键值，则在左子树中搜索 若 X 大于根结点键值，则在右子树中搜索 若 X...