珠海做网站找哪家好,宁波网页设计职业,深圳营销推广引流公司,如何做网站卖连接目录 头文件与STL动态规划最大数组子串和最长公共子序列最长连续公共子串最长递增子序列最大上升子序列和0-1背包多重背包多重背包问题 I整数拆分最小邮票最大子矩阵 数学问题朴素法筛素数线性筛素数快速幂 石子合并锯木棍并查集Dijkstra单源最短路Python进制转换(整数无限大)全… 目录 头文件与STL动态规划最大数组子串和最长公共子序列最长连续公共子串最长递增子序列最大上升子序列和0-1背包多重背包多重背包问题 I整数拆分最小邮票最大子矩阵 数学问题朴素法筛素数线性筛素数快速幂 石子合并锯木棍并查集Dijkstra单源最短路Python进制转换(整数无限大)全排列神奇的口袋全排列II放苹果求第k小八皇后问题哈夫曼编码KMP算法遍历建立二叉树 头文件与STL
#include iostream
#include cstring
#include algorithm
using namespace std;vector.insert(vector.begin(),2,99)//在头部插入2个99
vector.erase(vector.begin() 5, vector.end()) //删除第5个以后的元素mapstring,int
map.insert(pairstring, int())
map.count() //0或1
map.earse() //删除string s;
s.find()
s.substr(int start,int length) //切割子串
//输入含空格字符串
getline(cin,s); //优先队列
priority_queueint,vecotrint,greaterint; //less是降序
python输入
import sys
for line in sys.stdin:arr line.split()
//拼接列表 .join(list)a int(arr[0])
动态规划
最大数组子串和
dp[i]其实代表的是以i结尾的最大子串和
for(int i0;in;i){cina[i];// 需要额外的ans存储max因为是子串dp[i1]max(dp[i]a[i],a[i]);ansmax(dp[i1],ans);
}最长公共子序列
动态规划
for(int i1;is1.size();i){for(int j1;js2.size();j){if(s1[i-1]s2[j-1])dp[i][j]dp[i-1][j-1]1;else dp[i][j]max(dp[i-1][j],dp[i][j-1]);}
}最长连续公共子串
//t存储公共子串在s1中的末尾位置
int t0;
//最大长度要额外的maxLen存储max因为是子串
int maxLen0;
for(int i1;in;i){for(int j1;jm;j){if(s1[i-1]s2[j-1]){dp[i][j]dp[i-1][j-1]1;// 号确保 如果不唯一则输出s1中的最后一个。if(dp[i][j]maxLen){maxLendp[i][j];//存储公共子串在s1中的末尾位置可以输出子串ti-1;}} }
}最长递增子序列
https://www.nowcoder.com/practice/cf209ca9ac994015b8caf5bf2cae5c98?tpId40tagstitledifficulty0judgeStatus0rp1sourceUrl
dp[i]只代表以i结尾的最长递增子序列数
for(int i0;in;i){//初始化最长为本身 1dp[i]1;for(int j0;ji;j){//dp[i]代表以i结尾的最长递增子序列数if(a[i]a[j])dp[i]max(dp[j]1,dp[i]);ansmax(dp[i],ans);}
}最大上升子序列和
和上述最长递增子序列思路一致不过dp[i]代表以i结尾的最长递增子序列的和用ans存储结果
0-1背包
int dp[1001][1001];//代表前i个物体背包为j的最大价值
int n,bag;
int v[10001],w[10001];
cinnbag;
for(int i1;in;i){cinv[i]w[i];
}
dp[0][0]0;
for(int i1;in;i){for(int j1;jbag;j){if(jv[i]){dp[i][j]max(dp[i-1][j-v[i]]w[i],dp[i-1][j]);}else{dp[i][j]dp[i-1][j];}}
}
coutdp[n][bag];多重背包
每种物品无限件
for(int i1;in;i){for(int jv[i];jm;j){dp[j]max(dp[j],dp[j-v[i]]w[i]);}
}多重背包问题 I
第 i 种物品最多有 si件
//将 si拆成多个物品即01背包while(s--)
{a[t]v;b[t]w;
}//死拆把多重背包拆成01背包整数拆分
一个整数总可以拆分为2的幂的和
//奇数
if(i%2)dp[i]dp[i-1];
//偶数 没想明白***
else dp[i](dp[i-1]dp[i/2])%1000000000;最小邮票
dp[0][0]0;
for(int i1;im;i){//代表集不齐dp[0][i]1e9;
}for(int i1;in;i){for(int j1;jm;j){if(j-a[i]0)dp[i][j]min(dp[i-1][j-a[i]]1,dp[i-1][j]);elsedp[i][j]dp[i-1][j];}
}最大子矩阵 子矩阵的和pivot - dp[k-1][j] - dp[i][q-1] dp[k-1][q-1] for (int i 1; i n; i) {for (int j 1; j n; j) {cin matrix[i][j];//计算机前缀和dp[i][j] dp[i - 1][j] dp[i][j - 1] - dp[i - 1][j - 1] matrix[i][j];}}int ans INT_MIN;//记录最大子矩阵位置int x1,x2,y1,y2;for (int i 1; i n; i) {for (int j 1; j n; j) {int pivot dp[i][j];for (int k 1; k i; k) {for (int q 1; q j; q) {if((pivot - dp[k-1][j] - dp[i][q-1] dp[k-1][q-1])ans){ans max(ans, pivot - dp[k-1][j] - dp[i][q-1] dp[k-1][q-1]);x1k;x2i;y1q;y2j;}}}}}cout ansendl;coutx1y1 x2y2endl;数学问题
朴素法筛素数
求n以内的所有素数时间O(nlog(logn))【不是最优例如14会被2和7筛重复2次】
void get_primes(int n){for(int i2;in;i){//i被筛了直接跳过if(st[i]) continue;//i是素数添加进数组,并筛掉与i成倍数的非素数else {primes[cnt ] i;for(int j2*i;jn;ji){//j一定不是素数st[j]true;}}}
}线性筛素数
时间O(n)解决重复筛
forint i2;in;i){//i没被筛加入if(!st[i]) primes[prime_count]i;for(int j0;jprime_count;j){if(prime[j]*in) break;//翻倍一个数 * 素数一定为合数 st[primes[j]*i]true;//退出循环避免之后重复进行筛选if(i%primes[j]0) break;}
}快速幂
int qmi(int a,int b, int p){if(b0)return 1 ; int k qmi(a,b/2,p)%p;// k*k可能会超过int if(b%20)return (1LL*k*k) %p;else return ((1LL*k*k)%p*a)%p;}石子合并
贪心只能合并相邻的最小的两堆
int n;int min_idx0;int min_sum1e7;
// 边界处理ve.push_back(1e7);int ans0;cinn;for(int i1;in;i){int x;cinx;ve.push_back(x);if(min_sumve[i]ve[i-1]){min_sumve[i]ve[i-1];min_idxi;}}while(ve.size()2){ans min_sum;ve[min_idx]ve[min_idx]ve[min_idx-1];ve.erase(ve.begin()min_idx-1);min_sum1e7;
// min_idx0;if(ve.size()2) break; for(int i1;ive.size();i){if(min_sumve[i]ve[i-1]){min_sumve[i]ve[i-1];min_idxi;}}}coutansendl;
锯木棍
贪心-思想是WPL最小带权路径,永远合并最小的两个
#include iostream
#include queue
#include vector
#include algorithm
using namespace std;
//自定义比较结构体
struct cmp{//函数重载 注意两个括号bool operator()(int a,int b){//稳定if(ab) return false;else return ab;}
};int main(int argc, char** argv) {//priority_queueint,vectorint,greaterint que;priority_queueint,vectorint,cmp que;int n,l;cinnl;int tmp;int ans0;while(n--){cintmp;que.push(tmp);} while(que.size()!1){int aque.top();que.pop();int bque.top();que.pop();que.push(ab);ansansab;}coutans; return 0;
}并查集
int Find(int a){int xa;while(s[x]0){xs[x];}return x;
}
void Union(int a,int b){root1Find(a);root2Find(b);if(root2root1)return ;else{s[root2]root1;}}Dijkstra单源最短路
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定// 求1号点到n号点的最短路如果不存在则返回-1
int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1] 0;for (int i 0; i n - 1; i ){int t -1; // 在还未确定最短路的点中确定一个最短的点for (int j 1; j n; j )if (!st[j] (t -1 || dist[t] dist[j]))t j;// 用t更新其他点的距离for (int j 1; j n; j )dist[j] min(dist[j], dist[t] g[t][j]);st[t] true;}if (dist[n] 0x3f3f3f3f) return -1;return dist[n];}Python进制转换(整数无限大)
import sysfor line in sys.stdin:a line.split()aint(a[0])bbin(a)s(b[2:][::-1])print(int(s,2))
全排列
回溯法
void dfs(int k){if(kn1){for(int i1;in;i){coutarr[i] ;}cout\n;return ;}for(int i1;in;i){//还没访问的数if(!st[i]){st[i]true;// 存储第k个数arr[k]i;dfs(k1);// 恢复-现场st[i]false;}}
}
int main() { cinn;dfs(1);}
神奇的口袋
有一个神奇的口袋总容积是40有n个物品,体积为Vi装满40有多少种装法
void dfs(int u,int j){if(u40){ans; }else{//从j开始前面用过的舍弃掉防止重复for(int ij;in;i){if(!st[i]){st[i]true;dfs(uv[i],i);st[i]false;}}}
}全排列II
带有重复元素的全排列
void dfs(int k){if(kn1){for(int i1;in;i){coutarr[i] ;}cout\n;return ;}for(int i1;in;i){//还没访问的数if(!st[i]){st[i]true;// 存储第k个数arr[k]i;dfs(k1);// 恢复-现场st[i]false;//***当与后一个元素重复时跳过不排列,且这一步要在恢复现场之后做while(s[i1]s[i])i;}}
}
int main() { cinn;//使重复的元素排在一起sort(a,an);dfs(1);}放苹果
把M个同样的苹果放在N个同样的盘子里允许有的盘子空着不放问共有多少种不同的分法
//处理边界
for(int i0;im;i){//为0的可以不用处理数组默认为0//1个盘子的dp[i][1]1;
}
for(int i0;in;i){//0个苹果的dp[0][i]1;
}for(int i1;im;i){for(int j1;jn;j){//如果盘子多多余的用不到的盘子都是没用的if(ji){dp[i][j]dp[i][i];}//如果苹果多dp[i][j]等于 有空盘子的(挑一个盘子为空)没有空盘子(每个盘子初始都放一个苹果)的状态else{dp[i][j]dp[i][j-1]dp[i-j][j];}}
}求第k小
使用快排划分的思想
#include iostream
#include algorithm
/**求第k小 */
using namespace std;
int n;
int a[10001];
int k;
void partition(int start,int end) {int pivota[start];int lstart;int rend;while(lr) {while(a[l]pivot) {l;}while(a[r]pivot) {r--;}swap(a[l],a[r]);}a[l]pivot;if(lk-1) {couta[l];return ;}else if(lk){partition(l1,end);}else{partiton(start,l);}
}int main(int argc, char** argv) {cinn;cink;for(int i0; in; i) {cina[i];}partition(0,n-1);return 0;
}八皇后问题 哈夫曼编码
priority_queueint,vectorint,greaterint q;
int alpha[26];
//去最小的两个KMP算法
//字符串下标都从0开始
void getNextTable(int m){int j0;next[0]-1;int i-1;while(jm){if(i-1 || pattern[j]pattern[i]){i;j;next[j]i;}else{inext[i];}}return ;
}int kMP(string a,string b){int i0,j0;while(injm){if(j-1 || s[i]pattern[j]){i;j;}else{jnext[j];}}if(jm){return i-j1;}else{//匹配失败return -1;}
}遍历建立二叉树 TNode(char c):data©,left(nullptr),right(nullptr){}; using TreeNode struct TNode{char data;struct TNode* left;struct TNode* right;TNode(char c):data(c),left(nullptr),right(nullptr){};
};TreeNode* Build(TreeNode* root,char c){if(c#)return NULL;
// C style(TreeNode*)malloc(sizeof(TreeNode))rootnew TNode(c);char c1s[cnt];root-leftBuild(root-left,c1);char c2s[cnt];root-rightBuild(root-right,c2);return root;
}void Inorder(TreeNode* root){if(root-left)Inorder(root-left);coutroot-dataendl;if(root-right)Inorder(root-right);}
void postOrder(TreeNode* root){}int main(int argc, char** argv) {TreeNode* TNULL;TBuild(T,s[cnt]);Inorder(T);return 0;
}
