369

Dec 16, 2024 11:44 AM

Dec 17, 2024 4:34 AM

A - 369

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

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

条件：可以将三个整数 $A$ 、 $B$ 和 $x$ 按一定顺序排列，组成一个算术序列。

当且仅当 $q - p$ 等于 $r - q$ 时，按此顺序排列的三个整数 $p$ ， $q$ ， $r$ 的序列是算术序列。

void solve() {
    int a, b;cin >> a >> b;
    if (a == b) {
        cout << "1\n";return;
    }
    int ans = 3;
    if ((a - b) & 1) {
        ans--;
    }
    cout << ans << '\n';
}

B - Piano 3

高桥有一架钢琴，上面有 $100$ 个排成一行的琴键。从左边开始的第 $i$ 个键叫做第 $i$ 个键。

他会逐个按下 $N$ 个键来演奏音乐。在按下 $i$ /th 键时，他会用左手按下 $A_{i}$ 键，如果按下 $S_{i} =$ ，则用左手按下 $A_{i}$ 键，如果按下 $S_{i} =$ ，则用右手按下 $A_{i}$ 键。L "键，按 $S_{i} =$ 则用右手。R.

开始演奏前，他可以将双手放在任何他喜欢的键上，此时他的疲劳度为 0。在演奏过程中，如果他将一只手从 $x$ 移到 $y$ 键上，疲劳度会增加 $| y - x |$ (反之，除移动双手外，疲劳度不会增加)。用手按下某个键时，该手必须放在该键上。

找出表演结束时可能的最低疲劳度。

直接放在第一次弹的位置即可。

void solve() {
    int n;cin >> n;
    int l = 0, r = 0, ok1 = 0, ok2 = 0;
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        int a;char ch;cin >> a >> ch;
        if (!ok1 && ch == 'L') {
            l = a;ok1 = 1;
        } else if (!ok2 && ch == 'R') {
            r = a;ok2 = 1;
        }
        if (ch == 'L') {
            ans += abs(l - a);l = a;
        } else if (ch == 'R') {
            ans += abs(r - a);r = a;
        }

    }
    cout << ans << '\n';
}

C - Count Arithmetic Subarrays

给你一个由 $N$ 个正整数 $A_{i}$ 组成的序列。

求满足 $1 \leq l \leq r \leq N$ 的一对整数 $(l, r)$ 中，子序列 $A_{l \sim r}$ 构成等差数列的个数。

长度为 $1$ 的序列总是算术级数。

注：需要 long long

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), suf(n + 2);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 2;i <= n;i++) {
        suf[i] = a[i] - a[i - 1];
    }
    suf[n + 1] = 2e9;
    int ans = 0, cnt = 1, p = 0;
    for (int i = 2;i <= n;i++) {
        if (suf[i + 1] != suf[i]) {
            ans += (cnt + 1) * (cnt + 2) / 2;cnt = 1;p++;
        } else {
            cnt++;
        }
    }
    cout << ans - p + 1 << '\n';
}

D - Bonus EXP

高桥依次会遇到 $N$ 只怪物。 $i$ -th 怪物 $(1 \leq i \leq N)$ 的力量为 $A_{i}$ 。

对于每只怪物，他都可以选择放走或打败它。
每次行动都会获得以下经验值：

如果放走一只怪物，他将获得 $0$ 点经验值。
如果他以 $X$ 的力量击败了怪物，则会获得 $X$ 点经验值。
如果击败的是偶数怪物 (第 2 个、第 4 个......)，则额外获得 $X$ 点经验值。

求他能从 $N$ 个怪物身上获得的经验值上限。

Solution

有三种状态：

选择当前位置且当前位置是第奇数个
选择当前位置且当前位置是第偶数个
不选当前位置

则 $d p_{i, 0 / 1 / 2}$ 代表在前 $i$ 个数字中不选/选(odd/even) 能得到的最大经验值

若当前位置不选，则可能从前一个位置的任意一个状态转移而来
若选择当前位置且是第奇数个，则前一个位置可能不选，也可能从偶数个转移而来
若选择当前位置且是第偶数个，则前一个位置可能不选，也可能从奇数个转移而来(注意：当下标为 1 时，则不可能是从奇数个转移而来)

转移方程：

$d p_{i, 0} = max (d p_{i - 1, 0}, d p_{i - 1, 1}, d p_{i - 1, 2})$
$d p_{i, 1} = max (d p_{i - 1, 2}, d p_{i - 1, 0}) + a_{i}$
$d p_{i, 2} = max (d p_{i - 1, 1}, d p_{i - 1, 0}) + 2 \times a_{i}$

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    vector<array<int, 3>> dp(n + 1);
    for (int i = 1;i <= n;i++) {
        dp[i][0] = max({dp[i - 1][1], dp[i - 1][2],dp[i - 1][0]});
        dp[i][1] = max(dp[i - 1][2], dp[i - 1][0]) + a[i];
        if (i != 1)dp[i][2] = max(dp[i - 1][1], dp[i - 1][0]) + a[i] * 2;
    }
    cout << max({dp[n][0],dp[n][1],dp[n][2]}) << '\n';
}

E - Sightseeing Tour

有 $N$ 个岛屿和 $M$ 座双向桥梁连接两个岛屿。这些岛屿和桥梁的编号分别为 $1$ 、 $2$ 、 $\dots$ 、 $N$ 和 $1$ 、 $2$ 、 $\dots$ 、 $M$ 。
大桥 $i$ 连接着岛屿 $U_{i}$ 和 $V_{i}$ ，从任一方向穿过大桥所需的时间为 $T_{i}$ 。
没有一座桥将一个岛屿与自己连接起来，但是两个岛屿有可能被不止一座桥直接连接起来。
人们可以通过一些桥梁来往于任意两个岛屿之间。

给你 $Q$ 个问题，请逐一回答。 $i$ -个查询如下：

给你 $K_{i}$ 个不同的桥：桥 $B_{i, 1}, B_{i, 2}, \dots, B_{i, K_{i}}$ 。
求从岛屿 $1$ 到岛屿 $N$ 所需的最少时间，每座桥梁至少使用一次。
只考虑过桥的时间。
你可以以任何顺序和方向通过给定的桥梁。

Solution

floyed 算法

...

F - Gather Coins

有一个网格，网格中有 $H$ 行和 $W$ 列。让 $(i, j)$ 表示从上往下数第 $i$ 行，从左往上数第 $j$ 列的单元格。

在这个网格中有 $N$ 枚硬币，通过 $(R_{i}, C_{i})$ 单元可以拾取 $i$ 枚硬币。

您的目标是从 $(1, 1)$ 单元格开始，反复向下或向右移动一个单元格，到达 $(H, W)$ 单元格，同时尽可能多地拾取硬币。

请找出您能拾取的最大硬币数以及能达到最大值的路径之一。