369

Dec 16, 2024 11:44 AM
Dec 17, 2024 4:34 AM

A - 369

给你两个整数 AB

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

当且仅当 qp 等于 rq 时,按此顺序排列的三个整数 pqr 的序列是算术序列。

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 键时,他会用左手按下 Ai 键,如果按下 Si= ,则用左手按下 Ai 键,如果按下 Si= ,则用右手按下 Ai 键。L "键,按 Si= 则用右手。R.

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

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

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

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 个正整数 Ai 组成的序列。

求满足 1lrN 的一对整数 (l,r) 中,子序列 Alr 构成等差数列的个数。

长度为 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 怪物 (1iN) 的力量为 Ai

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

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

Solution

有三种状态:

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

转移方程:

#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 座双向桥梁连接两个岛屿。这些岛屿和桥梁的编号分别为 12N12M
大桥 i 连接着岛屿 UiVi ,从任一方向穿过大桥所需的时间为 Ti
没有一座桥将一个岛屿与自己连接起来,但是两个岛屿有可能被不止一座桥直接连接起来。
人们可以通过一些桥梁来往于任意两个岛屿之间。

给你 Q 个问题,请逐一回答。 i -个查询如下:

给你 Ki 个不同的桥:桥 Bi,1,Bi,2,,Bi,Ki
求从岛屿 1 到岛屿 N 所需的最少时间,每座桥梁至少使用一次。
只考虑过桥的时间。
你可以以任何顺序和方向通过给定的桥梁。

Solution

floyed 算法

...

F - Gather Coins

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

在这个网格中有 N 枚硬币,通过 (Ri,Ci) 单元可以拾取 i 枚硬币。

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

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