中石大第41次CSP培训Week4题解

作业链接：https://www.luogu.com.cn/contest/311113

邀请码：微信群通知

知识点：

• 动态规划
• 并查集
• KMP

难度：普及-

赛时答疑与赛后题解：视频讲解，周六答疑

A. [IOI 1994 / USACO1.5] 数字三角形 Number Triangles

[IOI 1994 / USACO1.5] 数字三角形 Number Triangles

思路

动态规划、递推

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int r, ans;
int a[N][N], dp[N][N];

int main() {
    cin >> r;
    for(int i = 1; i <= r; i ++)
        for(int j = 1; j <= i; j ++)
            cin >> a[i][j];
    for(int i = 1; i <= r; i ++)
        for(int j = 1; j <= i; j ++)
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j];
    for(int i = 1; i <= r; i ++)
        ans = max(ans, dp[r][i]);
    cout << ans << endl;
    return 0;
}

B. [PacNW 1999] Function

[PacNW 1999] Function

思路

递归、记忆化搜索

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 25;

int dp[N][N][N];

int w(long long a, long long b, long long c) {    // 记忆化搜索
    // 判断边界条件，下标不合法
    if(a <= 0 || b <= 0 || c <= 0)
        return 1;
    if(a > 20 || b > 20 || c > 20)
        return w(20, 20, 20);
    // 判断是否已经计算过
    if(dp[a][b][c])
        return dp[a][b][c];
    if(a < b && b < c)
        return dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
    return dp[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
}

int main() {
    long long a, b, c;
    while(cin >> a >> b >> c) {
        if(a == -1 && b == -1 && c == -1) 
            break;
        printf("w(%lld, %lld, %lld) = %d\n", a, b, c, w(a, b, c));
    }
    return 0;
}

C. 第27次CSP认证第二题：何以包邮？

第27次CSP认证第二题：何以包邮？（洛谷团队比赛）

第27次CSP认证第二题：何以包邮？（AcWing）

思路

01背包（一维优化）

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 35;
const int X = 5e6 + 5;
const int INF = 1e9;

int n, x;
long long a[N];
long long dp[X];   // dp[j]  表示前i个商品j元包邮情况下的最小花费

int main() {
    cin >> n >> x;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    for(int i = 1; i <= x; i ++)
        dp[i] = INF;
    for(int i = 1; i <= n; i ++) {
        for(int j = x; j >= 1; j --) {
            if(a[i] >= j)
                dp[j] = min(a[i], dp[j]);
            else
                dp[j] = min(dp[j-a[i]] + a[i], dp[j]);
        }
    }

    cout << dp[x] << endl;
    return 0;
}

D. 疯狂的采药

疯狂的采药

思路

完全背包（一维优化）

代码

#include <bits/stdc++.h>

using namespace std;

const int M = 1e4 + 5;
const int N = 1e7 + 5;

int t, m;
long long dp[N];   // dp[i] 表示采摘时间不超过 i 的最大总价值
int duration[M], value[M];

int main() {
    cin >> t >> m;

    for(int i = 1; i <= m; i ++)
        cin >> duration[i] >> value[i];

    for(int i = 1; i <= m; i ++)
        for(int j = duration[i]; j <= t; j ++)
            dp[j] = max(dp[j], dp[j - duration[i]] + (long long)value[i]);
    cout << dp[t] << endl;
    return 0;
}

E. 【模板】并查集

【模板】并查集

思路

并查集模板

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, m, x, y, z;
int father[N];

int getFather(int x) {
    if(father[x] == x)
        return x;
    return father[x] = getFather(father[x]);
}

int main() {
    cin >> n >> m;

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

    while(m --) {
        cin >> z >> x >> y;
        if(z == 1)
            father[getFather(x)] = getFather(y);
        else
            cout << (getFather(x) == getFather(y) ? 'Y' : 'N') << endl;
    }
    return 0;
}

F. 【模板】KMP

【模板】KMP

思路

KMP模版

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

string s1, s2;
int Next[N];

int main() {
    cin >> s1 >> s2;

    for(int i = 1; i < s2.size(); i ++) {
        int j = Next[i - 1];
        while(j > 0 && s2[i] != s2[j])
            j = Next[j - 1];
        if(s2[i] == s2[j])
            j ++;
        Next[i] = j;
    }

    int j = 0;
    for(int i = 0; i < s1.size(); i ++) {
        while(j > 0 && s1[i] != s2[j])
            j = Next[j - 1];
        if(s1[i] == s2[j])
            j ++;
        if(j == s2.size())
            cout << i - s2.size() + 2 << endl;
    }

    for(int i = 0; i < s2.size(); i ++)
        cout << Next[i] << ' ';
    return 0;
}