Sliding Cost

题目链接：https://cses.fi/problemset/task/1077

题目大意：你得到一个包括 n 个数的数组。你的任务是计算每个包含 k 个元素窗口，从左到右，使所有元素相等的最小总成本。你可以增加或减少每个元素，成本是是新值和原始值之间的差值。

解题思路：易得最小花费就是把所有数变成中位数，类似于滑动窗口，假设一个已经算好结果的窗口答案为 $ans_i$ ，那么滑动到下一个窗口，如果中位数没有变化，那么答案就是 $ans_i-abs(a[i-k]-mid)+abs(a[i+1]-mid)$ ，如果中位数变化了，我们分奇偶讨论，如果是奇数，比中位数大的和比中位数小的数是一一对应的，即使中位数发生变化，也没有影响，那么答案就是上式，如果是偶数，相比奇数会多出一个数，那么这个数需要单独处理，也就是说它会产生额外贡献，而它的贡献就是中位数变化的绝对值

int n, k, l, r, a[N];
ordered_set s;
void solve() {
    cin >> n >> k;
    lep(i, 1, n) cin >> a[i];
    lep(i, 1, k) s.insert(a[i]);
    ll ans = 0;
    l = *s.find_by_order(k / 2);
    lep(i, 1, k) ans += abs(l - a[i]);
    cout << ans << " ";
    lep(i, k + 1, n) {
        s.erase(s.find_by_order(s.order_of_key(a[i - k])));
        s.insert(a[i]);
        r = *s.find_by_order(k / 2);
        ans += abs(r - a[i]) - abs(l - a[i - k]);
        if (!(k & 1)) ans += r - l;
        l = r;
        cout << ans << " ";
    }
}

Monster Hunter

题目链接：https://codeforces.com/gym/102992/problem/M

题目大意：给你一棵树，树上每个节点都有怪兽，生命值为 $hp_i$ ,消灭某个节点的怪兽的花费是该怪兽的生命值加上所有与它距离为 1 的子节点的生命值之和，只有当某个节点的父节点的怪兽被消灭后，才可以攻击该节点的怪兽。现在你可以使用 m 次魔法，可以无限制且 0 花费的消灭 m 个节点的怪兽。当 $m=0,1,2...n$ 时，消灭所有怪兽的最小花费是多少
解题思路：设 $dp[u][n][2]$ 表示以 u 为根的子树，还剩下 n 个子节点没删，u 删没删的最小花费

$dp[u][i+j][0]=min(dp[u][i+j][0],dp[u][i][0]+min(dp[v][j][0],dp[v][j][1]))\\ dp[u][i+j][1]=min(dp[u][i+j][1],dp[u][i][1]+min(dp[v][j][0],dp[v][j][1]+w[v]))$

int n, sz[2007];
vector<int> G[2007];
ll dp[2007][2007][2], w[2007];
void dfs(int u, int fa) {
    dp[u][0][0] = 0;
    dp[u][1][1] = w[u];
    sz[u] = 1;
    for (auto v : G[u]) {
        if (v == fa) continue;
        dfs(v, u);
        rep(i, sz[u], 0) {
            rep(j, sz[v], 0) {
                dp[u][i + j][0] =
                    min(dp[u][i + j][0],
                        dp[u][i][0] + min(dp[v][j][0], dp[v][j][1]));
                dp[u][i + j][1] =
                    min(dp[u][i + j][1],
                        dp[u][i][1] + min(dp[v][j][0], dp[v][j][1] + w[v]));
            }
        }
        sz[u] += sz[v];
    }
}
void solve() {
    cin >> n;
    lep(i, 1, n) G[i].clear();
    lep(i, 0, n + 1) lep(j, 0, n + 1) dp[i][j][0] = dp[i][j][1] = 1e16;
    lep(i, 2, n) {
        int x;
        cin >> x;
        G[x].push_back(i);
    }
    lep(i, 1, n) cin >> w[i];
    dfs(1, 0);
    rep(i, n, 0) cout << min(dp[1][i][0], dp[1][i][1]) << ' ';
    cout << '\n';
}

Paimon Sorting

题目链接：https://codeforces.com/gym/103470/problem/D

题目大意：定义 SORT(A) 为

for(int i=1;i<=n;i++)
 for(int j=1;j<=n;j++)
  if(a[i]<a[j])
   swap(a[i],a[j]);

对于序列中的每一个 k ,执行 SORT 算法 swap 的次数是多少

解题思路：SORT 的本质就是对于每一个 i ，把 $a_i$ 放到序列的第一个，然后找单调栈， swap 的次数就是单调栈的数目减一，且前 i-1 个数是有序的

考虑如果已经知道前 i-1 个数的答案，插入第 i 个数的时候

如果它小于等于序列的最大值的话，那么在最后一轮之前，它都不会交换，而在最后一轮的时候，新增的 swap 次数就是单调栈比它大的数的个数
如果大于序列的最大值，假设次大值（也就是原序列的最大值）只有一个，那么当最大值与次大值交换后，就会变成小于等于的情况，那么对于答案的贡献就是 2 。如果不止一个，那么最大值会跟第二个次大值之后的每一个数交换位置，需要加上这些新的贡献

int n, x, id;
int a[N][2];
void solve() {
    cin >> n;
    ordered_set s;
    lep(i, 1, n) a[i][0] = a[i][1] = -1;
    cin >> x;
    s.insert(x);
    a[x][0]=0;
    ll ans = 0;
    lep(i, 1, n - 1) {
        cin >> x;
        cout << ans << " ";
        if (x > *s.rbegin()) {
            id = *s.find_by_order(s.order_of_key(x) - 1);
            if (a[id][1] != -1) ans += i - a[id][1];
            ans += 2;
        } else {
            id = s.order_of_key(x + 1);
            ans += s.size() - id;
        }
        s.insert(x);
        if (a[x][0] != -1) {
            if (a[x][1] == -1) a[x][1] = i;
        } else
            a[x][0] = i;
    }
    cout << ans << endl;
}

Crystalfly

题目链接：https://codeforces.com/gym/103470/problem/H

题目大意：给你一棵树，树上每个点都有相应的价值，第 0 秒的时候，你在一号节点，接下来每一秒你可以选择移动到相邻的节点上或者停在原地，当你到达某个节点的时候，你可以得到该节点的权值。不过当你到达某个节点时，它的所有子节点都会被扰动，权值会在 $t_i(1\le t \le 3)$ 时间后消失，问你在经过 $10^{10^{10}}$ 秒后可以得到的最大权值和是多少

解题思路：设 $f_u$ 表示节点 $u$ 在我们未进入之前已经激活，而它的所有儿子没有激活的最优答案， $sum_u$ 表示 $u$ 的所有儿子的 $f_v$ 之和，那么要求的答案就是 $w_1+f[1]$ ，当 $t_i\le2$ 时，最优策略是一路向下，当 $t_i=3$ 时，可以先选择一个其它节点，再返回取这个节点。对于这两种策略的方程如下：

$f[u]=max(f[u],sum[u]+w[v])$
$f[u] = max(f[u], sum[u] - f[v] + sum[v] + w[v] + *s.rbegin())$

int n, t[N];
vector<int> G[N];
ll w[N], f[N], sum[N];
void solve() {
    cin >> n;
    lep(i, 1, n) {
        G[i].clear();
        f[i] = sum[i] = 0;
        cin >> w[i];
    }
    lep(i, 1, n) cin >> t[i];
    lep(i, 1, n - 1) {
        int u, v;
        cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    function<void(int, int)> dfs = [&](int u, int fa) {
        multiset<int> s;
        for (auto v : G[u]) {
            if (v == fa) continue;
            dfs(v, u);
            sum[u] += f[v];
            if (t[v] == 3) s.insert(w[v]);
        }
        s.insert(-1e9);
        for (auto v : G[u]) {
            if (v == fa) continue;
            if (t[v] == 3) s.erase(s.find(w[v]));
            f[u] = max(f[u], sum[u] - f[v] + sum[v] + w[v] + *s.rbegin());
            if (t[v] == 3) s.insert(w[v]);
            f[u] = max(f[u], sum[u] + w[v]);
        }
    };
    dfs(1, 0);
    cout << w[1] + f[1] << endl;
}

Algorithm Solution

Algorithm

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

July 2022 Algorithm Solution 上一篇

May 2022 Algorithm Solution 下一篇

June 2022 Algorithm Solution

Sliding Cost

Monster Hunter

Paimon Sorting

Crystalfly