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;
}
- Educational Codeforces Round Rated 158educational codeforces round rated educational codeforces round 158 round codeforces rated based educational codeforces round 151 construction educational codeforces round rated 158 div for cf-educational educational codeforces round educational codeforces round 147 educational codeforces contest round educational codeforces monsters round