字符串处理
最长回文子串
Manacher(马拉车算法)
| #include<bits/stdc++.h> |
| using namespace std; |
| const int MAXN = 1e5; |
| char str[MAXN]; |
| char tmp[2*MAXN]; |
| int len[2*MAXN]; |
| int Manacher(char str[]){ |
| tmp[0] = '$'; |
| tmp[1] = '#'; |
| int str_len = strlen(str); |
| for(int i = 1;i <= str_len;i++){ |
| tmp[2*i] = str[i-1]; |
| tmp[2*i+1] = '#'; |
| } |
| tmp[2*str_len+2] = '\0'; |
| int mx = 0; |
| int maxlen = -1; |
| int mid; |
| for(int i = 1; tmp[i]; i++){ |
| if(i < mx) len[i] = min(len[2*mid-i],mx-i); |
| else len[i] = 1; |
| while(tmp[i-len[i]] == tmp[i+len[i]]) len[i]++; |
| if(len[i]+i > mx){ |
| mx = len[i]+i; |
| mid = i; |
| } |
| maxlen = max(maxlen,len[i]-1); |
| } |
| return maxlen; |
| } |
| int main(){ |
| int n; |
| cin>>n; |
| scanf("%s",str); |
| cout<<Manacher(str); |
| return 0; |
| } |
数学
素数
Eratosthenes(埃拉托色尼筛法)
| #include<bits/stdc++.h> |
| using namespace std; |
| int a[1000000]; |
| int main() |
| { |
| int sum=0,n; |
| int i,j; |
| while(~scanf("%d",&n)) |
| { |
| sum=0; |
| for(i=2;i<=n;i++) |
| a[i]=1; |
| for(i=2;i<=sqrt(n);i++){ |
| for(j=2*i;j<=n;j+=i){ |
| a[j]=0; |
| } |
| } |
| for(i=2;i<=n;i++){ |
| if(a[i]) |
| cout<<i<<endl;; |
| } |
| } |
| return 0; |
| } |
欧拉筛
| #include<stdio.h> |
| #include<stdbool.h> |
| #define N 100 |
| int main(void) |
| { |
| bool number[N+1]; |
| int prime[N+1]; |
| int i,j,count=0; |
| memset(number,true,sizeof(number)); |
| for(i=2;i<=N;i++) |
| { |
| if(number[i]) |
| prime[count++]=i; |
| for(j=0;j<count&&prime[j]*i<=N;j++) |
| { |
| number[prime[j]*i]=false; |
| if(i%prime[j]==0) |
| break; |
| } |
| } |
| for(i=2;i<N+1;i++) |
| if(number[i]==true) |
| printf("%d ",i); |
| return 0; |
| } |
快速幂
| ll poww(ll x, ll y, ll z) |
| { |
| ll ans = 1, base = x; while (y != 0) |
| { |
| if (y & 1 != 0) |
| ans = ans * base % z; |
| base = (base % z) * (base % z) % z; y >>= 1; |
| } |
| return ans; |
| } |
斐波那契(大数,根据第n项的值推出n)
| #include <bits/stdc++.h> |
| using namespace std; |
| const int maxx = 1e9 + 7; |
| typedef long long ll; |
| ll f[200050]; char s[100000]; |
| int main() |
| { |
| ios::sync_with_stdio(false); |
| map<ll, ll> ma; |
| f[0] = 0; f[1] = 1; |
| for (ll i = 2; i < 200001; i++) |
| { |
| f[i] = (f[i - 1] + f[i - 2]) % maxx; |
| ma[f[i]] = i; |
| } |
| ll n; |
| cin >> n; while (n--) |
| { |
| cin >> s; ll ans, num, l; |
| l = strlen(s); |
| num = 0; for (ll i = 0; i < l; i++) |
| { |
| num = num * 10 + s[i] - '0'; num %= maxx; |
| } |
| cout << ma[num] << endl; |
| } |
| return 0; |
| } |
大数(c++)
大数相加(正整数)
| #include <iostream> |
| #include <string> |
| #include <algorithm> |
| using namespace std; |
| int main() |
| { |
| int n; |
| cin >> n; |
| int m = 0; |
| int l = 0; |
| for (int i = 1; i <= n; i++) |
| { |
| string s1, s2, s(10000, '0'); |
| cin >> s1 >> s2; |
| m++; |
| cout << (l++ ? "\n" : ""); |
| reverse(s1.begin(), s1.end()); |
| reverse(s2.begin(), s2.end()); |
| for (int j = 0; j < s1.length(); j++) |
| s[j] = s1[j]; |
| int temp = 0; |
| for (int k = 0; k < s2.length(); k++) |
| { |
| temp += s[k] - 48 + s2[k] - 48; |
| s[k] = temp % 10 + '0'; |
| temp /= 10; |
| } |
| s[s2.length()] = s[s2.length()] - 48 + temp + 48; |
| reverse(s.begin(), s.end()); |
| reverse(s1.begin(), s1.end()); |
| reverse(s2.begin(), s2.end()); |
| cout << "Case" << m << ":" << endl; |
| cout << s1 << "+" << s2 << "=" << s.substr(s.find_first_not_of('0')) << endl; |
| } |
| return 0; |
| } |
大数相减(正整数)
| #include <iostream> |
| #include <string> |
| #include <cstring> |
| #include <vector> |
| #include <algorithm> |
| using namespace std; |
| int strComp(string &s1, string &s2) |
| { |
| int len1 = s1.length(); |
| int len2 = s2.length(); |
| if (len1 > len2) |
| return 0; |
| else if (len1 < len2) |
| return 1; |
| else |
| { |
| if (s1 >= s2) |
| return 0; |
| else |
| return 1; |
| } |
| } |
| int main() |
| { |
| string s1, s2; |
| while (cin >> s1 >> s2) |
| { |
| string s(10000, '0'); |
| bool fgEx = true; |
| if (strComp(s1, s2) == 1) |
| { |
| string temp; |
| temp = s1; |
| s1 = s2; |
| s2 = temp; |
| fgEx = false; |
| } |
| if (s1 == s2) |
| { |
| cout << s1 << " - " << s2 << " = " << "0" << endl; |
| continue; |
| } |
| reverse(s1.begin(), s1.end()); |
| reverse(s2.begin(), s2.end()); |
| for (int i = 0; i < s1.length(); i++) |
| s[i] = s1[i]; |
| for (int i = 0; i < s2.length(); i++) |
| { |
| if (s[i] >= s2[i]) |
| s[i] = s[i] - '0' - (s2[i] - '0') + '0'; |
| else |
| { |
| s[i + 1] = s[i + 1] - '0' - 1 + '0'; |
| s[i] = s[i] - '0' + 10 - (s2[i] - '0') + '0'; |
| } |
| } |
| if (fgEx == false) |
| { |
| reverse(s2.begin(), s2.end()); |
| cout << s2 << " - "; |
| reverse(s1.begin(), s1.end()); |
| cout << s1 << " = "; |
| reverse(s.begin(), s.end()); |
| cout << "-" << s.substr(s.find_first_not_of('0')) << endl; |
| } |
| else |
| { |
| reverse(s1.begin(), s1.end()); |
| cout << s1 << " - "; |
| reverse(s2.begin(), s2.end()); |
| cout << s2 << " = "; |
| reverse(s.begin(), s.end()); |
| cout << s.substr(s.find_first_not_of('0')) << endl; |
| } |
| } |
| return 0; |
| } |
大数相乘(正整数)
| #include <iostream> |
| #include <string> |
| #include <cstring> |
| #include <vector> |
| #include <algorithm> |
| using namespace std; |
| int main() |
| { |
| string s1, s2; |
| while (cin >> s1 >> s2) |
| { |
| string s(1000, '0'); |
| reverse(s1.begin(), s1.end()); |
| reverse(s2.begin(), s2.end()); |
| for (int i = 0; i < s1.length(); i++) |
| for (int j = 0; j < s2.length(); j++) |
| { |
| int temp = (s1[i] - '0') * (s2[j] - '0'); |
| s[i + j + 1] = s[i + j + 1] - '0' + (s[i + j] - '0' + temp) / 10 + '0'; |
| s[i + j] = (s[i + j] - '0' + temp) % 10 + '0'; |
| } |
| reverse(s.begin(), s.end()); |
| if (s.find_first_not_of('0') == string::npos) |
| cout << "0" << endl; |
| else |
| cout << s.substr(s.find_first_not_of('0')) << endl; |
| } |
| return 0; |
| } |
大数相除(正整数)
| #include <iostream> |
| #include <string> |
| #include <cstring> |
| #include <vector> |
| #include <algorithm> |
| using namespace std; |
| int strComp(string &s1, string &s2) |
| { |
| int len1 = s1.length(); |
| int len2 = s2.length(); |
| if (len1 > len2) |
| return 0; |
| else if (len1 < len2) |
| return 1; |
| else |
| { |
| if (s1 >= s2) |
| return 0; |
| else |
| return 1; |
| } |
| } |
| string Sub(string s1, string s2) |
| { |
| if (strComp(s1, s2) == 1) |
| return "-1"; |
| reverse(s1.begin(), s1.end()); |
| reverse(s2.begin(), s2.end()); |
| string s(1000, '0'); |
| for (int i = 0; i < s1.length(); i++) |
| s[i] = s1[i]; |
| for (int i = 0; i < s2.length(); i++) |
| { |
| if (s[i] >= s2[i]) |
| s[i] = s[i] - '0' - (s2[i] - '0') + '0'; |
| else |
| { |
| s[i + 1] = s[i + 1] - '0' - 1 + '0'; |
| s[i] = s[i] - '0' + 10 - (s2[i] - '0') + '0'; |
| } |
| } |
| reverse(s.begin(), s.end()); |
| if (s.find_first_not_of('0') == string::npos) |
| return "0"; |
| else |
| return s.substr(s.find_first_not_of('0')); |
| } |
| int main() |
| { |
| string s1, s2; |
| while (cin >> s1 >> s2) |
| { |
| string s(1000, '0'); |
| if (strComp(s1, s2) == 1) |
| { |
| cout << "0" << endl; |
| continue; |
| } |
| int len1 = s1.length(); |
| int len2 = s2.length(); |
| int dis = len1 - len2; |
| for (int i = 0; i < dis; i++) |
| s2 += '0'; |
| string ans(1000, '0'); |
| while (dis >= 0) |
| { |
| int sum = 0; |
| string temp; |
| while ((temp = Sub(s1, s2)) != "-1") |
| { |
| sum++; |
| s1 = temp; |
| } |
| ans[ans.length() - dis - 1] = sum + '0'; |
| dis--; |
| s2 = s2.substr(0, len2 + dis); |
| } |
| if (ans.find_first_not_of('0') == string::npos) |
| cout << "0" << endl; |
| else |
| { |
| string res = ans.substr(ans.find_first_not_of('0')); |
| cout << res << endl; |
| } |
| } |
| return 0; |
| } |
大数取模
| typedef long long ll; |
| cin >> s; |
| ll ans, num; |
| ll l = strlen(s); |
| num = 0; |
| for (ll i = 0; i < l; i++) |
| { |
| num = num * 10 + s[i] - '0'; |
| num %= maxx; |
| } |
图论
最小生成树
kruskal
| #include <bits/stdc++.h> |
| using namespace std; |
| struct city |
| { |
| int a; |
| int b; |
| int p; |
| } c[105]; |
| int p[105]; |
| int find(int x) |
| { |
| return p[x] != x ? p[x] = find(p[x]) : x; |
| } |
| void join(int x, int y) |
| { |
| x = find(x); |
| y = find(y); |
| if (x != y) |
| p[y] = x; |
| } |
| bool cmp(city x, city y) |
| { |
| return x.p < y.p; |
| } |
| int main() |
| { |
| int n, m; |
| while (cin >> n >> m) |
| { |
| int sum = 0; |
| if (n == 0) |
| break; |
| for (int i = 1; i <= m; i++) |
| p[i] = i; |
| for (int i = 0; i < n; i++) |
| cin >> c[i].a >> c[i].b >> c[i].p; |
| sort(c, c + n, cmp); |
| for (int i = 0; i < n; i++) |
| { |
| if (find(c[i].a) != find(c[i].b)) |
| { |
| join(c[i].a, c[i].b); |
| sum += c[i].p; |
| } |
| } |
| int flag = 0; |
| for (int i = 1; i <= m; i++) |
| { |
| if (p[i] == i) |
| flag++; |
| } |
| if (flag == 1) |
| cout << sum << endl; |
| else |
| puts("?"); |
| } |
| return 0; |
| } |
最短路——Dijkstra
| #include <bits/stdc++.h> |
| using namespace std; |
| const int maxn = 1e4 + 5; |
| const int INF = 0x3f3f3f3f; |
| int a[maxn][maxn]; |
| int dis[maxn]; |
| bool vis[maxn]; |
| int n, m, u, v, w; |
| struct node |
| { |
| int d, id; |
| }; |
| bool operator <(const node &a, const node &b) |
| { |
| return a.d > b.d; |
| } |
| priority_queue<node> que; |
| void Dijkstra() |
| { |
| for (int i = 1; i <= n; i++) |
| dis[i] = INF; |
| dis[1] = 0; |
| que.push(node{ dis[1], 1 }); |
| while (!que.empty()) |
| { |
| node p = que.top(); |
| que.pop(); |
| int mid = p.id; |
| |
| if (vis[mid] == 1) |
| continue; |
| vis[mid] = 1; |
| for (int i = 1; i <= n; i++) |
| { |
| if (dis[i] > dis[mid] + a[mid][i]) |
| { |
| dis[i] = dis[mid] + a[mid][i]; |
| que.push(node{ dis[i], i }); |
| } |
| } |
| } |
| cout << dis[n] << endl; |
| } |
| int main() |
| { |
| while (scanf("%d %d", &n, &m) && (n && m)) |
| { |
| memset(vis, 0, sizeof(vis)); |
| for (int i = 1; i <= n; i++) |
| for (int j = 1; j <= n; j++) |
| a[i][j] = INF; |
| for (int i = 1; i <= m; i++) |
| { |
| cin >> u >> v >> w; |
| a[u][v] = w; |
| a[v][u] = w; |
| } |
| Dijkstra(); |
| } |
| } |
搜索
DFS
| #include <stdio.h> |
| #include <stdlib.h> |
| int book[10], a[10], n; |
| |
| void dfs(int step) |
| { |
| int i; |
| if (step == n + 1) |
| { |
| for (i = 1; i <= n; i++) |
| printf("%d ", a[i]); |
| printf("\n"); |
| |
| return; |
| } |
| |
| for (i = 1; i <= n; i++) |
| { |
| if (book[i] == 0) |
| { |
| a[step] = i; |
| book[i] = 1; |
| dfs(step + 1); |
| book[i] = 0; |
| } |
| } |
| return; |
| } |
| int main() |
| { |
| while (~scanf("%d", &n)) |
| dfs(1); |
| |
| return 0; |
| } |
BFS
| #include<iostream> |
| #include<algorithm> |
| #include<queue> |
| #include<cstring> |
| using namespace std; |
| #define pill pair<int,int> |
| int sx,sy,ex,ey,n; |
| char ma[1050][1050]; |
| int vis[1050][1050]; |
| int step[1050][1050]; |
| int d[4][2]={-1,0,0,1,1,0,0,-1}; |
| queue<pair<int,int> >que; |
| void bfs(int x,int y) |
| { |
| vis[x][y]=1; |
| que.push(pill(x,y)); |
| while(!que.empty()) |
| { |
| x=que.front().first; |
| y=que.front().second; |
| que.pop(); |
| for(int i=0;i<4;i++) |
| { |
| int xx=x+d[i][0]; |
| int yy=y+d[i][1]; |
| if(ma[xx][yy]=='#'||xx<0||xx>=n||yy<0||yy>=n||vis[xx][yy]==1) continue; |
| que.push(pill(xx,yy)); |
| vis[xx][yy]=1; |
| step[xx][yy]=step[x][y]+1; |
| } |
| } |
| } |
| int main() |
| { |
| while(cin>>n) |
| { |
| memset(vis,0,sizeof(vis)); |
| for(int i=0;i<n;i++) |
| { |
| scanf("%s",ma[i]); |
| } |
| } |
| } |
动态规划
编辑距离
| #include <iostream> |
| #include <cstdio> |
| #include <cstring> |
| #include <algorithm> |
| using namespace std; |
| const int maxn = 1050; |
| int f[maxn][maxn]; |
| string a, b; |
| bool same(char x, char y) |
| { |
| if (x == y) |
| return 0; |
| return 1; |
| } |
| int main() |
| { |
| while (cin >> a >> b) |
| { |
| memset(f, 0, sizeof(f)); for (int i = 0; i <= a.size(); i++) |
| { |
| for (int j = 0; j <= b.size(); j++) |
| { |
| if (i == 0) |
| f[i][j] = j; |
| else if (j == 0) |
| f[i][j] = i; |
| else |
| f[i][j] = min(f[i - 1][j - 1] + same(a[i - 1], b[j - 1]), min(f[i - 1][j] + 1, f[i][j - 1] + 1)); |
| } |
| } |
| cout << f[a.size()][b.size()] << endl; |
| } |
| return 0; |
| } |
最长公共子序列
| #include <algorithm> |
| #include <cstdio> |
| #include <cstring> |
| #include <stack> |
| using namespace std; |
| const int maxn = 1050; |
| int dp[maxn][maxn]; |
| char a[maxn], b[maxn]; |
| int main() |
| { |
| scanf("%s %s", a + 1, b + 1); int n = strlen(a + 1), m = strlen(b + 1); for (int i = 1; i <= n; i++) |
| for (int j = 1; j <= m; j++) |
| { |
| if (a[i] == b[j]) |
| dp[i][j] = dp[i - 1][j - 1] + 1; |
| else |
| dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); |
| } |
| stack<char> ans; while (n >= 1 && m >= 1) |
| { |
| if (dp[n][m] == 0) |
| break; |
| if (dp[n][m] - dp[n - 1][m - 1] == 1 && dp[n - 1][m - 1] == dp[n - 1][m] && dp[n - 1][m - 1] == dp[n][m - 1]) |
| { |
| ans.push(a[n]); n--; m--; |
| } |
| else if (dp[n][m] == dp[n - 1][m] && n > 1) |
| n--; |
| else if (dp[n][m] == dp[n][m - 1] && m > 1) |
| m--; |
| } |
| while (!ans.empty()) |
| { |
| printf("%c", ans.top()); ans.pop(); |
| } |
| puts(""); return 0; |
| } |
最长递增子序列
| #include <iostream> |
| #include <algorithm> |
| #include <cstdio> |
| using namespace std; |
| const int maxn = 50050; |
| const int INF = 0x3f3f3f3f; |
| int dp[maxn], a[maxn]; |
| int main() |
| { |
| int n; cin >> n; for (int i = 0; i < n; i++) |
| { |
| cin >> a[i]; |
| } |
| fill(dp, dp + n, INF); for (int i = 0; i < n; i++) |
| { |
| *lower_bound(dp, dp + n, a[i]) = a[i]; |
| } |
| cout << lower_bound(dp, dp + n, INF) - dp << endl; |
| } |
最大子段和
| #include <iostream> |
| using namespace std; |
| int main() |
| { |
| int n, now; |
| long long maxsum, sum; |
| |
| while (cin >> n) |
| { |
| maxsum = sum = 0; |
| for (int i = 1; i <= n; i++) |
| { |
| cin >> now; |
| sum = max(sum, 0LL) + now; |
| maxsum = max(sum, maxsum); |
| } |
| cout << maxsum << endl; |
| } |
| return 0; |
| } |
换零钱
| #include <bits/stdc++.h> |
| using namespace std; |
| typedef long long ll; |
| ll solve(ll x) |
| { |
| int coins[13] = { 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000 }; |
| ll dp[100005] = { 0 }; |
| dp[0] = 1; |
| for (int i = 0; i < 13; i++) |
| { |
| for (int j = coins[i]; j <= x; j++) |
| { |
| dp[j] = (dp[j] + dp[j - coins[i]]) % 1000000007; |
| } |
| } |
| return dp[x]; |
| } |
| int main() |
| { |
| ll t, a; |
| cin >> t; |
| while (t--) |
| { |
| cin >> a; |
| cout << solve(a) << endl; |
| } |
| } |
计算几何
求多边形面积
| #include <iostream> |
| #include <cstdio> |
| #include <cstdlib> |
| using namespace std; |
| int main() |
| { |
| int ncase; |
| cin >> ncase; |
| int x, y, x0, y0, sum = 0; |
| cin >> x >> y; |
| x0 = x; |
| y0 = y; |
| while (--ncase) |
| { |
| int xtmp, ytmp; |
| cin >> xtmp >> ytmp; |
| sum += (x * ytmp - y * xtmp); |
| x = xtmp; |
| y = ytmp; |
| } |
| sum += (x * y0 - y * x0); |
| printf("%d\n", int(abs(sum) / 2)); |
| return 0; |
| } |