逛公园
##Luogu## 题目描述 ShortestPath DynamicProgramming NOIP 2017 D1T3 策策同学特别喜欢逛公园。公园可以看成一张NNN个点MMM条边构成的有向图，且没有自环和重边。其中111号点是公园的入口，NNN号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。 策策每天都会去逛公园，他总是从1号点进去，从NNN号点出来。 策策喜欢新鲜 ...
扩展欧几里得
从欧几里得讲起…… 欧几里得的辗转相除法计算的是两个自然数a和b的最大公约数g，意思是能够同时整除a和b的自然数中最大的一个。 两个数的最大公约数通常写成GCD(a, b)，或者简写成(a, b)。 (Greatest Common Divisor) 计算方法……辗转相除! 作为数论中一个很基础的内容，它的形式很漂亮，代码也很干净。 gcd(a,b)=gcd(b,agcd(a,b) = gcd( ...
十七岁
5e15dcdb3bbbdb8d74e8dcafcadae52551c066d20e4ef052d985c24a93b467bd0169c6d9339b48e9e626e7659e0541c95cdc34129ad97eaeedbd03c186afa6a091ed194ff2503b68342795c4451358a509ada3b2904b0c4a6494466cd2d4390f36867 ...
二进制原码,反码,补码
原码，反码，补码 Emmm就是用来表示数字的啊…… 对于有符号数： 在二进制数前面加上一个符号位表示正负,0表示正,1表示负 规则 负数的反码求法： 符号位不变。 其他位取反。 负数的补码求法： 符号位不变。 其他位取反。 最后一位加1。 对于有符号数而言： 二进制的最高位是符号位：0表示正数，1表示负数； 正数的原码、反码、补码都一样； 负数的反码 = 它的原码符号位不 ...
进制转换
进制转换(最大支持62进制) 很久之前就一直想搞这个东西，一直没有做出来，今天心血来潮写了出来。 因为中间存储数据的是long long所以如果一个进制表达的数字超出范围就无法转换了 Code #include <bits/stdc++.h> using namespace std; class NumConversion { private: long long _ ...
魔方大厦
测评请前往##Luogu## 题目背景 魔方大厦是个神奇的地方，王小一和他的同学们收到了一个陌生人的电话，告诉他们可以将大厦里面的房间分配给每一个人。作为一个时时刻刻都被同桌欺负的人，这可是个天大的扬眉吐气的好消息，于是他背上行囊准备出发。 题目描述 魔方大厦是一个边长为n的立方体。以它的一个顶点房间坐标为(0,0,0)(0,0,0)(0,0,0)，以对角线顶点房间坐标为(n−1,n−1,n−1 ...
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) : ...