Educational Codeforces Round 158 (Rated for Div. 2)
A
思路
找到每个加油站之间的距离的最大值，需要特殊处理最后一个加油站和 \(x\) 之间的来回距离
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e3 + 10;
const int M = 1e5 + 10;
void solve()
{
int n, x;
cin >> n >> x;
vector<int> a(n + 10);
for (int i = 1; i <= n; i++)
cin >> a[i];
int ans = (x - a[n]) * 2;
for (int i = 1; i <= n; i++)
ans = max(ans, a[i] - a[i - 1]);
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}B
思路
贪心经典题型，如果当前比前一个高，则累加高出的高度。如果当前比前面矮，则必然会被前面的操作所覆盖
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;
void solve()
{
int n;
cin >> n;
vector<ll> c(n + 10);
for (int i = 1; i <= n; i++)
cin >> c[i];
ll now = 1, ans = 0;
for (int i = 1; i <= n; i++)
{
if (c[i] > now)
ans += c[i] - now;
now = c[i];
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}C
思路
由变化的关系式可知，如果 \(a_i \le a_j\) ，不论操作多少次，都不会使 \(a_i \gt a_j\) 。故我们只需要判断数组中的最大值和最小值最后是否相等
每次的操作可以视作将加上一个数后右移一位
对于 \(a\) 和 \(b\) \((a \le b)\) ，本题变为判断如何让 \((b + x) / 2 - (a + x) / 2\) 差值更小
会发现如果 \(a\) 为奇数且 \(b\) 为偶数时， \(x = 1\) 会让差值更小
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;
void solve()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
int x = *min_element(all(a)), y = *max_element(all(a));
vector<int> ans;
while (x < y)
{
if (y - x == 1)
{
if (x % 2 == 1)
ans.push_back(1);
else
ans.push_back(0);
break;
}
if (x % 2 == 1)
{
x = (x + 1) / 2;
y = (y + 1) / 2;
ans.push_back(1);
}
else
{
x = x / 2;
y = y / 2;
ans.push_back(0);
}
}
cout << ans.size() << endl;
if (ans.size() <= n && ans.size())
{
for (int i = 0; i < ans.size(); i++)
{
if (i)
cout << ' ';
cout << ans[i];
}
cout << endl;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}D
思路
pre[i] ：消灭第 \(i-1\) 个怪物在最坏情况下所需的法术力量
suf[i] ：消灭第 \(i+1\) 个怪物在最坏情况下所需的法术力量
然后，我们遍历所有的怪物，对于每个怪物 \(i\) ，我们计算一个值，这个值是 a[i] ， pre[i] 和 suf[i] 中的最大值（即杀死这个怪物及其相邻的两个怪物所需的初始法术力量）。最后找到这个值的最小值，这个最小值就是需要的最小初始法术力量。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
#define endl '\n'
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 10), pre(n + 10), suf(n + 10);
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 2; i <= n; i++)
pre[i] = max(pre[i - 1], a[i - 1] + n - (i - 1));
for (int i = n - 1; i >= 1; i--)
suf[i] = max(suf[i + 1], a[i + 1] + i);
int ans = 0x7fffffff;
for (int i = 1; i <= n; i++)
ans = min(ans, max({a[i], pre[i], suf[i]}));
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}Educational Codeforces Round 158 (Rated for Div. 2)
http://xiaowhang.github.io/archives/324571094/