将代码保存为.cpp文件而不是.c文件（为了使用C++中的一些良好特性,故用C++的文件扩展名）提交代码时的选项也是C++而非C
对一般的OJ系统来说,一秒能承受的运算次数大概是 1 0 7 10^7 107~ 1 0 8 10^8 108
关于变量类型: 绝对值不超过 1 0 9 mathbb{10^9} 109都能用整型变量；若long long型赋的初值大于 2 31 − 1 2^{31}-1 231−1则需在初值后面加上LL,否则会编译错误。
对整型来说， 如果题目要求 1 0 9 10^9 109以内或者32位整数,就用int型存放；如果 1 0 18 10^{18} 1018以内或者64位整数,就要用long long型存放。
对浮点型来说，一般不使用float，碰到浮点型的数据都应该用double存储。对于double型变量,其输出格式是%f 而在scanf中是 %lf
对字符型来说，小写字母比大写字母的ASCII码值大32。 代表空字符NULL, 其ASCII码为0, 注意 不是空格
quadquadquadquadquad,,,,, 字符常量勿漏掉单引号标注, 打印时用%c ；而字符串常量用双引号标注, 存在字符型数组或string中, 打印时用%s
quadquadquadquadquad,,,,, 字符串在scanf中不用加&取址，因为数组名称已经代表了地址
关于scanf输入: 如果需要过滤一次换行符，可以单用一句 getchar();
quadquadquadquadquad,,,,,, 除了%c外, scanf对其他格式符(如%d)的输入都以空白符(即空格、Tab、回车)为结束判断标志。除非使用%c把空格按字符读入,其他情况都会自动跳过空格。( 注：结束的仅是一个%d 而不是整个一句scanf )
quadquadquadquadquad,,,,,, %s用来输入一个字符串并存在字符数组里，%c格式能够识别空格跟换行并将其输入，而%s通过空格或换行符来识别一个字符串的结束。另外,字符数组使用%s读入的时候也以空格跟换行为读入结束的标志。
quadquadquadquadquad,,,,,, 注：下图中若scanf中改为 scanf("%d %c %s",&a,&c,str); 则输出结果是 a=1,c=a,str=bcd
关于输出格式: %.mf , 可以让浮点数保留m位小数输出,这个“保留”使用的是精度的“四舍六入五成双”规则。很多题目都会要求浮点数的输出保留×位小数(或是精确到小数点后××位),就是用这个格式来进行输出(如果是四舍五入,那么需要用到round函数)
quadquadquadquadquad,, %0md , 只在%md中间多加了0。和%md的唯一不同点在于,当变量不足m位时,将在前面补足够数量的0而不是空格。
quadquadquadquadquad,, %md , 可以使不足m位的int型变量以m位进行右对齐输出,其中高位用空格补齐;如果变量本身超过m位,则保持原样。
关于数组: 如果数组大小较大(大概 1 0 5 10^5 105级别)，则需要将其定义在主函数外面，否则会使程序异常退出。原因是函数内部申请的局部变量来自系统栈,允许申请的空间较小;而函数外部申请的全局变量来自静态存储区,允许申请的空间较大。
quadquadquad,,, 二维数组按行(逐行)赋值，如 int a[5][6] = { {1, 2, 3}, {1, 2}, {}, {1, 2, 3, 4, 5}, {} } ; 其他未被赋值的元素被默认赋为0
quadquadquad,,, 必须注意二维数组使用首地址 &a[0][0] 时只有 a[0] 与之可以等价互换, 而若像一维数组只用数组名 a 时并不等价
quadquadquad,,, 将数组的所有元素赋相同的值, 通常选用 fill函数 (详见经验总结)
关于字符数组: char str[15] = { ‘H’, ‘e’, ‘l’, ‘l’, ‘o’ , ’ ’ , ‘!’ }; 等效于 char str[15] = “Hello !”; 但后者只限于初始化，程序的其他位置不能这样直接将字符串赋值给字符数组。
quadquadquadquadquad, getchar和putchar各用来输入和输出单个字符。若需要把输入中每行末尾的换行符吸收掉可巧妙单用一行getchar();
quadquadquadquadquad, gets用来输入一行字符串（注意: gets识别换行符n作为输入结束，因此scanf完一个整数后，如果要使用gets，需要先用getchar吸收整数后的换行符），并将其存放在一维的字符数组（或二维数组中的一维）中；puts用来输出一行字符串，即将一维数组（或二维数组的一维）在界面上输出，并紧跟一个换行。
quadquadquadquadquad, 字符数组的每一位都是一个char字符，在一维字符数组的末尾都有一个空字符 即NULL,以表示存放的字符串的结尾。注意结束符 占用一个字符位，因此开字符数组的时候千万要记得字符数组的长度一定要比实际存储字符串的长度至少多1。还需注意如果不是使用scanf函数的%s格式或gets函数输入字符串(例如使用getchar), 一定要在输入的每个字符串后加入" ",否则printf和puts输出字符串会因无法识别字符串末尾而输出一大堆乱码。
常用math函数: fabs(double x) ,,,, 用于对double型变量取绝对值
quadquadquadquadquad,,,, floor(double x) ,,,, 用于对double型变量向下取整
quadquadquadquadquad,,,, ceil(double x) ,,,,,, 用于对double型变量向上取整
quadquadquadquadquad,,,, round(double x) , 用于将double型变量x四舍五入,返回类型也是double型,需进行取整
quadquadquadquadquad,,,, pow(double r, double p) , 用于计算幂次方,要求r和p都是double型
quadquadquadquadquad,,,, sin(double x)、cos(double x)、tan(double x) 注意其中的参数要求是弧度制
quadquadquadquadquad,,,, sqrt(double x)、asin(double x)、acos(double x)、atan(double x)
quadquadquadquadquad,,,, log(double x) 注意其底数为e, C中没有对任意底数求对数的函数,因此必须借助换底公式来转换不是以e为底的对数
常用的<string.h>的函数: strlen(字符数组名) , 得到字符数组中第一个 前的字符的个数 (其函数内部是用循环实现, 故不要重复使用)
quadquadquadquadquadquadquadquadquad,,,, stremp(字符数组1,字符数组2) , 返回两个字符串大小的比较结果,比较原则是按字典序
quadquadquadquadquadquadquadquadquad,,,, strcpy(字符数组1,字符数组2) ,,, 把字符数组2复制给字符数组1,这里的复制包括了结束符
quadquadquadquadquadquadquadquadquad,,,, strcat (字符数组1,字符数组2) ,,, 把字符数组2接到字符数组1后面
sscanf与sprintf : sscanf可以理解为string + scanf, sprintf则可以理解为string + printf,均在<stdio.h>头文件下。
quadquadquadquadquadquad,,,, sscanf (str, “%d”, &n); ,,, 把字符数组str中的内容以"%d"的格式写到n中 (从左至右读)
quadquadquadquadquadquad,,,, sprintf (str, “%d”, n); ,quad 把n以"%d"的格式写到字符数组str中 (从右至左读)
sprintf 跟 printf 在用法上几乎一样，只是打印的目的地不同而已。前者打印到字符串中，后者则直接在命令行上输出。
更复杂的应用如这两个代码。其一使用sscanf将字符数组str中的内容按"%d:%lf,%s"的格式写到int型变量n, double型变量db,char型数组str2中。其二使用sprint将int型变量n, double型变量db,char型数组str 2按 "%d:%.2f,%s"的格式写到字符数组str中。
函数中关于传递的参数: 全局变量是指在定义之后的所有程序段内都有效的变量(即定义在所有函数之前)。局部变量定义在函数内部,且只在函数内部生效,函数结束时局部变量销毁。
quadquadquadquadquadquadquadquad,,,,, 函数的某个参数是数组时,参数中数组的第一维不需要填写长度 (如果是二维数组,那么第二维需要填写长度),实际调用时也只需要填写数组名。最重要的是,数组作为参数时,在函数中对数组元素的修改就等同于是对原数组元素的修改(这与普通的局部变量不同)。不过虽然数组可以作为参数,但是却不允许作为返回类型出现。
quadquadquadquadquadquadquadquad,,,,, 指针类型也可以作为函数参数的类型，这时视为把变量的地址传入函数。如果在函数中对这个地址中的元素进行改变 (注意是修改*p而不是x=*p后修改x)，原先的数据就会确实地被跟着改变。数组的情况与此同理。
quadquadquadquadquadquadquadquad,,,,, 引用 (设置函数时在函数的参数类型后面加个&) 可以不使用指针而达到修改传入参数的目的。引用就相当于给原来的变量又取了个别名，这样旧名字跟新名字其实都是指同一个东西。对引用变量的操作就是对原变量的操作。由于引用是产生变量的别名，因此常量不能使用引用。故对于指针的引用，由于变量a的地址&a是常量，必须赋给指针变量p后才能引用，如 void swap(int ∗ * ∗ &p, int ∗ * ∗ &q)
关于指针变量: 指针变量也可以进行加减法,其结果就是两个地址偏移的距离。对一个 int*型的指针变量p来说, p+1是指p所指的int型变量的下一个int型变量地址。这个所谓的下一个是跨越了一整个int型(即4Byte),因此如果是p+i,则说明是跨越到当前int型变量之后的第i个int型变量。此外,指针变量支持自增和自减操作,因此p++等同于p=p+1使用。指针变量的加减法一般用于数组中。
quadquadquadquadquad,,, 数组名称也作为数组的首地址使用,因此对int型数组a[MAX]来说,有a==&a[0]成立。结合指针变量可以进行加减法,可知 a+i 等同于 &a[i] 。但a+i其实只是地址,如果想要访问其中的元素a,变成 *(a+i) 才和 a[i] 等价。
若考虑浮点数经计算后的误差: 会对比较大小、函数中的定义域受限时传入参数、输出0.00变成了-0.00等有影响。解决方法详见 P 75 P_{75} P75
多点测试: 当题目没有说明有多少数据需要读入时,就可以利用scanf的返回 ,值是否为EOF(即End Of File)来判断输入是否结束。处理方式即 while( scanf("%d", &n) != EOF ) {···} , 当处理字符串时还可用while( gets(str) != NULL )
注意在多点测试中,每一次循环之内都要重置一下变量和数组,否则在下一组数据来临的时候变量和数组的状态就不是初始状态了。
几个余数的定理和性质及其应用 : [link]
进制转换 : P进制转十进制时在循环体中从低位到高位开始累加，十进制转Q进制时的处理技巧。 详见 P 93 mathcal P_{ mathcal {93} } P93
求最大公约数 : 设a,b均为正整数, 则 gcd(a, b) = gcd(b, a%b)
求最小公倍数 : lcm(a, b) = ab/gcd(a, b) 考虑到实际计算时可能产生溢出, 故一般写为 lcm(a, b) = a ÷ gcd(a, b) × b
涉及分数表示时的约分 : 求出分子绝对值 与分母绝对值 的最大公约数d, 然后令分子分母同时除以之
判断是否为素数 : 若暴力求解, 即采用循环枚举来判断n是否为素数, 则考虑下述性质后最多只需循环到sqrt(n)
对一个正整数n来说, 如果它存在1和本身之外的因子, 那么一定是在sqrt(n)的左右成对出现。
而对于“质因子”分解, 会得到一个更强的结论 : 对一个正整数n来说, 如果它存在[2,n]范围内的质因子, 要么这些质因子全部小于等于sqrt(n), 要么只存在一个大于sqrt(n)的质因子, 而其余质因子全部小于等于sqrt(n)。
分解质因子 : 先打印出质数表, 此时更快的方法可采用 Eratosthenes筛法, 再进行质因子分解
如果要求一个正整数N的因子个数 : 只需要对其质因子分解, 得到各质因子 p i p_i pi的个数分别为 e 1 , e 2 , . . . , e k e_1, e_2, ..., e_k e1,e2,...,ek 于是N的因子个数就是 ( e 1 + 1 ) (e_1+1) (e1+1)× ( e 2 + 1 ) (e_2+1) (e2+1)× . . . ... ...× ( e k + 1 ) (e_k+1) (ek+1), 原因是, 对每个质因子 p i p_i pi都可以选择其出现0次、1次、… 、 e i e_i ei次, 共 e i e_i ei+1种可能, 组合起来就是答案。而由同样的原理可知, N的所有因子之和为 ( 1 + p 1 + p 1 2 + . . . + p 1 e 1 ) (1+p_1+p_1^2+...+p_1^{e_1}) (1+p1+p12+...+p1e1)× ( 1 + p 2 + p 2 2 + . . . + p 2 e 2 ) (1+p_2+p_2^2+...+p_2^{e_2}) (1+p2+p22+...+p2e2)× . . . ... ...× ( 1 + p k + p k 2 + . . . + p k e k ) (1+p_k+p_k^2+...+p_k^{e_k}) (1+pk+pk2+...+pkek)
求n!中有多少个质因子p : n/p + n/p2 + n/p3 + ··· 其中的除法均向下取整。例如10!有5+2+1=8个质因子2
计算组合数 C n m C_n^m Cnm : 若用定义式算则由于n!太大而容易溢出, 可借助 C n m = C n − 1 m + C n − 1 m − 1 C_n^m=C_{n-1}^m+C_{n-1}^{m-1} Cnm=Cn−1m+Cn−1m−1的性质来递归
quadquadquadquadquadquad,, 注 : 为了更快, 可以设置全局变量的数组C[n][m]来打表, 以避免在递归中重复递归计算某些C[n’ ][m’ ]
用scanf读入字符时，一般要在输入控制符%c前面加空格，用来屏蔽空白符 [link]
关于scanf的返回值以及其中的空格和回车问题,细节详见 [link]
关于第一条的详解：空格不是必须的,但有了空格就可以忽略你输入的空格。例如 scanf("%d %c",&n,&c)，你输入了 ′ 3 a ′ '3,,a' ′3a′(a前面有个空格)，a就能被c接受。但c%前如果没空格,那c就只接受了空格，这个可以防止误操作，忽略空格输入,接受第一个非空格输入。
如果需要过滤一次换行符，可以单用一句 getchar();
用scanf读入英语句子 可以利用二维的字符数组进行存储，此时每行一维数组存储一个单词。数组是逐行依次进行存储的
quadquad 例如 char ans[99][99]; while( scanf("%s", &ans[m]) != EOF ) m++; //m为总单词个数或ans的行数
处理小技巧汇总 ：
字符串和数字之间相互转换 [link] 其中的b是把string看出b进制数来输出10进制数、string转数字[link] 注 : stringstream s;是用#include<sstream>
将一串数字分成几段来处理，例如 int time=20190204; int y=time/10000; int m=time%10000/100; int d=time%100;
整数除以2后若需四舍五入 可以通过判断它是否为奇数来分别解决，避免浮点数的介入或使用round
大整数的四则运算时, 不便求数组的长度(只有字符型可以用strlen()函数), 于是可设成结构体, 其中添加 int len 并随时修改此变量。
返回数组中的最大值的max_element函数。
快速得到类型符的溢出上限, 如 快速得到 int 的最大值 : [link]。
在链表中排序可借助静态链表, 即开一类型为node结构体的数组, 然后模拟链表, 利用sort排序, 并把有效结点全排在无效结点之前。
数组一键赋值: 如全部赋为define的INF则 int ans[MAX]; , fill( ans, ans+MAX, INF); , 注意前两个参数构成的区间是左闭右开。
quadquadquadquadquad,, 对于m×n的二维数组, 则将其视为长度等于n×m的一位数组, 因此可用 fill( &ans[0][0], &ans[0][0]+m*n, INF);
quadquadquadquadquad,, 必须注意二维数组使用首地址 &ans[0][0] 时只有 ans[0] 与之可以互换, 而不能用数组名 ans
注 : 虽然 ans, ans[0], &ans[0][0] 三者按%d输出的值相等, 但只有 ans[0] 和 &ans[0][0] 之间等价, ans和后两者的数据类型不同(因此也不能互相之间直接判等)
二分查找小技巧： 需要注意的是,如果二分上界超过int型数据范围的一半,那么当欲查询元素在序列较靠后的位置时,语句mid = (let+ right) /2中的left+right就有可能超过int而导致溢出,此时一般使用mid = left + (right-left) /2 这条等价语句作为代替以避免溢出。
二分法的其他应用见 P 127 mathcal P_{ mathcal {127} } P127 例如: 寻找有序序列中第一个满足某条件的元素的位置。 (如 第一个满足“值大于等于x”的元素的位置。但注意此类问题不会出现 left>right 的情况,最后return的也是left或right而非mid)
从N个整数中枚举所有的选取方案 : (eg.背包选物, 卡车装货). 物理图像: 二叉树(迷宫选岔路口)。解决方法: 深度优先搜索(递归)。
深度优先搜索的实质: 递归 (联想树的先序遍历·可用栈)。 图像: 当碰到岔道口时总是先选择其中的一条岔路前进, 而不管其他岔路, 直到碰到死胡同时才返回最近的岔道口并选择其他岔路。
广度优先搜索的实质: 分层搜索 (联想树的层序遍历·用队列)。 图像: 当碰到岔道口时总是先依次访问从该岔道口能直接到达的所有岔道口, 然后再按这些岔道口被访问的顺序去依次访问它们能直接到达的所有岔道口, 以此类推, 直到所有的岔道口都被访问为止。
注：在广度优先搜索(BFS)中设置的hash数组的含义是判断结点是否已入过队, 而不是结点是否已被访问。区别在于 : 如果设置成是否已被访问, 有可能在某个结点正在队列中(但还未访问)时由于其他结点可以到达它而将这个结点再次入队, 导致很多结点反复入队, 计算量大大增加。因此BFS中让每个结点只入队一次, 故需要设置hash数组的含义为"结点是否已入过队"而非结点是否已被访问。
二叉树: 如果函数中修改的是指针L指向的内容, 而不是L本身, 则在定义此函数时的参数L不需要加引用, 对指针实现的结点内容的修改是不需要加引用的。那么如何判断操作二叉树的函数中是否要加引用呢？如果函数中需要新建结点, 即对二叉树的结构做出修改, 就需要加引用; 如果只是修改当前已有结点的内容, 或仅仅是遍历树, 就不用加引用。
根据先序遍历和中序遍历序列重建二叉树: P 294 mathcal P_{ mathcal {294} } P294 画图易知, 如果递归过程中当前先序序列的区间为 [preL, preR], 中序序列的区间为 [inL, inR], 那么左子树的结点个数为 numLeft=k-inL。这样左子树的先序序列区间就是 [preL+1, preL+numLef], 左子树的中序序列区间是[inL, k-1]。右子树的先序序列区间是[preL+numLeft+1, preR], 右子树的中序序列区间是[k+1, inR]。其中in k _k k== , preL
树的静态写法: 若题目中对树的节点已经给出了它们各自的编号, 则可用编号作为node数组的下标, 从而采用树的静态写法
平衡二叉树AVL: 插入结点后需要相应的左旋右旋, 在"二叉排序树的插入代码"的基础上增加旋转操作即可, 详见 P 321 mathcal P_{ mathcal {321} } P321
若不需要构建哈夫曼树, 而只需求得最终的带权路径总长, 则可只借助排序(如优先队列) : 初始时排所有权值, 每次弹出两个最小值并将它们的和重新加入排序, 直到排序的序列只剩下一个数。同时在外部设sum变量, 每次相加后将和值也累加入sum即得。
并查集: 合并两个并查集时, 是把其中一个集合的根节点的父亲指成另一个集合的根节点。前者必须是对根节点, 而不是一个其他元素
图论: 如果从u到v有多条最短路径，则可在Dijkstra算法的过程中保存下所有的这些路径。最后才逐个遍历这些最短路径，从中选出满足第二筛选要求的唯一最短路径。但若题目的要求不复杂或不多，则依然选择只在Dijkstra算法中最短路径不唯一时特殊处理 (即在 elseif(distt[v]+G[v][i] == distt[i]) 处)。
quadquad 求最短路一般用Dijkstra算法。如果图中涉及了负环或负的边权 (例如求最长路径时边权乘-1), 则用基于Bellman-Ford优化而来的SPFA算法。如果要求图中所有任意两点间的最短距离或存在数组d[n][n]中, 则用Floyd算法。 注 : 负权环可以无限制的降低总路径长度
quadquad 求最小生成树 : Prim算法思想和Dijkstra算法思想相同, 做法也几乎相同。在Kruskal算法中, 判断加入一条边后是否会和已选择的边构成环, 实际上是判断这条边的两个端点 原本是否在不同的连通块中。
quadquad 求关键路径 : 先求点, 再夹边。即 先通过拓扑序列求各结点的V_early[i] 再由逆拓扑序列求各结点的V_late[i] , 最后通过夹边公式计算出各条边的E_early[i][j]和E_late[i][j] 。则E_early[i][j]==E_late[i][j]确定关键活动。
quadquad 判断一个有向图中是否有环, 可采用拓扑排序, 如果队列为空时入过队的结点数目恰好为N, 则该图为有向无环图, 否则有环
动态规划: 解决拥有重叠子问题和最优子结构的问题. 核心: 设计 , 状态 , 和 , 状态转移方程. (必须设计一个有无后效性的状态和相应的状态转移方程)
拥有重叠子问题: 一个问题可以被分解为若干个子问题 , 且这些子问题会重复出现。 拥有最优子结构: 一个问题的最优解可以由其子问题的最优解有效地构造出来。
分治和动态规划: 二者都将问题分解为子问题,再合并子问题的解得到原问题的解 , 但分治法用于没有重叠子问题,动态规划用于有重叠子问题。
其他注意细节 ：
交换 x, y 时例如 int temp = x, x = y, y = temp; 错误。{int temp = x; x = y; y = temp;}正确。
如果引用了iostream或者vector, 又加了using namespace std;这条语句, 就不要使用hash这样的变量名。因为这样会跟std命名空间里面的hash变量名冲突, 导致编译失败或者运行出错。类似的还有math.h的yl变量名, 如果将其作为全局变量, 就会导致编译错误, 若编译有报错或者运行莫名出错,则可以考虑这些因素。
STL还可参考此链接
注 : 仅 , vector , 和 , string , 支持对迭代器进行加减某个数字 , (it自增自减除外)。 迭代器.begin()指向首元素, 而.end()指向尾元素的下一个。
quad,,, 常用的容器即 : 变长数组 、字符数组(字符串) 、广义数组键值对(映射) 、集合 、各种数据结构。优先使用迭代器来定位或遍历, 其通用操作多
quad,,, 若想在结构体之间比较大小, 则需在定义结构体时也在内部定义＜的功能, 在set, map, priority_queue中用结构体作为元素时必须要重载！并且当用结构体作为set的元素时, 结构体中有几种变量则要设置几级比较。如姓名+分数的结构体则先比较分数相等时比较姓名。 重载方法详见 P 224 mathcal{P_{224}} P224
vector , 变长数组 两个维都可变长的二维数组则可用 vector<vector<int>> ans;
,,,, 可以像普通数组一样访问元素 quad vector<int>::iterator it = ans.begin(); , 优先用迭代器 quad 此时it类似于指针,由*it访问相应元素
,,,, .push_back(x)添加元素x quadquad .pop_back()删除尾元素 quadquad .size()获取元素个数 quadquad .clear()清空
,,,, .insert(it,x)在迭代器it处插入x quadquad .erase(it)删除it处元素 quadquad .erase(itL, itR)删除迭代器[itL,itR)间的元素 左闭右开
,,,, 用于设立数组时长度需要根据实际情况自动变化, 省去了#define MAX 。用邻接表存储图时可以选择用vector而不是单链表
string , 注 : 使用 #include<string> 而不是 #include<string.h> 此后则可和基本数据类型一样使用 , string ans = “Hello”;
,,,, 可以像字符数组一样访问string 如上面的ans[1]=‘e’ quad 读入和输出string只能用#include<iostream>中的cin和cout
,,,, string::iterator it = ans.begin(); , 使用迭代器 quad ans3 , = , ans1 , + , ans2; , 可直接拼接字符串 quad 字符串之间也可直接判等或比较大小
,,,, .insert(pos, string) quadquad .erase(pos, length) quadquad .erase(it)按迭代器 quadquad .erase(itL, itR) quadquad .size()字符串长度 quadquad .clear()
,,,, .substr(pos, length); 返回从pos位置(数字,非迭代器)开始的长度为length的字串
,,,, ans.find(str2); 当str2是ans的子串时,返回其在ans中第一次出现的位置pos; 如果str2不是ans的子串,则返回-1
,,,, place(pos, length, str2); 把ans从pos号位开始,长度为length的子串替换为str2
,,,, ans.find(str2, pos); 从ans的pos号位开始匹配str2,返回值与上者相同 quadplace(itL, itR, str2); 把ans的迭代器[itL, itR)范围的子串替换为str2
,,,, .insert(it, itL, itR); it为原字符串的欲插入位置, itL和itR为待插字符串的首尾迭代器, 将串[itL, itR)插在it的位置上, 如 itL = str2.begin(); itR = d();
map , 常用于建立字符或字符串到整数之间的映射, 如读取结点信息建立图 , 、遇到大整数等时代替开普通数组建立hash
,,,, 可以像数组一样使用map。如map<char, int> ans;后再赋值或访问ans[‘H’] quad 在存入map过程中它会自动在内从小到大排序
,,,, map<typename, typename>::iterator it = ans.begin(); 使用迭代器 quadquad it->first是当前映射的键, it->second是当前映射的值
,,,, .find(key);返回键为key的映射的迭代器, 若key不存在则返回的迭代器等于.end() quadquad,,,, .erase(it);删除it迭代器所指的这对映射
,,,, .size()当前有几对映射 quad .clear()清空 quad .erase(itL, itR);删除迭代器[itL,itR)间的映射 quad, .erase(key);删除键key所在的这对映射
,,,,, 注 : 如果要建立字符串到整型的映射,必须使用string而不能用char数组。如果map<int, , int> , ans; , 则相当于建立普通数组ans
set , 内部自动有序的集合(自动递增排序并且自动去掉重复元素)
,,,, 只能通过迭代器访问set的元素,若要遍历则只能用 , for(set<typename>::iterator it=ans.begin(); , it , != , d(); , it++)
,,,, .insert(x)插入元素x quad .erase(x)删除值为x的元素 quad .erase(it)删除迭代器it处的元素 quad .erase(itL, itR)删除[itL,itR)间的元素
,,,, .find(x)返回set中对应值为x的迭代器 quad .size()获取元素个数 quad .clear()清空 quadquad set的其他版本 : multiset 、unordered_set
queue
,,,, .push(x)入队 quad .front()取队首元素 quad .back()取队尾元素 quad .pop()出队 quad .empty()判空 quad .size()元素个数
,,,, 需要注意的是, 当使用STL的queue时, 元素入队的push操作只是制造了该元素的一个副本入队, 因此在入队后对原元素的修改不会影响队列中的副本, 而对队列中副本的修改也不会改变原元素。这就是说, 当需要对队列中的元素进行修改而不仅仅是访问时, 队列中存放的元素最好不要是元素本身, 而是它们的编号(如果是数组的话则是下标)。处理链表或图时则可直接使用指针来入队。
,,,,, 注 : 若清空队列则需手动 while( , !q.empty() , ) , q.pop(); , 或直接定义一个新的队列 quadquad 使用.front()和.pop()必须先进行判空 , 栈中对应.top()和.pop()
priority_queue , 注 : 同样与上面都用 #include<queue> 和 using namespace std;
,,,, 注 , : , priority_queue<int> , q; , 默认是数字越大优先级越高, , 字母则是字典序越大 , ; , 若想用越小的优先级越高则 , priority_queue<int, , vector<int>, , greater<int>> , q;
,,,, .push(x)入队 quad .top()取队首(即堆顶)元素 quad .pop()出队 quad .empty()判空 quad .size()元素个数 quad 注 : 与上述queue中的注意项类同
stack
,,,, .push(x)入栈 quad .top()取栈顶元素 quad .pop()出栈 quad .empty()判空 quad .size()元素个数 quad 注 : 与上述queue中的注意项类同
链表
#include<algorithm>头文件下的常用函数 , 注 : 使用时同样需要添加 using namespace std;
,,,, max(x, y) quad min(x, y) ,,,, 参数只能是两个, 若要返回三个数x,y,z的最大值可以用max(x, max(y, z));
,,,, max_element(itL, itR); ,,,, 返回数组指针在[itL, itR)之间的元素 的最大值
,,,, abs(x) ,,,,,,,,,,,,,,,,,,,,,, 参数x必须是整数,浮点型的绝对值请用math头文件下的fabs(x);
,,,, swap(x, y) ,,,,,,,,,,,,,,,,,, 交换x和y的值
,,,, fill(itL, itR, x); ,,,,,,,,,,,,,,,,,, 将指针在[itL, itR)之间的数组元素 或 迭代器在[itL, itR)之间的容器元素 全都赋值为x
,,,, reverse(itL, itR); ,,,,,,,,,,,,,,,,,, 将数组指针在[itL, itR)之间的元素或容器的迭代器在[itL, itR)之间的元素进行反转，如123→321
,,,, next_permutation(itL, itR); ,,,, 将指针在[itL, itR)之间的数组序列 或 迭代器在[itL, itR)之间的容器序列 变成全排列中的下一个序列
,,,, lower_bound(L, R, x) ,,,, 用来寻找在数组或容器的[L,R)范围内 , 第一个值大于等于x的元素的位置, 如果是数组则返回该位置的指针; 如果是容器则返回该位置的迭代器
,,,, upper_bound(L, R, x) ,,,, 用来寻找在数组或容器的[L,R)范围内 , 第一个值大于x的元素的位置, 如果是数组则返回该位置的指针; 如果是容器则返回该位置的迭代器
,,,,, 以上两者常用于一个有序数组或容器中, 如果数组或容器中没有需要寻找的元素, 则它们均返回可以插入该元素的位置的指针或迭代器(即假设存在该元素时,该元素应当在的位置)
,,,,
#include<algorithm>头文件下的 sort() , 注 : 使用时同样需要添加 using namespace std;
,,,,, sort(itL, itR); ,,,, 将指针在[itL, itR)之间的数组元素 或 迭代器在[itL, itR)之间的容器元素 按递增排序 字母则按字典序
,,,,, sort(itL, itR, cmp); ,,,, 可通过自定义cmp函数来实现递减排序 ,,,, 整型x和y例如 , int cmp(int x, int y) { return x>y; }
,,,,, 注 : 结构体之间排序时同理, 例如 int cmp(node x, node y) { return x.score > y.score ; }
,,,,, 若结构体需要实现一级排序相等时还要二级排序, 则例如 int cmp(node x, node y) { if(x.score!=y.score) return x.score > y.score; , else return x.name < y.name; }
,,,,, 在STL标准容器中, 只有 vector, string, deque 是可以使用sort的。而 set, map 这种容器的元素本身就有序。
,,,,, 例如将字符串按照字符串的长度从小到大排序则 int cmp(string x, string y) { return x.length() < y.length() ; }
算法笔记[M]. 机械工业出版社 , 胡凡, 2016
本文发布于:2024-02-04 23:52:32，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170719241860900.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
