ch03 部分题目思路

发布于:2025-07-07 ⋅ 阅读:(12) ⋅ 点赞:(0)

G. 收集

由于稀有度相同的物品需要一起处理,我们先把他们聚集到一起。
类似这样:

vector<int> g[maxn];
...
{
  cin >> x >> c;
  g[c].push_back(x);
}

那么我们需要一个贪心的思路:

  • 肯定是按 ccc 从小往大收集的;
  • 对于相同的 ccc 收集完最后一个肯定是要么停留最左边要么停留在最右边

故设 dp(i,0)dp(i,0)dp(i,0) 表示收集完稀有度为 iii 的物品后停留在最左边,dp(i,1)dp(i,1)dp(i,1) 则表示停留在最右边。

对于转移,则是讨论一下:

  • 收集完第 i−1i-1i1 层的物品后,在最左边还是最右边,将来要停留在这一层的最左边还是最右边,即 dp(i−1,0/1)dp(i-1,0/1)dp(i1,0/1) 转移到 dp(i,0/1)dp(i,0/1)dp(i,0/1)

注意的是,可能存在某一层是没有物品的,而下一层是有物品的,需要存储上一层的 c,设其为 pre。则状态转移使用 dp[pre][]dp[pre][]dp[pre][] 而不是 dp[i−1][]dp[i-1][]dp[i1][]

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll a[200010][2], x;
ll dp[200010][2]; // dp[i][0]: 从小到大走;dp[i][1]:从大往小走
bool vis[200010];
int main() {
    int n, c;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        a[i][0] = INT_MAX; // c == i 的位置最小值
        a[i][1] = INT_MIN; // c == i 的位置最大值
    }
    for (int i = 1; i <= n; ++i) {
        cin >> x >> c;
        a[c][0] = min(a[c][0], x);
        a[c][1] = max(a[c][1], x);
        vis[c] = 1;
    }
    int p = 0; // 前一个 c
    vis[n + 1] = 1; // 最后一层回到位置 0, a[n+1][0] = a[n+1][1] = 0
    for (int i = 1; i <= n + 1; ++i) {
        if (!vis[i]) continue;
        for (int j = 0; j < 2; ++j) {
            dp[i][j] = min(abs(a[p][0] - a[i][j]) + dp[p][1], 
                abs(a[p][1] - a[i][j]) + dp[p][0]) + a[i][1] - a[i][0]; 
        }
        p = i;
    }
    cout << dp[n + 1][0] << endl;
    return 0;
}

H. 选择

对于每一个 iii,我们考虑让 aia_iaibib_ibi 之间建一条边,则这些边之间形成了若干个环
则原问题等价于对于每个环,任意两条相邻的边至少选一条,不同的环之间没有限制
dp 算出每个环选点的方案数,然后再乘起来,就是总的方案数

  • 相信大家都会做一排物品,相邻两件至少选一件,求方案数记作 f[i]

  • 现在处理环记作 g[i],将下面两个方案相加

    • 最后一个不选:f[i-3]
    • 最后一个选:f[i-1]

可以先递推计算 f,再递推计算 'g'

也可以整理得到: g[i] = f[i-3] + f[i-1] = (f[i-4]+f[i-5]) + (f[i-2]+f[i-3]) = (f[i-2]+f[i-4]) + (f[i-3]+f[i-5]) = g[i-1] + g[i-2]

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll M = 998244353;
const int maxn = 2e5 + 10;

// 相邻的数至少选一个
// 线性:f[i] = f[i-2] + f[i-1]
// 环形:g[i] = f[i-3] + f[i-1] --> g[i] = g[i-1] + g[i-2]
ll g[maxn];
int a[maxn], bi, nxt[maxn];
bool vis[maxn];
int main() {
    g[1] = 1, g[2] = 3;
    for (int i = 3; i < maxn; ++i) {
        g[i] = (g[i - 1] + g[i - 2]) % M;
    }

    int n, x, b;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        cin >> bi;
        nxt[a[i]] = bi;
    }
    ll res = 1;
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            int p = i, cnt = 0;
            while (!vis[p]) {
                vis[p] = 1, ++cnt;
                p = nxt[p];
            }
            res = res * g[cnt] % M;
        }
    }
    cout << res << endl;
    return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到