洛谷 P1001. A+B Problem 题解（欢迎投稿）

· · 题解

字数：7496。

以下算法以后写代码（欢迎催更）

算法一 模拟

#include <bits/stdc++.h>
using namespace std;
int a, b;
int main()
{
    cin >> a >> b;
    cout << a + b;
    return 0;
}

关于 #define

#include <bits/stdc++.h>
#define ans using namespace std; \
int main(){ \
    int a, b; \
    cin >> a >> b; \
    cout << a + b; \
    return 0; \
}
ans
#include <bits/stdc++.h>
#define _ using
#define __ namespace
#define ___ std
#define ____ int
#define _____ main
#define ______ cin
#define _______ cout
#define ________ return
#define _________ 0
_ __ ___;
____ _____(){
    ____ __________, ___________;
    ______ >> __________ >> ___________;
    _______ << __________ + ___________;
    ________ _________;
}
#include <bits/stdc++.h>
#define IOI using
#define AK namespace
#define ME std
#define HELLO int
#define WORLD main
#define QWERTYUIOP cin
#define ASDFGHJKL cout
#define ZXCVBNM return
#define _ 0
IOI AK ME;
HELLO WORLD(){
    HELLO LUOGU, COM;
    QWERTYUIOP >> LUOGU >> COM;
    ASDFGHJKL << LUOGU + COM;
    ZXCVBNM ~~0^_^0;
}

算法二 打表

略（

算法三 二分

#include <bits/stdc++.h>
using namespace std;
#ifndef INT_MIN
#define INT_MIN -2147483648
#endif
#ifndef INT_MAX
#define INT_MAX 2147483647
#endif
int a, b;
int main() {
    scanf("%d%d", &a, &b);
    int l = INT_MIN, r = INT_MAX;
    while (l < r) {
        int mid = l + r;
            mid /= 2;
        if (mid == a + b){l = mid; break;}
        if (mid <  a + b) l = mid + 1;
        if (mid >  a + b) r = mid - 1;
    }
    cout << l;
    return 0;
}

算法四 不用加号算加法

4.1 用减号

#include <bits/stdc++.h>
using namespace std;
int a, b;
int main()
{
    cin >> a >> b;
    cout << a - -b;
    return 0;
}

4.2 位运算

递归版

#include <bits/stdc++.h>
using namespace std;
int add(int x, int y){
    if(!y){
        return x;
    }
    return add(x ^ y, (x & y) << 1);
}
int a, b;
int main(){
    cin >> a >> b;
    cout << add(a, b);
    return 0;
}

非递归版

#include <bits/stdc++.h>
using namespace std;
int a, b;
int main(){
    cin >> a >> b;
    while (b)
    {
        int x = a ^ b, y = (a & b) << 1;
        a = x;
        b = y;
    }
    cout << a;
    return 0;
}

算法五 动态规划

5.1 线性 \texttt{DP}（数字三角形模型）

考虑用 f[i][j] 表示 i + j，但是 \texttt{MLE + TLE}，不行，于是，我们需要数字三角形模型。

为什么说是模型呢？因为它不是三角形，是长方形（2\times1）：

a
b

因此，问题就变成了：选择 n (n=2) 个数，使得第 i 个数在第 i 行，并且相邻两个数的列相邻（差的绝对值 \le1），求这 n 个数的和的最大值。

让 f[i][j] 表示在取 i 行并且最后一行取第 j 列时的最优解。

状态转移方程：f[i][j] = max({f[i - 1][j - 1], f[i - 1][j], f[i - 1][j + 1]}) + a[i][j]

边界条件：f[1][j] = a[1][j]

#include <bits/stdc++.h>
using namespace std;
int n, m, x, f[10][10], ans;
int main()
{
    n = 2; m = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> x;
            if (i == 1) // 边界条件
            {
                f[i][j] = x;
            }
            else
            {
                f[i][j] = max({f[i - 1][j - 1], f[i - 1][j], f[i - 1][j + 1]}) + x;
            }
            if (i == n)
            {
                ans = max(ans, f[i][j]);
            }
        }
    }
    cout << ans;
    return 0;
}

5.2 区间 \texttt{DP}

用 f[i][j] 表示

\sum_{k=i}^ja_i(1\le i,j\le n=2) 
#include <bits/stdc++.h>
using namespace std;
int n, a[10], f[10][10];
int main()
{
    n = 2;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        f[i][i] = a[i];
    }
    for (int dis = 1; dis < n; dis++)
    {
        for (int l = 1; l + dis <= n; l++)
        {
            int r = l + dis;
            f[l][r] = max(f[l][r - 1] + a[r], f[l - 1][r] + a[l]);
        }
    }
    cout << f[1][n];
    return 0;
}

5.3 背包 \texttt{DP}（\texttt{0-1} 背包）

把一个数看作价值 x，体积 1 的物品，而背包体积上限为 2。

#include <bits/stdc++.h>
using namespace std;
int m, n, w[10], c[10], f[10];
int main()
{
    n = m = 2;
    for(int i = 1; i <= n; i++)
    {
        cin >> c[i];
        w[i] = 1;
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = m; j > 0; j--)
        {
            if(w[i] <= j)
            {
                f[j] = max(f[j], f[j - w[i]] + c[i]);
            }
        }
    }
    cout << f[m];
    return 0;
}

5.4 树形 \texttt{DP}

让 a_2 作为 a_1 的子节点。

#include <bits/stdc++.h>
using namespace std;
int n, a[10], fa[10], f[10];
void dfs(int id)
{
    for (int i = 1; i <= n; i++)
    {
        if (fa[i] == id)
        {
            dfs(i);
            f[id] = max(f[id], f[i]);
        }
    }
    f[id] += a[id];
}
int main()
{
    n = 2; fa[2] = 1;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    dfs(1);
    cout << f[1];
    return 0;
}

5.5 状压 \texttt{DP}

f[(1 << x) + (1 << y)] 表示 a[x] + a[y]。

#include <bits/stdc++.h>
using namespace std;
int n, a[10], f[10];
int lg2(int x)
{
    if (x < 2)
    {
        return 0;
    }
    return lg2(x / 2) + 1;
}
int main()
{
    n = 2;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i < (1 << n); i++)
    {
        f[i] = f[i - (i & -i)] + a[lg2(i & -i)];
    }
    cout << f[(1 << n) - 1];
    return 0;
}

算法六、前缀和

#include <bits/stdc++.h>
using namespace std;
int n, a[10];
int main()
{
    n = 2;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    cout << a[n];
    return 0;
}

算法七、并查集

#include <bits/stdc++.h>
using namespace std;
int n, a[10], fa[10], sum[10];
int find(int x)
{
    if (fa[x] != x)
    {
        fa[x] = find(fa[x]);
    }
    return fa[x];
}
void merge(int x, int y)
{
    int fx = find(x), fy = find(y);
    fa[fy] = fx;
    sum[fx] += sum[fy];
}
int main()
{
    n = 2;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = a[i];
        fa[i] = i;
    }
    merge(1, 2);
    cout << sum[1];
    return 0;
}

算法八、树状数组

#include <bits/stdc++.h>
using namespace std;
inline int lowbit(int x)
{
    return x & -x;
}
int n, x, tree[10];
void add(int id, int val)
{
    while (id <= n)
    {
        tree[id] += val;
        id += lowbit(id);
    }
}
int sum(int id)
{
    int ret = 0;
    while (id)
    {
        ret += tree[id];
        id ^= lowbit(id);
    }
    return ret;
}
int main()
{
    n = 2;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        add(i, x);
    }
    cout << sum(n);
    return 0;
}

算法九、线段树

#include <bits/stdc++.h>
using namespace std;
int n, a[10];
struct Node
{
    int l, r, sum;
} tr[40];
void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r)
{
    if (l == r)
    {
        tr[u] = {l, r, a[l]};
        return;
    }
    tr[u] = {l, r, 0};
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].sum;
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        int res = 0;
        if (l <= mid)
        {
            res += query(u << 1, l, r);
        }
        if (r > mid)
        {
            res += query(u << 1 | 1, l, r);
        }
        return res;
    }
}
int main()
{
    n = 2;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    build(1, 1, n);
    cout << query(1, 1, n);
    return 0;
}

总结

略（