系统性训练,励志刷完挑战程序设计竞赛-代码整理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

相关文章

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

jupyter代码块没有运行图标的解决方案

《jupyter代码块没有运行图标的解决方案》:本文主要介绍jupyter代码块没有运行图标的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录jupyter代码块没有运行图标的解决1.找到Jupyter notebook的系统配置文件2.这时候一般会搜索到

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

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

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