Educational Codeforces Round 158 (Rated for Div. 2)

A - Line Trip

解题思路:

每次到加油站油都会加满，所以我们考虑到达两个加油站间需要的最大油量即可。

注意：最后一站的油量是一个来回。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
    ll n, x;
    cin >> n >> x;
    vector<ll> a(n + 1);
    a[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans = max(ans, a[i] - a[i - 1]);
    }
    ans = max(ans, 2 * (x - a[n]));
    cout << ans << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

B - Chip and Ribbon

解题思路:

若$a[i] > a[i-1]$，那么从$a[i-1]$顺路往后走完后，还要回头到$i$走$a[i] - a[i-1]$次。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
    ll n;
    cin >> n;
    vector<ll> a(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += max(0ll, a[i] - a[i - 1]);
    }
    cout << ans - 1 << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

C - Add, Divide and Floor

解题思路:

设最大数和最小数的差值为$maxa - mina = dist$。我们要通过操作将$dist$变为0.

$(maxa + x) - (mina + x) = dist$。正常来说加减无意义，因为差值不变。但本题操作是将差值除以二下取整，那么加减导致奇偶性的变换就有意义了。

举例：

例1. $maxa = 2,mina = 1$

若加$0$，即保持原本奇偶性:

$(2,1) \to (1,0) \to (0,0)$，两步。

若加$1$，即改变原本奇偶性:

$(3,2) \to (1,1)$，一步。

例2. $maxa = 3,mina = 2$

若加$0$，即保持原本奇偶性:

$(3,2) \to (1,1) $，一步。

若加$1$，即改变原本奇偶性:

$(4,3) \to (2,1) \to (1,0) \to (0,0)$，三步。当然这里第二步开始可以加不同的$x$，但总归不如什么都不加。

所以，当当前最大数为偶数，最小数为奇数时二者都加一，否则直接操作即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
    ll n;
    cin >> n;
    vector<ll> a(n + 1);
    ll maxa = 0;
    ll mina = 1e18 + 10;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        maxa = max(maxa, a[i]);
        mina = min(mina, a[i]);
    }
    ll t = (maxa - mina);
    ll cnt = 0;
    vector<int> ans;
    while (t)
    {
        if ((t & 1) && (maxa % 2 == 0))
        {
            maxa = (maxa + 1) / 2;
            mina = (mina + 1) / 2;
            ans.push_back(1);
        }
        else
        {
            maxa = (maxa + 0) / 2;
            mina = (mina + 0) / 2;
            ans.push_back(0);
        }
        t = (maxa - mina);
    }
    ll res = ans.size();
    cout << res << endl;
    if (res && res <= n)
    {
        for (int i = 0; i < res; i++)
        {
            printf("%d ", ans[i]);
        }
        cout << endl;
    }
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

D - Yet Another Monster Fight

解题思路:

我们假定第一个选择的下标为$idx，l < idx ,r > idx$。

则对于$a[l]$，最坏的情况为$a[l] + n - l$,即选择玩所有$l$右边的数后，再选择自己。

则对于$a[l]$，最坏的情况为$a[r] + i - 1$,即选择玩所有$r$左边边的数后，再选择自己。

所以，我们可以预处理出对于每个位置，如果选择不是自己，那么最坏情况的花费。同时，预处理出第一个下标为$i$时，左边的最大花费$pre[i-1]$以及右边的最大花费$suf[i+1]$。

那么答案就是$min(max(a[i],pre[i-1],suf[i+1]))$。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
void solve()
{
    ll n;
    cin >> n;
    vector<ll> a(n + 10, 0), f(n + 10);
    vector<ll> pre(n + 10), suf(n + 10);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pre[i] = a[i] + n - i;
        pre[i] = max(pre[i], pre[i - 1]);
    }
    ll ans = 1e18;
    // cout << suf[4] << endl;
    for (int i = n; i; i--)
    {
        suf[i] = (a[i] + i - 1);
        suf[i] = max(suf[i], suf[i + 1]);
        f[i] = max(a[i], max(pre[i - 1], suf[i + 1]));
        // cout << i << ' ' << pre[i] << ' ' << suf[i] << ' ';
        // cout << f[i] << endl;
        ans = min(f[i], ans);
    }
    // cout << suf[4] << endl;
    cout << ans << endl;
}

int main()
{
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}