AtCoder Beginner Contest 252

比赛链接

D Distinct Trio

Description

题目链接

Solution

考虑容斥，设 $pre[a_i]$ 表示 $i$ 之前和 $a_i$ 相同的数的个数，$suf[a_i]$ 表示 $i$ 之后和 $a_i$ 相同的数的个数。对于给定的 $j$，答案可以表示为 $(j - 1)*(n - j) - \sum_k pre[k]suf[k] - pre[a_j] * (n - j) - suf[a_j] * (j - 1) + 2 * pre[a_j] * suf[a_j]$，即从总的方案数中扣除 $a_i$ 和 $a_k$ 相同的方案数，再扣除 $a_i = a_j$ 或 $a_j = a_k$ 的方案数。由于 $a_i = a_j = a_k$ 的方案数被扣除了两次，因此要加回去。$pre$，$suf$ 以及 $\sum_k pre[k]suf[k]$ 可以在顺序遍历时 $O(1)$ 更新，因此总的时间复杂度为 $O(n)$。

Code

Distinct Trio

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl
#define int long long

using namespace std;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int n, m, T, a[MAXN], pre[MAXN], suf[MAXN];
int ans;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i < n) pre[a[i]]++;
    }
    int eq = 0, ans = 0;
    for (int i = n - 1; i >= 2; i--) {
        eq -= suf[a[i]] * pre[a[i]];
        if (a[i] != a[i + 1]) eq -= suf[a[i + 1]] * pre[a[i + 1]];
        suf[a[i + 1]]++;
        pre[a[i]]--;
        eq += suf[a[i]] * pre[a[i]];
        if (a[i] != a[i + 1]) eq += suf[a[i + 1]] * pre[a[i + 1]];
        int tmp = (i - 1) * (n - i) - eq;
        tmp -= (i - 1) * suf[a[i]];
        tmp -= (n - i) * pre[a[i]];
        tmp += suf[a[i]] * pre[a[i]] * 2;
        ans += tmp;
    }
    cout << ans;
    return 0;
}

E Road Reduction

Description

题目链接

Solution

设 $D_i$ 表示从节点 $1$ 到节点 $i$ 的最短路，则对 $\forall i$，有 $d_i \ge D_i$。因此，需要保留的道路是最短路树上的边，在求最短路时记录起点到各个节点最短路的最后一条边即可。

Code

Road Reduction

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

#define int long long

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int n, m, T;
int dis[MAXN], lastEdge[MAXN];
bool vis[MAXN];
vector<tuple<int, int, int>> G[MAXN];

signed main() {
    // freopen("1.in", "r", stdin);
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w, i});
        G[v].push_back({u, w, i});
    }
    for (int i = 2; i <= n; i++) dis[i] = LONG_LONG_MAX;
    priority_queue<pair<int, int>> q;
    q.push({0, 1});
    while (!q.empty()) {
        auto [d, cur] = q.top();
        q.pop();
        if (vis[cur]) continue;
        vis[cur] = 1;
        for (auto& [to, w, i] : G[cur]) {
            if (dis[to] > dis[cur] + w) {
                dis[to] = dis[cur] + w;
                lastEdge[to] = i;
                if (!vis[to]) q.push({-dis[to], to});
            }
        }
    }
    for (int i = 2; i <= n; i++) cout << lastEdge[i] << " ";
    return 0;
}

F Bread

Description

题目链接

Solution

倒着考虑，问题转化为求合并面包的最小代价，每次选取代价最小的两块合并即可。需要注意的是，如果有剩下的面包，那么剩下的面包也需要被合并。显然剩下的面包只有一块，因为对剩下的面包再做分割会增大合并的代价。

Code

Bread

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
LL n, l, a[MAXN];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> l;
    priority_queue<LL, vector<LL>, greater<LL>> q;
    LL sum = 0;
    for (int i = 1; i <= n; i++) cin >> a[i], q.push(a[i]), sum += a[i];
    if (sum != l) q.push(l - sum);

    LL ans = 0;
    while (q.size() >= 2) {
        LL v1 = q.top();
        q.pop();
        LL v2 = q.top();
        q.pop();
        ans += v1 + v2;
        q.push(v1 + v2);
    }
    cout << ans;
    return 0;
}

G Pre-Order

Description

题目链接

Solution

$a[l...r]$ 表示了以 $a[l]$ 为根的树的先序遍历结果。我们将根去掉，就得到了 $a[l + 1...r]$，它表示 $a[l]$ 的子树构成的森林的先序遍历结果，且子树的根节点的编号是递增的。

根据上述观察结果，考虑动态规划。设 $t[l][r]$ 表示先序遍历为 $a[l...r]$ 的树的个数，$f[l][r]$ 表示先序遍历为 $a[l...r]$ 的森林的个数。那么有如下状态转移方程：

• $t[l][r] = f[l + 1][r]$
• $f[l][r] = \sum \limits_{k = l + 1}^{r} t[l][k - 1] * f[k][r] * (a[l] < a[k])$。

最终答案为 $t[1][n]$。

Code

Pre-Order

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 5E2 + 5;
const int MOD = 998244353;
int n, a[MAXN];
int t[MAXN][MAXN], f[MAXN][MAXN];

void add(int& a, int b) { a = (a + b) % MOD; }

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], t[i][i] = 1, f[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            add(t[l][r], f[l + 1][r]);
            for (int k = l + 1; k <= r; k++)
                if (a[l] < a[k])
                    add(f[l][r], 1ll * t[l][k - 1] * f[k][r] % MOD);
            add(f[l][r], t[l][r]);
        }
    }
    cout << t[1][n];
    return 0;
}