vvVB0

基于c++ 队列核心思想： 先进先出 头文件：#include< queue>1.定义及初始化：queue (<数据类型，容器类型>）初始化时必须要有数据类型，容器可省略，省略时则默认为deque 类型eg:queueq1;queueq2;queue＜char＞q3；//默认为用deque容器实现的queue； queue＜char, list＜char＞＞q1；//用list容器实现的queue queue＜int, deque＜int＞＞q2； //用deque容器实现的queue 2.queue常用函数push() 在队尾插入一个元素pop() 删除队列第一个元素size() 返回队列中元素个数empty() 如果队列空则返回truefront() 返回队列中的第一个元素back() 返回队列中最后一个元素 eg:1.push（） queue q; q.push(“first”); q.push(“second”); cout<

1.卡特兰数C0 = 1,C1 = 1, C2 = 2, C3 = 5, C4 = 14, C5 = 42,C6 = 132, C7 = 429, C8 = 1430递推式1:f[n]=f[0]∗f[n−1]+f[1]∗f[n−2]+…+f[n−1]∗f0 递推式2：h[n]=h[n−1]∗(4∗n−2)/(n+1) 递推式3：也叫组合数公式h[n]=C[2n,n]/(n+1)(n=0,1,2,…),C是组合数PS:C[m,n]=C[m−1,n−1]+C[m−1,n] 且规定：C[n,0]=1 C[n,n]=1 C[0,0]=1 递推式4：也叫组合数公式h[n]=C[2n,n]−C2n,n−1 应用：‘3.1044 [NOIP2003 普及组] 栈’ 出栈的顺序个数 建立数组f。f[i]表示i个数的全部可能性。f[0] = 1, f[1] = 1; //当然只有一个设 x 为当前出栈序列的最后一个，则x有n种取值 （总共有n个数，每个数都有可能最后出栈） 由于x是最后一个出栈的，所以可以将 ...

题目： 【深基18.例3】查找文献题目描述小 K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小 K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。 假设洛谷博客里面一共有 $n(n\le10^5)$ 篇文章（编号为 1 到 $n$）以及 $m(m\le10^6)$ 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。 这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。 请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。 输入格式共 $m+1$ 行，第 1 行为 2 个数，$n$ 和 $m$，分别表示一共有 $n(n\le10^5)$ 篇文章（编号为 1 到 $n$）以及$m(m\le10^6)$ 条参考文献 ...

题目： 图的遍历题目描述给出 $N$ 个点，$M$ 条边的有向图，对于每个点 $v$，求 $A(v)$ 表示从点 $v$ 出发，能到达的编号最大的点。 输入格式第 $1$ 行 $2$ 个整数 $N,M$，表示点数和边数。 接下来 $M$ 行，每行 $2$ 个整数 $U_i,V_i$，表示边 $(U_i,V_i)$。点用 $1,2,\dots,N$ 编号。 输出格式一行 $N$ 个整数 $A(1),A(2),\dots,A(N)$。 样例 #1样例输入 #112344 31 22 44 3 样例输出 #114 4 3 4 提示 对于 $60\%$ 的数据，$1 \leq N,M \leq 10^3$。 对于 $100\%$ 的数据，$1 \leq N,M \leq 10^5$。 代码：$ include using namespace std;const int maxn = 100001;int m,n;vectorl[maxn];bool vis[maxn];int result[maxn];void dfs(int z,int a){ vis[z] = true;//a表示 ...

题目：对于一个递归函数w(a,b,c)如果 a ≤ 0 或 b ≤ 0 或 c ≤ 0 就返回值 1。如果 a > 20 或 b > 20 或 c > 20 就返回 w(20,20,20)如果 a < b 并且 b < c 就返回 w(a,b,c−1)+w(a,b−1,c−1)−w(a,b−1,c)。其它的情况就返回 w(a−1,b,c)+w(a−1,b−1,c)+w(a−1,b,c−1)−w(a−1,b−1,c−1)这是个简单的递归函数，但实现起来可能会有些问题。当 a,b,c 均为 15 时，调用的次数将非常的多。你要想个办法才行。注意：例如w(30,−1,0) 又满足条件 1 又满足条件 2，请按照最上面的条件来算，答案为 1。 输入格式会有若干行。并以 −1,−1,−1 结束。输出格式输出若干行，每一行格式：w(a, b, c) = anseg:输入1 1 12 2 2-1 -1 -1输出w(1, 1, 1) = 2w(2, 2, 2) = 4 代码： include define ll long longusing nam ...

1.undefined reference to `WinMain’翻译：找不到main原因：main拼写错误 2.初始化数组错误：dp[1001] = 1；原因：并非初始化所有数为1，只是让边界为1 错误：memset(dp, 1, sizeof(dp));原因：并没有初始化所有数为1，因为memset是按照字节大小来初始化的，若机器字长为16位，初始化后相当于每个元素的值都为0001 0001 0001 0001（2进制），而并非1 纠正：所以初始化非零整数时，最好用循环 3.[Error] expected initializer before numeric constant错误：const int maxn 10001;没有写=纠正：const int maxn = 10001; 4.[Error] expected ‘)’ before ‘;’ token[Error] expected ‘;’ before ‘)’ token错误：dfs(step+1;l[z][i]);纠正：dfs(step+1,l[z][i]);应该用，而不是；

题目：给出正整数 n，要求按如下方式构造数列：1.只有一个数 n 的数列是一个合法的数列。2.在一个合法的数列的末尾加入一个正整数，但是这个正整数不能超过该数列最后一项的一半，可以得到一个新的合法数列。请你求出，一共有多少个合法的数列。两个合法数列a,b不同当且仅当两数列长度不同或存在一个正整数i≤∣a∣,使得a i !=b i​输入格式输入只有一行一个整数，表示 n。输出格式输出一行一个整数，表示合法的数列个数 代码：//20 include using namespace std; int n;int dp[1001]; int dfs(int n){ if(n == 1) { return dp[n]; } if(dp[n] > 1) { return dp[n]; } for(int i = 1; i <= n/2; i++){ dp[n] += dfs(i); } return dp[n];} int main(){ cin>>n; for(int i = ...

算法思想：通过存储已经遍历过的状态信息，从而避免对同一状态重复遍历的搜索算法即要求所有状态的目标值都是固定的，不随外在因素而变化，例如斐波那契数列

题目：输入格式输入文件只含一个整数n（1≤n≤18）。 输出格式输出文件只有一行，即可能输出序列的总数目(类似栈先进先出)。 错误思路：从序列中找规律n = 1 ,1进1出 一种序列n = 2, 1进1出，2进2出 和 1进2进，2出1出，两种序列n = 3，123->123 213 231 132 321n = 4, 1234->4321, 正确思路：题目本质：栈内个数和栈外个数的动态变化 每种变化都有一个固定的值例如：栈内有一个数，栈外有一个数的情况：要么栈内的数出去->栈内0个数，栈外一个数要么栈外的数入栈->栈内2个数，栈外一个数和栈内栈外的数是几没有关系 dp思路：设dp[i][j] i表示栈内元素个数，j表示栈外元素个数最优子结构：[i-1][j] [i+1][j-1]边界：栈外没有元素时，无论栈内几个元素，出栈顺序都为一种，即j = 0, dp[i][0] = 1状态转化方程：dp[i][j] = dp[i-1][j] + dp[i+1][j-1] 代码：法一：动态规划 dp 记忆搜索 include using namespace std; lo ...

思想：拆分子问题，记住过往，减少重复计算。 典型特征：最优子结构、状态转移方程、边界、重叠子问题eg：f(n-1)和f(n-2) 称为 f(n) 的最优子结构f(n)= f（n-1）+f（n-2）就称为状态转移方程f(1) = 1, f(2) = 2 就是边界比如f(10)= f(9)+f(8),f(9) = f(8) + f(7) ,f(8)就是重叠子问题。 解题思路：穷举分析确定边界找出规律，确定最优子结构写出状态转移方程 1.穷举分析拆分子问题：通过固定的方法如何得到目标eg：当台阶数是1的时候，有一种跳法，f（1） =1当只有2级台阶时，有两种跳法，第一种是直接跳两级，第二种是先跳一级，然后再跳一级。即f(2) = 2;当台阶是3级时，想跳到第3级台阶，要么是先跳到第2级，然后再跳1级台阶上去，要么是先跳到第 1级，然后一次迈 2 级台阶上去。所以f(3) = f(2) + f(1) =3当台阶是4级时，想跳到第3级台阶，要么是先跳到第3级，然后再跳1级台阶上去，要么是先跳到第 2级，然后一次迈 2 级台阶上去。所以f(4) = f(3) + f(2) =5当台阶是5级时…… ...