NOIP复赛笔记
这是一个普通的备赛笔记 一些基本函数和C++中STL库的用法 多记住一点，万一复赛用上了呢！另一个笔记 Heads #include <bits/stdc++.h> using namespace std; Class & Struct 基本结构 class Node { private: ...... public: ...... ...
并查集中的元素个数
……怎么样去求一个并查集中某一个集合的元素个数呢？ 究竟在找的时候递归得到答案，并完之后遍历，还是一个一个在合并的时候去查找呢？ 基本思想 初始化时将与father数组对应的num数组中的元素全部变为1 每一次合并时将被合并集合元素数加到合并到的集合的父节点的num中 => father[x] = y; //x的爸爸是y => num[y] += num[x]; //爸爸的元素数 ...
二维并查集
一道题目引发的扩展…… 岛屿的数量 题目 LeetCode 给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。 示例 1 输入: 11110 11010 11000 00000 输出: 1 2 输入: 11000 11000 00100 00011 输出: ...
并查集
定义 并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。 模版 class Unionfind { private: vector<int> father; public: Unionfind(int max_size) : ...
动态规划
定义及分类 多阶段决策过程的最优化问题。 动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。 Code实例 01Bag 题目 01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1W_1W1，W2W_2W2至WnW_nWn，与之相对应的价值为P1P_1P1,P2P_2P2至PnP_nPn。 在01背包问题中，因为每种物品只有一个，对于每个物品只需 ...
广度优先搜索
BFS主要思想 将全部邻接点入队列，以FIFO原则，依次访问所有未访问节点 模版题及其实现 最小花费 在n个人中，某些人的银行账号之间可以互相转账。 这些人之间转账的手续费各不相同。 给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得转账后B收到100元。 输入格式 第一行输入两个正整数n,m，分别表示总人数和可以互相转账的人的对数。 以下m行每行输入三个正 ...
二叉树的遍历
二叉树 二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。 二叉树的定义和结构 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(N ...
线段树
线段树的作用 线段树是一种二叉搜索树,它能以较低时间复杂度O(logN)得解决大规模求和、gcd等 空间复杂度为2N，但实际应用时还需4N的空间 查询和单点更改的代码实现 class NumArray { public: int *tree; int size; NumArray(vector<int> nums) { ...
First-blog
First Blog Formats Testing Testing testing Hyperlink 行内形式: Github 自动链接: Github http://github.com/GZTimeHacker List first item second item third item Table 表头1 表头2 表头3 表头4 默认左对齐 左对齐 居中对其 右对齐 ...
问
5e15dcdb3bbbdb8d74e8dcafcadae52530b6b8f271318fd724817cb4e9b31b054a68d85ee4907e7862cc9ca265535a088c9aa01e3ad2fdaf2f437b9c4470806fb04a6ff796ca222cfea0846dad925f8049e2ed2875f50b0d0ff09d57a13aec6059838 ...