余弦の博客

题目集总目录 学习指路博客 图论 # 07 - 图 4 哈利・波特的考试 (25 分) 本题链接 是很基本的算法应用，一定要做。如果不会，那么看看小白专场，会详细介绍 C 语言的实现方法 # 题目大意 给出每两个动物之间所需魔咒长度 哈利・波特最后应该带去考场的动物要使得最难变的动物所需总魔咒长度最小。 输出哈利・波特最后应该带去考场的动物的编号、以及最长的变形魔咒的长度 # 思路 用 Floyd 算法得出最短路矩阵 dist (dist [i][j] 表示 i 到 j 所需最短长度，在每行里找最难变 (即 dist [i][j] 最大) 的元素，在这些元素中找最小的，输出最小值的下标 i...

题目集总目录 学习指路博客 图 # 06 - 图 1 列出连通集 (25 分) 本题链接 非常基础的训练，一定要做 # 题目大意 输出图中所有连通集。先输出 DFS 的结果，再输出 BFS 的结果。 # 代码 #include <iostream>#include <cstdio>#include <queue>using namespace std;const int maxn = 11;int N,E,x,y;bool visited[maxn];int...

题目集总目录 学习指路博客 堆与哈夫曼树与并查集 # 05 - 树 7 堆中的路径 (25 分) 本题链接 将在 “小白专场” 中介绍 C 语言的实现方法，是建立最小堆的基本操作训练，一定要做 # 题目大意 给出最小堆的插入序列，和下标序列，每个下标 i 输出 Data [i] 到根结点路径上的值。 # 代码 #include <iostream>using namespace std;const int mindata = -10005;const int maxsize = 10000;typedef struct HeapStruct...

题目集总目录 学习指路博客 二叉搜索树与平衡二叉树 # 04 - 树 4 是否同一棵二叉搜索树 (25 分) 本题链接 小白专场将详细介绍 C 语言实现方法，属于基本训练，一定要做 # 题目大意 对于输入的各种插入序列，判断它们是否能生成一样的二叉搜索树。 # 思路 1. 分别建两棵树的判别方法 2. 不建树直接判断序列 3. 建一棵树再判别其他序列是否与该树一致 这里采用的是思路 3 # 代码 #include <iostream>using namespace std;#define maxsize 11typedef struct TNode*...

题目集总目录 学习笔记指路博客 线性表、堆栈 # 02 - 线性结构 1 两个有序链表序列的合并 (15 分) 本题链接 这是一道 C 语言函数填空题，训练最基本的链表操作。如果会用 C 编程的话，一定要做； # 代码 #include <stdio.h>#include <stdlib.h>typedef int ElementType;typedef struct Node *PtrToNode;struct Node { ElementType Data; PtrToNode Next;};typedef...

题目集总目录 # 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) {...

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

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

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

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...