核心算法ACM模板.docx
- 文档编号:17142338
- 上传时间:2023-07-22
- 格式:DOCX
- 页数:85
- 大小:48KB
核心算法ACM模板.docx
《核心算法ACM模板.docx》由会员分享,可在线阅读,更多相关《核心算法ACM模板.docx(85页珍藏版)》请在冰点文库上搜索。
核心算法ACM模板
一、贪心算法1
1、区间选点1
2、区间覆盖1
3、不相交区间2
4、哈夫曼编码2
5、最小值最大化、最大值最小化(二分查找)2
二、动态规划7
1、最长公共子序列(LCS)7
2、最长上升公共子序列(LIS)9
3、子段和13
4、DAG上的动态规划19
5、区间DP25
6、状态压缩DP35
7、双线DP38
8、背包问题(见背包九讲)41
三、数据结构41
1、并查集41
2、树状数组43
3、(字符串)KMP匹配45
四、最小生成树算法48
Prime核心算法48
Kruskal算法53
五、单源最短路径57
Dijkstra核心算法57
Bellman_Ford算法61
SPFA算法(Bellman_Ford的队列实现)64
六、二分图匹配67
1、匈牙利算法67
七、网络流68
1、SAP算法68
2、Dinic算法70
一、贪心算法
1、区间问题
区间选点
选取尽量少的点覆盖所有的区间,是每个区间至少包含一个点。
对区间右端点进行排序。
区间覆盖
选取尽量少的区间覆盖整个区域。
对左端点进行排序。
不相交区间
选取尽量多的不相交区间。
对区间右端点进行排序。
2、哈夫曼编码
3、最小值最大化、最大值最小化(二分查找)
NYOJ疯牛问题(最小值最大化)
农夫John建造了一座很长的畜栏,它包括N(2<=N<=100,000)个隔间,这些小隔间依次编号为x1,...,xN(0<=xi<=1,000,000,000).
但是,John的C(2<=C<=N)头牛们并不喜欢这种布局,而且几头牛放在一个隔间里,他们就要发生争斗。
为了不让牛互相伤害。
John决定自己给牛分配隔间,使任意两头牛之间的最小距离尽可能的大,那么,这个最大的最小距离是什么呢?
#include
#include
#include
usingnamespacestd;
intn,c;
intpos[100005];
booljudge(intk)
{
intcnt=1;
intst=pos[0];
for(inti=1;i { if(pos[i]-st>=k) { ++cnt; if(cnt>=c) returntrue; st=pos[i]; } } returnfalse; } intBinary_search(intleft,intright)///二分枚举满足条件的最大距离 { while(left<=right) { intmid=(left+right)>>1; if(judge(mid))///所求距离>=mid,可以继续增大试探 left=mid+1; else///所求距离 right=mid-1; } returnleft-1; } intmain() { while(~scanf("%d%d",&n,&c)) { for(inti=0;i scanf("%d",&pos[i]); sort(pos,pos+n); printf("%d\n",Binary_search(0,pos[n-1]-pos[0])); } return0; } NYOJ摘枇杷(最大值最小化) 理工学院的枇杷快熟了,ok,大家都懂得。 而且大家都知道,学校的枇杷树都是一列一列的。 现在小Y同学已经在筹划怎么摘枇杷了。 现在我们假设有一列枇杷树,而且每棵枇杷树上枇杷果的数量小Y都已经知道了。 假设现在有n棵枇杷树,小Y可以把这n棵枇杷树分成m组,每组枇杷果的数量是这组内每棵枇杷树上枇杷果数量的和。 注意,每组的枇杷树必须是连续的。 (每组最少1棵树,最多n棵树)。 小Y把枇杷往寝室拿的时候是一组一组拿的,所花费的力气等于这m组中枇杷果最多的那组枇杷果的数量。 现在小Y想花尽量少的力气把这些枇杷果拿回寝室。 #include #include intn,m,a[1005]; booljudge(intx) { ints=0,count=0; for(inti=0;i { if(s+a[i]>x) { count++; s=a[i]; if(count>m-1)///当count==m时,而i returnfalse; } else s+=a[i]; } returntrue;///每次运送x时,m组内就能运完 } intBinary_search(intl,intr) { while(l<=r) { intmid=(l+r)/2; if(judge(mid))r=mid-1; elsel=mid+1; } returnl;///当从while中退出时,最后一次操作是r=mid-1,原本的l<=r不再满足,所以l才是所要求的值 } intmain() { while(~scanf("%d%d",&n,&m)) { memset(a,0,sizeof(a)); intMax=0,sum=0; for(inti=0;i { scanf("%d",&a[i]); sum+=a[i]; Max=Max>a[i]? Max: a[i]; } printf("%d\n",Binary_search(Max,sum)); } return0; } 二、动态规划 最长公共子序列(LCS) 最长公共子序列也称作最长公共子串(不要求连续),英文缩写为LCS(LongestCommonSubsequence)。 其定义是,一个序列S,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则S称为已知序列的最长公共子序列。 二维表: for(inti=1;i<=n1;i++) { for(intj=1;j<=n2;j++) { if(a[i]==b[j])c[i][j]=c[i-1][j-1]+1; elseif(c[i-1][j]>=c[i][j-1])c[i][j]=c[i-1][j]; elsec[i][j]=c[i][j-1]; } } 空间优化(滚动数组) #include #include intdp[1005]; intmain() { intt; scanf("%d",&t); while(t--) { getchar(); chara[1005]={0},b[1005]={0}; memset(dp,0,sizeof(dp)); scanf("%s%s",a+1,b+1); intla=strlen(a+1); intlb=strlen(b+1); for(inti=1;i<=la;i++) { intold=0;//old表示c[i-1][j-1] for(intj=1;j<=lb;j++) { inttmp=dp[j];//注意 if(a[i]==b[j])dp[j]=old+1; elseif(dp[j-1]>dp[j])dp[j]=dp[j-1]; old=tmp; } } printf("%d\n",dp[lb]); } return0; } 时间优化(转化为LIS时间复杂度O(nlogn))见LIS 1、最长上升公共子序列(LIS) 最长递增子序列问题: 在一列数中寻找一些数,这些数满足:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 核心 算法 ACM 模板
![提示](https://static.bingdoc.com/images/bang_tan.gif)