字符串处理

最长回文子串

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)//精华就在于此:它保证每个合数只会被它的最小质因数筛去,因此每个数只会被标记一次,所以时间复杂度是O(n)
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)//当你在第n+1步的时候,说明前n部已经排好了。
{
for (i = 1; i <= n; i++)
printf("%d ", a[i]);
printf("\n");
return; //返回之前的一步;
}
for (i = 1; i <= n; i++) //按照1,2,3.。。的方式一一尝试。
{
if (book[i] == 0) //判断扑克牌i是不是还在手里
{
a[step] = i; //将i牌放在第step个盒子里。
book[i] = 1; //表示扑克牌不再第step个盒子里
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;
}
Nickname
Email
Website
0 comments