头像

小朋友不讲武德




在线 


活动打卡代码 AcWing 423. 采药

#include <iostream>

using namespace std;

const int N = 110;
int t, n;
int v[N], w[N];
int f[N][N * 10];

int main() {
    cin >> t >> n;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= t; j ++ ) {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << f[n][t] << endl;
    return 0;
}



用快速幂算出n个人的所有方案数, 为2^n, 再用0-1背包的思想求出所有能力值小于k的方案数

二者之差就是最终答案

计蒜客上的一道题, 思考了很久终于想到一个解决方案 题目

题目描述

蒜头君作为蒜厂篮球队的经理,要从 n 名队员中选出若干人组队参加篮球争霸赛。为了获得参赛资格,球队中所有队员的能力值 p 之和不得小于 k。

现在给出你所有球员的能力值,请问蒜头君共有多少种组队方案。这个方案数可能很大,需要对 10007 取模。每个组队方案的人数没有任何限制。

输入格式
输入为 2 行:

第一行是两个空格隔开的整数 n, k (1 <= n <= 100, 1 <= k <= 10^4)
分别表示队员的数目和球队总能力值的下限;
第二行是 n 个空格隔开的整数 p (1 <= p <= 100)为每个球员的能力值;

输出格式
输出为 1 个整数,为蒜头君的组队方案数,结果对 10007 取模。

样例

样例输入
5 10
2 4 6 8 10

样例输出
25

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110, K = 10010, MOD = 10007;

int n, k;
int p[N];
int f[N][K];

int qmi(int a, int b) {
    int res = 1 % MOD;
    while (b) {
        if (b & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> p[i];

    for (int i = 0; i <= n; i++) f[i][0] = 1;
    for (int i = 0; i <= k - 1; i++) f[0][i] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k - 1; j++) {
            f[i][j] = f[i - 1][j];
            if (j >= p[i])
                f[i][j] = (f[i][j] + f[i - 1][j - p[i]]) % MOD;
        }
    }

    cout << (qmi(2, n) - f[n][k - 1] + MOD) % MOD << endl;
    return 0;
}



用递归法逐个填充

从样例中可以看到,n 矩阵就是在 n - 1 矩阵的上面多一行 1~n,左侧多一列 1~n
由此可以用递归法来填充,先以坐标(1, 1)为起点填充 n 所在的一行一列,再把
横纵坐标都加1,递归填充 n - 1 所在的一行一列,一直到 n 等于 0 的时候结束。

#include <iostream>
using namespace std;

const int N = 110;

int n;
int a[N][N];

void ff(int n, int x, int y) {
    if (n <= 0) return;
    for (int i = 1; i <= n; i++) a[x][y + i - 1] = i, a[x + i - 1][y] = i;
    ff(n - 1, x + 1, y + 1);
}

void print(int n) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << a[i][j] << ' ';
        }
        cout << endl;
    }

}

int main() {
    while (1) {
        cin >> n;
        if (!n) break;

        ff(n, 1, 1);
        print(n);
        cout << endl;
    }

    return 0;
}



自动兑换机

来自洛谷

比赛时间到了没法验证了, 等待开放的时候再提交试试看.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 10010;

int n, m, t;
int a[N];
int f[110][N];

bool cmp(int a, int b) {
    char x[20], y[20];
    sprintf(x, "%d", a);
    sprintf(y, "%d", b);
    int i = 0, j = 0;
    while (i < strlen(x) && j < strlen(y)) {
        if (x[i] < y[j]) return false;
        else if (x[i] > y[j]) return true;
        i++, j++;
    }
    if (i == strlen(x)) return false;
    return true;
}

int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        double c;
        cin >> c;
        m = c * 100;

        sort(a + 1, a + 1 + n, cmp);

        //for (int i = 1; i <= n; i++) cout << a[i] << ' ' ; cout << endl;
        memset(f, 0x3f, sizeof(f));
        for (int i = 0; i <= n; i++) f[i][0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                f[i][j] = f[i - 1][j];
                if (j >= a[i])
                    f[i][j] = min(f[i][j], f[i][j - a[i]] + 1);
            }

        }

        int id = 0, rr = m;
        for (int i = 1; i <= n; i++) {
            //cout << f[i][m] << ' ';
            if (f[i][m] <= rr) { id = i; rr = f[i][m]; }

        }
        if (id == 0) { cout << "No Solution" << endl; continue; }

        cout << f[id][m] << ' ';
        int i = id, j = m, all = m;
        while (all > 0) {
            int cnt = 0;
            while (f[i][j] == f[i][j - a[i]] + 1) {
                cnt++, all -= a[i], j -= a[i];

            }
            if (cnt) {
                cout << a[i] << '*' << cnt;
                if (all) cout << '+';
            } else {
                i--;
            }

        }
        cout << endl;
    }

    return 0;
}



新鲜事 原文

背包问题全解析(还不全) https://juejin.cn/post/6875966041604751368



01背包问题,求体积恰好等于m时的最大价值

需要对 f 数组作特殊的初始化,详见代码注释。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    /* 当求体积正好等于 m 时的最大价值时,需要如下的初始化 */
    // 1. 所有方案的价值都置为负无穷
    memset(f, 0xf0, sizeof(f));
    // 2. 只有当前体积为 0 时,对于所有物品 i,都有一种合法方案,就是
    //    什么也不选,对应此时的最大价值为0. 
    // 3. 最后的答案还是 f[n][m]
    for (int i = 0; i <= n; i++) f[i][0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            f[i][j] = f[i - 1][j];
            if (j >= v[i])
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    }

    cout << f[n][m] << endl;
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



BF 算法解决有边数限制的最短路径

为了防止链式更新, 需要用到一个 backup 数组, 以免 a 更新了 b, 在同一次迭代里 b 又更新了 c 点.
每次迭代都要枚举 m 条边有点笨, 所以 spfa 算法就是为了优化 BF 的, 用邻接表存储边, 每次只更新
d[a] 发生变化了的所有边. 用队列记录记录所有变化了的节点.

BF 算法也可以用来判断负环

迭代第 n 次时, 如果发现还有某个点的距离发生了变化, 那就说明存在一条长度为 n + 1 的路径, 就
必定存在负权回路.

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010;

struct Edge {
    int a, b, c;
} edges[N];

int n, m, k, x, y, z;
int d[N], backup[N];

int bf() {
    memset(d, 0x3f, sizeof(d));
    d[1] = 0;

    for (int i = 1; i <= k; i++) {
        memcpy(backup, d, sizeof(d));   // 防止链式更新, 下面更新 d[b] 时要用到 backup[a] 不能用 d[a]
        for (int j = 0; j < m; j++) {
            int a = edges[j].a, b = edges[j].b, c = edges[j].c;
            d[b] = min(d[b], backup[a] + c);
        }
    }

    return d[n];
}

int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        cin >> x >> y >> z;
        edges[i].a = x, edges[i].b = y, edges[i].c = z;
    }

    int t = bf();
    if (t > 0x3f3f3f3f / 2) cout << "impossible" << endl;
    else cout << t << endl;
    return 0;
}


新鲜事 原文

CSP小朋友迷惑行为 小孩装 "大" 人 ``` int main() { freopen("stairs.in", "R", stdin); freopen("stairs.out", "W", stdout); ```


活动打卡代码 AcWing 496. 机器翻译

这个提高组的题有点水

#include <iostream>
#include <queue>
#include <set>
using namespace std;

const int N = 1010, M = 110;
queue<int> q;
set<int> dict;

int n, m;
int ans;

int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (dict.count(x) == 0) {
            ans++;
            dict.insert(x), q.push(x);
            if (q.size() > m) {
                int t = q.front();
                dict.erase(t), q.pop();
            }
        }
    }

    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 441. 数字统计

入门组的题越发的简单了起来....

#include <iostream>
using namespace std;

int l, r;
int ans;

int main() {
    cin >> l >> r;
    for (int i = l; i <= r; i++) {
        int x = i;
        while (x) {
            if (x % 10 == 2) ans++;
            x /= 10;
        }
    }

    cout << ans << endl;
}