Jer's blog

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Quick Start Create a new post 1$ hexo new "My New Post" More info: Writing Run server 1$ hexo server More info: Server Generate static files 1$ hexo generate More info: Generating Deploy to remote sites 1$ hexo deploy More info: Deployment

程序 最重要的啦！ 12freopen("***.in", "r", stdin);freopen("***.out", "w", stdout); freopen在里 不开longlong见祖宗？ 按数据范围做决定，longlong读入时间大 数组空间不要开小。线段树开 倍，无向图开 倍。主席树开25倍 万能头不建议与x1/y1食用 与两种系统的换行符是不同的，其中的换行符时\n,而的换行符是\r\n。 当指数为整数时尽量不用 pow 函数，自己手写快速幂。 123456789ll qpow(ll n, ll base, ll mod) { ll ret = 1; while(n) { if(n & 1) ret = ret * base % mod; base = base * base % mod; n >>= 1; } return ret;} 打表出省一，有些数据范围小，自己程序过不了的可以考虑本地运行打表。 线段树 push_up()时要回传tag i与 j 的区别 ...

powerby洛谷词典2 洛谷词典 当前词条数： 来源 洛谷词典1.0 2020/9/12版 另一个洛谷词典 2020/11/28版 作者及他人贡献 ### 推荐阅读 洛谷重要人物信息 ### 食用方法 Ctrl+F搜索 按首字母检索 # and awsl即“啊我死了”，是“啊，XX太可爱，我要死了”的缩写，主要用来形容对看到可爱的事物时的激动心情。 AK指比赛全对 AuNOI/IOI/WC/APIO/CTSC等拿金牌 az“啊这”缩写 AFOAway From OI awa表示很萌awa Akssh5307据说@Karry5307在HNOI2021 用了 SSH 贺题 # bool bushi,bs等词在括号里使用，或者用删除线，表示括号外的消息也为开玩笑，后三个为第一个的变体 犇犇洛谷知名ghs区（，起名原因：6*牛 BDS,BFS,BDFS,BaiduFirstSearch百度搜/搜/广度优先搜索 爆蛋,爆零,抱灵,抱铃FAKE的表现，说自己题目得分0分（最后一个来自犇犇，曾经指抱@灵空，现在指@铃酱） 布吉岛不知道 bug程序错误 btd标题党 板块漂移学说指xxs在洛谷 ...

chen_zhe先生 浙江也无非是这样。NOIP爆0的时节，望去确也象绯红的轻云，但WA下也缺不了成群结队的“天朝OIer”的速成班，头顶上盘着大辫子，顶得绿帽的顶上高高耸起，形成一棵主席树。也有解散辫子，盘得平的，除下帽来，油光可鉴，宛如小蒟蒻的算法一般，还要将脖子扭几扭。实在标致极了。 天朝OIer会馆的门房里有几本《算法导论》买，有时还值得去一转；倘在上午，里面的几间洋房里倒也还可以坐坐的。但到傍晚，有一间的地板便常不免要咚咚咚地响得震天，兼以满房烟尘斗乱；问问精通时事的人，答道，“那是在学DP。” 到别的地方去看看，如何呢？ 我就往上海的OI专门机房去。从长沙出发，不久便到一处驿站，写道：新♂日♂暮♂里。不知怎地，我到现在还记得这名目。其次却只记得温州了，这是江南皮革厂的老板黄鹤王八蛋欠钱的地方。上海是一个强市，并不大；夏天热得利害；还没有浙江的OIer。 大概是物以希为贵罢。北京的白菜运往浙江，便用红头绳系住菜根，倒挂在水果店头，尊为“胶菜”；福建野生着的芦荟，一到北京就请进温室，且美其名曰“龙舌兰”。我到上海也颇受了这样的优待，不但机房不收学费，几个教练还为我的食宿操心。我 ...

黑板上写着一道数学题： 1a>0, a+1<0. 数竞大神小AA对信息学大佬小BB说：“ 你连初中数学都没学过吗？原不等式组显然无解。” 小BB拿起了一根粉笔，对小AA微微一笑，转身在黑板上写下了： 1a=2147483647. 少年chen_zhe 明亮的机房中开着一台神秘的电脑，旁边是一个题库，都存着一望无际的chen_zhe做的神仙毒瘤题，其间有一个十二三岁的少年，血管里流着网络流，靠着一棵平衡树，向蒟蒻的lhy930尽力地踩去，lhy930被爆踩了好久后却将身一扭，反从他的胯下跳进他家的内存池了。 这少年便是chen_zhe。我被他爆踩时，也不过十多岁，离现在将有几年了；那时我还没开始学OI，也很LJ，我正是一个蒟蒻。那一年，我家是一件大比赛的值年。这比赛，说是三十多年才能轮到一回，所以很毒瘤；正月里做神仙毒瘤题，题目很多，数据很讲究，做的人也很多，数据也很要防偷去。我家只有一个忙月，忙不过来，他便对父亲说，可以叫他的儿子chen_zhe来出题配数据的。 我的父亲允许了；我也很高兴，因为我早听到chen_zhe这名字，而且知道他和我仿佛年纪，是个神犇巨佬，会做和出神 ...

哈夫曼树浅谈 1.定义 结点的权：有某种现实含义的数值（如：表示结点的重要性等 结点的带权路径长度：从树的 根结点 到该结点的路径长度（经过的边数）与该结点上权值的乘积 树的带权路径长度：树中所有 叶结点 的带权路径长度之和（ WPL, Weighted PathLength ） 在含有 n 个带权叶结点的二叉树中，其中带权路径长度（ WPL ）最小的 二叉树 称为哈夫曼树，也称最优二叉树 2.构造 12哈夫曼树权值越大的叶子离根越近贪心算法思想，先选择最小的叶子 给定 n 个权值分别为 w1, w2,…, wn 的结点，构造哈夫曼树的算法描述如下： 将这 n 个结点分别作为 n 棵仅含一个结点的二叉树，构成森林 F 。 构造一个新结点，从 F 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。 从 F 中删除刚才选出的两棵树，同时将新得到的树加入F 中。 重复步骤2和3，直至 F 中只剩下一棵树为止。 代码实现 123456789101112131415161718192021222324252627282930 ...

背包 易错点 初值如：（0 ，1）/（-1 ，1e9 ,0)...... 递推方程 边界问题是否出界 0-1背包 两种表达方式 1234567891011121314151617181920212223242526272829#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;int main() { int n ,m; cin >> n >> m; int dp[2000][2000]={0}; //dp[i][j]为前i个物体，用j体积最大价值 int w[2000] ,v[2000]; memset(dp ,-1, sizeof(dp));//dp[][]==-1表示不可能 dp[0][0]=0;//特殊的没用物体，用0体积可能，但价值为0 for(int i=1;i<=n;i++) cin >> w[i] >> v[i]; for(int i=1 ...

数组储存 数组一般采用顺序储存结构，因为存储单位元是一维的，而数组可以是多维的，如何用一组连续的储存单位来储存多维数组呢？以二维数组为例，可以按行序储存即先存第一列 ，再存第二列 ，......; 如果按行序，如何找到的存储位置 若表中大多数储存为空则浪费空间，需使用压缩存储的方法减少浪费 知识点概述 什么是压缩存储？ 把多个相同的元素分配一个存储空间 ，元素为0的不分配空间。 什么样的矩阵能够压缩？ 特殊矩阵，如：对称矩阵，对角矩阵 ，三角矩阵，稀疏矩阵等。 什么叫稀疏矩阵？ 矩阵中非零元素的个数较少 ，一般认为非零元素个数小于5%的矩阵为稀疏矩阵。 稀疏矩阵的压缩储存 三元组法 M由{(1,2,12) ,(1,3,9) ,(3,1,-1) ,(3,6,14) ,(4,3,24) ,5,2,18) ,(6,1,15) ,(6,4,-7)} 和矩阵(6，7)唯一确定。 十字链表法 在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了(row ,col ,value)以外，还有两个域： right：用于链接同一行中的下一个非零元素； down：用以链接同一 ...

散列（Hash）表 基本概念 基本思想：记录的储存位置与关键字之间存在对应关系 对应关系-hash函数 Address(i) = H(key) 根据关键字函数映射 散列表的查找 123根据散列表函数 H(key)=k查找key=9 ，则访问H(9)=9号位置 ，若内容为9则成功；若查不到，则返回一个特殊值 ，如空指针或空记录。 正题 数值的哈希 Hash函数的作用就是通过对数据进行计算。得出存放该放该数据的对应位置。使得数据和存放位置相对应完成高效的查找。因此，Hash表的各种操作能否做到常数时间的关键就是Hash函数的构造。 取余法 用关键字key除于M的余数作为hash表中的位置函数表达式可以写成：h(k)=k%P ，适用于整数 乘积取整法 用关键字k除于一个在（0 ，1）中的实数A （最好是无理数） ，得到一个（0 ，k）之间的实数；取出小数部分 ，乘以M，再取整数部分 ，即得k在Hash表中位置。函数表达式为： 这类函数适用于小数 冲突处理法 散列表会有冲突，即多个不同的关键值对应同一个索引，所以需要设计一些结构去解决这些冲突 挂链法（Separate Ch ...

线性数据结构 数据结构 优点 缺点 数组 插入快 查找慢 ，删除慢 ，大小固定只能存储单一元素 有序数组 比无序数组查询快 插入慢 ，删除慢 ，大小固定只能存储单一元素 栈 提供后进先出的存储方式 存储其他项慢 队列 提供先进先出的存储方式 存储其他项 链表 插入快 ，删除快 查找慢 二叉树 如果数是平衡的 ，则查找，插入，删除快 删除算法复杂 2-3-4树 查找，插入，删除快 ，树总是平衡的 算法复杂 哈希表 如果关键字已知则存储极快 删除慢 ，如果不知道关键字存储慢，对储存空间使用不充足 堆 插入 ，删除快 ，对最大数据储存快 对其他数据存取慢 图 对现实世界建模 有些算法慢而复杂 红黑树 查找，插入，删除快 ，树总是平衡的 算法复杂 二叉堆 链表 树状数组 指针 1. 指针变量（int *p) 与普通变量（int a)的关系 123p ------ &a //&为取地址运算符*p ------ a //*为间接运算符*p=3 ------ a=3 2. 指针变量定义 1int *p=NULL; ...

堆排序 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include <cstdio>#include <iostream>#include <algorithm>using namespace std;int a[1000000];int heap[1000000] ,cnt;int n;/*下标 1 2 3 4 5 | 6 7*/int query(){//查询最大 if(!cnt)return -1; return heap[1]; }void insert(int x){//插入 cnt++; heap[cnt]=x; int k=cnt; while(k!=1 && heap[k] > heap[k/2])swap(heap[k] ,heap[k/2]) ,k=k/2;}void del(int x){//删除 swap(heap[x] ...