A. Line Trip

遍历所有加油站的位置，答案就是相距最远的(注意最后一个加油站，因为掉头要算两遍)

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
#include <bits/stdc++.h>

void repeater()
{
	int n, x; std::cin >> n >> x;
	int lst = 0;
	int ans = 0;
	for(int i = 0; i < n; i++)
	{
		int tmp; std::cin >> tmp;
		ans = std::max(tmp - lst, ans);
		lst = tmp;
	}
	ans = std::max(2 * (x - lst), ans);
	std::cout << ans << "\n";
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t; std::cin >> t;
	while(t--) repeater();

	return 0;
}

B. Chip and Ribbon

可以把每个位置上的数看成一根竖着的柱子的高度，一次操作相当于摆一根横着的柱子上去。从前往后遍历，如果当前的高度小于前一个，那么前面操作的时候已经覆盖到了；如果高于前一个，高出来的部分就是要操作的次数。注意最后答案减一，因为第一次操作不用传送

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
#include <bits/stdc++.h>

using i64 = long long;

void repeater()
{
	int n; std::cin >> n;
	std::vector<int> a(n);
	for(int i = 0; i < n; i++)
		std::cin >> a[i];
	i64 ans = a[0], pre = a[0];
	for(int i = 1; i < n; i++)
	{
		if(a[i] > pre)
			ans += a[i] - pre;
		pre = a[i];
	}
	std::cout << ans - 1 << "\n";
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t; std::cin >> t;
	while(t--) repeater();

	return 0;
}

C. Add, Divide and Floor

将原数列升序排序，那么让第一个数和最后一个数相等的次数是最大的，并且当他们相等时，整个数列都相等。接下来考虑如何让操作次数最少的。

当 a1a_1 为奇数， ana_n 为偶数时，令 xx 为 11 ，他们会接近的更快；而其它情况要不就是没影响，要不会起负作用。

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
#include <bits/stdc++.h>

void repeater()
{
	int n; std::cin >> n;
	std::vector<int> a(n);
	for(int i = 0; i < n; i++)
		std::cin >> a[i];
	if(n == 1)
	{
		std::cout << 0 << "\n";
		return;
	}

	sort(a.begin(), a.end());
	int x = a[0], y = a[n - 1];
	int cnt = 0;
	std::vector<int> ans;
	while(x < y)
	{
		if(x % 2 == 1 && y % 2 == 0)
		{
			x++;
			ans.emplace_back(1);
		}
		else ans.emplace_back(0);
		x >>= 1, y >>= 1;
		cnt++;
	}
	std::cout << cnt << "\n";
	if(cnt <= n) 
	{
		for(auto i : ans)
			std::cout << i << " ";
		std::cout << "\n";
	}
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t; std::cin >> t;
	while(t--) repeater();

	return 0;
}

D. Yet Another Monster Fight

显然答案具有单调性，可以考虑二分。那么关键就是 checkcheck 函数怎么写。

记伤害为 xx ，假设我们起始点为 ii ，那么对于其左边的点 jj ，最坏情况是打完右边所有的再打它，此时伤害为 x−(n−j)x -(n-j) ，这个伤害要大于它的血量，于是 a[j]−j⩽x−na[j]-j \leqslant x-n；而对于右边，a[j]+j⩽x+1a[j]+j \leqslant x+1 。于是我们可以枚举起点，看看这个起点是否合法。判断合法的方式可以通过判断最大的 a[j]−ja[j]-j 和 a[j]+ja[j]+j 是否符合不等式。而这个可以预处理得到。

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
#include <bits/stdc++.h>

using i64 = long long;

void repeater()
{
	int n; std::cin >> n;
	std::vector<i64> a(n + 1);
	for(int i = 1; i <= n; i++)
		std::cin >> a[i];
	std::vector<i64> pre(n + 1, -0x3f3f3f3f), suf(n + 2, -0x3f3f3f3f);
	for(int i = 1; i <= n; i++) pre[i] = std::max(pre[i - 1], a[i] - i);
	for(int i = n; i >= 1; i--) suf[i] = std::max(suf[i + 1], a[i] + i);


	auto check = [&](i64 x) -> bool
	{
		for(int i = 1; i <= n; i++)
		{
			if((a[i] <= x) && (pre[i - 1] <= x - n) && (suf[i + 1] <= x + 1))
				return true;
		}
		return false;
	};	

	i64 l = 0, r = 1e18;
	while(l < r)
	{
		i64 mid = (l + r) >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	std::cout << l << "\n";
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t = 1; 
	//std::cin >> t;
	while(t--) repeater();

	return 0;
}