Mashup Trainings Day 3: F0RE1GNERS' Contest 题解整合

ultmaster edited 3 月前

Problem A

wiki

Problem B

看似有零,其实没零。要打请打 kblack

UPD: 加强了数据,结果 网上随便找的 std 好像挂了(难以置信)。现在数据可能是错的了。(妙啊)

方法一:类似 这题 的做法,加上减号以后更简单了, 转移到 ,老方法线段树维护。

方法二:注意到因为加减号同时存在,一旦不是乘号,接下来所有的式子都有对偶可以抵消,于是转化成求前缀积乘常数的和,线段树维护,遇到 的时候没有逆元可以做特殊记号处理。

Problem C

wiki

Problem D

Qingdao 2017.

根据题意模拟即可。请确保你的板子是对的。

Problem E

题意:有根树上有 个节点,每个节点上有一个技能,每氪一点钱,技能就能升一级。如果掌握技能等级为 ,就可以获得 的收益。第 个技能最高等级为 。同时,如果要掌握技能 ,父亲节点上的技能至少要达到 级。求在给定开销范围内,能得到的最大收益。

题解:这题官方题解是日文的。网上也没有相关的可阅读的材料。所以如果有错误欢迎指出。

考虑下述简化版问题:普通的 01 背包,物品之间存在一种树形的依赖关系(要取当前物品的话,父亲物品必须取)。这个问题的话,很容易想到一种树形 DP,记 f[u][w] 为 u 的子树,重量为 w 的最大收益。转移的时候要将若干子树合并。复杂度是 ;计数问题的话,可以用 FFT 优化到 ,但意义并不大。但是:其实可以不合并子树的。假设节点 u 有孩子 a, b, c。可以这么考虑:

还是不理解的可以自行网搜「树形依赖背包」。网上的方法可能与这里介绍的方法在「更新顺序」上不大一样。

考虑原问题,原问题的难点在于:不同的子树对于 u 的个数的依赖是不同的,而且 u 可以选的个数可能比被依赖的要更多(也就是说,是多重背包问题)。

到此为止本问题已经全部解决,时间复杂度是 。常数较大,可能需要优化得比较好才能过。

核心代码如下:

vector<int> G[N];
int n; LL K;
LL h[N], s[N], p[N], l[N];
LL f[N][M], g[M];

void up(LL& a, const LL& b) { a = max(a, b); }

void backpack(LL *now, LL price, LL num, LL *ret) {
    deque<pair<LL, int> > q;
    FOR (i, 0, K + 1) {
        LL v = now[i] - i * price;
        while (!q.empty() && q.back().first <= v) q.pop_back();
        q.emplace_back(v, i);
        ret[i] = q.front().first + i * price;
        if (q.front().second == i - num) q.pop_front();
    }
}

void go(int u, LL* dp) {
    backpack(dp, s[u], h[u], f[u]);
    for (int &v: G[u]) {
        go(v, dp);
        dp = f[v];
        backpack(dp, s[u], h[u] - l[v], g);
        FOR (i, 0, K + 1 - l[v])
            up(f[u][i + l[v]], g[i] + s[u] * l[v]);
    }
}

int main() {
    FOR (i, 1, n + 1)
        sort(G[i].begin(), G[i].end(), [](int a, int b) { return l[a] < l[b]; });
    go(1, f[0]);
    cout << f[1][K] << endl;
}

Problem F

wiki

大家这个随机化水平还是高的啊。

我放了放时限结果放过了随机化。现在时限又改成 5 秒了。

Problem G

网上 大概说得比我清楚。

Problem H

HackerRank

blog

Problem I

HackerRank
官方题解很详细

Problem J

wiki

Problem K

wiki

Comments

你正在回复博客
存在问题!