《个人整理ACM模板》由会员分享，可在线阅读，更多相关《个人整理ACM模板（72页珍藏版）》请在金锄头文库上搜索。
1、0. 头文件#define _CRT_SBCURE_NO_DEPRECATE#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;const int maxn = 110;1. const int INF = 0x3f3f3f3f;经典1.埃拉托斯特尼筛法/* |埃式筛法| |快速筛选素数| |16/11/05ztx|*/int primemaxn; bool is_primemaxn;int
2、sieve(int n) int p = 0; for(int i = 0; i = n; +i) is_primei = true; is_prime0 = is_prime1 = false; for (int i = 2; i = n; +i) / 注意数组大小是n if(is_primei) primep+ = i; for(int j = i + i; j 0) if (n & 1) / 判断是否为奇数，若是则true res = (res * x) % m; x = (x * x) % m; n = 1; / 相当于n /= 2; return res;3.大数模拟大数加法/* |
3、大数模拟加法| |用string模拟| |16/11/05ztx, thanks to caojiji|*/string add1(string s1, string s2) if (s1 = & s2 = ) return 0; if (s1 = ) return s2; if (s2 = ) return s1; string maxx = s1, minn = s2; if (s1.length() = 0; -i) maxxa- += minni - 0; / a一直在减 ， 额外还要减个0 for (int i = maxx.length()-1; i 0;-i) if (maxxi
4、 9) maxxi -= 10;/注意这个是减10 maxxi - 1+; if (maxx0 9) maxx0 -= 10; maxx = 1 + maxx; return maxx;大数阶乘/* |大数模拟阶乘| |用数组模拟| |16/12/02ztx|*/#include #include using namespace std;typedef long long LL;const int maxn = 100010;int nummaxn, len;/* 在mult函数中，形参部分：len每次调用函数都会发生改变，n表示每次要乘以的数，最终返回的是结果的长度 tip: 阶乘都是先求之
5、前的(n-1)!来求n! 初始化Init函数很重要，不要落下*/void Init() len = 1; num0 = 1;int mult(int num, int len, int n) LL tmp = 0; for(LL i = 0; i len; +i) tmp = tmp + numi * n; /从最低位开始，等号左边的tmp表示当前位，右边的tmp表示进位（之前进的位） numi = tmp % 10; / 保存在对应的数组位置，即去掉进位后的一位数 tmp = tmp / 10; / 取整用于再次循环,与n和下一个位置的乘积相加 while(tmp) / 之后的进位处理 nu
6、mlen+ = tmp % 10; tmp = tmp / 10; return len;int main() Init(); int n; n = 1977; / 求的阶乘数 for(int i = 2; i = 0; -i) printf(%d,numi); / 从最高位依次输出,数据比较多采用printf输出 printf(n); return 0;4.GCD/* |辗转相除法| |欧几里得算法| |求最大公约数| |16/11/05ztx|*/int gcd(int big, int small) if (small big) swap(big, small); int temp; w
7、hile (small != 0) / 辗转相除法 if (small big) swap(big, small); temp = big % small; big = small; small = temp; return(big);5.LCM/* |辗转相除法| |欧几里得算法| |求最小公倍数| |16/11/05ztx|*/int gcd(int big, int small) if (small big) swap(big, small); int temp; while (small != 0) / 辗转相除法 if (small big) swap(big, small); te
8、mp = big % small; big = small; small = temp; return(big);6.全排列/* |求1到n的全排列, 有条件| |16/11/05ztx, thanks to wangqiqi|*/void Pern(int list, int k, int n) / k表示前k个数不动仅移动后面n-k位数 if (k = n - 1) for (int i = 0; i n; i+) printf(%d, listi); printf(n); else for (int i = k; i n; i+) / 输出的是满足移动条件所有全排列 swap(listk
9、, listi); Pern(list, k + 1, n); swap(listk, listi); 7.二分搜索/* |二分搜索| |要求：先排序| |16/11/05ztx, thanks to wangxiaocai|*/ left为最开始元素, right是末尾元素的下一个数，x是要找的数int bsearch(int *A, int left, int right, int x) int m; while (left = x) right = m; else left = m + 1; / 如果要替换为 upper_bound, 改为:if (Am = v) x = m+1; else y = m; return left;/* 最后left = right 如果没有找到135577找6，返回7 如果找有多少的x，可以用lower_bound查找一遍，upper_bound查找一遍，下标相减 C+自带的lower_bound(a,a+n,x)返回数组中最后一个x的下一个数的地址 upper_bound(a,a+n,x)返回数组中第一个x的地址 如果a+n内没有找到x或x的下一个地址，返回a+n的地址 lower_bound(a,a+n,x）-upper_bound(a,a+n,x)返回数组中x的个数*/数据结构并查集8.并查集/* |合并节点操作| |16/11
