呐呐呐~第一份随笔

本文主要是介绍呐呐呐~第一份随笔，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Become an ACMer

算法被发明出来，是为了解决问题；而评价一个算法的好坏，在于它能否迅速、简洁、优雅地解决问题。

“保持一颗热爱的心。你也能够成功的吧。”

这是学习算法的初衷。相信自己吧。

PART 1 预备知识

<1>

我们常常需要（1）快读（2）重定向（3）打表（4）预处理 等等，这些都是对数据读写的处理。
（1）快读常用于读入数据量较多的 int, 它的原理由 getchar() 实现；

inline int read()
{
    int s = 1, v = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            s = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        v = (v << 3) + (v << 1) + (c ^ 48);
        c = getchar();
    }
    return s * v;
}

（2）重定向常用于文件读写，它通过 freopen() 实现；

freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);

（3）打表用于解决时间复杂度高且数据范围小的问题，将所有结果输出并记录在数组里；

（4）预处理是将一些可能会用到的数据提前处理并记录下来，便于以后调用，如埃氏筛、欧拉筛。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int n, cnt, a[N], p[N];
void Era()
{
    for (int i = 2; i <= N; ++i)
    {
        if (!a[i])
            p[cnt++] = i;
        for (int j = i; j <= N; j += i)
            a[j] = 1;
    }
}
int main()
{
    cin >> n;
    Era();
    cout << p[n];
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e8;
int n, cnt, a[N], p[N];
void Euler()
{
    for (int i = 2; i <= N; ++i)
    {
        if (!a[i])
            p[cnt++] = i;
        for (int j = 0; j < cnt; j++)
        {
            if (i * p[j] > N)
                break;
            a[i * p[j]] = true;
            if (i % p[j] == 0)
                break;
        }
    }
}
int main()
{
    cin >> n;
    Euler();
    cout << p[n];
}

<2>

一些经典问题的解法是值得背诵的。

（1）八皇后（深度优先搜索，状态压缩)

#include <bits/stdc++.h>
using namespace std;
int N, cnt, b1[100], b2[100], b3[100];
void dfs(int n)
{
    if (n > N)
    {
        cnt++;
        return;
    }
    for (int i = 1; i <= N; i++)
        if (b1[i] == 0 && b2[N - n + i] == 0 && b3[n + i] == 0)
        {
            b1[i] = 1, b2[N - n + i] = 1, b3[n + i] = 1;
            dfs(n + 1);
            b1[i] = 0, b2[N - n + i] = 0, b3[n + i] = 0;
        }
}
int main()
{
    cin >> N;
    dfs(1);
    cout << cnt;
}

#include <bits/stdc++.h>
using namespace std;
unsigned long long res, k, n, cnt, num[1000], s[1000], f[10][300][300];
void init()
{
    for (int i = 0; i < (1 << n); i++)
    {
        if (i & (i << 1))
            continue;
        int sum = 0;
        for (int j = 1; j < (1 << n); j <<= 1)
        {
            if (j & i)
                sum++;
        }
        num[++cnt] = sum;
        s[cnt] = i;
        f[1][cnt][sum] = 1;
    }
}
void dp()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= cnt; j++)
            for (int r = 0; r <= k; r++)
                if (r >= num[j])
                    for (int q = 1; q <= cnt; q++)
                        if (!(s[j] & s[q]) && !((s[j] << 1) & s[q]) && !((s[j] >> 1) & s[q]))
                            f[i][j][r] += f[i - 1][q][r - num[j]];
    for (int i = 1; i <= cnt; i++)
        res += f[n][i][k];
}
int main()
{
    cin >> n >> k;
    init();
    dp();
    cout << res;
}

（2）迷宫（广度优先搜索）

#include <bits/stdc++.h>
using namespace std;
int n, m, sx, sy, ex, ey;
int a[100][100], b[100][100], d[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
struct node
{
    int x, y, step;
};
queue<node> q;
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    cin >> sx >> sy >> ex >> ey;
    q.push({sx, sy, 0});
    while (!q.empty())
    {

        int x = q.front().x, y = q.front().y, step = q.front().step;
        q.pop();
        if (x == ex && y == ey)
        {
            cout << step;
            return 0;
        }
        for (int i = 0; i < 4; i++)
        {
            int tx = x + d[i][0], ty = y + d[i][1];
            if (a[tx][ty] == 1 && b[tx][ty] == 0)
            {
                b[tx][ty] = 1;
                q.push({tx, ty, step + 1});
            }
        }
    }
    cout << "-1";
}

（3）路标设置（二分法）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int l, n, k, ans, a[N];
bool check(int x)
{
    int i = 1, cnt = 0;
    while (i < n)
    {
        int j = 1;
        while (a[i] - a[i - 1] > j * x)
        {
            cnt++;
            j++;
        }
        i++;
    }
    if (cnt <= k)
        return true;
    else
        return false;
}
int main()
{
    cin >> l >> n >> k;
    for (int i = 0; i < n; i++)
        cin>>a[i];
    int left = 1, right = l;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (check(mid))
        {
            right = mid - 1;
            ans = mid;
        }
        else
            left = mid + 1;
    }
    cout << ans;
}

（4）背包（记忆化搜索，动态规划）

#include <bits/stdc++.h>
using namespace std;
int n, W, w[100], v[100], f[1000][1000];
int dfs(int i, int j)
{
    if (f[i][j] >= 0)
        return f[i][j];
    int res;
    if (i == n)
        res = 0;
    else if (j < w[i])
        res = dfs(i + 1, j);
    else
        res = max(dfs(i + 1, j), dfs(i + 1, j - w[i]) + v[i]);
    return f[i][j] = res;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> w[i] >> v[i];
    cin >> W;
    memset(f, -1, sizeof(f));
    cout << dfs(0, W);
}

#include <bits/stdc++.h>
using namespace std;
int n, W, w[100], v[100], f[1000][1000];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> w[i] >> v[i];
    cin >> W;
    for (int i = n - 1; i >= 0; i--)
        for (int j = 0; j <= W; j++)
            if (j < w[i])
                f[i][j] = f[i + 1][j];
            else
                f[i][j] = max(f[i + 1][j], f[i + 1][j - w[i]] + v[i]);
    cout << f[0][W];
}

（5）最小逆序对数（分治）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e6 + 5;
int t, n, m, tot, cnt;
int a[N], b[N], c[N], d[N], A[N], p[N];
void disc()
{
    sort(d + 1, d + 1 + tot);
    cnt = unique(d + 1, d + 1 + tot) - d - 1;
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(d + 1, d + 1 + cnt, a[i]) - d;
    for (int i = 1; i <= m; i++)
        b[i] = lower_bound(d + 1, d + 1 + cnt, b[i]) - d;
}
int lowbit(int x)
{
    return x & (-x);
}
void upd(int x)
{
    for (; x <= cnt; x += lowbit(x))
        c[x]++;
}
ll qry(int x)
{
    ll summ = 0;
    for (; x; x -= lowbit(x))
        summ += c[x];
    return summ;
}
ll calc()
{
    ll summ = 0;
    for (int i = 1; i <= tot; i++)
    {
        summ += qry(cnt) - qry(A[i]);
        upd(A[i]);
    }
    return summ;
}
void solve(int Lb, int Rb, int La, int Ra)
{
    if (Lb > Rb)
        return;
    int mid = (Lb + Rb) >> 1;
    int val = b[mid];
    int minn = 2e9, summ1 = 0, summ2 = 0;
    for (int i = Ra - 1; i >= La; i--)
    {
        if (a[i] < val)
            summ2++;
    }
    minn = summ2;
    p[mid] = La;
    for (int i = La + 1; i <= Ra; i++)
    {
        if (a[i - 1] < val)
            summ2--;
        if (a[i - 1] > val)
            summ1++;
        if (summ1 + summ2 < minn)
        {
            minn = summ1 + summ2;
            p[mid] = i;
        }
    }
    solve(Lb, mid - 1, La, p[mid]);
    solve(mid + 1, Rb, p[mid], Ra);
}
int main()
{
    cin >> t;
    while (t--)
    {
        tot = 0;
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            d[++tot] = a[i];
        }
        for (int i = 1; i <= m; i++)
        {
            cin >> b[i];
            d[++tot] = b[i];
        }
        sort(b + 1, b + 1 + m);
        disc();
        for (int i = 1; i <= cnt; i++)
            c[i] = 0;
        solve(1, m, 1, n + 1);
        tot = 0;
        int k = 1;
        for (int i = 1; i <= n; i++)
        {
            while (p[k] == i && k <= m)
            {
                A[++tot] = b[k];
                k++;
            }
            A[++tot] = a[i];
        }
        while (k <= m)
        {
            A[++tot] = b[k];
            k++;
        }
        cout << calc();
    }
}

这篇关于呐呐呐~第一份随笔的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！