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;//注意这个是减10maxx[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