树的BFS不需要判重，因为根本不会重复；但对于图来说，如果不判重，时间和空间都将产生极大的浪费。 

双向BFS的使用要求之一就是知道终止状态

状态空间的一般搜索过程 

OPEN表：用于存放刚生成的节点 

CLOSE表：用于存放将要扩展或已扩展的节点 

 

竞赛中一般都是限制128M(大约10000000)

 

多源BFS一般路径查询多次，所以可以定义结构体数组！

搜索的路径输出

路径输出有2种方式，一种是用STL提供的queue，但是必须在结构体中加step或pre，来标记他本身的操作或上一个操作，第二种是手动写队列，通过数组下标来记录，这种简单

在广搜时每一步都记入队列，通过每一个点向外发射，把每种可能都一次加进队列里，每一次扩展完一个地点就让它出队，继续下一个点的扩展，在结构体中声明多一个数组变量pre来记录每一个点的来源，即某一步是从哪一步扩展来的，方便输出结果时的追踪。

利用函数的调用

，对每一点都倒向追踪回去，

确定是前一步是哪个点，然后返回输出追溯的每一步。

 

一句话概括：如果以后能用链式前向星的话就尽量用链式前向星 别用vector邻接表

 

因为我以前学图论的时候，先接触到的就是vector邻接表的写法，所以后来一直都是用vector邻接表的写法，后来也接触到了链式前向星的写法，然后那时候也了解到了vector邻接表与链式前向星有内存性能上的差异，因为vector扩充时是默认多申请50%的内存空间，所以一些特别变态的题目可能会卡内存只能用链式前向星的写法写。不过当时也没特别在意，也想着到时候看边数量特别大的话再说，vector邻接表也写惯了，可是最近居然被卡了两道时间的题目，让我意识到可能链式前向星写法与vector写法还有时间上的差距，我猜与STL实现上有关。

 

 

深度优先遍历在编码上可以使用栈或者递归实现，当使用递归时就叫做回溯法，，八皇后问题-回溯法，可以求解所有可能的解，而广度优先一般不可以求得所有解，但是可应用于最优解问题，利用分支限界的思想，所以一般求解最优化问题使用广度优先，深度优先也可以。。

另外广度优先求图中两点最短路径，要求是不带权或者每条边的权值相等。如果带权就只能使用迪杰斯特拉算法。

---

 

 

01背包n行m列填表

　eg：number＝4，capacity＝8

i	1	2	3	4
w(体积)	2	3	4	5
v(价值)	3	4	5	6

void FindMax()//动态规划{    int i,j;    //填表    for(i=1;i<=number;i++)    {        for(j=1;j<=capacity;j++)        {            if(j
     
      V[i-1][j-w[i]]+v[i])//不装价值大                {                    V[i][j]=V[i-1][j];                }                else//前i-1个物品的最优解与第i个物品的价值之和更大                {                    V[i][j]=V[i-1][j-w[i]]+v[i];                }            }        }    }}
     

由此可以得出递推关系式：

　　　　1) j<w(i)      V(i,j)=V(i-1,j)

　　　　2) j>=w(i)     V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝

　　g) 填表，首先初始化边界条件，V(0,j)=V(i,0)=0；

 

　　h) 然后一行一行的填表，

　　　　1) 如，i=1，j=1，w(1)=2，v(1)=3，有j<w(1)，故V(1,1)=V(1-1,1)=0；

　　　　2) 又如i=1，j=2，w(1)=2，v(1)=3，有j=w(1),故V(1,2)=max｛ V(1-1,2)，V(1-1,2-w(1))+v(1) ｝=max｛0，0+3｝=3；

　　　　3) 如此下去，填到最后一个，i=4，j=8，w(4)=5，v(4)=6，有j>w(4)，故V(4,8)=max｛ V(4-1,8)，V(4-1,8-w(4))+v(4) ｝=max｛9，4+6｝=10；所以填完表如下图：

 

---

 

 

每次访问0入度集合时查看大小，当元素多于1的时候可行的选择就出现了分歧——即可判定此DAG的拓扑排序不唯一（当然本题的信息在不断更新，所以不能立刻判死）。

---

 

1.anagram :变位词 - 

一种把某个词或句子的

字母的位置（顺序）加以改换所形成的新词，英文叫做anagram，词典把这个词翻译成“变位词”。

譬如 (说， 的过去式)就有dais(讲台)这个变位词；triangle（三角形）就有integral（构成整体所必要的）这个变位词；Silent（不要吵）和Listen（听我说）也是。

---

Connected component   连通分量

---

 

dfs，bfs复杂度一般是 ∑(每个状态的决策）

如果采用邻接表存储，一般情况下复杂度为O(E)（边数）

---

 vector建图

---

 

这个把map当作二维数组赋值的方法你学到了吗？喵~

---

 

for(int i=n;i>=0;i--)

　　for(int j=i;j<n;j++)

　　　　　　···　　

后缀

---

 任意n进制，其中，都是质数

当且仅当分母仅包含到的任意次方的组合时，该分数可以化为有限小数，否则都能化为无限循环小数

---

 一个有向无环图(DAG)通常可以表示某种动作序列或者方案，而有向无环图的拓扑序列通常表示某种方案切实可行。

---

 拓扑排序就是解决对有向图的点进行线性排序的相关问题

---

 

2.已知秒数

LL hh = s/3600;

LL mm = (s%3600)/60;

LL ss = (s%3600)%60;

3.【矩阵快速幂】：

因为F(2)和F(1)是已知的，当n>=3时，每次都乘以矩阵B，就能推出下一个矩阵。而矩阵的第一行第一列的元素就是所求的结果。

---

 

1.

upper_bound()是返回第一个>x的数的下标 

lower_bound()是返回第一个>=x的数的下标 

2.

for(int i=0;i

 3.

upper_bound(a+i+1,a+n,d)-a;//找出这个数出现的最后一个位置的后一个位置  

4.可以求长度为n的有序数组a中的k的个数，即为upper_bound(a,a+n,k)-lower_bound(a,a+n,k)

5.

1.lower_bound(a,a+n,d)-a，返回a[i]<d的个数。

 

2.upper_bound(a,a+n,d)-a,  返回a[i]<=d的个数。

6.

fill(a,a+n,x);    将数组a0~an位置赋值为x。

 7.发现在两个不同数组和自身里面的二分搜索不一样

两个不同数组：

for(int i=0;i

自身[本数组]：

for(int i=0;i

　8.　cbrt(a * b);   //求一个数的三次方程

　9.

字符串的前缀是指字符串的任意首部。

比如字符串“abbc”的前缀有“a”,“ab”,“abb”,“abbc”。

同样，字符串的任意尾部是字符串的后缀，“abbc”的后缀有“c”,“bc”,“bbc”,“abbc”

10.

 严格 上升用 lower

不降 upper 

 11.

 状态既可以指一个阶段上作决策时所依据的自然状况和客观条件，又可以指一个阶段上所作决策后的结局状况，故一个阶段的状态常有首、末状态之分，以区别阶段上决策的出发点和结局状况。但，一般地，人们往往仅选择各阶段的首、末状态之一，作为各阶段的状态，所以，当谈到各阶段的状态时，要么都指的是各阶段的首状态，要么都指的是各阶段的末状态。

　　在前面的概念中，我们看到了两种不同的状态表达方式：各阶段的首状态与各阶段的末状态

　　这里想要说的就是，当读者在做动态规划问题时：

　　（1）如果状态转移方程中的S(k)表示的是各阶段的首状态：即：S(k) =S(k-1) + x(k-1)，此时使用逆推法； S(1) = 最大数量

　　（2）如果状态转移方程中的S(k)表示的是各阶段的末状态：即：S(k) =S(k-1) + x(k)，此时使用顺推法。 S(n) = 最大数量

结论：

　　顺推法与逆推法中递推公式的不同导致使用顺推还是逆推方式的不同。

12.用memset赋值就算是0x3f3f3f也不行  ，只能0 / -1

13.

连续背包（bag）

【问题描述】

从T组物品中选出一些物品，放入背包中，求剩余空间的最小值。

限制条件：从每组物品中挑选物品必须要选取连续的一段。就是说，如果这组物品共有n个： 物品1、物品2、物品3、…、物品n，那么只能选取物品i、物品i+1、…、物品j，其中1<=i<=j<=n,或者不选。

那么所求性价比最高的，直到超出背包容量

14.01背包记录路径：

f数组是从上到下、 从右往左计算的。 在计算f(i, j)之前，f[j]里保存的就是f(i－ 1 , j)的值，而f[j－W]里保存的是f(i－ 1 , j－W)而不是f(i, j－W)——别忘了j是逆序枚举的，此时f(i,j－W)还没有算出来。 这样，f[j] =(max[j] , f[j－V]＋W)实际上是把保存在f[j]中，覆盖掉f[j]原来的f(i－1, j)。提示9-17：在递推法中，如果计算顺序很特殊，而且计算新状态所用到的原状态不多，可以尝试用滚动数组减少内存开销。图9-6 0-1背包问题的计算顺序滚动数组虽好，但也存在一些不尽如人意的地方，例如，打印方案较困难。 当动态规划结束之后，只有最后一个阶段的状态值，而没有前面的值。 不过这也不能完全归咎于滚动数组，规划方向也有一定责任——即使用二维数组，打印方案也不是特别方便。 事实上，对于“前i个物品”这样的规划方向，只能用逆向的打印方案，而且还不能保证它的字典序最小（字典序比较是从前往后的）。

 

 15.

 最小前缀和前缀和一样

到i为止前面i个数的最小值 

16.完全背包的核心不同点是允许同一物品的重复计算！

 

17.在一般的01背包压缩空间的时候，体积/容量的遍历是从大到小，因为dp[v]=max(dp[v],dp[v-c[i]]+w[i])，

当前的dp[v]只取决于比自己小的dp[v-c[i]]，所以从大到小遍历时每次dp[v-c[i]]和dp[v]

都是上一次的状态。

18.

多重背包和01背包、完全背包的区别：多重背包中每个物品的个数都是给定的，可能不是一个，绝对不是无限个。

 19.累加或者乘积一定注意用long long

---

 

1.模拟一般模块化，方便查错。

2.看清题目。分清楚石子归并还是贪心/哈弗曼树；01背包还是暴力枚举（cf惨痛教训）

3.搜索和动态规划是在多种策略中选取最优解，贪心算法则不同。它遵循某种规则，不断地选取当前最优策略。

4.priority_queue的用法：

priority_queue其实是C++STL中的一个神奇的容器。翻译成中文叫做“优先队列”，其实相当于个heap（堆），我们可以利用它来实现简单的堆操作，避免了手打堆得麻烦，注意使用前需要引用头文件：

include<queue>

定义一个优先队列需要这样，降序排列处理最大数：std::priority_queue<int> q;　　//q是队列的名称，可以随便起名，int是类型说明，常用int和long long

然而，这样定义的优先队列是数大的元素优先级高，先被弹出队列，说白了就是降序排列。priority_queue只能对最大数进行操作，无法处理最小数。若是想要升序排列处理最小数，也很简单。

升序排列处理最小数：std::priority_queue<int,vector<int>,greater<int> > q;

//特别提醒：最后的两个‘>’之间一定要加个空格，否则会被一些编译器识别为位运算符“>>”。

q.push(1); //压入元素1q.top();//返回此时优先级最高的元素q.pop();//弹出优先级最高的元素，但不返回它的值q.empty();//返回一个bool值，如果队列为空返回true，否则返回falseq.size();//返回队列中元素的个数

 5.1和0既非素数也非合数。

6.一般的筛法（PPT里叫埃拉托斯特尼筛法，名字异常高贵）的效率是O(NlglgN)（其实很接近O(n)啊！），对于一些例如 N=10000000 的残暴数据会跪，于是，线性筛登场。

7.a[i]=tolower(a[i]);//大写转小写 a[i]=toupper(a[i]);//小写转大写

8.

if((a%4==0 && a%100!=0)||(a%400==0))　　//闰年2月29天       e+=29;

 

9.新技能：

a & (1 << j ) 表示数a 二进制的第 j 位是什么

 

if (a[i]&(1<<j)) 这句的意思是判断 a[i] 的第 j 位是否为1。 //  1 << x 就是将1左移x位 (bit)，比如 1 << 3 == 0b1000。

10.

sprintf(_d,"%ld",d); //将d转换为字符串_d

 11.首先在回文数中，如果位数为偶数的话，那么这些回文数都可以被11整除，如1001、1221、345543都是11的倍数

 12.

for (int i=1;i<=n;i++) //从int数组转化为数 ,若char数组为s*10+a[i]-'0';    s=s*10+a[i];

 13.

itoa()函数

itoa():char *itoa( int value, char *string,int radix);

原型说明：

value：欲转换的数据。

string：目标字符串的地址。

radix：转换后的进制数，可以是10进制、16进制等，范围必须在 2-36。

功能：将整数value 转换成字符串存入string 指向的内存空间 ,radix 为转换时所用基数(保存到字符串中的数据的进制基数)。

返回值：函数返回一个指向 str，无错误返回。

14.回文判断，求出数的逆序，如果逆序跟正序相等，就是回文数.

bool ispalindrome(int n)   //回文判断，求出数的逆序，如果逆序跟正序相等，就是回文数 {      int temp,total;      temp=n;      total=0;      if(temp==0) return true;      while(temp!=0)      {            total=total*10+temp%10;            temp=temp/10;      }      if(n==total)   return true;      else  return false;}

 15.任何一个数mod(就是%)1都等于0

16.string可以直接比较字典序大小a>b等等

17.

find会挨个查找set，当到达set.end()时，也就是一个也没找到，返回endset
     
       s;s.find(element) != s.end() // 没到达end，说明在set中找到element这个元素map
      
        mp;mp.find(element) != mp.end() //在mp中找到这个元素
      
     

　　

/*性质1：如果数a、b都能被c整除，那么它们的和（a+b）或差(a－b)也能被c整除。性质2：几个数相乘，如果其中有一个因数能被某一个数整除，那么它们的积也能被这个数整除。能被2整除的数，个位上的数能被2整除（偶数都能被2整除），那么这个数能被2整除能被3整除的数，各个数位上的数字和能被3整除，那么这个数能被3整除能被4整除的数，个位和十位所组成的两位数能被4整除，那么这个数能被4整除能被5整除的数，个位上为0或5的数都能被5整除，那么这个数能被5整除能被6整除的数，各数位上的数字和能被3整除的偶数，如果一个数既能被2整除又能被3整除，那么这个数能被6整除能被7整除的数，若一个整数的个位数字截去，再从余下的数中，减去个位数的2倍，如果差是7的倍数，则原数能被7整除。如果差太大或心算不易看出是否7的倍数，就需要继续上述「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。例如，判断133是否7的倍数的过程如下：13－3×2＝7，所以133是7的倍数；又例如判断6139是否7的倍数的过程如下：613－9×2＝595 ， 59－5×2＝49，所以6139是7的倍数，余类推。能被8整除的数，一个整数的末3位若能被8整除，则该数一定能被8整除。能被9整除的数，各个数位上的数字和能被9整除，那么这个数能被9整除能被10整除的数，如果一个数既能被2整除又能被5整除，那么这个数能被10整除（即个位数为零）能被11整除的数，奇数位（从左往右数）上的数字和与偶数位上的数字和之差（大数减小数）能被11整除，则该数就能被11整除。 11的倍数检验法也可用上述检查7的「割尾法」处理！过程唯一不同的是：倍数不是2而是1！能被12整除的数，若一个整数能被3和4整除，则这个数能被12整除能被13整除的数，若一个整数的个位数字截去，再从余下的数中，加上个位数的4倍，如果差是13的倍数，则原数能被13整除。如果差太大或心算不易看出是否13的倍数，就需要继续上述「截尾、倍大、相加、验差」的过程，直到能清楚判断为止。能被17整除的数，若一个整数的个位数字截去，再从余下的数中，减去个位数的5倍，如果差是17的倍数，则原数能被17整除。如果差太大或心算不易看出是否17的倍数，就需要继续上述「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。   另一种方法：若一个整数的末三位与3倍的前面的隔出数的差能被17整除，则这个数能被17整除能被19整除的数，若一个整数的个位数字截去，再从余下的数中，加上个位数的2倍，如果差是19的倍数，则原数能被19整除。如果差太大或心算不易看出是否19的倍数，就需要继续上述「截尾、倍大、相加、验差」的过程，直到能清楚判断为止。另一种方法：若一个整数的末三位与7倍的前面的隔出数的差能被19整除，则这个数能被19整除能被23整除的数，若一个整数的末四位与前面5倍的隔出数的差能被23(或29)整除，则这个数能被23整除能被25整除的数，十位和个位所组成的两位数能被25整除。能被125整除的数，百位、十位和个位所组成的三位数能被125整除。*/

 18.

sort复杂度：nlogn 尽量不用cin 19.coprime "互质" 20. https://www.cnblogs.com/hadilo/p/5914302.html

 　　扩展欧几里得算法，简称 exgcd，一般用来求解不定方程，求解线性同余方程，求解模的逆元等

　　引理：存在 x , y 使得 gcd(a,b)=ax+by

21.数据范围12（很小）。显然DFS

给你两个操作，问能不能把数字a变成b。这题大多数一眼看就是dfs

22.

在这些之前都有的前提，那就是真个数组是一个非降序列！！！！！！lower_bound()函数怎么使用呢？我想这就是很多读者会遇到的问题，下边就有小编我来帮大家解释一下吧，自豪的说几句大笑。说起来我用一句话来概括，就是它的参数就是：一个数组元素的地址（或者数组名来表示这个数组的首地址，用来表示这个数组的开头比较的元素的地址，不一定要是首地址，只是用于比较的“首”地址），一个数组元素的地址（对应的这个数组里边任意一个元素的地址，表示这个二分里边的比较的"结尾'地址），再然后就是一个你要二分查找的那个数。参数说完了，现在说说返回值，返回值就是返回第一次出现大于等于那个要查找的数的地址，注意两点，第一，是地址，不是指那个要查找的数的下标，所以就注定了在这个函数的后边就要减去一个尾巴，那就是这个数组的数组名，即这个数组的首地址得意，只有这样才代表那个要查找的数字的下标，当然如果没有找到那个数，也是会返回的，那么返回的又会是什么呢？疑问；这就是我要讲的第二点，那就是要大于等于那个数，等于好理解大笑，大于怎么理解呢疑问，比如说我并没有找到那个数，加入一个的数组里边就有5个数，分别是1,1,1,3,5,而我需要找的那个数就是2，怎么返回呢疑问小编告诉你哦，就是返回那个第一个大于2的数的地址，就是返回3的地址，那么再有一组数据就是5个数1,1,1,3,3，还是需要找寻2，那么该返回什么呢？小编告诉你哦，那就是第一个3的地址。下边来段代码你理解下吧

 23.

两个字符串之间的汉明距离是指两个相等长度的字符串，对应位置上不同字符的个数。

例子如下：

A=abcdef

B=adddef

则A与B之间的汉明距离是2，因为第二位和第三位不同。

24.

最近做题的时候，经常遇到范围是2^63，取模2^64的这种题目。遇到这种限制条件时就要想到用unsigned long long类型。

可以简洁地声明为typedef unsigned long long ull。这样，如果ull类型的整数溢出了，就相当于取模2^64了。因为ull的范围是[0,2^64-1]。

而ll的范围是[-2^63,2^63-1]，因为有符号的第63位表示“正负”而不表示数值。

25.双指针利用序列的递增性。

26.容斥原理：一般在集合的个数m比较小，并且并集这些项容易计算时适合使用容斥原理。

27.

substr有2种用法：

假设：string s = "0123456789";

string sub1 = s.substr(5); //只有一个数字5表示从下标为5开始一直到结尾：sub1 = "56789"

 

string sub2 = s.substr(5, 3); //从下标为5开始截取长度为3位：sub2 = "567"

 

28.

void dfs(答案,搜索层数,其他参数){    if(层数==maxdeep){        更新答案;        return;     }    (剪枝)     for(枚举下一层可能的状态){        更新全局变量表示状态的变量;        dfs(答案+新状态增加的价值,层数+1,其他参数);        还原全局变量表示状态的变量;    }}

 

28.%c吃回车

29记忆化搜索：.一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。

30.动态规划是一种算法，有两种实现方式：递推和记忆化搜索

31.计算一个数x的位数是log10(x)+1，计算log10(a^b)+1可以化为b*log10(a)+1

32.矩阵快速幂中矩阵的构造技巧

对于出现线性递推的题目，当直接暴力计算的复杂度太高时，我们可以考虑用矩阵快速幂进行加速。

因为虽然矩阵乘法的复杂度为O（n^3），但是通过二进制分解，整体的复杂度变成了 log(n^3) = 3logn = O(logn)，复杂度是对数级别的，非常小。

但是矩阵快速幂的难点就是在如何构造矩阵来完成计算。

因为矩阵快速幂是用来加速线性递推的，所以最核心的部分就是线性递推公式。

最经典的就是斐波那契数列的递推： f(n) = f(n-1) + f(n-2);

其对应的矩阵就是     　　　　　　 f(n+1)      1    1      f(n)

                                  　　   　    f(n)  =    0    1     *   f(n-1)

可以发现，左面是个常数矩阵，而右面的列向量中每一项就是递推公式中的依赖项。

当递推公式中出现常数时，我们只需在右面的列向量中加入个常数1，即可。

剩下的就是我们如何去构造左面的常数矩阵。其实给出了右面的列向量，我们在根据题中的递推公式，在左面的常数矩阵中填入对应的常数即可。

这样，这个问题就圆满的解答了。

 

33.

cin>>str; //遇到空格不在写入 str

getline(cin, str); //遇到回车(换行)不在写入 str

34.使用typedef目的一般有两个，一个是给变量一个易记且意义明确的新名字，另一个是简化一些比较复杂的类型声明。

 

35.需要付出代价并且获得收益，这是背包问题

 36. n - n / k * k  =  n % k

获取距离n最近的k的倍数的方法是: n / k * k  = n - n % k 

37.

if(a>2*b)

a%=2*b(效率高)

a-=2*b(减法太慢)

把a减到小于2*b等价于a%(2*b)

 38.

通过count()和find()查找元素如果需要判断某map中是否存在某key的元素，不能通过取下标的方式判断，因为这样会使得向map中添加新元素。map标准库中提供了两个判断key是否存在的方法。map::count(k)，返回map中k出现的次数，为0当然就表示不存在了。map::find(k)，如果map中存在按k索引的元素，则返回指向该元素的iterator；如果不存在则返回end()

　　39.

c语言中-'a'+10是什么意思[16进制]

遇到小写十六进制数转换成数字时用比如0x0b应当对应十进制11如果我拿到字符：'b'，将之转换成11的方法就是'b'-'a'得到1，加10得到11，同理'f'-'a'+10=15

 

当要把一个字符格式数字转化为整型数字时，可以这样用：char a = '7' ; int  b = a - '0' ;  //b = 7同理 数字加'0'可转化为字符

 

40. 18446744073709551615 = 2^64 - 1 是unsigned long long能表示的最大的数，输入输出用%llu或%I64u。

41.我们知道f【Fib数列%p】如果出现了连续的1，0就意味这着开始循环了，因为接下来的项就是1 1 2 3 5等等

42.初始化map写在函数比较好,模块化

void init(){    mp["Weapon"] = 1;    mp["Shield"] = 2;    mp["Two-Handed"] = 3;    mp["Finger"] = 4;    mp["Feet"] = 5;    mp["Legs"] = 6;    mp["Waist"] = 7;    mp["Wrist"] = 8;    mp["Hand"] = 9;    mp["Torso"] = 10;    mp["Neck"] = 11;    mp["Shoulder"] = 12;    mp["Head"] = 13;}

 43. upper_bound，功能是在一段单调递增的序列中找到第一个大于目标元素的地址。用处是可以统计小于或等于value的元素有多少个（所以要减1）

44.能以规律总结方式做的题，不要同分类讨论和模拟做。很容易把问题繁琐化，造成AC压力。