算法|我的算法模板(带分析博客) 算法与数据结构|数据结构

目录
引言:不同的人模版不同,程序是人思维的结晶,最好用自己的代码,殊途同归!
(以下模版均有其对应的分析博客,点击标题即可跳转)
数据结构篇
1.并查集
2.字典树
3.线段树与树状数组
4.ac自动机
5.大根堆
算法篇
1.KMP算法
2.素数处理
3.gcd与扩展gcd
4.二分查值法
(1).最大化最小值
(2).最小化最大值
5.排序算法合集(模版仅摘选几个高效的)
(1).插入排序
(2).冒泡排序
(3).归并排序
(4).堆排序
(5).快速排序
(6).计数排序
(7).基数排序
6.快速幂算法
待整理的代码

数据结构篇 1.并查集在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。

//并查集(路径压缩) const int max_n=100005; int par[max_n]; void init(int n){//初始化 for(int i=1; i<=n; i++) par[i]=i; }int find(int x){//查找x所在集合的根 if(par[x]!=x) par[x]=find(par[x]); //递归返回的同时压缩路径 return par[x]; }void unite(int x,int y){//合并x与y所在集合 x=find(x); y=find(y); par[x]=y; }bool same(int x,int y){//x与y在同一集合则返回真 return find(x)==find(y); }

2.字典树处理大量字符串

//一个只带更新字符串与查找字符串的字典树（为了效率以数组实现） #include #include #include const int maxn=26; //这里假设字符串中只出现26个小写字母 const int maxm=100000; struct treenode{ bool end; //标志此节点是否是某字符串的结尾 treenode* next[maxn]; }head; treenode memory[maxm]; int mallocp=0; void init(){ head.end=1; for(int i=0; iend=0; for(int i=0; inext[i]=NULL; return newnode; }void update(char* s){ int k=0,temp; treenode* t=&head; while(s[k]){ temp=s[k]-97; if(!t->next[temp]) t->next[temp]=createnew(); t=t->next[temp]; k++; } t->end=1; }bool search(char* s){ int k=0,temp; treenode* t=&head; while(s[k]){ temp=s[k]-97; if(!t->next[temp]) return false; t=t->next[temp]; k++; } if(t->end) return true; return false; }int main(){ init(); char x[1000]; char t; while(1){ fflush(stdin); scanf("%c",&t); if(t=='q'){ scanf("%s",&x); if(search(x)) printf("匹配成功！\n"); else printf("匹配失败！\n"); } else if(t=='u'){ scanf("%s",&x); update(x); printf("更新完毕！\n"); } else if(t=='e'){ printf("退出ing....\n"); break; } else printf("无效命令！,请重新输入！\n"); } return 0; }//一个以链表实现带删除功能允许重复字符串的字典树 #include #include #include int charmapping[256]; //字符映射数组,charmapping[i]=x表示ascii码为i的字符对应于treenode中的next[x] void init_charmapping(){ for(int i='a'; i<='z'; i++){ //我的这个字典树现在只允许输入小写字符组成的字符串,然而由于有charmapping的存在,增加新字符添加映射并且增大maxn就好,很方便. charmapping[i]=i-'a'; } } const int maxn=26; //这里假设字符串中只出现26个小写字母 const int maxm=100000; struct treenode{ int count; //标志此节点所表示字符串在所有字符串中以前缀形式出现的总次数 treenode* next[maxn]; }head; void init_trie(){ head.count=1; //初始化为1包括空串并且避免树头被删 for(int i=0; icount=0; for(int i=0; inext[i]=NULL; return newnode; }void update(char* s,int num){ //向字典树添加num个字符串s int k=0,temp; treenode* t=&head; while(s[k]){ t->count+=num; temp=charmapping[s[k]]; if(!t->next[temp]) t->next[temp]=createnew(); t=t->next[temp]; k++; } t->count+=num; }bool search(char* s,int num){//查找字典树中是否已经存在num个字符串s int k=0,temp; treenode* t=&head; while(s[k]){ temp=charmapping[s[k]]; if(!t->next[temp]||t->next[temp]->countnext[temp]; k++; } int snum=t->count; for(int i=0; inext[i]) snum-=t->next[i]->count; //这里是核心!!!结点t代表的字符串出现的次数就是总次数减去所有子节点次数和 if(snum>=num) return true; //如果字符串s的数目snum大于等于num return false; }void erase(char* s,int num){//删除字典树中的num个字符串s并释放无用结点,删除前一定要先search是否存在 int k=0,temp; treenode* t=&head; treenode* t1; //t1后面的结点都是删除后需要被释放的 head.count-=num; while(s[k]){ temp=charmapping[s[k]]; t->next[temp]->count-=num; if(t->next[temp]->count==0){ t1=t->next[temp]; t->next[temp]=NULL; k++; break; } t=t->next[temp]; k++; } while(s[k]){ //释放无用结点 temp=charmapping[s[k]]; t=t1->next[temp]; free(t1); t1=t; k++; } free(t1); }char temp[1000]; void printall(treenode* tnode,int pos){ //递归打印字典树咯,打出了就是字典序升序的 int count=tnode->count; for(int i=0; inext[i]) count-=tnode->next[i]->count; for(int i=0; inext[charmapping[i]]){ temp[pos]=i; temp[++pos]='\0'; printall(tnode->next[charmapping[i]],pos); temp[--pos]='\0'; } } }int main(){ init_charmapping(); //初始化映射 init_trie(); //初始化字典树 char x[1000]; char order; //命令 int num; //数目 printf("q：查询\nu：插入\nd：删除\np：打印字典树\ne：退出\n"); while(1){ printf("请输入命令："); fflush(stdin); scanf("%c",&order); if(order=='q'){ printf("请输入要查找的字符串与数目："); scanf("%s%d",&x,&num); if(search(x,num)) printf("匹配成功。\n\n"); else printf("匹配失败，不存在%d个\"%s\"\n\n",num,x); } else if(order=='u'){ printf("请输入要插入的字符串与数目："); scanf("%s%d",&x,&num); update(x,num); printf("%d个\"%s\"已加入字典树。\n\n",num,x); } else if(order=='d'){ printf("请输入要删除的字符串与数目："); scanf("%s%d",&x,&num); if(!search(x,num)){ printf("树中无%d个字符串\"%s\"请重新键入命令！\n\n",num,x); continue; } erase(x,num); printf("%d个\"%s\"已从字典树中删除。\n\n",num,x); } else if(order=='p'){ printf("当前字典树内有如下字符串：\n"); temp[0]='\0'; printall(&head,0); } else if(order=='e'){ printf("退出ing....\n"); break; } else printf("无效命令,请重新输入！\n命令q：查询是否存在字符串\n命令u：往字典树加入字符串\n命令d：删除某个字符串\n命令p：按字典序升序输出字典树\n命令e：退出程序\n\n"); } return 0; }

3.线段树与树状数组 RMQ,区间求和,区间状态求解这些问题

//线段树 /* 常见使用方法：一.基于线段树的RMQ 要求完成： 1.给定s和t，求s到t区间内的最小值(求最大值只需修改部分细节) 2.给定i，x把a[i]的值修改为x */ #include #include using namespace std; const int maxn=10000; const int inf=(1<<30); int n; int dat[4*maxn]; int min(int a,int b){ if(a>b) return b; return a; } void update(int k,int x){ k+=n-2; dat[k]=x; while(k>0){ k=(k-1)>>1; dat[k]=min(dat[(k<<1)+1],dat[(k<<1)+2]); } }void init(int tn){ n=1; while(nr||b=r) return dat[k]; else{ int v1=query(a,b,(k<<1)+1,l,(l+r)>>1); int v2=query(a,b,(k<<1)+2,((l+r)>>1)+1,r); return min(v1,v2); } }int main(){ cin>>n; init(n); int t1,t2; char ch; getchar(); while(1){ scanf("%c%d%d",&ch,&t1,&t2); if(ch=='Q') printf("%d\n",query(t1,t2,0,1,n)); else if(ch=='U') update(t1,t2); getchar(); } return 0; } /* 二. 求指定区间和 1.求指定区间l到r的和 2.对第i个加x */ #include #include using namespace std; const int maxn=10000; int n; int dat[4*maxn]; void update(int k,int x){ k+=n-2; dat[k]=x; while(k>0){ k=(k-1)>>1; dat[k]=dat[(k<<1)+1]+dat[(k<<1)+2]; } }void init(int tn){ n=1; while(nr||b=r) return dat[k]; else{ int v1=query(a,b,(k<<1)+1,l,(l+r)>>1); int v2=query(a,b,(k<<1)+2,((l+r)>>1)+1,r); return v1+v2; } }int main(){ cin>>n; init(n); int t1,t2; char ch; getchar(); while(1){ scanf("%c%d%d",&ch,&t1,&t2); if(ch=='Q') printf("%d\n",query(t1,t2,0,1,n)); else if(ch=='U') update(t1,t2); getchar(); } return 0; }//树状数组BIT /* 作用： 1.给定i计算1到i的和 2.给定i和x，执行ai+=x； */ #include #include using namespace std; const int maxn=10000; int bit[maxn+1],n; int sum(int i){ int s=0; while(i>0){ s+=bit[i]; i-=i&-i; } return s; }void add(int i,int x){ while(i<=n){ bit[i]+=x; i+=i&-i; } }void init(n){ int tn=n,t; n=1; while(n>1; add[(k<<1)+1]+=add[k]; dat[(k<<1)+1]+=temp*add[k]; add[(k+1)<<1]+=add[k]; dat[(k+1)<<1]+=temp*add[k]; add[k]=0; } void update(int k,int l,int r,int val){ if(rtr) return ; if(r<=tr&&l>=tl){ dat[k]+=val*(r-l+1); add[k]+=val; return ; } update((k<<1)+1,l,(l+r)>>1,val); update((k+1)<<1,((l+r)>>1)+1,r,val); } int query(int k,int l,int r){ if(rtr) return 0; if(r<=tr&&l>=tl) return dat[k]; if(add[k]) pushdown(k,l,r); return query((k<<1)+1,l,(l+r)>>1)+query((k+1)<<1,((l+r)>>1)+1,r); }

4.ac自动机求解字符串多模匹配问题

#include #include #include #include #include using namespace std; const int maxkeywordlen=51; const int maxstrlen=1000001; char keyword[maxkeywordlen],str[maxstrlen]; int charmapping[256]; //字符映射数组,charmapping[i]=x表示ascii码为i的字符对应于treenode中的next[x] void init_charmapping(){ for(int i='a'; i<='z'; i++){ //我的这个字典树现在只允许输入小写字符组成的字符串,然而由于有charmapping的存在,增加新字符添加映射并且增大maxn就好,很方便. charmapping[i]=i-'a'; } } struct node{ node *fail; //失败指针,此节点失配时将跳向fail所指节点 int end; //此值表示以此节点为结尾的单词个数 node *next[26]; //指向子节点 }root; node *getnode(){//构造一个新结点并做好初始化,返回指向该节点的指针 node *newnode=(node *)malloc(sizeof(node)); newnode->end=0; newnode->fail=NULL; for(int i=0; i<26; i++) newnode->next[i]=NULL; return newnode; } void insert(char *s){ //向ac自动机加入字符串s int k=0,temp; node* t=&root; for(int i=0; s[i]; i++){ temp=charmapping[s[i]]; if(!t->next[temp]) t->next[temp]=getnode(); t=t->next[temp]; } t->end++; } void build_fail(){ //构造ac自动机的失败指针 queue q; q.push(&root); while(!q.empty()){ node* t=q.front(); q.pop(); for(int i=0; i<26; i++){ if(t->next[i]){ if(t==&root) t->next[i]->fail=&root; else{ node *p=t->fail; while(p!=NULL){ if(p->next[i]){ t->next[i]->fail=p->next[i]; break; } p=p->fail; } if(p==NULL) t->next[i]->fail=&root; } q.push(t->next[i]); } } } } void free_trie(){ //释放ac自动机, 只留根节点 queue q; for(int i=0; i<26; i++){ if(root.next[i]){ q.push(root.next[i]); root.next[i]=NULL; } } while(!q.empty()){ node* t=q.front(); q.pop(); for(int i=0; i<26; i++) if(t->next[i]) q.push(t->next[i]); free(t); } } int match(char *s){ //计算ac自动机中所有模式串在字符串s中出现的次数之和 node *now=&root; int ans=0; for(int i=0; s[i]; i++){ int temp=charmapping[s[i]]; if(now->next[temp]) now=now->next[temp]; else{ node* p=now->fail; while(p!=NULL&&p->next[temp]==NULL) p=p->fail; if(p==NULL) now=&root; else now=p->next[temp]; } if(now->end){ node *tn=now; while(tn!=NULL){ ans+=tn->end; tn->end=0; tn=tn->fail; } } } return ans; }int main(){ init_charmapping(); int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); for(int i=0; i



 
5.大根堆 
const int maxn=100001;

class myheap_max{
	private:
int heap[maxn];

int heap_size;

	public:
void init(){
for(int i=0;
i


 或者

 
priority_queu que;


 算法篇 
1.KMP算法 涉及字符串匹配的问题.

 
//kmp算法
const int maxn=100005;

int next[maxn];
//next数组 
void getnext(char* s){//构造next数组,真正的模版
	next[0]=-1;

	int i=0,j=-1;
 //j为什么初值赋值-1?0其实也行,仅仅是为了少一个判断, 
	while(s[i]){
if(j==-1||s[i]==s[j]) next[++i]=++j;
 
else j=next[j];

	}
}void kmp(char* a,char* b){ //输出a中每个匹配b串的下标,不同问题这个函数的写法多变
	int blen=0;

	while(b[blen]) blen++;

	getnext(b);

	int i=0,j=0;

	while(a[i]){
if(j==-1||a[i]==b[j]){
i++,j++;

if(!b[j]){
printf("%d ",i-blen);

j=next[j];

}
}
else j=next[j];

	}
}


 
2.素数处理 素数相关的问题.

 
// 位操作求素数 
const int maxn=1000000;

int prime[maxn],primenum;

int flag[maxn/32+1];
//数组大小实际缩小8倍 
void wei_prime(int t){
	primenum=0;

	flag[0]|=3;

	for(int k=1;
k<=t/32+1;
k++) flag[k]=0;

	for(int i=2;
i<=t;
i++){
if(!((flag[i/32]>>(i%32))&1)){
for(int j=i*i;
j<=t;
j+=i) flag[j/32]|=(1<<(j%32));

prime[primenum++]=i;

}	
	}
}
void wei_prime_onlyflag(int t){
	flag[0]|=3;

	for(int k=1;
k<=t/32+1;
k++) flag[k]=0;

	for(int i=2;
i<=t;
i++) if(!((flag[i/32]>>(i%32))&1)) for(int j=i*2;
j<=t;
j+=i) flag[j/32]|=(1<<(j%32));

}
void printby_flag(int t){
	for(int i=0;
i<=t;
i++) if(!((flag[i/32]>>(i%32))&1)) printf("%d ",i);

}


 
3.gcd与扩展gcd gcd算法是一个很古老的用于计算两数最大公约数的算法,而扩展gcd是基于gcd的一个扩展算法,用于求解模线性方程ax≡b (mod n).

 
//gcd与扩展gcd
int gcd(int a,int b){ //返回a,b的最大公因数
	if(b==0) return a;

	return gcd(b,a%b);

}ll extgcd(ll a,ll b,ll &x,ll &y){ //扩展gcd
	if(b==0){
x=1;

y=0;

return a;

	}
	ll d=extgcd(b,a%b,x,y);

	ll t=x;

	x=y;

	y=t-a/b*y;

	return d;

}ll cal(ll a,ll b,ll c){ //计算ax+by=c的满足条件的x 
ll x,y;

ll gcd=extgcd(a,b,x,y);

if(c%gcd!=0) return -1;
 //不存在解 
x*=c/gcd;

b/=gcd;

if(b<0) b=-b;

ll ans=x%b;

if(ans<=0) ans+=b;
 //对ans为负的特殊处理+ 
return ans;

}


 
4.二分查值法 用于求满足某条件的最大化最小值的答案或最小化最大值答案.

 
(1).最大化最小值

 
bool c(double mid){
//判断答案为mid时是否满足条件,满足返回true,否则false
}
 
void solve(){
	double l=0,r=maxa,mid;

	while(r-l>0.001){
mid=(l+r)/2;

if(c(mid)) l=mid;
 
else r=mid;

	}
	printf("%.1lf",l);

}


 
(2).最小化最大值

 
bool c(double mid){
//判断答案为mid时是否满足条件,满足返回true,否则false
}
 
void solve(){
	double l=0,r=maxa,mid;

	while(r-l>0.001){
mid=(l+r)/2;

if(c(mid)) r=mid;
 
else l=mid;

	}
	printf("%.1lf",r);

}


 
5.排序算法合集(模版仅摘选几个高效的) 
(1).插入排序

 
(2).冒泡排序

 
(3).归并排序

 
void merge(int *a,int l,int r,int mid){
	int temp[r-l],tempnum=0;

	int pos1=l,pos2=mid+1;

	while(pos1<=mid&&pos2<=r){
if(a[pos1]<=a[pos2]) temp[tempnum++]=a[pos1++];

else temp[tempnum++]=a[pos2++];

	}
	while(pos1<=mid) temp[tempnum++]=a[pos1++];

	while(pos2<=r) temp[tempnum++]=a[pos2++];

	for(int i=0;
i


 
(4).堆排序

 
const int maxn=100001;

class myheap_max{
	private:
int heap[maxn];

int heap_size;

	public:
void init(){
for(int i=0;
i=l;
i--){
a[i]=que.top();

que.pop();

	}
}


 
(5).快速排序

 
void quick_sort(int *a,int l,int r){
	if(l>=r) return;

	int key=a[l],left=l,right=r;

	while(left=key&&left


 
(6).计数排序

 
const int tmin=0;
//输入数据最小界 
const int tmax=1000001;
 //输入数据最大界 
const int k=tmax-tmin+1;
//区间大小 
int count[k];
//这里count[i]存的是输入数据中i+tmin出现的次数 
void jishu_sort(int *a,int l,int r){
	for(int i=0;
i


 
(7).基数排序

 
 
#include 
 
const int k=10;
//关键码区间大小 
void radix_sort(int* a,int l,int r,int key){ //排序a数组区间[l,r]内的数字
	if(key<1||r-l+1<2) return;

	int count[k];
//这里count[i]存的是输入数据中i出现的次数 
	for(int i=0;
i

 
6.快速幂算法 
ll fastpower(ll a,ll b,ll mod)//计算(a^b)%mod 
{
ll ans=1;

ll powerofa=a;

while(b){
if(b&1) ans=ans*powerofa%mod;
//一种位运算 
powerofa=powerofa*powerofa%mod;

b>>=1;

}
return ans;

}


 

 
待整理代码 
//用邻接表和邻接矩阵存图. 基于邻接表的拓扑排序 
#include 
#include 
#include 
using namespace std;

const int inf=0x3f3f3f3f;

int main(){
	int v,e,x,y;

	cin>>v>>e;

	int a[v+1][v+1];

	for(int i=0;
i<=v;
i++) for(int j=0;
j<=v;
j++) a[i][j]=i==j?0:inf;

	vector m[v+1];

	while(e--){
cin>>x>>y;

a[x][y]=1;

m[x].push_back(y);

	}
	for(int i=1;
i<=v;
i++){
for(int j=1;
j<=v;
j++) cout<";

for(int j=0;
j q;

	for(int i=1;
i<=v;
i++) if(!rudu[i]) q.push(i);

	int tuopuans[v];

	int count=0,t,flag[v+1];

	for(int i=1;
i<=v;
i++) flag[i]=0;

	while(!q.empty()){
t=q.front();

q.pop();

if(flag[t]) break;

else flag[t]=1;

tuopuans[count++]=t;

for(int i=0;
i
#include 
#include 
#include 
using namespace std;

typedef pair p;

int main(){
	int v,e,x,y;

	while(scanf("%d %d",&v,&e)!=EOF){
vector m[v+1];

while(e--){
scanf("%d %d",&x,&y);

m[y].push_back(x);

}
int rudu[v+1];

for(int i=0;
id[e.from]+t.cost){
d[e.to]=d[e.from]+e.cost;

if(i==v-1) return true;

}
}
	}
	return false;

}
//dijkstra迪杰斯特拉算法 不允许负边的存在 struct edge{
	int to,cost;

};
typedef pair p;

int v;

vector g[max_v];

int d[max_v];
void dijkstra(int s){
	priority_queue,greater > q;

	fill(d,d+v,inf);

	d[s]=0;

	q.push(p(0,s));

	while(!q.empty()){
p t=q.top();

q.pop();

int v=t.second;

if(d[v]d[v]+e.cost){
d[e.to]=d[v]+e.cost;
 
q.push(p(d[e.to],e.to));

}
}
	}
}// Floyd-warshall 弗洛伊德算法任意两点间最短路
int d[max_v][max_v];

int v;

void warshall_floyd(){
	for(int i=0;
i p;

int v,s;

vector g[max_v];

int d[max_v];

int prev[max_v];
void dijkstra(int s){
	priority_queue,greater > q;

	fill(d,d+v,inf);

	fill(prev,prev+v,-1);

	d[s]=0;

	q.push(p(0,s));

	while(!q.empty()){
p t=q.top();

q.pop();

int v=t.second;

if(d[v]d[v]+e.cost){
d[e.to]=d[v]+e.cost;
 
prev[e.to]=v;

q.push(p(d[e.to],e.to));

}
}
	}
}//kruskal克鲁斯卡尔算法 
#include 
#include 
using namespace std;

#define max_v 1000
#define max_e 5000
int par[max_v];

void init(int n){
	for(int i=0;
i>v>>e;

	for(int i=0;
i>es[i].u>>es[i].v>>es[i].cost;

	cout<
#include 
#include 
using namespace std;

typedef pair p;
const int max_n=1000;

const int inf=(1<<30);

vector m[max_n];

bool used[max_n];

int v,e;

int prim(){
priority_queue,greater > q;

q.push(p(0,1));

int res=0,num=0;

while(!q.empty()){
p t=q.top();

q.pop();

num++;

res+=t.first;

int v=t.second;

used[v]=1;

for(int i=0;
i>v>>e,~v){
for(int i=0;
i>from>>to>>c;

m[from].push_back(p(c,to));

m[to].push_back(p(c,from));

}
cout,是指向相等元素所在区间的 左闭右闭 区间的一对指针int a[7]={1,2,3,3,3,4,5};

pair t=equal_range(a,a+7,3);
 
for(int* i=t.first;
i!=t.second;
i++) cout<<*i<<" ";
注意事项：
1.默认传入区间元素已经是升序排列
2.cout<<*lower_bound(a,a+7,3)<
#include 
using namespace std;
int main(){
	int a[5]={1,2,3,4,5};

	stable_sort(a,a+5);
//从小到大 
	do{
for(int i=0;
i<5;
i++) cout<());
//从大到小 
	do{
for(int i=0;
i<5;
i++) cout<
#include 
using namespace std;
int main(){
	int n,m;
//n是物品geshu，m是背包最大容量
	scanf("%d",&n);

	int w[n],v[n];
// w是物品费用，v是物品价值
	for(int i=0;
i=w[i];
j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

	printf("%d",dp[m]);
 //能获得的最大价值 
	return 0;

}//完全背包问题（每种物品无限个）
#include 
#include 
using namespace std;
int main(){
	int n,m;
//n是物品geshu，m是背包最大容量
	scanf("%d",&n);

	int w[n],v[n];
// w是物品费用，v是物品价值
	for(int i=0;
i
#include 
using namespace std;
int main(){
	int n,m;
//n是物品geshu，m是背包最大容量
	scanf("%d",&n);

	int w[n],v[n],k[n];
// w是物品费用，v是物品价值，k是物品个数 
	for(int i=0;
i=m) for(int j=w[i];
j<=m;
j++) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
 
else{
int tk=k[i];

int k=1;

while(k<=tk){
for(int j=m;
j>=k*w[i];
j--) dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);

tk-=k;

k<<=1;

}
if(tk) for(int j=m;
j>=tk*w[i];
j--) dp[j]=max(dp[j],dp[j-tk*w[i]]+tk*v[i]);

}
	}
	printf("%d",dp[m]);
 //能获得的最大价值 
	return 0;

}//3种背包问题的封装void zeroonepack(int w,int v){//01背包 
	for(int i=m;
i>=w;
i--) dp[i]=max(dp[i],dp[i-w]+v);

}void completepack(int w,int v){//完全背包问题 
	for(int i=w;
i<=m;
i++) dp[i]=max(dp[i],dp[i-w]+v);

}void multiplepack(int w,int v,int k){
	if(w*k>=m) completepack(w,v);

	else{
for(int t=1;
t<=k;
k-=t,t<<=1) zeroonepack(t*w,t*v);

if(k) zeroonepack(k*w,k*v);

	}
}//LCS 最长公共子序列 待搞成m+n#include 
using namespace std;
int main(){
	string a,b;

	cin>>a>>b;

	int alen=a.length(),blen=b.length();

	int dp[alen+1][blen+1];

	for(int i=0;
i0;
i--) printf("%c ",a[path[i]]);

	printf("%c\n",a[path[0]]);

	return 0;

}//LIS最长上升子序列n*logn复杂度 二分法实现 
#include 
#include 
using namespace std;

const int inf=(1<<30);

int main(){
	int n,t,res=0;

	scanf("%d",&n);

	int a[n],dp[n];

//dp[i]的含义是长度为i+1的上升子序列中末尾元素的最小值，故dp数组中存的不是最长上升子序列 
	for(int i=0;
i


 【算法|我的算法模板(带分析博客)】



		  	

    
    




    
    
    


推荐阅读

           
                  
              
                  凉血祛风糖浆的说明书 
                
                   
                
              
            

                  
              
                  非师范学生当老师 非师范生怎么当上老师 
                
                   
                
              
            

                  
              
                  linux抓网络数据命令 linux网络抓包分析工具 
                
                   
                
              
            

                  
              
                  什么是视频滤镜，视频滤镜原理 
                
                   
                
              
            

                  
              
                  微信声音锁登录无法识别如何解决 微信声音锁登录无法识别如何解决呢 
                
                   
                
              
            

                  
              
                  黄芪水一个星期喝几次是合理的 
                
                   
                
              
            

                  
              
                  圣诞语录短句简短 圣诞语录短句简短给朋友 
                
                   
                
              
            

                  
              
                  十条笑话:儿子喜欢上隔壁家女儿，我该怎么办? 
                
                   
                
              
            

                  
              
                  关于电脑怎么同步微信视频号的信息 
                
                   
                
              
            

                  
              
                  易拉罐吹跑车声音教程 这么强大的操作 
                
                   
                
              
            

                  
              
                  枯萎的玫瑰花瓣可以做什么 
                
                   
                
              
            

                  
              
                  redis和数据库不一致时怎么解决 Redis和sql区别 
                
                   
                
              
            

                  
              
                  天之蓝海之蓝梦之蓝 洋河海之蓝酒价格表 
                
                   
                
              
            

                  
              
                  心烦的时候怎么办 
                
                   
                
              
            

                  
              
                  如何在云服务器上安装PHP？ 云服务器怎么安装php 
                
                   
                
              
            

                  
              
                  安装辅材包括哪些 安装辅材包括哪些东西 
                
                   
                
              
            

                  
              
                  华为编程语言仓颉官网报名，谁创造了汉语 
                
                   
                
              
            

                  
              
                  新产品上市的推广话术 新品上市广告语怎么写 
                
                   
                
              
            

                  
              
                  廖常初plc编程及应用，PLC编程及应用 第3版 廖常初 课后答案 
                
                   
                
              
            

                  
              
                  紫砂壶怎么选 
                
                   
                
              
            

          

一个小故事，我的思考。 
 家乡的那条小河 
 前任 
 画解算法（1.|画解算法：1. 两数之和） 
 Guava|Guava RateLimiter与限流算法 
 opencv|opencv C++模板匹配的简单实现 
 绘本讲师训练营【18期】14/21《我的情绪小怪兽》故事会新体验 
 我的友谊纪念日 
 从我的第一张健身卡谈传统健身房 
 阴雨