Hello Flu1t

今天发现了一个函数next_permutation(a,a+n)即求当前排列的下n个排列例如n=1 对1234用 求出1243在全排列问题中很有效 火星人这道题就是说 求一个全排列之下的第n个排列正常也可以dfs写 只需要res到m+1时输出就行了 并且注意要剪枝 [p1088火星人] [c++]12345678910111213141516#include<bits/stdc++.h>using namespace std;int n,m;int a[10100];int main(){ cin>>n; cin>>m; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<m;i++) { next_permutation(a,a+n); } for(int i=0;i<n;i++) cout<<a[i]<<" "; return 0;} ...

首先通过上台阶这道题 我们理解了搜索树这个东西 1.就像树结构一样 向深处搜索 每一个路径一定会走到头 走到头以后回溯 继续往可以走的路径移动..再回溯 回溯个人理解：n个子节点的状态都需由父节点推出 所以父节点每次推子节点的时候初始状态是相同的 需要子节点恢复到之前的状态得到父节点 这便是回溯2.使用栈3.空间O(n)4.不具有最短性 重点 回溯与剪枝 [acwing92递归实现指数型枚举] [c++]1234567891011121314151617181920212223242526272829303132#include<bits/stdc++.h>using namespace std;const int N=1000;int n;int st[N],p[N];//1表示选 2表示不选 void dfs(int x){ if(x>n) //枚举到第n+1个位置 那么说明前面n个排完了 输出 { for(int i=1;i<=n;i++) { if(st[i]==1) cout<<i<<& ...

一般处理的问题1.将两个集合合并2.询问两个元素是否在一个集合当中 如果是暴力做法 数组存储每个元素属于哪一个集合1.belong[x]=aif(belong[x]=belong[y]) O(1)2.如果想合并 极其麻烦 元素多了就寄了 基本原理用树的形式维护每一个集合 树根的编号就是集合的编号每个节点存储它的父节点p[x]表示x的父节点1.将一棵树插到另一棵树px是x的集合编号 py是y的集合编号 合并就是p[x]=y 求某个点属于哪个集合 通过其父节点求x的集合编号 while(p[x]!=x) x=p[x]; 路径压缩优化 一旦找到根节点 整个路径上所有结点直接指向根节点 [并查集] [c++]12345678910111213141516171819202122232425262728293031#include<bits/stdc++.h>using namespace std;const int N=1000010;int n,m;int p[N]; //存父节点int find(int x) //返回x的祖 ...

先序遍历: 从一棵二叉树根节点为起点 沿着二叉树外沿 逆时针走一圈回到根节点 路上遇到的元素顺序 就是先序遍历的结果 中序遍历:二叉树每个节点垂直方向投影下来（可以理解为每个节点从最左边开始垂直掉到地上） 然后从左往右数 得出的结果便是中序遍历的结果 后序遍历：围着树的外围绕一圈 如果发现一剪刀就能剪下的葡萄（必须是一颗葡萄）（也就是葡萄要一个一个掉下来，不能一口气掉超过1个这样） 就把它剪下来 组成的就是后序遍历了 层序遍历：先根再左再右

回顾一下f[i][j] 所有只考虑前i个物品 且总体积不大于j的所有选法 当前种类的物品，“选了多少个”：选0个，就是前面物品在当前体积下的最大价值：f[i-1][j]；选1个，前面物品在去掉当前1个物品体积的最大价值+当前1个物品的价值：f[i-1][j-1v[i]]+1w[i];选2个，前面物品在去掉当前2个物品体积的最大价值+当前2个物品的价值：f[i-1][j-2v[i]]+2w[i];不难能推导出 完全背包的动态转移方程 f[i,j]=f[i-1,j-v[i]*k]+w[i]*k (注意k有限制条件的)将其展开f[i,j]=max(f[i-1,j],f[i-1,j-v[i]]+W,f[i-1,j-2v[i]]+2W…)f[i,j-v[i]]=max(f[i-1],j-v[i],f[i-1,j-2v]+w…)两者相似 从第二项开始每项差一个w所以f[i,j]=max(f[i-1,j],f[i,j-v]+w) 这样就不用枚举k了 这时我们便发现 二维完全背包和二维01背包非常的相似 其实唯一的区别就是01背包 f[i][j]=ma ...

01背包是重中之重 是其它所有背包的铺垫01背包 n种物品 每种只有一个完全背包 n种物品 每种无限个多重背包 n种物品每种个数不一样 f[i][j] 下标0到i的物品任取 放到容量为j的背包里 01背包 每种物品仅有一件 可以选择放或者不放只考虑第i件物品1.如果体积超了 那么一定就是f[i-1][j]2.如果不放 容量价值不变 转化为前i-1件物品放入容量为j的背包最大价值f[i-1][j]3.放了之后 容量减重量 价值增加f[i-1][j-w[i]]+v[i]max(f[i-1][j],f[i-1][j-w[i]]+v[i])就是对于第i件物品的最优解 f数组的初始化f[i][j]对应表格如下 0 1 2 3 4 0 a b c d e 1 f g h i j 2 k l m n o i即f[1][3]由递推公式 一定是由左上角递推得到的 那么第一列第一行一定要初始化背包容量为0 价值一定为0 所以第一列初始化为0除此之外b一定要初始化为0 不然递推会出错 其它的非0下标不用初始化 均会被覆盖 [01背包二维] [c++]123456 ...