首页 > 其他 > 详细

模板集合

时间：2020-10-30 22:28:11      阅读：23      评论：0      收藏：0      [点我收藏+]

持续更新中....

已知二叉树前、中序遍历，求后序遍历：


#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
string s1, s2;
inline void dfs(int l1, int r1, int l2, int r2)
{
    int m = s2.find(s1[l1]);
    if (m > l2) dfs(l1 + 1, l1 + m - l2, l2, m - 1);
    if (m < r2) dfs(l1 + m - l2 + 1, r1, m + 1, r2);
    cout << s1[l1];
}
int main()
{
    cin >> s2 >> s1;
    dfs(0, s1.length() - 1, 0, s2.length() - 1);
    return 0;
}

已知二叉树后、中序遍历，求前序遍历：

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
string mid, end, ans;
inline void dfs(int l1, int r1, int l2, int r2)
{
    int k = mid.find(end[r2]);
    cout << end[r2];
    if (k > l1) dfs(l1, k - 1, l2, r2 - r1 + k - 1);
    if (k < r1) dfs(k + 1, r1, l2 + k - l1, r2 - 1);
}
int main()
{
    cin >> mid >> end;
    int len = mid.length();
    dfs(0, len - 1, 0, len - 1);
    return 0;
}

Dijkstra + 堆优化

#include <iostream>
#include <cstdio>
#include <queue>
#define inf 0x7fffffff
using namespace std;
inline void read(int &x)
{
    x = 0;
    int f = 1;
    char ch = getchar();
    while (ch < ‘0‘ || ch > ‘9‘)
    {
        if (ch == ‘-‘)
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= ‘0‘ && ch <= ‘9‘)
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    x *= f;
}
struct edge
{
    int f, t, v;
} e[200001];
int cnt = 0;
int head[100001];
inline void add(int x, int y, int v)
{
    e[++cnt].t = y;
    e[cnt].f = head[x];
    e[cnt].v = v;
    head[x] = cnt;
}
struct node
{
    int dis, sub;
    friend bool operator >(node a, node b)
    {
        return a.dis < b.dis;
    }
    friend bool operator <(node a, node b)
    {
        return a.dis > b.dis;
    }
};
int dis[100001], n, vis[100001], m;
inline void Dijkstra(int s)
{
    priority_queue<node>q;
    for (int i = 1; i <= n; i++)
    {
        dis[i] = inf;
    }
    dis[s] = 0;
    q.push((node) {0, s});
    while (!q.empty())
    {
        node h = q.top();
        q.pop();
        if (vis[h.sub])
        {
            continue;
        }
        vis[h.sub] = 1;
        for (int i = head[h.sub]; i; i = e[i].f)
        {
            int w = e[i].t;
            if (dis[w] > dis[h.sub] + e[i].v)
            {
                dis[w] = dis[h.sub] + e[i].v;
                if (!vis[w]) q.push((node) {dis[w], w});
            }
        }
    }
}
int main()
{
    read(n);
    read(m);
    int s;
    read(s);
    int u, w, v;
    for (int i = 1; i <= m; i++)
    {
        read(u);
        read(w);
        read(v);
        add(u, w, v);
    }
    Dijkstra(s);
    for (int i = 1; i <= n; i++)
    {
        cout << dis[i] << " ";
    }
    return 0;
}

prim最小生成树 +堆优化

#include <iostream>
#include <cstdio>
#include <queue>
#define inf 0x7fffffff
using namespace std;
typedef long long ll;
template<class T>inline void read(T &x)
{
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < ‘0‘ || ch > ‘9‘)
    {
        if (ch == ‘-‘)
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= ‘0‘ && ch <= ‘9‘)
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    x *= f;
}
struct edge
{
    int f, t, v;
} e[1000001];
int head[5001], cnt = 0, dis[5001], n, m;
inline void add(int x, int y, int v)
{
    e[++cnt].f = y;
    e[cnt].t = head[x];
    e[cnt].v = v;
    head[x] = cnt;
}
struct node
{
    int minv, mindis;
    friend bool operator >(node a, node b)
    {
        return a.mindis < b.mindis;
    }
    friend bool operator <(node a, node b)
    {
        return a.mindis > b.mindis;
    }
};
bool vis[5001];
int sum;
inline int prim()
{
    priority_queue<node>q;
    q.push((node) {1, 0});
    for (int i = 2; i <= n; i++)
    {
        dis[i] = inf;
    }
    dis[1] = 0;
    int ans = 0;
    sum = 0;
    while (!q.empty() && sum < n)
    {
        node h = q.top();
        q.pop();
        int x = h.minv;
        if (vis[x])
        {
            continue;
        }
        vis[x] = 1;
        sum++;
        ans += h.mindis;
        for (int i = head[x]; i; i = e[i].t)
        {
            int w = e[i].f;
            if (e[i].v < dis[w])
            {
                dis[w] = e[i].v;
                q.push((node) {w, dis[w]});
            }
        }
    }
    return ans;
}
int main()
{
    read(n);
    read(m);
    int u, v, w;
    for (int i = 1; i <= m; i++)
    {
        read(u);
        read(v);
        read(w);
        add(u, v, w);
        add(v, u, w);
    }
    int ans = prim();
    if (sum == n)
    {
        cout << ans;
    } else {
        cout << "orz";
    }
    return 0;
}

SPFA

#include <iostream>
#include <cstdio>
#include <queue>
#define inf 0x7fffffff
using namespace std;
inline void read(int &x)
{
    x = 0;
    int f = 1;
    char ch = getchar();
    while (ch < ‘0‘ || ch > ‘9‘)
    {
        if (ch == ‘-‘)
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= ‘0‘ && ch <= ‘9‘)
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    x *= f;
}
struct edge {
    int to, from, v;
} e[500001];
int cnt = 0;
int head[500001];
queue<int>q;
inline void add(int x, int y, int v)
{
    e[++cnt].to = y;
    e[cnt].from = head[x];
    e[cnt].v = v;
    head[x] = cnt;
}
int dis[500001];
int vis[500001];
int n, m, s;
inline void spfa(int s)
{
    q.push(s);
    for (int i = 1; i <= n; i++)
    {
        dis[i] = inf;
    }
    dis[s] = 0;
    vis[s] = 1;
    while (!q.empty())
    {
        int h = q.front();
        q.pop();
        vis[h] = 0;
        for (int i = head[h]; i; i = e[i].from)
        {
            int w = e[i].to;
            if (dis[w] > dis[h] + e[i].v)
            {
                dis[w] = dis[h] + e[i].v;
                if (!vis[w])
                {
                    vis[w] = 1;
                    q.push(w);
                }
            }
        }
    }
}
int main()
{
    read(n);
    read(m);
    read(s);
    int u, v, w;
    for (int i = 1; i <= m; i++)
    {
        read(u);
        read(v);
        read(w);
        add(u, v, w);
    }
    spfa(s);
    for (int i = 1; i <= n; i++)
    {
        printf("%d ", dis[i]);
    }
    return 0;
}

区间dp(石子合并)：

#include <iostream>
#include <cstdio>
#define inf 0x7fffffff
using namespace std;
typedef long long ll;
template<class T>inline void read(T &x)
{
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < ‘0‘ || ch > ‘9‘)
    {
        if (ch == ‘-‘)
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= ‘0‘ && ch <= ‘9‘)
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    x *= f;
}
int dp1[201][201], a[201], b[201], dp2[201][201];
int main()
{
    int n;
    read(n);
    for (int i = 1; i <= n * 2; i++)
    {
        if (i <= n)
        {
            read(a[i]);
            a[i + n] = a[i];
        }
        b[i] = b[i - 1] + a[i];
    }
    for (int p = 1; p < n; p++)
    {
        for (int i = 1, j = p + 1; j <= 2 * n; i++, j++)
        {
            dp2[i][j] = inf;
            for (int k = i; k < j; k++)
            {
                dp1[i][j] = max(dp1[i][j], dp1[i][k] + dp1[k + 1][j] + b[j] - b[i - 1]);
                dp2[i][j] = min(dp2[i][j], dp2[i][k] + dp2[k + 1][j] + b[j] - b[i - 1]);
            }
        }
    }
    int ans1 = 0, ans2 = inf;
    for (int i = 1; i <= n; i++)
    {
        ans1 = max(ans1, dp1[i][i + n - 1]);
        ans2 = min(ans2, dp2[i][i + n - 1]);
    }
    cout << ans2 << endl << ans1;
    return 0;
}

快速幂&取余运算

#include<iostream>
using namespace std;
int main() {
    long long b, p, k;
    long long s = 1;
    cin >> b >> p >> k;
    cout << b << ‘^‘ << p << " mod " << k << ‘=‘;
    while (p > 0) {
        if (p % 2 == 1) {
            s = s * b % k;
        }
        b = b * b % k;
        p /= 2;
    }
    cout << s % k;
    return 0;
}

矩阵快速幂

#include <iostream>
#include <cstdio>
#include <cstring>
#define mod 1000000007
using namespace std;
typedef long long ll;
template<class T>inline void read(T &x)
{
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < ‘0‘ || ch > ‘9‘)
    {
        if (ch == ‘-‘)
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= ‘0‘ && ch <= ‘9‘)
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    x *= f;
}
int n;
struct rect
{
    ll a[101][101];
    void clear()
    {
        memset(a, 0, sizeof(a));
    }
    void build()
    {
        for (int i = 1; i <= n; i++)
        {
            a[i][i] = 1;
        }
    }
};
rect operator *(rect a, rect b)
{
    rect x;
    x.clear();
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                x.a[i][j] = (x.a[i][j] + a.a[i][k] * b.a[k][j] % mod) % mod;
            }
        }
    }
    return x;
}
int main()
{
    read(n);
    ll k;
    read(k);
    rect x;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            read(x.a[i][j]);
        }
    }
    rect ans;
    ans.clear();
    ans.build();
    while (k)
    {
        if (k & 1) ans = ans * x;
        x = x * x;
        k >>= 1;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cout << ans.a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

状压dp(集合)，\(O(3 ^ n)\)

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
template<class T>inline void read(T &x)
{
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < ‘0‘ || ch > ‘9‘)
    {
        if (ch == ‘-‘)
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= ‘0‘ && ch <= ‘9‘)
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    x *= f;
}
int dp[1 << 18], s[1 << 18], a[19], lg[1 << 18];
int main()
{
    int n, w;
    read(n);
    read(w);
    for (int i = 0; i < n; i++)
    {
        read(a[i]);
    }
    for (int i = 0; i < n; i++)
    {
        lg[1 << i] = i;
    }
    for (int i = 1; i < (1 << n); i++)
    {
        s[i] = s[i ^ (i & -i)] + a[lg[i & -i]];
    }
    for (int i = 1; i < (1 << n); i++)
    {
        dp[i] = 0x7fffffff;
    }
    for (int i = 1; i < (1 << n); i++)
    {
        for (int j = i; j; j = (j - 1)&i)
        {
            if (s[j] <= w)
            {
                dp[i] = min(dp[i], dp[i ^ j] + 1);
            }
        }
    }
    cout << dp[(1 << n) - 1];
    return 0;
}

状压dp (TSP问题)(收作业)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
template<class T>inline void read(T &x)
{
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < ‘0‘ || ch > ‘9‘)
    {
        if (ch == ‘-‘)
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= ‘0‘ && ch <= ‘9‘)
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    x *= f;
}
int a[17][3];
int dp[17][1 << 16];
int dis[17][17];
int main()
{
    int n, m, q;
    read(n);
    read(m);
    read(q);
    for (int i = 1; i <= q; i++)
    {
        read(a[i][0]);
        read(a[i][1]);
    }
    read(a[0][0]);
    read(a[0][1]);
    for (int i = 0; i <= q; i++)
    {
        dis[i][i] = 0;
    }
    for (int i = 0; i <= q; i++)
    {
        for (int j = i + 1; j <= q; j++)
        {
            dis[i][j] = abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1]);
            dis[j][i] = dis[i][j];
        }
    }
    memset(dp, 127, sizeof(dp));
    for (int i = 1; i <= q; i++)
    {
        dp[i][1 << (i - 1)] = dis[0][i];
    }
    for (int k = 0; k < (1 << q); k++)
    {
        for (int i = 1; i <= q; i++)
        {
            if (!(k & (1 << (i - 1)))) continue;
            for (int j = 1; j <= q; j++)
            {
                if (i == j || !(k & (1 << (j - 1)))) continue;
                dp[i][k] = min(dp[i][k], dp[j][k ^ (1 << (i - 1))] + dis[i][j]);
            }
        }
    }
    int ans = 0x7fffffff;
    for (int i = 1; i <= q; i++)
    {
        ans = min(ans, dp[i][(1 << q) - 1] + dis[0][i]);
    }
    if(q == 0)
    {
        cout << 0;
    }else{
        cout << ans;
    }
    return 0;
}

状态压缩（放置问题）（炮兵布阵）

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
template<class T>inline void read(T &x)
{
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < ‘0‘ || ch > ‘9‘)
    {
        if (ch == ‘-‘)
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= ‘0‘ && ch <= ‘9‘)
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    x *= f;
}
int count(int s)
{
    int ans = 0;
    while (s)
    {
        s -= (s & -s);
        ans++;
    }
    return ans;
}
int f[105][77][77], h[105], a[77], cnt[77], n, m;
char str[105][15];
int c = 0;
void work()
{
    for (int i = 0; i < (1 << m); i++)
    {
        if (!(i & (i >> 2)) && !(i & (i << 2)) && !(i & (i >> 1)) && !(i & (i << 1)))
        {
            a[++c] = i;
            cnt[c] = count(i);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (str[i][j] == ‘H‘)
            {
                h[i] |= (1 << (j - 1));
            }
        }
    }
}
void dp()
{
    for (int i = 1; i <= c; i++)
    {
        for (int j = 1; j <= c; j++)
        {
            if (!(a[i]&h[1]) && !(a[j]&h[2]) && !(a[i]&a[j]))
            {
                f[2][i][j] = cnt[i] + cnt[j];
            }
        }
    }
    for (register int i = 3; i <= n; i++)
    {
        for (register int l = 1; l <= c; l++)
        {
            if (!(a[l]&h[i]))
            {
                for (register int j = 1; j <= c; j++)
                {
                    for (register int k = 1; k <= c; k++)
                    {
                        if (!(a[l]&a[j]) && !(a[l]&a[k]))
                        {
                            f[i][k][l] = max(f[i][k][l], f[i - 1][j][k] + cnt[l]);
                        }
                    }
                }
            }
        }
    }
}
int main()
{
    read(n);
    read(m);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> str[i][j];
        }
    }
    work();
    dp();
    int ans = 0;
    for (int i = 1; i <= c; i++)
    {
        for (int j = 1; j <= c; j++)
        {
            if (!(a[i]&a[j]))
            {
                ans = max(ans, f[n][i][j]);
            }
        }
    }
    cout << ans;
    return 0;
}

有理数取膜：

\[b^{p-1}\equiv 1 \pmod{p} \]

\[a\times b^{-1}\equiv a\times b^{p-1}\times b^{-1}\equiv a\times b^{p-2}\pmod{p} \]

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define mod 19260817
using namespace std;
typedef long long ll;
typedef double db;
template<class T>inline void read(T &x)
{
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < ‘0‘ || ch > ‘9‘)
    {
        if (ch == ‘-‘)
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= ‘0‘ && ch <= ‘9‘)
    {
        x = x * 10 % mod + (ch - 48) % mod;
        ch = getchar();
    }
    x = x * f % mod;
}
ll qpow(ll a, ll b)
{
    ll ans = 1;
    ll p = mod - 2;
    while (p)
    {
        if (p & 1) ans = ans * b % mod;
        b = b * b % mod;
        p >>= 1;
    }
    return ans * a % mod;
}
int main()
{
    ll a, b;
    read(a);
    read(b);
    if (b == 0)
    {
        cout << "Angry!";
        return 0;
    }
    cout << qpow(a, b) << endl;
    return 0;
}

模板集合

原文：https://www.cnblogs.com/entropyw-OI/p/13904078.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！