ACM算法模板 · 一些常用的算法模板 |
您所在的位置：网站首页 › 田径比赛中的数学题怎么做 › ACM算法模板 · 一些常用的算法模板 |
|
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; const int INF = 0x3f3f3f3f; 经典1.埃拉托斯特尼筛法 /* |埃式筛法| |快速筛选素数| |16/11/05ztx| */ int prime[maxn]; bool is_prime[maxn]; int sieve(int n){ int p = 0; for(int i = 0; i = 1; // 相当于n /= 2; } return res; }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() < s2.length()){ maxx = s2; minn = s1; } int a = maxx.length() - 1, b = minn.length() - 1; for (int i = b; i >= 0; --i){ maxx[a--] += minn[i] - '0'; // a一直在减 ， 额外还要减个'0' } for (int i = maxx.length()-1; i > 0;--i){ if (maxx[i] > '9'){ maxx[i] -= 10;//注意这个是减10 maxx[i - 1]++; } } if (maxx[0] > '9'){ maxx[0] -= 10; maxx = '1' + maxx; } return maxx; }大数阶乘 /* |大数模拟阶乘| |用数组模拟| |16/12/02ztx| */ #include #include using namespace std; typedef long long LL; const int maxn = 100010; int num[maxn], len; /* 在mult函数中，形参部分：len每次调用函数都会发生改变，n表示每次要乘以的数，最终返回的是结果的长度 tip: 阶乘都是先求之前的(n-1)!来求n! 初始化Init函数很重要，不要落下 */ void Init() { len = 1; num[0] = 1; } int mult(int num[], int len, int n) { LL tmp = 0; for(LL i = 0; i < len; ++i) { tmp = tmp + num[i] * n; //从最低位开始，等号左边的tmp表示当前位，右边的tmp表示进位（之前进的位） num[i] = tmp % 10; // 保存在对应的数组位置，即去掉进位后的一位数 tmp = tmp / 10; // 取整用于再次循环,与n和下一个位置的乘积相加 } while(tmp) { // 之后的进位处理 num[len++] = tmp % 10; tmp = tmp / 10; } return len; } int main() { Init(); int n; n = 1977; // 求的阶乘数 for(int i = 2; i = 0; --i) printf("%d",num[i]); // 从最高位依次输出,数据比较多采用printf输出 printf("\n"); return 0; }4.GCD /* |辗转相除法| |欧几里得算法| |求最大公约数| |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); 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); temp = 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", list[i]); } printf("\n"); }else { for (int i = k; i < n; i++) { // 输出的是满足移动条件所有全排列 swap(list[k], list[i]); Pern(list, k + 1, n); swap(list[k], list[i]); } } }7.二分搜索 /* |二分搜索| |要求：先排序| |16/11/05ztx, thanks to wangxiaocai| */ // left为最开始元素, right是末尾元素的下一个数，x是要找的数 int bsearch(int *A, int left, int right, int x){ int m; while (left < right){ m = left + (right - left) / 2; if (A[m] >= x) right = m; else left = m + 1; // 如果要替换为 upper_bound, 改为:if (A[m] n) return -1; Q.push(v2); } } } } return dist[e]; } /* 不断的将s的邻接点加入队列，取出不断的进行松弛操作，直到队列为空 如果一个结点被加入队列超过n-1次，那么显然图中有负环 */ Floyd-Warshall13.弗洛伊德算法 /* |Floyd算法| |任意点对最短路算法| |求图中任意两点的最短距离的算法| */ for (int i = 0; i < n; i++) { // 初始化为0 for (int j = 0; j < n; j++) scanf("%lf", &dis[i][j]); } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); } } } 二分图14.染色法 /* |交叉染色法判断二分图| |16/11/05ztx| */ int bipartite(int s) { int u, v; queueQ; color[s] = 1; Q.push(s); while (!Q.empty()) { u = Q.front(); Q.pop(); for (int i = 0; i < G[u].size(); i++) { v = G[u][i]; if (color[v] == 0) { color[v] = -color[u]; Q.push(v); } else if (color[v] == color[u]) return 0; } } return 1; }15..匈牙利算法 /* |求解最大匹配问题| |递归实现| |16/11/05ztx| */ vectorG[maxn]; bool inpath[maxn]; // 标记 int match[maxn]; // 记录匹配对象 void init() { memset(match, -1, sizeof(match)); for (int i = 0; i < maxn; ++i) { G[i].clear(); } } bool findpath(int k) { for (int i = 0; i < G[k].size(); ++i) { int v = G[k][i]; if (!inpath[v]) { inpath[v] = true; if (match[v] == -1 || findpath(match[v])) { // 递归 match[v] = k; // 即匹配对象是“k妹子”的 return true; } } } return false; } void hungary() { int cnt = 0; for (int i = 1; i cnt)-=t; } for(int i=0;inext[i] = NULL; } int main() { int n; char str1[50]; char str2[50]; while(scanf("%d",&n)!=EOF) { root = new Trie; while(n--) { scanf("%s %s",str1,str2); if(str1[0]=='i') { Insert(str2); }else if(str1[0] == 's') { if(Search(str2)) printf("Yes\n"); else printf("No\n"); }else { int t = Search(str2); if(t) Delete(str2,t); } } } return 0; }28.AC自动机 /* |16/11/06ztx| */ #include #include #include #include using namespace std; #define N 1000010 char str[N], keyword[N]; int head, tail; struct node { node *fail; node *next[26]; int count; node() { //init fail = NULL;// 默认为空 count = 0; for(int i = 0; i < 26; ++i) next[i] = NULL; } }*q[N]; node *root; void insert(char *str) { // 建立Trie int temp, len; node *p = root; len = strlen(str); for(int i = 0; i < len; ++i) { temp = str[i] - 'a'; if(p->next[temp] == NULL) p->next[temp] = new node(); p = p->next[temp]; } p->count++; } void build_ac() { // 初始化fail指针，BFS 数组模拟队列： q[tail++] = root; while(head != tail) { node *p = q[head++]; // 弹出队头 node *temp = NULL; for(int i = 0; i < 26; ++i) { if(p->next[i] != NULL) { if(p == root) { // 第一个元素fail必指向根 p->next[i]->fail = root; }else { temp = p->fail; // 失败指针 while(temp != NULL) { // 2种情况结束：匹配为空or找到匹配 if(temp->next[i] != NULL) { // 找到匹配 p->next[i]->fail = temp->next[i]; break; } temp = temp->fail; } if(temp == NULL) // 为空则从头匹配 p->next[i]->fail = root; } q[tail++] = p->next[i]; // 入队 } } } } int query() // 扫描 { int index, len, result; node *p = root; // Tire入口 result = 0; len = strlen(str); for(int i = 0; i < len; ++i) { index = str[i] - 'a'; while(p->next[index] == NULL && p != root) // 跳转失败指针 p = p->fail; p = p->next[index]; if(p == NULL) p = root; node *temp = p; // p不动，temp计算后缀串 while(temp != root && temp->count != -1) { result += temp->count; temp->count = -1; temp = temp->fail; } } return result; } int main() { int num; head= tail = 0; root = new node(); scanf("%d", &num); getchar(); for(int i = 0; i < num; ++i) { scanf("%s",keyword); insert(keyword); } build_ac(); scanf("%s", str); if(query()) printf("YES\n"); else printf("NO\n"); return 0; } /* 假设有N个模式串，平均长度为L；文章长度为M。 建立Trie树：O(N*L) 建立fail指针：O(N*L) 模式匹配：O(M*L) 所以，总时间复杂度为:O( (N+M)*L )。 */ 线段树29.线段树 1）点更新 /* |16/12/07ztx| */ struct node { int left, right; int max, sum; }; node tree[maxn > 1; build(m |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |