Jer's blog

程序 最重要的啦！ 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] ...