ACM刷题之路（十六）Acm程序设计竞赛自制模板 |
您所在的位置：网站首页 › 怎么自制刷题程序 › ACM刷题之路（十六）Acm程序设计竞赛自制模板 |
ACM刷题之路（十六）Acm程序设计竞赛自制模板
|
2020年2月更新：算法模板V2.1版 下载地址 前言 本模板是我在备战省赛的时光中，把复习过的和新学的算法中比较常用的代码、思路，整合成了模板，供以后的ACM竞赛直接使用，因为时间匆忙、水平有限，若有不足之处，欢迎大佬提出。本版本为V1.0版，会不定期更新。 以下所有代码都是我个人手敲，并且通过HDU、POJ等知名OJ上做题实践验证过的结果，是我两个月的成果。 水平有限，代码比较累赘，以后有机会进一步减少少考的算法，增加比较常用的算法合集。 希望能够抛砖引玉，如有意见，欢迎留言，或E-mail [email protected] 目录
前言..................................................................................................................................................................... 1 目录..................................................................................................................................................................... 1 常用思路.............................................................................................................................................................. 1 常见递推公式....................................................................................................................................................... 1 函数库—algorithm................................................................................................................................................ 1 函数库—cstring.................................................................................................................................................... 2 函数库—cmath..................................................................................................................................................... 2 快速幂................................................................................................................................................................. 3 回文数................................................................................................................................................................. 3 二分..................................................................................................................................................................... 3 尺取法................................................................................................................................................................. 3 辗转相除法.......................................................................................................................................................... 3 水仙花数.............................................................................................................................................................. 4 并查集................................................................................................................................................................. 4 分割问题.............................................................................................................................................................. 4 日期差公式.......................................................................................................................................................... 4 组合大小计算....................................................................................................................................................... 4 最大连续子序列和................................................................................................................................................ 5 LIS(最长上升子序列)............................................................................................................................................. 5 LCS(最长公共子序列)............................................................................................................................................ 6 大数a+b............................................................................................................................................................... 6 求第k个排列(阶乘法)........................................................................................................................................... 7 最短路1. Dijkstra算法.......................................................................................................................................... 8 最短路2. Floyd算法.............................................................................................................................................. 9 最小生成树prim算法.......................................................................................................................................... 10 凸包................................................................................................................................................................... 11 深搜dfs.............................................................................................................................................................. 13 广搜bfs.............................................................................................................................................................. 13 母函数或多重背包.............................................................................................................................................. 13 01背包............................................................................................................................................................... 14 完全背包............................................................................................................................................................ 14 多重背包............................................................................................................................................................ 14 状压DP.............................................................................................................................................................. 15 线段树................................................................................................................................................................ 16 常用思路 1.计算a到b之间有多少符合条件的数，可打表后二分找a和b的位置后相减 例: scanf("%lld%lld", &n, &m); i = lower_bound(s1.begin(), s1.end(), n) - s1.begin(); j = upper_bound(s1.begin(), s1.end(), m) - s1.begin(); printf("%lld\n", j - i);2.前缀和思想，不要直接暴力模拟。 3.(x1,y1)(x1,y1)(x2,y2)(x2,y2)两点连线之间的整点数是gcd(|x1−x2|,|y1−y2|)+1 4. 满足在[2,n]范围内有多少个数是非次方数（也就是不是x^k(k>1)这样的） 答案： 常见递推公式 f(n)=4*f(n-2)-f(n-4) f（n）=f（n-1）+6×（i-1） f(n)=f(n-4)+f(n-2)+f(n-1)（n>4） f[i]=f[i-1]+f[i-2]*4; f(n)=f(n-2)+f(n-1)，n>3。 F[i] = F[i-1] + 2 * F[i-2]; a[n][m] = a[n-1][m] +a[n][m-1] 函数库—algorithm //————————algorithm———————— int a[] = { 1, 3, 5, 7, 9, 11, 13 }; lower_bound(a, a + 7, 7);//返回第一个大于等于7的地址 upper_bound(a, a + 7, 7);//返回第一个小于等于7的地址 binary_search(a, a + 7, 8);//若a到a+7有8，返回true 否则返回false reverse(a, a + 7);//反转a到a+7的元素 fill(a, a + 7, 4);//填充函数，把a到a+7全部填充为4 int b[11] = { 1, 2, 3, 4 }; copy_backward(a, a + 7, b + 7);//把a数组复制到b，首地址，尾地址，复制后数组的尾地址 next_permutation(b, b + 4);//b数组的下一个排列 prev_permutation(b, b + 4);//b数组的上一个排列 replace(b, b + 4, 3, 5);//把b到b+4中所有3替换成5 stable_sort(a, a + 7, cmp);//按照cmp规则稳定排序a到a+7 unique(a, a + 7);//去重，返回去重后数组的尾地址 printf("%d\n", *max_element(a, a + 6));//返回序列a到a+6的最大元素地址 //————————algorithm————————函数库—cstring //————————cstring———————— char a[200] = "hello world"; char b[] = "hello acm"; cout |
【本文地址】
今日新闻 |
推荐新闻 |