Atcoder Beginner Contest 369 题解

竞赛结果：Contestant,4815th,Solved ABD,-14

note

1. 博主忘了写补题博客了
2. 本场进行时正在线下进行新生赛后台，打的不好。C题居然没想出来。

todo

1. 因为是补作，时间比较紧迫不再提供题目大意，下场恢复，这场择期补上
2. FG还需要进一步梳理

A.369

思路

暴力求解即可。为了保险把范围开的大了一点。

代码

void solve()
{
    int a, b;
    cin >> a >> b;
    int cnt = 0;
    for (int i = 10000; i >= -10000; i--)
    {
        vector vec = {a, b, i};
        sort(all(vec));
        if (vec[2] - vec[1] == vec[1] - vec[0])
            cnt++;
    }
    cout << cnt << endl;
}

B.Piano 3

思路

将左手初始放在第一个左手音符上，右手初始放在第一个右手音符上，所得解法就是最佳解法。因为你需要按顺序处理每只手的音符。

代码

void solve()
{
    int n;
    cin >> n;
    vector<int> L;
    vector<int> R;
    for (int i = 0; i < n; i++)
    {
        int x;
        char op;
        cin >> x >> op;
        if (op == 'L')
            L.push_back(x);
        else
            R.push_back(x);
    }
    int fat = 0;
    for (int i = 1; i < L.size(); i++)
        fat += abs(L[i - 1] - L[i]);
    for (int i = 1; i < R.size(); i++)
        fat += abs(R[i - 1] - R[i]);
    cout << fat << endl;
}

C.Count Arithmetic Subarrays

思路

从左到右遍历，找到不符合等差数列关系的分割点后记录，计算 $\sum{\frac{x*(x+1)}{2}}$。

代码

using i64 = long long;
void solve()
{
    auto f = [&](i64 n)
    { return n * (n + 1) / 2; };
    int n;
    cin >> n;
    vector<int> vec(n);
    for (int &i : vec)
        cin >> i;
    i64 ans = n;
    int pre = 0;
    for (int i = 1; i < n - 1; i++)
    {
        if (vec[i] - vec[i - 1] != vec[i + 1] - vec[i])
        {
            ans += f(i - pre);
            pre = i;
        }
    }
    ans += f(n - 1 - pre);
    cout << ans << endl;
}

D.Bonus EXP

思路

状态转移的dp，可以证明不会跳过相邻的两只怪物，否则解法必然不是最优。

设 $dp[2][n]$，$dp[0]$ 表示杀敌为奇数，$dp[1]$ 表示杀敌数为偶数，然后在两者之间进行转移即可。

代码

using i64 = long long;
void solve()
{
    int n;
    cin >> n;
    vector<i64> vec(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> vec[i];
    vector<vector<i64>> dp(2, vector<i64>(n + 1));
    dp[0][1] = vec[1];
    for (int i = 2; i <= n; i++)
    {
        dp[0][i] = max(dp[0][i - 1], dp[1][i - 1] + vec[i]);
        dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + (2 * vec[i]));
    }
    cout << max(dp[0][n], dp[1][n]) << endl;
}

---

以下为补题部分

E.Sightseeing Tour

思路

数据足够小，这题用什么寻路算法都可以，跑一遍两点之间最短路以后，用DFS将所有可能出现的点与点的连接方式跑一遍（枚举所有出现方式用全排列，数据范围够小可以跑的开），求 $ min $ 即可。

代码

const int MAXN = 450;
struct Edge
{
    int to, weight;
};
struct Node
{
    int dis, from;
    bool operator>(const Node &a) const { return dis > a.dis; }
};
vector<Edge> edges[MAXN];
vector<int> dis(MAXN), vis(MAXN);
priority_queue<Node, vector<Node>, greater<Node>> que;
void dijkstra(int n, int s)
{
    dis = vector<int>(MAXN, INT_MAX);
    vis = vector<int>(MAXN, 0);
    dis[s] = 0;
    que.push({0, s});
    while (!que.empty())
    {
        int from = que.top().from;
        que.pop();
        if (vis[from])
            continue;
        vis[from] = 1;
        for (auto edge : edges[from])
        {
            int to = edge.to, weight = edge.weight;
            if (dis[to] > dis[from] + weight)
            {
                dis[to] = dis[from] + weight;
                que.push({dis[to], to});
            }
        }
    }
}

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> bridges;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        bridges.push_back({u, v, w});
        edges[u].push_back({v, w});
        edges[v].push_back({u, w});
    }
    vector<vector<int>> res_dis(n + 1);
    for (int i = 1; i <= n; i++)
    {
        dijkstra(n, i);
        res_dis[i] = dis;
    }
    int q;
    cin >> q;
    while (q--)
    {
        int k;
        cin >> k;
        vector<int> vec(k);
        for (auto &v : vec)
            cin >> v;
        sort(all(vec));
        int ans = INT_MAX;
        auto dfs = [&](auto dfs, int cur, int i, int sum)
        {
            if (i == k)
            {
                ans = min(ans, sum + res_dis[cur][n]);
                return;
            }
            auto [u, v, w] = bridges[vec[i] - 1];
            dfs(dfs, v, i + 1, sum + res_dis[cur][u] + w);
            dfs(dfs, u, i + 1, sum + res_dis[cur][v] + w);
        };
        do
        {
            dfs(dfs, 1, 0, 0);
        } while (next_permutation(all(vec)));
        cout << ans << endl;
    }
}