头像

您的昵称经审核未通过请...


访客:1656

离线:1天前


活动打卡代码 AcWing 282. 石子合并

0


活动打卡代码 AcWing 902. 最短编辑距离

include[HTML_REMOVED]

using namespace std;

const int N = 1007;

int n, m;
char str1[N], str2[N];
int p[N][N];

// 这次p[i][j]代表的是str1的前i个字符变换成str2的前j个字符,需要经过的最少变换次数
int main()
{
cin >> n >> str1 + 1;
cin >> m >> str2 + 1;

// 初始化
for (int i = 0; i <= m; i ++) p[0][i] = i; // 当str1长度为零的时候,对应的操作只能是删除,操作次数就是str2的长度i
for (int i = 0; i <= n; i ++) p[i][0] = i; // 当str2长度为零的时候,对应的操作只能是插入,操作次数就是str1的长度i

for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= m; j ++)
    {
        p[i][j] = min(p[i - 1][j], p[i][j - 1]) + 1;
        if (str1[i] == str2[j]) p[i][j] = min(p[i][j], p[i-1][j-1]);
        else p[i][j] = min(p[i][j], p[i - 1][j - 1] + 1);
    }
cout << p[n][m] << endl;
return 0;

}




#include<iostream>
#include<cstdio>

using namespace std;

const int N = 1007;
int n, m;
char str1[N], str2[N];
int p[N][N];

int main()
{
    cin >> n >> m;
    cin >> str1 + 1 >> str2 + 1;

    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            p[i][j] = max(p[i - 1][j], p[i][j - 1]);
            if (str1[i] == str2[j]) p[i][j] = max(p[i][j], p[i - 1][j - 1] + 1);
        }
    }
    cout << p[n][m] << endl;
    return 0;
}


活动打卡代码 AcWing 840. 模拟散列表

// 开放寻址法:
#include<iostream>
#include<cstring>

using namespace std;

const int N = 2e5 + 3, null = 0x3f3f3f3f;
int p[N];

int find (int a)
{
    int c = (a % N + N) % N;
    while (p[c] != null && p[c] != a)
    {
        c ++;
        if (c == N + 1) c = 0; // 如果到头了,就回到开始的位置。
    }
    return c;
    // 这个函数返回的是 a 应该呆在的位置
}

int main()
{
    memset(p, 0x3f, sizeof p); // 赋初值,0x3f3f3f3f;
    int m;
    cin >> m;
    while (m --)
    {
        char op[2];
        int a;
        scanf("%s%d",op, &a);
        int k = find(a); if (*op == 'I') p[k] = a;
        else
        {
            if (p[k] != 0x3f3f3f3f) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}



#include<iostream>
#include<cstdio>

using namespace std;

const int N = 1007;
int n;
int arr[N], p[N];
int ans;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) scanf("%d", &arr[i]);

    for (int i = 1; i <= n; i ++)
    {
        p[i] = 1;
        for (int j = 1; j <= i; j ++)
        {
            if (arr[i] > arr[j]) p[i] = max(p[i], p[j] + 1);
        }
        ans = max(ans, p[i]);
    }
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 9. 分组背包问题

#include<iostream>
using namespace std;
const int N = 107;
int n, m;
int p[N], v[N], w[N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        int s;
        cin >> s;
        for (int j = 1; j <= s; j ++) cin >> v[j] >> w[j];

        for (int j = m; j >= 1; j --)
            for (int k = 1; k <= s; k ++)
                if (j >= v[k])
                    p[j] = max( p[j], ( p[j - v[k]] + w[k] ) );
    }
    cout << p[m] << endl;
    return 0;
}
// 根据题意,每层i循环,都只需要用到当前这一层的w,v。所以可以覆盖输入。


活动打卡代码 AcWing 5. 多重背包问题 II

#include<iostream>
#include<cmath>
#include<cstdio>

using namespace std;
// log 2 (2000) = 11
const int N = 2007, M = 11000;
int n, m;
int v[M], w[M], cnt;
int p[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        int v1, w1, s1;
        scanf("%d%d%d", &v1, &w1, &s1);
        int k = 1;
        while (k <= s1)
        {
            cnt ++;
            v[cnt] = k * v1, w[cnt] = k * w1;
            s1 -= k;
            k *= 2;
        }
        if (s1 > 0) v[++ cnt] = s1 * v1, w[cnt] = s1 * w1;
    }

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

    cout << p[m] << endl;

    return 0;
}


活动打卡代码 AcWing 4. 多重背包问题

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 107;
int n, m;
int s[N], v[N], w[N];
int arr[N][N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) scanf("%d%d%d", &v[i], &w[i], &s[i]);

    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            for (int k = 0; k <= s[i]; k ++)
            {
                if (j >= v[i] * k) arr[i][j] = max(arr[i][j], arr[i - 1][j - k * v[i]] + w[i] * k);
            }
        }
    }
    cout << arr[n][m] << endl;
    return 0;
}


活动打卡代码 AcWing 907. 区间覆盖

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 7;
int n, cnt, res;

struct range
{
    int l, r;
    bool operator< (const range &w) const
    {
        return w.l > l;
    }
}ranges[N], ran[N];

int main()
{
    int st, ed;
    cin >> st >> ed;
    cin >> n;

    for (int i = 0; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        if (!(b < st || a > ed))
            ran[cnt ++] = {a, b};
    }

    sort(ran, ran + cnt);

    bool success = false;

    for (int i = 0; i < cnt; i ++)
    {
        int j = i, t = -2e9;
        while (j < cnt && ran[j].l <= st)
        {
            t = max(t, ran[j].r);
            j ++;
        }

        if (t <= st) break;

        res ++;

        if (t >= ed)
        {
            success = true;
            break;
        }

        st = t;
    }
    if (success == true) cout << res << endl;
    else puts("-1");
    return 0;
}


活动打卡代码 AcWing 906. 区间分组

#include<iostream>
#include<queue>
#include<algorithm>
#include<cstdio>

using namespace std;

const int N = 1e5 + 7;
int n; 
struct ranger
{
    int l, r;
    bool operator< (const ranger &W) const
    {
        return l < W.l;
    }
}arr[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        arr[i] = {l, r};
    }

    sort(arr, arr + n);

    priority_queue<int, vector<int>, greater<int>> heap; // 定义小根堆

    for (int i = 0; i < n; i ++)
    {
        ranger t = arr[i];
        if (heap.empty() || heap.top() >= t.l) heap.push(t.r);
        else
        {
            heap.pop();
            heap.push(t.r);
        }
    }
    printf("%d\n", heap.size());
    return 0;
}