Uncle Drew's ACM Template

字符串处理

最长回文子串

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;
}