NOIP&CSP注意事项
程序
最重要的啦!
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美文
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)表
基本概念
基本思想:记录的储存位置与关键字之间存在对应关系
对应关系-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] ...