四处搜刮整理模板 小灰灰 2022-06-16 04:08 135阅读 0赞 1.筛法 int prime[maxn]; bool is_prime[maxn]; int sieve(int n){ int p = 0; for(int i = 0; i <= n; ++i) is_prime[i] = true; is_prime[0] = is_prime[1] = false; for (int i = 2; i <= n; ++i){ // 注意数组大小是n if(is_prime[i]){ prime[p++] = i; for(int j = i + i; j <= n; j += i) // 轻剪枝,j必定是i的倍数 is_prime[j] = false; } } return p; // 返回素数个数 } 2.快速幂算法 typedef long long LL; // 视数据大小的情况而定 LL powerMod(LL x, LL n, LL m) { LL res = 1; while (n > 0){ if (n & 1) // 判断是否为奇数,若是则true res = (res * x) % m; x = (x * x) % m; n >>= 1; // 相当于n /= 2; } return res; } 3.大数阶乘 #include <iostream> #include <cstdio> 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 <= n; ++i) { len = mult(num, len, i); } for(int i = len - 1; i >= 0; --i) printf("%d",num[i]); // 从最高位依次输出,数据比较多采用printf输出 printf("\n"); return 0; } 4.大数加法 #include<stdio.h> #include<string.h> char s1[1001],s2[1001]; int a[1001],b[1001],c[1001]; int main() { int i,k,n,m; scanf("%s%s",s1,s2); memset(c,0,sizeof(c)); n=strlen(s1); m=strlen(s2); for(i=0; i<n; i++) a[i]=s1[n-i-1]-'0'; for(i=0; i<m; i++) b[i]=s2[m-i-1]-'0'; if(n>m) k=n; else k=m; for(i=0; i<=k; i++) { c[i]+=a[i]+b[i]; if(c[i]>9) { c[i+1]++; c[i]%=10; } } i=k; while(c[i]==0) i--; if(i<0) printf("0"); else { for(;i>=0;i--) printf("%d",c[i]); } printf("\n"); return 0; } 5.全排列 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]); } } } 6.二分搜索 // 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] <= 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的个数 */ 7.二分法求最长递增子序列 #include<bits/stdc++.h> using namespace std; int n; int ch[100005]; int dp[100005]; int Binary(int x,int len1) { int left=1; int right=len1; while(left<=right) { int mid1=left+(right-left)/2; if(dp[mid1]==x) return mid1; else if(dp[mid1]<x) { left=mid1+1; } else right=mid1-1; } return left; } int main() { while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) { cin>>ch[i]; } memset(dp,0,sizeof(dp)); dp[1]=ch[1]; int len1=1; for(int i=2;i<=n;i++) { if(ch[i]>dp[len1]) { dp[++len1]=ch[i]; } else { int t=Binary(ch[i],len1); dp[t]=ch[i]; } } cout<<len1<<endl; } return 0; } 8,。最长公共子序列 void getnext(char str[maxn], int nextt[maxn]) { int j = 0, k = -1; nextt[0] = -1; while (j < m) { if (k == -1 || str[j] == str[k]) { j++; k++; nextt[j] = k; } else k = nextt[k]; } } void kmp(int a[maxn], int b[maxn]) { int nextt[maxm]; int i = 0, j = 0; getnext(b, nextt); while (i < n) { if (j == -1 || a[i] == b[j]) { // 母串不动,子串移动 j++; i++; } else { // i不需要回溯了 // i = i - j + 1; j = nextt[j]; } if (j == m) { printf("%d\n", i - m + 1); // 母串的位置减去子串的长度+1 return; } } printf("-1\n"); } 9.并查集 int father[maxn]; // 储存i的father父节点 void makeSet() { for (int i = 0; i < maxn; i++) father[i] = i; } int findRoot(int x) { // 迭代找根节点 int root = x; // 根节点 while (root != father[root]) { // 寻找根节点 root = father[root]; } while (x != root) { int tmp = father[x]; father[x] = root; // 根节点赋值 x = tmp; } return root; } void Union(int x, int y) { // 将x所在的集合和y所在的集合整合起来形成一个集合。 int a, b; a = findRoot(x); b = findRoot(y); father[a] = b; // y连在x的根节点上 或father[b] = a为x连在y的根节点上; } /* 在findRoot(x)中: 路径压缩 迭代 最优版 关键在于在路径上的每个节点都可以直接连接到根上 */ 10.克鲁斯卡尔算法 /* 第一步:点、边、加入vector,把所有边按从小到大排序 第二步:并查集部分 + 下面的code */ void Kruskal() { ans = 0; for (int i = 0; i<len; i++) { if (Find(edge[i].a) != Find(edge[i].b)) { Union(edge[i].a, edge[i].b); ans += edge[i].len; } } } 11.普利姆算法 struct node { int v, len; node(int v = 0, int len = 0) :v(v), len(len) {} bool operator < (const node &a)const { // 加入队列的元素自动按距离从小到大排序 return len> a.len; } }; vector<node> G[maxn]; int vis[maxn]; int dis[maxn]; void init() { for (int i = 0; i<maxn; i++) { G[i].clear(); dis[i] = INF; vis[i] = false; } } int Prim(int s) { priority_queue<node>Q; // 定义优先队列 int ans = 0; Q.push(node(s,0)); // 起点加入队列 while (!Q.empty()) { node now = Q.top(); Q.pop(); // 取出距离最小的点 int v = now.v; if (vis[v]) continue; // 同一个节点,可能会推入2次或2次以上队列,这样第一个被标记后,剩下的需要直接跳过。 vis[v] = true; // 标记一下 ans += now.len; for (int i = 0; i<G[v].size(); i++) { // 开始更新 int v2 = G[v][i].v; int len = G[v][i].len; if (!vis[v2] && dis[v2] > len) { dis[v2] = len; Q.push(node(v2, dis[v2])); // 更新的点加入队列并排序 } } } return ans; } 12.迪杰斯特拉算法 struct node { int v, len; node(int v = 0, int len = 0) :v(v), len(len) {} bool operator < (const node &a)const { // 距离从小到大排序 return len > a.len; } }; vector<node>G[maxn]; bool vis[maxn]; int dis[maxn]; void init() { for (int i = 0; i<maxn; i++) { G[i].clear(); vis[i] = false; dis[i] = INF; } } int dijkstra(int s, int e) { priority_queue<node>Q; Q.push(node(s, 0)); // 加入队列并排序 dis[s] = 0; while (!Q.empty()) { node now = Q.top(); // 取出当前最小的 Q.pop(); int v = now.v; if (vis[v]) continue; // 如果标记过了, 直接continue vis[v] = true; for (int i = 0; i<G[v].size(); i++) { // 更新 int v2 = G[v][i].v; int len = G[v][i].len; if (!vis[v2] && dis[v2] > dis[v] + len) { dis[v2] = dis[v] + len; Q.push(node(v2, dis[v2])); } } } return dis[e]; } 13.弗洛伊德算法 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.背包 // 01背包: void bag01(int cost,int weight) { for(i = v; i >= cost; --i) dp[i] = max(dp[i], dp[i-cost]+weight); } // 完全背包: void complete(int cost, int weight) { for(i = cost ; i <= v; ++i) dp[i] = max(dp[i], dp[i - cost] + weight); } // 多重背包: void multiply(int cost, int weight, int amount) { if(cost * amount >= v) complete(cost, weight); else{ k = 1; while (k < amount){ bag01(k * cost, k * weight); amount -= k; k += k; } bag01(cost * amount, weight * amount); } } 15.博弈论 BASH #define _MAX 10000 int a[_MAX]; int b[_MAX]; int bash(int N, int K) { if (N % (K + 1) == 0) { return 2; } return 1; } int main() { int T; scanf("%d", &T); for (int i = 0; i < T; i++) { scanf("%d%d", a + i, b + i); } for (int i = 0; i < T; i++) { if (bash(a[i], b[i]) == 1) { printf("A\n"); } else { printf("B\n"); } } return 0; } NIM int main(int argc, const char * argv[]) { int N, stone, tag = 0; scanf("%d", &N); while (N--) { scanf("%d", &stone); tag ^= stone; } //tag为0则为后手赢,否则为先手赢 printf("%c\n", tag == 0 ? 'B' : 'A'); return 0; } SG函数打表 const int MAX_DIG = 64; // SG打表 // f[]:可以取走的石子个数 // sg[]:0~n的SG函数值 // hash[]:mex{} int f[MAX_DIG]; int sg[MAX_DIG]; int hash[MAX_DIG]; void getSG(int n) { memset(sg, 0, sizeof(sg)); for (int i = 1; i <= n; i++) { memset(hash, 0, sizeof(hash)); for (int j = 1; f[j] <= i; j++) { hash[sg[i - f[j]]] = 1; } for (int j = 0; j <= n; j++) // 求mes{}中未出现的最小的非负整数 { if (hash[j] == 0) { sg[i] = j; break; } } } } SG DFS const int MAX_DIG = 64; // DFS // 注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍 // n是集合s的大小 S[i]是定义的特殊取法规则的数组 int s[MAX_DIG]; int sg[MAX_DIG * 100]; int n; int SG_dfs(int x) { if (sg[x] != -1) { return sg[x]; } bool vis[MAX_DIG]; memset(vis, 0, sizeof(vis)); for (int i = 0; i < n; i++) { if (x >= s[i]) { SG_dfs(x - s[i]); vis[sg[x - s[i]]] = 1; } } int e; for (int i = 0; ; i++) { if (!vis[i]) { e = i; break; } } return sg[x] = e; } Wythoff int main() { int t, a, b, m, k; scanf("%d", &t); while (t--) { scanf("%d%d", &a, &b); if (a > b) { a ^= b; b ^= a; a ^= b; } m = b - a; k = (int)(m * (1 + sqrt(5)) / 2.0); //m = ? * a //k = m / ? //?:黄金分割数 //如果a == k,则为后手赢,否则先手赢(奇异局) printf("%s\n", a == k ? "B" : "A"); } return 0; } 持续更新中。。。。。。
还没有评论,来说两句吧...