系统性训练,励志刷完挑战程序设计竞赛-代码整理43~68【初级篇】

本文主要是介绍系统性训练,励志刷完挑战程序设计竞赛-代码整理43~68【初级篇】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2014年9月4日大概完成到这边了。编写了几天突然感觉到cpp很上手。现在码的速度也提上去了。再见

/*
刚开始不明白到底是干什么的。后来仔细想想,我检查是弱爆了。
简单就是意思就是请求组合n中选m的种,即n的m划分。不重复。使用dp存储。求解组合类问题思路有了吧。当然用组合工程直接求也行。
DP计数:从n物品中划分出m种不同的组合 4
3
100004
*/#include<iostream>
using namespace std;
int n,m,M;
const int MAXN=1<<10;
int dp[MAXN][MAXN];void input(){scanf("%d%d%d",&n,&m,&M);	
}//dp[i][j] j的i划分总数 
void sovle(){dp[0][0]=1;for(int i=1;i<=m;i++)for(int j=0;j<=n;j++){if(j-i>=0)dp[i][j]=(dp[i][j-i]+dp[i-1][j])%M;elsedp[i][j]=dp[i-1][j];}printf("%d\n",dp[m][n]);
}int main(){input();sovle();	return 0;	
}


/*
最后使用stl中的函数快速的求解二分上下限的方法不错。值得学习。5
4 2 3 1 53
*/
#include <iostream>
using namespace std;
const int MAXN=1<<10;
int n,a[MAXN],dp[MAXN],INF=(1<<31)-1;void input(){scanf("%d",&n);int i=0;while(i<n)scanf("%d",&a[i++]);		
}//dp[i],a[i]个元素结尾的最长上升子序列的值void sovle1(){int ans=0;for(int i=0;i<n;i++){dp[i]=1;for(int j=0;j<i;j++){if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+1);	}	ans=max(ans,dp[i]);	}	printf("%d\n",ans);
}void sovle2(){fill(dp,dp+n,INF);for(int i=0;i<n;i++){*lower_bound(dp,dp+n,a[i])=a[i];}printf("%d\n",lower_bound(dp,dp+n,INF)-dp); //数组名dp返回的是数组首地址,l_b方法同样是dp的数组的地址号,相差12/4(int %d输出)=3 printf("%d\n",lower_bound(dp,dp+n,INF));printf("%d\n",dp);
}
int main(){input();sovle1();sovle2();return 0;	
}


/*3
3 5 8
3 2 2
17Yes
*/#include<iostream>
using namespace std;const int MAXN=1<<10;
int n,a[MAXN],m[MAXN],K,dp[MAXN][MAXN];void input(){scanf("%d",&n);int i=0;while(i<n)scanf("%d%d",&a[i],&m[i++]);scanf("%d",&K);	
}//dp[i+1][j]=前i个元素相加和得到j时,i元素的剩余个数
//3类,1:i-1得到j,此时i元素的剩余量为mi
//2:i 前i中加和出j-ai,那么第i种剩余量为k,所以剩余此时i的剩余量为k-1个 
void sovle(){memset(dp,-1,sizeof(dp));dp[0][0]=0; //初始化for(int i=0;i<n;i++)for(int j=0;j<=K;j++){if(dp[i][j]>=0){  //说明i-1之和=j了。 i+1对应的是i剩余m[i] dp[i+1][j]=m[i];}else if(j<a[i] || dp[i+1][j-a[i]]<=0){ //j<a[i]不满足选择a[i],dp[i+1][j-a[i]]<=0即前i元素之和等于j-a[i]时,i的元素剩余量<=0。所以dp[i+1][j]=-1;即不能选 dp[i+1][j]=-1;}else{dp[i+1][j]=dp[i+1][j-a[i]]-1;  //dp[i+1][j-a[i]] ,前i种加和j-a[i]时,i的剩余量>0,那么dp[i+1][j]=K-1了。 }	}/* for(int i=0;i<=n;i++){for(int j=0;j<=K;j++){printf("%d ",dp[i][j]); }printf("\n");	}*/if(dp[n][K]>=0)printf("Yes\n");elseprintf("No\n");}int main(){input();sovle();		return 0;
}


/*
如果w数值范围较大,需要转换dp。即将内层循环次数最小,价值v代替 
//dp[i+1][j],挑选前i个物品的总价值j时,总重量的最小值 4
2 3
1 2
3 4
2 2
57
*/#include<iostream>
using namespace std;
const int MAX_N=100,MAX_V=100;
const int MAXN=1<<20;
int n,W,w[MAXN],v[MAX_V],dp[MAX_N+1][MAX_N*MAX_V+1];int INF=1<<11;void input(){scanf("%d",&n);int i=0;while(i<n)scanf("%d%d",&w[i],&v[i++]);scanf("%d",&W);	}void sovle(){fill(dp[0],dp[0]+MAX_N*MAX_V+1,INF);dp[0][0]=0;for(int i=0;i<n;i++){for(int j=0;j<=MAX_N*MAX_V;j++){if(j<v[i])dp[i+1][j]=dp[i][j];elsedp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i]);}}int ans=0;for(int i=0;i<=MAX_N*MAX_V;i++){//printf("%d  ",dp[n][i]);if(dp[n][i]<=W) ans=i;}printf("%d\n",ans);}int main(){input();sovle();	return 0;	
}


/*
下面是三种不同的技巧。不过答案是14.不是书上的10.难道我错了?
话说完全背包与01背包状态转移一样。3
3 4
4 5
2 3
710
*/ 
#include<iostream>
using namespace std;
const int MAXN=1<<10;
int n,W,w[MAXN],v[MAXN],dp[MAXN][MAXN],dpp[MAXN];void input(){scanf("%d",&n);int i=0;while(i<n)scanf("%d%d",&w[i],&v[i++]);scanf("%d",&W);	
}
//从前i种物品挑选总重量小于j时的总价值最大,此时与01背包问题相同 
//dp[i+1][j]=dp[i][j];
//dp[i+1]][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]);
void sovle1(){for(int i=0;i<n;i++)for(int j=0;j<=W;j++){if(j<w[i])dp[i+1][j]=dp[i][j];elsedp[i+1][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]);//dp[i+1][j]=(j<w[i])?dp[i][j]:max(dp[i][j],dp[i+1][j-w[i]]+v[i]);} printf("%d\n",dp[n][W]);
}//重复利用数组 
void sovle2(){for(int i=0;i<n;i++)for(int j=w[i];j<=W;j++){dpp[j]=max(dpp[j],dpp[j-w[i]]+v[i]);}printf("%d\n",dpp[W]);	
}//滚动二维数组,类似dp[2][MAXN] ,x=x&1,交叉奇偶 
void sovle3(){memset(dp,0x00,sizeof(dp));for(int i=0;i<n;i++)for(int j=0;j<=W;j++){if(j<w[i])dp[(i+1)&1][j]=dp[i&1][j];elsedp[(i+1)&1][j]=max(dp[i&1][j],dp[(i+1)&1][j-w[i]]+v[i]);//dp[i+1][j]=(j<w[i])?dp[i][j]:max(dp[i][j],dp[i+1][j-w[i]]+v[i]);} printf("%d\n",dp[n&1][W]);} int main(){input();sovle1();sovle2();sovle3();	return 0;
}


/*
2014阿里巴巴笔试题有一道是关于最长公共子序列lcp问题的,不过也可以转化为lcs问题。请看下面的方法就明白了。经典dp:lcs问题 
si+1=tj+1  dp[i+1][j+1]=dp[i][j]+1;此处另外三项相等
其他  dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);选择(si+1,ti),(si,ti+1)2个子串中的的最大值 4
4
abcd
becd3
2
*/
#include <iostream>
using namespace std;
const int MAXN=1<<10;
char s[MAXN],t[MAXN];
int n,m,dp[MAXN][MAXN];void input(){scanf("%d%d",&n,&m);scanf("%s%s",&s,&t);
}//求解dp[n][m] ,lcs问题 
void sovle1(){for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(s[i]==t[j])dp[i+1][j+1]=dp[i][j]+1;elsedp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);}}printf("%d\n",dp[n][m]);
}//求解lcs连续公共子串 
void sovle2(){memset(dp,0x00,sizeof(dp));int max=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(s[i]==t[j]){dp[i+1][j+1]=dp[i][j]+1;max=max<dp[i+1][j+1]?dp[i+1][j+1]:max;//printf("%d\n",max);	}else{dp[i+1][j+1]=0;	//非连续=0	}		}}/*for(int i=0;i<=n;i++){for(int j=0;j<=m;j++){printf("%d ",dp[i][j]);	}printf("\n");}*/printf("%d\n",max);}int main(){input();sovle1();sovle2();return 0;
}


 /*
使用dp的时候一定要确定好状态,以及转移代价。然后求解dp。求解dp一般从边界开始递推,多的情况下有n^3次的复杂度求解。普通的dp为n^2,内层循环尽量大,
外层循环尽量小,可以减少cpu的切换,还有提高缓存命中率,一定程度上在机器本身上减少了运行代价。编程艺术上面都这么来的,其实书上写的也有局限性,只是作者没有
注意到实际情况。不过这样来写只是根据不同的编译器确定的。因为锅测试了下。如果不开编译器优化,基本没有差距。有的情况下还会有相反代价的运行。
看来有时候真的需要实践,实践是检验真理唯一标准,。一定木错。4
2 3
1 2
3 4
2 2
57
*/
#include<iostream>
using namespace std;
const int MAXN=1<<7;
int w[MAXN],v[MAXN],n,W,dp[MAXN][MAXN]; void input(){scanf("%d",&n);int i=0;while(i<n){scanf("%d %d",&w[i],&v[i]);i++;	}//while(--i>=0)printf("--%d %d\n",w[i],v[i]);	scanf("%d",&W);
}
//从第i件物品挑选小于j的重量 
int rec(int i,int j){if(dp[i][j]>=0) return dp[i][j];int res;if(i==n) res=0;else if(j<w[i]){res=rec(i+1,j);}else{//选择与不选择 res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i]); 	}return dp[i][j]=res;
}//枚举 
void sovle1(){memset(dp,-1,sizeof(dp));printf("%d\n",rec(0,W));		
}//dp[i][j] ,从第i个物品挑选出总重量小于j时,总价值最大, 
void sovle2(){//memset(dp,0,sizeof(dp));for(int i=0;i<=W;i++){dp[n][i]=0;}for(int i=n-1;i>=0;i--)for(int j=0;j<=W;j++){if(j<w[i]){dp[i][j]=dp[i+1][j];  //上,右方向计算dp 			} else{dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);  //[]扩错第二个参数,尼玛,调试半个小时,坑死我了 //第二个参数思维方向为递归选择最大值,保持dp[i][j]的价值总和最大 }			}			printf("%d\n",dp[0][W]);for(int i=0;i<n;i++){for(int j=0;j<=W;j++){printf("%d ",dp[i][j]);}	printf("\n");}
}//dp[i+1][j],从前i个物品挑选出总重量不超过j物品的总价值最大 
void sovle3(){memset(dp,0,sizeof(dp));for(int i=0;i<n;i++)for(int j=0;j<=W;j++){if(j<w[i])dp[i+1][j]=dp[i][j];else dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);}printf("%d\n",dp[n][W]);
}int main(){input();sovle1();sovle2();	sovle3();return 0;
}


/*
修理栅栏,话说还用优先队列priority_queue存来维护最小值还是不错的。毕竟底层是二叉堆logn的代价
贪心策略:总的开销为所有的叶子节点的代价长度*深度之和。所以最短的板是叶子最深的节点,
次短的板是其兄弟节点。一直合并到根部即可 3
8 5 834
*/#include<iostream>
using namespace std;
const int MAXN=1<<11;
int N,L[MAXN];
typedef long long ll;void input(){scanf("%d",&N);int i=0;while(i<N){scanf("%d",&L[i++]);}	
}void sovle(){ll ans=0;while(N>1){int min1=0,min2=1;if(L[min1]>L[min2]) swap(min1,min2);for(int i=2;i<N;i++){if(L[i]<L[min1]){min2=min1;min1=i;}else if(L[i]<L[min2]){min2=i;}}	//合并 int t=L[min1]+L[min2];ans+=t;//将N-1的值转移到min2中,t转移到min1if(min1==N-1) swap(min1,min2);L[min1]=t;		L[min2]=L[N-1];	N--;	 	}	printf("%lld\n",ans);}int main(){input();sovle();return 0;
}


/*
囧,nn复杂度
贪心策略:向前走,R内最右侧,R外最近侧,循环至n结束即可 6
10
1 7 15 20 30 503
*/
#include<iostream>
using namespace std;
const int MAXN=1<<7;
int x[MAXN],n,r;void input(){scanf("%d",&n);scanf("%d",&r);int i=0;while(i<n){scanf("%d",&x[i++]);}		
}void sovle1(){int ans=0,a=0,f;sort(x,x+n);int cyc=-1; //防止过界循环标记 while(a<n){for(int i=a;i<n;i++){if(x[i]>(x[a]+r)){f=i-1;//printf("%d ",x[f]);break;	}}ans++;	for(int i=f;i<n;i++){if(x[i]>(x[f]+r)){a=i;if(cyc==a) goto loop ;	 cyc=a;//printf("%d ",a);break;}   }}loop:printf("%d\n",ans);	
}	void sovle2(){int i=0,ans=0;while(i<n){int s=x[i++];//s是没有覆盖的最左边的点 //一直向右前进到距离大于R的点 while(i<n && x[i]<=s+r)i++;int P=x[i-1];//标记点//一直向右前进至R之后未标记的点while(i<n&& x[i]<=P+r)i++;ans++;}printf("%d\n",ans);
}int main(){input();sovle1();sovle2();	return 0;
}


/*
贪心策略:比较s与s的逆序,较小者取其头部加入T即可 
6
ACDBCBABCBCD
*/
#include<iostream>
using namespace std;
const int MAXN=1<<8;
char s[MAXN];
int n;void input(){scanf("%d",&n);scanf("%s",&s);	
}
void sovle(){int a=0,b=n-1;bool f=true;while(a<=b){//判断取值左右 for(int i=0;i<n;i++){if(s[a+i]<s[b-i]){f=true;	break;}else if(s[a+i]>s[b-i]){f=false;break;}}if(f==true) printf("%c",s[a++]);else printf("%c",s[b--]);	}
}int main(){input();sovle();return 0;
}


这篇关于系统性训练,励志刷完挑战程序设计竞赛-代码整理43~68【初级篇】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/745346

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时