头像

Mup丶Superman

华中农业大学




离线:8小时前


最近来访(28)
用户头像
党梦竹
用户头像
只会一点点
用户头像
ctOS
用户头像
shower
用户头像
SONDER_2
用户头像
xiaodie
用户头像
神秘刀光男
用户头像
1253981891
用户头像
来不及了
用户头像
lxmj
用户头像
Just_Because
用户头像
mjlx
用户头像
smile2game
用户头像
yxc
用户头像
ZhgDgE
用户头像
寻_0

活动打卡代码 AcWing 1021. 货币系统

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20, M = 3010;

typedef long long LL;

int n, m;
LL f[M];


int main()
{
    scanf("%d%d", &n, &m);

    f[0] = 1;

    for (int i = 1; i <= n; i ++)
    {
        int v;
        scanf("%d", &v);
        for (int j = v; j <= m; j ++) f[j] += f[j - v];
    }

    printf("%lld\n", f[m]);

    return 0;
}


活动打卡代码 AcWing 1023. 买书

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int price[4] = {10, 20, 50, 100};
int f[N];

int main()
{
    scanf("%d", &n);

    f[0] = 1;

    for (int i = 0; i < 4; i ++)
        for (int j = price[i]; j <= n; j ++)
            f[j] += f[j - price[i]];

    printf("%d\n", f[n]);

    return 0;
}


活动打卡代码 AcWing 278. 数字组合

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int M = 10010;

int n, m;
int f[M];

int main()
{
    scanf("%d%d", &n, &m);

    f[0] = 1;

    for (int i = 0; i < n; i ++)
    {
        int v;
        scanf("%d", &v);
        for (int j = m; j >= v; j --) f[j] += f[j - v];
    }

    printf("%d\n", f[m]);

    return 0;
}



#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1010, M = 510, K = 110;

int n, m, k;
int cnt[K], hurt[K];
int f[M][N];

int main()
{
    scanf("%d%d%d", &n, &m, &k);

    for (int i = 1; i <= k; i ++) scanf("%d%d", &cnt[i], &hurt[i]);

    int C = 0, R = m;

    for (int u = 1; u <= k; u ++)
        for (int i = m; i > hurt[u]; i --)
            for (int j = n; j >= cnt[u]; j --)
            {
                if (f[i][j] < f[i - hurt[u]][j - cnt[u]] + 1) f[i][j] = f[i - hurt[u]][j - cnt[u]] + 1;
                if (f[i][j] > C) C = f[i][j];
            }

    for (int i = 1; i <= m; i ++) 
        if (f[i][n] == C)
        {
            R = i - 1;
            break;
        }

    printf("%d %d\n", C, m - R);

    return 0;
}


活动打卡代码 AcWing 1024. 装箱问题

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 20010, M = 35;

int V, n;
int f[M][N];
int v[M];

int main()
{
    scanf("%d%d", &V, &n);

    for (int i = 1; i <= n; i ++) scanf("%d", &v[i]);

    int res = 0;

    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= V; 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]] + v[i]);
            res = max(res, f[i][j]);
        }
    }

    printf("%d\n", V - res);

    return 0;
}


活动打卡代码 AcWing 423. 采药

二维
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int T = 1010, M = 110;

int n, m;
int t[M], w[M];
int f[M][T];
int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i ++) scanf("%d%d", &t[i], &w[i]);

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

    printf("%d\n", f[m][n]);

    return 0;
}
一维
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int T = 1010, M = 110;

int n, m;
int t[M], w[M];
int f[T];
int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i ++) scanf("%d%d", &t[i], &w[i]);

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

        }

    printf("%d\n", f[n]);

    return 0;
}


活动打卡代码 AcWing 2041. 干草堆

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int n, k;
int q[N];

int main()
{
    scanf("%d%d", &n, &k);

    for (int i = 1; i <= k; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        q[a] += 1;
        q[b + 1] -= 1;
    }

    for (int i = 1; i <= n; i ++) q[i] += q[i - 1];

    nth_element(q + 1, q + (n + 1) / 2, q + 1 + n);

    printf("%d\n", q[(n + 1) / 2]);

    return 0;
}


活动打卡代码 AcWing 2058. 笨拙的手指

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

vector<int> p, q;

int get2(vector<int> &nums)
{
    int res = 0;
    for (auto x: nums) res = res * 2 + x;
    return res;

}

int get3(vector<int> &nums)
{
    int res = 0;
    for (auto x: nums) res = res * 3 + x;
    return res;

}

int main()
{
    string a, b;

    cin >> a >> b;

    for (int i = 0; i < a.size(); i ++) p.push_back(a[i] - '0');

    for (int i = 0; i < b.size(); i ++) q.push_back(b[i] - '0');

    bool flag = false;

    int res;

    for (int i = 0; i < p.size(); i ++)
    {
        p[i] = 1 - p[i];
        for (int j = 0; j < q.size(); j ++)
        {
            for (int k = 0; k < 3; k ++)
            {
                if (q[j] == k) continue;
                else
                {
                    int t = q[j];
                    q[j] = k;
                    if (get2(p) == get3(q))
                    {
                        res = get2(p);
                        flag = true;
                        break;
                    }
                    q[j] = t;
                }
            }
        }
        p[i] = 1 - p[i];
        if (flag) break;
    }

    printf("%d\n", res);

    return 0;
}


活动打卡代码 AcWing 429. 奖学金

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310;

struct student
{
    int a, b, c;
    int sum;
    int id;
};

int n;
student students[N];

bool cmp(student s1, student s2)
{
    if (s1.sum != s2.sum) return s1.sum > s2.sum;
    if (s1.a != s2.a) return s1.a > s2.a;
    return s1.id < s2.id;

}

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> students[i].a >> students[i].b >> students[i].c;
        students[i].sum = students[i].a + students[i].b + students[i].c;
        students[i].id = i;
    }
    sort(students + 1, students + n + 1, cmp);

    for (int i = 1; i <= 5; i++)
    {
        cout << students[i].id << ' ' << students[i].sum << endl;
    }
    return 0;
}


活动打卡代码 AcWing 680. 剪绳子

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n, m;
int a[N];

bool check(double x)
{
    int res = 0;

    for (int i = 1; i <= n; i ++)
        res += a[i] / x;

    return res >= m;
}

int main()
{
    scanf("%d%d", &n, &m);

    int maxv = 0;

    for (int i = 1; i <= n; i ++) scanf("%d", &a[i]), maxv = max(maxv, a[i]);

    double l = 0, r = maxv;

    while (r - l >= 1e-4)
    {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    printf("%.2lf", l);

    return 0;
}