二进制原码，反码，补码
原码，反码，补码 Emmm 就是用来表示数字的啊…… 对于有符号数： 在二进制数前面加上一个符号位表示正负，0表示正,1表示负 规则 负数的反码求法： 符号位不变。 其他位取反。 负数的补码求法： 符号位不变。 其他位取反。 最后一位加 1。 对于有符号数而言： 二进制的最高位是符号位：0 表示正数，1 表示负数； 正数的原码、反码、补码都一样； 负数的反码 = 它的原码符号位不变，其他位取反（0->1 ; 1->0）； 负数的补码 = 它的反码 +1； 0 的反码、补码都是...
进制转换
进制转换 (最大支持 62 进制) 很久之前就一直想搞这个东西，一直没有做出来，今天心血来潮写了出来。 因为中间存储数据的是long long所以如果一个进制表达的数字超出范围就无法转换了 Code #include <bits/stdc++.h> using namespace std; class NumConversion { private: long long _int_num; int _in_sys = 10; int _out_sys = 10; stack<int> tmp; string...
魔方大厦
测评请前往##Luogu## 题目背景 魔方大厦是个神奇的地方，王小一和他的同学们收到了一个陌生人的电话，告诉他们可以将大厦里面的房间分配给每一个人。作为一个时时刻刻都被同桌欺负的人，这可是个天大的扬眉吐气的好消息，于是他背上行囊准备出发。 题目描述 魔方大厦是一个边长为 n 的立方体。以它的一个顶点房间坐标为(0,0,0)(0,0,0)(0,0,0)，以对角线顶点房间坐标为(n−1,n−1,n−1)(n-1,n-1,n-1)(n−1,n−1,n−1)建立坐标系。每个房间可能在 6...
NOIP 复赛笔记
这是一个普通的备赛笔记 一些基本函数和 C++ 中 STL 库的用法 多记住一点，万一复赛用上了呢！另一个笔记 Heads #include <bits/stdc++.h> using namespace std; Class & Struct 基本结构 class Node { private: ...... public: ...... }; struct Node { ...... }; 构造函数 Node(int a, int b, int c) : x(a), y(b),...
并查集中的元素个数
……怎么样去求一个并查集中某一个集合的元素个数呢？ 究竟在找的时候递归得到答案，并完之后遍历，还是一个一个在合并的时候去查找呢？ 基本思想 初始化时将与 father 数组对应的 num 数组中的元素全部变为 1 每一次合并时将被合并集合元素数加到合并到的集合的父节点的 num 中 => father[x] = y; //x 的爸爸是 y => num[y] += num[x]; //爸爸的元素数再加上孩子的元素数 对现有 max(初始化为 0) 和当前集合元素数取 max 取最大元素数，减少计算量 查询元素所在集合的元素数即访问其父根节点的 num 数组值 =>...
二维并查集
一道题目引发的扩展…… 岛屿的数量 题目 LeetCode 给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。 示例 1 输入： 11110 11010 11000 00000 输出：1 2 输入： 11000 11000 00100 00011 输出：3 思路与实现过程 这道题隶属于 Leetcode...
并查集
定义 并查集，在一些有 N 个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。 模版 class Unionfind { private: vector<int> father; public: Unionfind(int max_size) : father(std::vector<int>(max_size+1)) { for (int i = 0; i <= max_size;...
动态规划
定义及分类 多阶段决策过程的最优化问题。 动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。 Code 实例 01Bag 题目 01 背包是在 M 件物品取出若干件放在空间为 W 的背包里，每件物品的体积为W1W_1W1，W2W_2W2至WnW_nWn，与之相对应的价值为P1P_1P1,P2P_2P2至PnP_nPn。 在 01 背包问题中，因为每种物品只有一个，对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中，则不需要处理。 求解将哪些物品装入背包可使价值总和最大。 主要思路 每一个物品有 2 种状态：不装 (0) 和装...
广度优先搜索
BFS 主要思想 将全部邻接点入队列，以 FIFO 原则，依次访问所有未访问节点 模版题及其实现 最小花费 在 n 个人中，某些人的银行账号之间可以互相转账。 这些人之间转账的手续费各不相同。 给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问 A 最少需要多少钱使得转账后 B 收到 100 元。 输入格式 第一行输入两个正整数 n,m，分别表示总人数和可以互相转账的人的对数。 以下 m 行每行输入三个正整数 x,y,z，表示标号为 x 的人和标号为 y 的人之间互相转账需要扣除 z%的手续费 (z<100)。 最后一行输入两个正整数 A,B。数据保证 A 与...
二叉树的遍历
二叉树 二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。 二叉树的定义和结构 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; 以存储 int 值为数据的二叉树为例，每一个二叉树节点有一个左节点和右节点，故以此建立树节点的结构体，初识孩子指针为...