AtCoder Beginner Contest 369 A-F

AtCoder Beginner Contest 369 A-F (opens new window)

A - 369

Question

给定两个整数 $A$ 和 $B$。

有多少个整数 $x$ 满足以下条件？

• 条件：可以按照某种顺序排列整数 $A$、$B$ 和 $x$，使它们构成一个等差数列。

如果且仅如果 $q-p$ 等于 $r-q$，那么按照这个顺序排列的三个整数 $p$、$q$ 和 $r$ 就构成一个等差数列。

Solution

如果 $A,B$ 相同，答案为 $1$

如果 $A,B$ 之差为偶数，答案为 $3$

否则答案为 $2$

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int A, B;
    cin >> A >> B;
    if (A == B) {
        cout << 1 << '\n';
        return 0;
    }
    int ans = 2;
    if ((B - A) % 2 == 0) ans += 1;
    cout << ans << '\n';
    return 0;
}

B - Piano 3

Question

Takahashi有一架有100个按键的钢琴，这些按键排成一行。从左边数起，第i个按键被称为按键i。

他将逐个按下N个按键来演奏音乐。对于第i次按下，如果$S_i=$ L，他将使用左手按下按键$A_i$；如果$S_i=$ R，他将使用右手按下按键$A_i$。

在开始演奏之前，他可以将两只手放在任意他喜欢的按键上，此时他的疲劳水平为0。在演奏过程中，如果他将一只手从按键x移动到按键y，疲劳水平将增加$|y-x|$（反之，除了移动手之外的任何原因都不会增加疲劳水平）。要用一只手按下某个按键，那只手必须放在该按键上。

找到演奏结束时可能的最小疲劳水平。

Solution

开始时必然放在一个第一个琴键上

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a, b;
    for (int i = 1; i <= n; i++) {
        int x; char ch; cin >> x >> ch;
        if (ch == 'L') a.push_back(x);
        else b.push_back(x);
    }
    int ans1 = 0;
    for (int i = 0; i + 1 < a.size(); i++)
        ans1 += abs(a[i + 1] - a[i]);
    int ans2 = 0;
    for (int i = 0; i + 1 < b.size(); i++)
        ans2 += abs(b[i + 1] - b[i]);
    cout << ans1 + ans2 << '\n';
    return 0;
}

C - Count Arithmetic Subarrays

Question

给定一个包含 $N$ 个正整数的序列 $A=(A_1,A_2,\dots,A_N)$。

找到满足 $1\leq l\leq r\leq N$ 且子序列 $(A_l,A_{l+1},\dots,A_r)$ 为等差数列的整数对 $(l,r)$ 的数量。

Solution

考虑到等差数列除了在端点处，没有相交，所以 $O(n)$ 查找每段长度即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    // freopen ("C.in", "r", stdin);
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    ll ans = 0;
    for (int i = 1; i <= n;) {
        int j = i + 1; 
        if (j > n) break;
        int d = a[j] - a[i];
        while (j <= n && a[j] - a[j - 1] == d) j += 1;
        j -= 1;
        int len = j - i + 1;
        ans += 1LL * len * (len - 1) / 2;
        i = j;
    }
    ans += n;
    cout << ans << '\n';
    return 0;
}

D - Bonus EXP

Question

Takahashi 按顺序会遭遇 $N$ 只怪物。第 $i$ 只怪物 $(1\leq i\leq N)$ 的攻击力为 $A_i$。

对于每只怪物，他可以选择放走或击败它。
每个行动将按以下方式奖励他经验值：

• 如果他放走了一只怪物，他将获得 $0$ 经验值。
• 如果他打败了一只攻击力为 $X$ 的怪物，他将获得 $X$ 经验值。
  如果是打败的偶数次怪物(第2、4、...)，他将获得额外的 $X$ 经验值。

求他可以获得的 $N$ 只怪物中的最大总经验值。

Solution

DP，定义 $dp[i][0/1]$ 表示对于前 $i$ 个怪物，一共击败的怪物数量对 $2$ 取模后的最大总经验值

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int main() {
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<ll>> dp(n + 1, vector<ll>(2, -INF));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i][0] = max({dp[i - 1][0], dp[i - 1][1] + a[i] * 2});
        dp[i][1] = max({dp[i - 1][1], dp[i - 1][0] + a[i]});
    }
    cout << max(dp[n][0], dp[n][1]) << '\n';
    return 0;
}

E - Sightseeing Tour

Question

有 $N$ 个岛屿和 $M$ 条双向桥梁连接两个岛屿。 岛屿和桥梁分别编号为 $1$、$2$、$\ldots$、$N$ 和 $1$、$2$、$\ldots$、$M$。
桥 $i$ 连接岛屿 $U_i$ 和 $V_i$，穿过它所需的时间为 $T_i$。 没有桥连接一个岛屿本身，但两个岛屿之间可能直接连接多个桥。 可以通过一些桥梁在任意两个岛屿之间旅行。

你将获得 $Q$ 个查询，回答每个查询。第 $i$ 个查询如下:

给定 $K_i$ 条不同的桥梁: 桥梁 $B_{i,1}, B_{i,2}, \ldots, B_{i,K_i}$。 寻找使用每个桥梁至少一次从岛屿 $1$ 到岛屿 $N$ 所需的最短时间。 只考虑穿过桥梁所花费的时间。
可以按任意顺序和方向穿过给定的桥梁。

• $2 \leq N \leq 400$
• $N-1 \leq M \leq 2 \times 10^5$
• $1 \leq U_i < V_i \leq N$
• $1 \leq T_i \leq 10^9$
• $1 \leq Q \leq 3000$
• $1 \leq K_i \leq 5$
• $1 \leq B_{i,1} < B_{i,2} < \cdots < B_{i,K_i} \leq M$
• 所有输入值均为整数。
• 可以通过某些桥梁在任意两个岛屿之间旅行。

Solution

和之前合肥区域赛的那个想法差不多

先用 Floyd 刷出多源最短路

由于 $k$ 非常小，所以我们枚举 $k$ 的全排列，表示经过必经过桥梁的顺序，但是由于每个桥梁有两种经过方式：假设 $k_i$ 的两端是 $u,v$，两种方式是 $u\rightarrow v$ 和 $v\rightarrow u$ 则我们还需要枚举每个桥是那种方式通过的，这里就需要 $2^k$ ，然后从一个桥的一个端点到下一个桥的一个端点就用我们预处理的多源最短路得到

总时间复杂度为 $O(n^3+Qkk!2^k)$

Code

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 405;
const int MAXM = 2e5 + 5;
#define int long long
int dis[MAXN][MAXN];
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;

struct Edge {
    int u, v, w;
}e[MAXM];

signed main() {
    int n, m; cin >> n >> m;
    memset(dis, 0x3f, sizeof(dis));
    for (int i = 1; i <= m; i++) {
        int u, v, l; cin >> u >> v >> l;
        dis[u][v] = dis[v][u] = min(dis[u][v], l);
        e[i] = {u, v, l};
    }
    for (int i = 1; i <= n; i++) dis[i][i] = 0;
    for (int k = 1; k <= n; k++) 
        for (int i = 1; i <= n; i++) 
            for (int j = 1; j <= n; j++) 
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    
    int Q; cin >> Q;
    while (Q--) {
        int k; cin >> k;
        vector<int> c(k);
        for (int i = 0; i < k; i++) cin >> c[i];
        vector<int> idx(k);
        iota(idx.begin(), idx.end(), 0);
        vector<int> p(k);
        ll ans = INF;
        do {
            for (int S = 0; S < (1 << k); S++) {
                ll now_ans = 0;
                p.clear(); p.push_back(1);
                for (int i = 0; i < k; i++) {
                    Edge &now_edge = e[c[idx[i]]];
                    now_ans += now_edge.w;
                    if (S >> i & 1) {
                        p.push_back(now_edge.u);
                        p.push_back(now_edge.v);
                    }
                    else {
                        p.push_back(now_edge.v);
                        p.push_back(now_edge.u);
                    }
                }
                p.push_back(n);
                for (int i = 0; i < p.size(); i += 2)
                    now_ans += dis[p[i]][p[i + 1]];
                ans = min(ans, now_ans);
            }
        }while (next_permutation(idx.begin(), idx.end()));
        cout << ans << '\n';
    }
    return 0;
}

F - Gather Coins

现有一个 $H$ 行 $W$ 列的网格，$(i,j)$ 表示位于从上往下第 $i$ 行、从左往右第 $j$ 列的单元格。

在这个网格中有 $N$ 枚硬币，第 $i$ 枚硬币可以通过经过单元格 $(R_i,C_i)$ 来获取。

你的目标是从单元格 $(1,1)$ 出发，每次只能向下或向右移动一格，到达单元格 $(H,W)$ 的过程中尽可能多地捡起硬币。

寻找一种方案，在拾取的硬币数量最多的同时到达单元格 $(H,W)$。

找出你能够拾取的最大硬币数量，并给出一种实现该最大值的路径。### 约束条件

• $2\leq H,W \leq 2\times 10^5$
• $1\leq N \leq \min(HW-2, 2\times 10^5)$
• $1\leq R_i \leq H$
• $1\leq C_i \leq W$
• $(R_i,C_i)\neq (1,1)$
• $(R_i,C_i)\neq (H,W)$
• $(R_i,C_i)$ 两两不同。
• 所有输入值均为整数。

Solution

先考虑朴素的 $dp$，定义 $dp[i][j]$ 表示走到 $(i,j)$ 的最大拾取硬币数量，那么转移方程就是：

$dp[i][j]=\max\{dp[i'][j']\}+1\ (i'\le i,j'\le j)$

但是由于 $NM$ 很大，考虑优化，我们发现，固定住 $i$ 不动，其实 $j'\in [1,j]$ 里面找一个最小的然后转移

所以把每个点按照 pair<int,int> 的顺序排序，然后先按照 $i$ 从小到大处理，使用线段树来找最小值转移

问方案就是在线段树内加上最小值所在的节点

Code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

struct Node {
    int val;
    pair<int, int> pos;
    bool operator < (const Node &rhs) const {
        return val < rhs.val;
    }
};

Node merge (Node a, Node b) {
    return a.val < b.val ? b : a;
}

struct Segment_Tree {
    vector<Node> tr;
    Segment_Tree(int n) : tr(n << 2) {}

    void push_up (int x) {
        tr[x] = merge(tr[x << 1], tr[x << 1 | 1]);
    }

    void update (int x, int l, int r, int pos, Node val) {
        if (l == r) {
            if (tr[x] < val) tr[x] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) update(x << 1, l, mid, pos, val);
        else update(x << 1 | 1, mid + 1, r, pos, val);
        push_up(x);
    }

    Node query (int x, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) return Node({0, {0, 0}});
        if (ql <= l && r <= qr) return tr[x];
        int mid = (l + r) / 2;
        return merge(query(x << 1, l, mid, ql, qr), query(x << 1 | 1, mid + 1, r, ql, qr));
    }
};

int main() {
    freopen ("F.in", "r", stdin);
    int N, M, K; cin >> N >> M >> K;
    vector<pii> pos(K + 1);
    map<pii, pii> pre;
    for (int i = 1; i <= K; i++) cin >> pos[i].first >> pos[i].second;

    Segment_Tree seg(M + 1);

    sort(pos.begin() + 1, pos.end());
    for (int i = 1; i <= K; i++) {
        auto [x, y] = pos[i];
        Node tmp = seg.query(1, 1, M, 1, y);
        if (tmp.val) pre[{x, y}] = tmp.pos;
        seg.update(1, 1, M, y, {tmp.val + 1, {x, y}});
    }

    Node ans = seg.query(1, 1, M, 1, M);
    cout << ans.val << '\n';
    vector<pii> res;
    for (auto [x, y] = ans.pos;;) {
        res.push_back({x, y});
        if (pre.find({x, y}) == pre.end()) break;
        auto [nx, ny] = pre[{x, y}];
        x = nx, y = ny;
    }
    res.push_back({1, 1});
    reverse(res.begin(), res.end());
    res.push_back({N, M});
    // for (auto [x, y] : res) cout << x << ' ' << y << '\n'; 
    string ans_;
    for (int i = 0; i + 1 < res.size(); i++) {
        int dx = res[i + 1].first - res[i].first;
        int dy = res[i + 1].second - res[i].second;
        for (int j = 0; j < dx; j++) ans_.push_back('D');
        for (int j = 0; j < dy; j++) ans_.push_back('R');
    }
    cout << ans_ << '\n';
    return 0;
}