GESP 六级

B3873 [GESP202309 六级] 小杨买饮料

提示

01背包

总容量不低于L，这不是01背包的典型模型

观察数据范围l<=2000, li <= 1e6，这有明显的冲突

2L的证明，是个难题

用刷表法，更好理解

代码

// 01背包
// 总容量不低于L，这不是01背包的典型模型
// 观察数据范围l<=2000, li <= 1e6，这有明显的冲突
// 2L的证明，是个难题
// 用刷表法，更好理解
#include <bits/stdc++.h>

using namespace std;

const int N = 510;

int n, L;
int dp[5010];
int a[N], b[N];

int main() {
    cin >> n >> L;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        b[i] = min(b[i], L);
    }

    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 2 * L; j >= b[i]; j--)
            dp[j] = min(dp[j], dp[j - b[i]] + a[i]);

    int ret = 0x3f3f3f3f;
    for (int j = L; j <= 2 * L; j++) ret = min(ret, dp[j]);

    if (ret == 0x3f3f3f3f) cout << "no solution";
    else cout << ret;

    return 0;
}

B3874 [GESP202309 六级] 小杨的握手问题

思路

求每个数前面有几个数比自己小

求逆序对，是从小到大排列，a[i]>a[j], i...mid 这个范围都是比a[j]大的，都是逆序对

求正序对，是从大到小排序，a[i]<a[j], i...mid 这个范围都是比a[j]小的，都是正序对

代码

// 求每个数前面有几个数比自己小
// 求逆序对，是从小到大排列，a[i]>a[j], i...mid 这个范围都是比a[j]大的，都是逆序对
// 求正序对，是从大到小排序，a[i]<a[j], i...mid 这个范围都是比a[j]小的，都是正序对

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 10;

int a[N], tmp[N], n;
long long cnt;

void merge_sort(int l, int r) {
    if (l >= r) return ;

    int mid = l + r >> 1;
    merge_sort(l, mid); merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = 1;
    while (i <= mid && j <= r) {
        if (a[i] < a[j]) {
            cnt += mid - i + 1;
            tmp[k++] = a[j++];
        }
        else tmp[k++] = a[i++];
    }

    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];

    for (int i = l, k = 1; i <= r; i++, k++) a[i] = tmp[k];
}

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

    merge_sort(1, n);

//  for (int i = 1; i <= n; i++) cout << a[i] << ' ';
//  puts("");

    cout << cnt;

    return 0;
}

P10108 [GESP202312 六级] 闯关游戏

提示

每个关卡向后有M种选择，向后走ai关。离开这个关卡时，我们可以获得bi分。问离开时可以最多多少分

dp[i]，刷表法，答案是dp[n]，下标0-index。注意bi可能是负数

代码

// 每个关卡向后有M种选择，向后走ai关。离开这个关卡时，我们可以获得bi分。问离开时可以最多多少分
// dp[i]，刷表法，答案是dp[n]，下标0-index。注意bi可能是负数

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e4 + 10, M = 110;

int n, m, a[M], b[N];
ll dp[N];

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    memset(dp, 0xcf, sizeof dp);
    dp[0] = 0;
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < m; j++) {
            int t = min(i + a[j], n);

            dp[t] = max(dp[t], dp[i] + b[i]);

//          printf("---%d %d %d\n", i, t, dp[t]);
        }

    cout << dp[n];

    return 0;
}

P10109 [GESP202312 六级] 工作沟通

提示

n名员工，自己、父亲、父亲的父亲，可以领导自己

Q次询问，问可以领导所有人的员工编号（如有多种选择，选编号最大的）

代码

// n名员工，自己、父亲、父亲的父亲，可以领导自己
// Q次询问，问可以领导所有人的员工编号（如有多种选择，选编号最大的）

#include <bits/stdc++.h>

using namespace std;

const int N = 310;

int f[N], n, q, m;
map<int, int> mp;

void dfs(int x) {
    mp[x]++;
    if (x == 0) return ;

    dfs(f[x]);
}


int main() {
    cin >> n;
    for (int i = 1; i <= n - 1; i++) cin >> f[i];
    cin >> q;

    while (q--) {
        mp.clear();
        cin >> m;
        for (int i = 0; i < m; i++) {
            int x;
            cin >> x;

            dfs(x);
        }

        int ret = 0;
        for (auto x : mp) {
            if (x.second == m) ret = max(ret, x.first);
        }   

        cout << ret << '\n';
    }

    return 0;
}

P10376 [GESP202403 六级] 游戏

提示

从n->c, 每次可以-a,或者-b, 问有多少种方案

代码

```cpp
// 从n->c, 每次可以-a,或者-b, 问有多少种方案
// dp[i + a or b] += dp[i];  答案是 dp[c]
// 这个题目的状态转移方程，debug了很久，没有理清楚c != i 这个逻辑，产生了重复

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

int n, a, b, c;
int dp[N];

int main() {
    cin >> n >> a >> b >> c;

    dp[n] = 1;
    for (int i = n; i > c; i--) {
        if (i - a >= c) dp[i - a] = (dp[i - a] + dp[i]) % MOD;
        else dp[c] = (dp[c] + dp[i]) % MOD;

        if (i - b >= c) dp[i - b] = (dp[i - b] + dp[i]) % MOD;
        else dp[c] = (dp[c] + dp[i]) % MOD;
    }
    cout << dp[c];

    return 0;
}
```

代码02

// 从n->c, 每次可以-a,或者-b, 问有多少种方案
// dp[i + a or b] += dp[i];  答案是 dp[c]
// 枚举阶段的时候，只枚举到 i > c

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

int n, a, b, c;
int dp[N];

int main() {
    cin >> n >> a >> b >> c;

    dp[n] = 1;
    for (int i = n; i > c; i--) {
        dp[max(i - a, c)] = (dp[max(i - a, c)] + dp[i]) % MOD;
        dp[max(i - b, c)] = (dp[max(i - b, c)] + dp[i]) % MOD;
    }
    cout << dp[c];

    return 0;
}

P10377 [GESP202403 六级] 好斗的牛

提示

每头牛的攻击范围是[ai, bi]，攻击范围内不能有第二头牛。最少需要多长连续的牛棚可以把所有牛放下

观察到 n <= 9，这是一个排列枚举，维护最小值的问题

代码

// 每头牛的攻击范围是[ai, bi]，攻击范围内不能有第二头牛。最少需要多长连续的牛棚可以把所有牛放下
// 观察到 n <= 9，这是一个排列枚举，维护最小值的问题

#include <bits/stdc++.h>

using namespace std;

pair<int, int> a[20];
int n;
bool vis[20];
vector<int> chosen;
int ret = 0x3f3f3f3f;

void upd() {
    int p = 1;
    for (int i = 0; i < n - 1; i++) {
        int t = max(a[chosen[i]].second, a[chosen[i + 1]].first);
        p += t + 1;
    }

    ret = min(ret, p);

    return ;
}

void dfs(int u) {
    if (u == n + 1) {
        upd();
        return ;
    }

    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;

        vis[i] = true;
        chosen.push_back(i);
        dfs(u + 1);
        chosen.pop_back();
        vis[i] = false;
    }
}


int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].first;
    for (int i = 1; i <= n; i++) cin >> a[i].second;

    dfs(1);

    cout << ret;

    return 0;
}

P10721 [GESP202406 六级] 计算得分

代码

// 按官方给的题解思路

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[30], n, m;
string s;
int dp[N];

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

    for (int i = 1; i <= m; i++) {
        dp[i] = dp[i - 1];

        for (int j = 1; j <= n; j++) {
            int l = i - j * 3 + 1;
            if (l <= 0) break;

            // 从后向前枚举，这一段连续都是abc
            if (s.substr(l - 1, 3) == "abc") dp[i] = max(dp[i], dp[l] + a[j]);
            else break;
        }
    }

    cout << dp[m];

    return 0;
}

P10722 [GESP202406 六级] 二叉树

提示

一颗二叉树，结点是0或者1

每次操作，会将这个结点的子树内的所有结点，在相反操作

q次操作后，所有结点的状态

n<=1e5, q<=1e5

代码

// 一颗二叉树，结点是0或者1
// 每次操作，会将这个结点的子树内的所有结点，在相反操作
// q次操作后，所有结点的状态
// n<=1e5, q<=1e5
// 把操作维护到所有的结点上，然后做dfs进行下放，利用奇偶性变更结点的状态

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

vector<int> h[N];
int n, q;
int op[N];
string s;

void dfs(int u, int fa) {
    for (auto i : h[u]) {
        if (i == fa) continue;

        op[i] += op[u];
        op[i] %= 2;
        dfs(i, u);
    }
}

int main() {
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int fa;
        cin >> fa;
        h[fa].push_back(i);
    }
    cin >> s >> q;
    while (q--) {
        int x;
        cin >> x;
        op[x] ++;
        op[x] %= 2;
    }

    dfs(1, -1);
    for (int i = 0; i < n; i++)
        if (op[i + 1] % 2 == 1) {
            if (s[i] == '0') s[i] = '1';
            else s[i] = '0';
        }

    cout << s;

    return 0;
}

代码02

// 一颗二叉树，结点是0或者1
// 每次操作，会将这个结点的子树内的所有结点，在相反操作
// q次操作后，所有结点的状态
// n<=1e5, q<=1e5
// 把操作维护到所有的结点上，然后做dfs进行下放，利用奇偶性变更结点的状态
// 没构造测试点，就直接交了，竟然直接AC了。用时14分钟
// 改成异或的方式

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

vector<int> h[N];
int n, q;
int op[N];
string s;

void dfs(int u, int fa) {
    for (auto i : h[u]) {
        if (i == fa) continue;

        op[i] ^= op[u];
        dfs(i, u);
    }
}

int main() {
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int fa;
        cin >> fa;
        h[fa].push_back(i);
    }
    cin >> s >> q;
    while (q--) {
        int x;
        cin >> x;
        op[x] ^= 1;
    }

    dfs(1, -1);
    for (int i = 0; i < n; i++)
        if (op[i + 1] == 1) {
            if (s[i] == '0') s[i] = '1';
            else s[i] = '0';
        }

    cout << s;

    return 0;
}

P11246 [GESP202409 六级] 小杨和整数拆分

提示

将n拆分成完全平方数之和，拆分个数越少越好

求方案数类型的dp

代码

// 将n拆分成完全平方数之和，拆分个数越少越好
// 求方案数类型的dp

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int f[N], n;

bool check(int n) {
    int x = sqrt(n);

    return x * x == n;
}

int main() {
    cin >> n;

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

        if (check(f[i])) {
            f[i] = 1;
            continue;
        }

        // 看了题解，这里只需要 右边这部分的完全平方数
        // 枚举的时候，是构造出来的完全平方数
        for (int j = 1, len = sqrt(i); j <= len; j++) 
            f[i] = min(f[i], f[i - j * j] + 1);
    }

    cout << f[n];

    return 0;
}

代码02

#include <bits/stdc++.h>

using namespace std;

int n;
int dp[100010];

int main(){
    memset(dp, 0x3f, sizeof dp);
    cin >> n;
    dp[0] = 0;
    dp[1] = 1;
    for(int i = 2; i <= n; i ++){
        for(int j = 1; j <= i / j; j ++){
            dp[i] = min(dp[i], dp[i - j * j] + 1);
        }
    }

    cout << dp[n];
    return 0;
}

P11247 [GESP202409 六级] 算法学习

提示

70%数据，m, n <=9，可以利用两层循环，不断枚举

100%数据，m,n<=1e5，把每个算法放到一个开放链表里，每个链表按bi从大到小排序

代码

// 70%数据，m, n <=9，可以利用两层循环，不断枚举
// 100%数据，m,n<=1e5，把每个算法放到一个开放链表里，每个链表按bi从大到小排序
// 创建一个队列，每个<k的算法，入队。循环执行队列中，没有学完的算法（类似报数出队问题）
// 如果h[i]空了，但是第i种算法，还是小于k，肯定-1
// 用一个last来维护，上一次学习是什么算法，如果队列中只剩下一个元素的时候，last碰撞，就输出-1

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m, k;
vector<int> h[N];
struct node {
    int a, b;
}p[N];
int last = -1;
int score[N];
int ret;

bool cmp(node a, node b) {
    if (a.a != b.a) return a.a < b.a;
    return a.b > b.b;
}

int main() {
    cin >> m >> n >> k;
    for (int i = 0; i < n; i++) cin >> p[i].a;
    for (int i = 0; i < n; i++) cin >> p[i].b;
    sort(p, p + n, cmp);

    for (int i = 0; i < n; i++) h[p[i].a].push_back(p[i].b);

//  for (int i = 1; i <= m; i++) {
//      printf(":---%d\n", i);
//      for (auto x : h[i]) cout << x << ' '; puts("");}

    queue<int> q;
    for (int i = 1; i <= m; i++) q.push(i);

    bool flag = false;
    while (!q.empty()) {
        int t = q.front(); q.pop();
        if (h[t].size() == 0 || t == last) {
            flag = true;
            break;
        }

        vector<int>::iterator it = h[t].begin();
        score[t] += *it;
        ret++;
        last = t;

        if (score[t] < k) q.push(t);

        h[t].erase(it);
    }

    if (flag) cout << -1;
    else cout << ret;

    return 0;
}

代码02

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int m, n, k;
pair<int, int> a[N];
int b[N], c[N], maxn, cnt, ans;
bool flag;

int main() {
    cin >> m >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i].second;
    for (int i = 1; i <= n; i++) cin >> a[i].first;

    // 按收益从小到大排序
    sort(a + 1, a + 1 + n);

    for (int i = n; i >= 1; i--) {
        if (b[a[i].second] < k) {
            b[a[i].second] += a[i].first;
            if (b[a[i].second] >= k) cnt++;

            ans++;

            c[a[i].second]++;
            maxn = max(maxn, c[a[i].second]);
        }
    }

    if (cnt != m || maxn > (n + 1) / 2) cout << -1;
    else cout << max(ans, maxn * 2 - 1); // 要么是用了多少题，要么是需要额外的题补充插空避免连续两道相同的题

    return 0;
}

P11375 [GESP202412 六级] 树上游走

提示

二叉树，结点i的左儿子2i，右儿子2i+1

问移动n次后，位于哪个结点

向上和向下，走是会抵消的

代码

// 二叉树，结点i的左儿子2i，右儿子2i+1
// 问移动n次后，位于哪个结点

// 向上和向下，走是会抵消的
// 并且题目的最后，明确了，最终结果不会爆long long
// 所以要模拟这个抵消过程，而不是实际走的过程

#include <bits/stdc++.h>

using namespace std;

const long long INF = 1e12;

int main() {
    long long n, i;
    string s;
    cin >> n >> i >> s;

    int t = 0;
    for (auto c : s) {
        if (c == 'U') {
            if (i / 2 >= 1) {
                if (t) t--;
                else i /= 2;
            }
        }
        if (c == 'L') {
            if (2 * i > INF) t++;
            else i = 2 * i;
        }
        if (c == 'R') {
            if (2 * i + 1> INF) t++;
            else i = 2 * i + 1; 
        }
    }

    cout << i;

    return 0;
}

代码02

// 题意
// 思路：超过1e12的时候，不要真的走

#include <bits/stdc++.h>

using namespace std;

const long long inf = 1e12;

long long n, p, cnt;
string s;
stack<char> stk;

int main() {
    cin >> n >> p >> s;

    for (auto c : s) {
        if (c == 'U') {
            if (!stk.empty()) stk.pop();
            else {
                if (p > 1) p /= 2;
            }
        }
        if (c == 'L') {
            if (p * 2 > inf) stk.push('L');
            else p *= 2;
        }
        if (c == 'R') {
            if (p * 2 + 1 > inf) stk.push('R');
            else p = p * 2 + 1;
        }
    }

    cout << p << '\n';

    return 0;
}

P11376 [GESP202412 六级] 运送物资

提示

[A, B]两个城市之间有一些运输站，每个运输站有ci的容量限制

m 个货车，ai趟送A，bi趟送B

将这些货车，安排到这些运输站里，使得整体的运输成本最少

ai >= bi 的货车，放在一起，排序，差值越大的靠前，从左到右遍历分配

ai < bi 的货车，放在一起，排序，bi-ai 差值越大的靠前，从右到左分配

代码

// [A, B]两个城市之间有一些运输站，每个运输站有ci的容量限制
// m个货车，ai趟送A，bi趟送B
// 将这些货车，安排到这些运输站里，使得整体的运输成本最少

// ai >= bi 的货车，放在一起，排序，差值越大的靠前，从左到右遍历分配
// ai < bi 的货车，放在一起，排序，bi-ai 差值越大的靠前，从右到左分配
// 贪心思想

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 +10;

int n, m, x;
pair<int, int> p[N];
struct node {
    int a, b, delta;

}A[N], B[N];
int idxa, idxb;

bool cmp(node a, node b) {
    return a.delta > b.delta;
}

long long ret;

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

    // 车站从左到右排好序
    for (int i = 0; i < n; i++) cin >> p[i].first >> p[i].second;
    sort(p, p + n);

    // 这些货车排好序
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        if (a >= b) A[idxa++] = {a, b, a - b};
        else B[idxb++] = {a, b, b - a};
    }
    sort(A, A + idxa, cmp);
    sort(B, B + idxb, cmp);

    int L = 0;
    for (int i = 0; i < idxa; i++) {
        if (p[L].second >= 1) {
            ret += 1ll * A[i].a * p[L].first * 2;
            ret += 1ll * A[i].b * (x - p[L].first) * 2;
            p[L].second--;
        }
        else {
            L++;
            ret += 1ll * A[i].a * p[L].first * 2;
            ret += 1ll * A[i].b * (x - p[L].first) * 2;
            p[L].second--;  
        }
    }

    int R = n - 1;
    for (int i = 0; i < idxb; i++) {
        if (p[R].second >= 1) {
            ret += 1ll * B[i].a * p[R].first * 2;
            ret += 1ll * B[i].b * (x - p[R].first) * 2;
            p[R].second--;
        }
        else {
            R--;
            ret += 1ll * B[i].a * p[R].first * 2;
            ret += 1ll * B[i].b * (x - p[R].first) * 2;
            p[R].second--;  
        }
    }

    cout << ret;

    return 0;
}

P11962 [GESP202503 六级] 树上漫步

提示

一棵树，从一个结点出发，走偶数步，可以结束漫步过程

问从每个结点出发，可以结束漫步的结点，有多少个

代码

// 一棵树，从一个结点出发，走偶数步，可以结束漫步过程
// 问从每个结点出发，可以结束漫步的结点，有多少个
// n<=2e5

// 对于n<=1e3的数据，我们可以从每个结点，进行一遍bfs，维护到其他点的距离，如果是偶数的，就是可以结束漫步的
// 这是n^2的

// 我们可以维护，每个结点到根结点的距离，作为共同的祖先。看到祖先的距离差值，是不是偶数
// 用bfs维护出最短路，距离是奇数有多少，距离偶数有多少 答案就有了

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

vector<int> h[N];
int n, d[N], odd, even;

void bfs() {
    memset(d, 0x3f, sizeof d);
    queue<int> q;
    q.push(1);
    d[1] = 0;

    while (!q.empty()) {
        int t = q.front(); q.pop();
        for (auto u : h[t]) {
            if (d[u] != 0x3f3f3f3f) continue;
            d[u] = d[t] + 1;
            q.push(u);
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        h[a].push_back(b); h[b].push_back(a);
    }

    bfs();

    for (int i = 1; i <= n; i++) 
        if (d[i] % 2) odd++;
        else even++;

    for (int i = 1; i <= n; i++)
        if (d[i] % 2) cout << odd << ' ';
        else cout << even << ' ';

    return 0;
}

P11963 [GESP202503 六级] 环线

提示

不跨环的情况，就是[1..n]的最大字段和

跨环的情况，两头是选的，中间有一部分是不选的。那么就是[1..n]的和，减去，中间的最小子段和

代码

// 不跨环的情况，就是[1..n]的最大字段和
// 跨环的情况，两头是选的，中间有一部分是不选的。那么就是[1..n]的和，减去，中间的最小子段和

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
typedef long long ll;

ll a[N], n;
ll maxn = -1e18, minn = 1e18;
ll total;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        total += a[i];
    }

    ll sum = 0, sum2 = 0;
    for (int i = 1; i <= n; i++) {
        sum = max(sum + a[i], a[i]);
        maxn = max(maxn, sum);

        sum2 = min(sum2 + a[i], a[i]);
        minn = min(minn, sum2);
    }   



    cout << max(maxn, total - minn == 0 ? maxn: total - minn);

    return 0;
}

代码02

// 单调队列

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
typedef long long ll;

ll a[N * 2], s[N * 2], n;
int q[N * 2], l, r;
ll ans = -1e18;

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

    for (int i = 1; i <= n * 2; i++) s[i] = s[i - 1] + a[i];

    // q[....] 存放的是，
    // 从小到大，i之前的比s[i]都小的前缀和
    // 单调的
    for (int i = 1; i <= n * 2; i++) {
        while (l <= r && i - q[l] > n) l++;  // 左边滑动出去的部分
        ans = max(ans, s[i] - s[q[l]]);
        while (l <= r && s[q[r]] > s[i]) r--; // 右边不符合需求的前缀和，吐掉
        q[++r] = i; // 入队
    }

    cout << ans;

    return 0;
}

P13015 [GESP202506 六级] 学习小组

提示

两种dp的写法，都要理解一下。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int a[N], n, dp[N]; // dp[i]表示i个人可以获得的最大价值

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

    // 线性dp
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++) 
            dp[i] = max(dp[i], dp[j] + a[i - j]);

    cout << dp[n];

    return 0;
}

代码02

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int v[N], w[N], n, dp[N]; // 完全背包

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

    for (int i = 1; i <= n; i++)
        for (int j = w[i]; j <= n; j++) 
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

    cout << dp[n];

    return 0;
}

P13016 [GESP202506 六级] 最大因数

代码

// 每次向上爬一个结点，这个结点就是自己的最大因数
// 模拟可得60pts

#include <bits/stdc++.h>

using namespace std;

bool is_prime(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= n / i; i++)
        if (n % i == 0) return false;

    return true;
}

int main() {
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;

        int step = 0;
        // 找x,y的最大公约数
        while (x != y) {
            if (x > y) swap(x, y);
            if (is_prime(y)) {
                step++;
                y = 1;
                continue;
            }

            for (int i = 2; ; i++)
                if (y % i == 0) {
                    step++;
                    y = y / i;

                    break;
                }
        }

        cout << step << '\n';
    }



    return 0;
}

代码02

// 官方题解思路
// 把x,y进行分解因子，放到一个数组里
// x = 12
// 12 2 2 3
//    6 3 1
// 下面这一行，b[i] = a[i - 1] / a[i], 这个b[i]就是父结点

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int a[N], b[N];
int prime[N];

void f(int x, int a[]) {
    a[0] = x;

    int idx = 0;
    for (int i = 2; i <= x / i; i++)
        while (x % i == 0) prime[++idx] = i, x /= i;

    if (x > 1) prime[++idx] = x;

    // 存向上的父结点链路，向上爬
    for (int i = 1; i <= idx; i++) a[i] = a[i - 1] / prime[i];
}

int main() {
    int q;
    cin >> q;

    while (q--) {
        int x, y;
        cin >> x >> y;

        f(x, a);
        f(y, b);

        int i = 0, j = 0;
        while (a[i] != b[j]) {
            if (a[i] > b[j]) i++;
            else j++;
        }

        cout << i + j << '\n';
    }

    return 0;
}

P14075 [GESP202509 六级] 划分字符串

提示

dp[i]表示以i结尾可以获得的最大价值

O(n*26)，每次从i的位置向前找可以切分的子串长度，虽然是两层循环

但是因为都是小写字母，最多循环26次就肯定会重复

代码

// dp[i]表示以i结尾可以获得的最大价值
// O(n*26)，每次从i的位置向前找可以切分的子串长度，虽然是两层循环
// 但是因为都是小写字母，最多循环26次就肯定会重复

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

long long dp[N];
int a[N], n;
string s;

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

    for (int i = 1; i <= n; i++) {
        map<char, int> mp;
        // j枚举的是右边子串的第一个位置
        for (int j = i; j >= 1; j--) {
            if (mp.count(s[j - 1])) break;
            mp[s[j - 1]] = 1;

            dp[i] = max(dp[i], dp[j - 1] + a[i - j + 1]);
        }
    }

    cout << dp[n];

    return 0;
}

代码02

// dp[i]表示以i结尾可以获得的最大价值
// O(n*26)，每次从i的位置向前找可以切分的子串长度，虽然是两层循环
// 但是因为都是小写字母，最多循环26次就肯定会重复

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

long long dp[N];
int a[N], n;
string s;

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

    s = ' ' + s;
    dp[1] = a[1];
    for (int i = 1; i <= n; i++) {
        map<char, int> mp;
        for (int j = i - 1; j >= 1; j--) {
            if (mp.count(s[j])) break;
            mp[s[j]] = 1;

            dp[i] = max(dp[i], dp[j] + a[i - j]);
        }
    }

    cout << dp[n];

    return 0;
}

P14076 [GESP202509 六级] 货物运输

提示

重新思考题意，我们发现这是一颗树

一颗树有很多分支，分支最长的那条，只走一遍。其他分支走两遍

代码

// 重新思考题意，我们发现这是一颗树
// 一颗树有很多分支，分支最长的那条，只走一遍。其他分支走两遍
// 答案就是 所有边长的和*2-最长的那边分支

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e5 + 10;

vector<pair<int, int>> h[N];
int n;
ll sum;
bool vis[N];
set<int> st;
ll maxn;

void dfs(int u, ll len) {
    int cnt = 0;
    for (auto x : h[u]) {
        if (!vis[x.first]) {
            cnt++;
            vis[x.first] = true;
            dfs(x.first, len + x.second);
            vis[x.first] = false;
        }
    }

    if (cnt == 0)  maxn = max(maxn, len);
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, l;
        cin >> u >> v >> l;
        h[u].push_back({v, l});
        h[v].push_back({u, l});
        sum += l;
    }

    vis[1] = true;
    dfs(1, 0);
    cout << sum * 2 - maxn;

    return 0;
}