雨羊的博客|Rainsheep

STL常用容器总结之十：string

string的概念可以用来存放字符串，操作方便 string的基本操作头文件#include<string> String s;定义一个string；初始化 string s=”abc”;定义的时候直接赋值； Cin>>string;输入一个字符串，以空格、tab、换行结束； getline(

STL

背包模板

模板 /** * 多重背包： * 有N种物品和一个容量为 V的背包。第i种物品最多有 num[i]件可用， * 每件耗费的空间是C[i]，价值是W[i]。 * 求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。 */ #include <iostream> #in

动态规划

莫队算法

莫队算法我早有耳闻。。可惜前不久才去学习。但是自己看了看论文，也就 1h 左右，就能够全部理解了。也就是说其实这个算法不难。。好了，让我们进入正题。我们首先来看一道例题： Description 有n个数字，给出k，以及m个查询。每次查询的格式是L，r，求L~r（左右包含）这个区间内数字的

算法

最短距离模板

dijkstra算法：求指定两点间的距离（不适用负边权），O(n^2) #include<iostream> #include<vector> #include<cstdio> using namespace std; const int INF = 0x3fffffff; const

图

最小生成树模板

prim 算法按点算，适合于点少的情况邻接矩阵，时间复杂度 o(n^2) //PTA公路村村通 #include<iostream> #include<cstdio> using namespace std; const int INF = 0x3fffffff; const int MAXV

图

取模运算

取模运算规则（不适合除法） <1> (a + b) % p = (a % p + b % p) % p <2> a>=b时， (a - b) % p = (a % p - b % p+p) % p ,a<b时，判断结果正负 <3> (a * b) % p = (a % p * b % p) % p

计算机基础知识

原码，补码和反码

计算机中，数字是按补码存的，补码可以直接相加减，在依次变为反码，原码，就是最后的结果。一位二进制有八个数字，一个有符号定点数的最高位为符号位，0是正，1是副。正数的反码和补码都是和原码相同。负数的反码是将其原码除符号位之外的个位求反。负数的补码是将其原码除符号位之外的各位求反之后在末位再加1

计算机基础知识

二叉树遍历

已知先序中序构树 #include <cstdio> #include <iostream> using namespace std; const int N = 50; int pre[N], in[N], post[N]; //存放先序，中序，后序的数组 int n;//树中元素

树

a^b%c

利用二进制来写，提供一种新思路，也更加简洁，迅速 //res=ab%c //将b转化为二进制，1即为有这一个数，0即没有 //例如9的二进制1001 即 23+20 //则a9=a8*a1; a23和a20 的乘积 //求a的b次方对c取模 //(ab)%c==(a%c)(a%b) int fun(

数学问题

高精度运算

前言在这里，我们约定，能用 int 表示的数据视为单精度，否则为高精度。所有函数的设计均采用带返回值的形式。本文包含高精度加法高精度减法高精度乘法 3.1 高精度乘高精度的朴素算法 3.2 高精度乘高精度 FFT 优化算法 3.3 高精度乘单精度高精度除法 4.1 高精度除高精度 4.2

基础