526互联

Educational Codeforces Round 158 (Rated for Div. 2) A-C

发布时间 2023-11-25 08:47:40作者: qdhys

A

大致题意： 有一条长度为x的直线公路，最开始你位于0号点并且此时你的油箱装满了油，公路有n个加油站，当你经过加油站的时候你可以在加油站加满油，每走一个单位需要花费1升油量，起始位置和终点没有加油站，请问你的油箱容量至少为多少升才可以够你跑一个来回。

解题思路： 我们的路径大致是这样0 -> a[1] -> a[2] -> ... a[n] -> x - > a[n] -> ... a[2] -> a[1] -> 0,观察发现除了a[n] -> n - > a[n]的时候这两段路程走完之前没有加油站其他的时候都有加油站，所以只需要算出其他路径的差的最大值和2 * (n - a[n])取一个max就是答案。

#include <bits/stdc++.h>
 
#define ll long long
#define db double
typedef std::pair<int, int > PII;
typedef std::pair<int, std::pair<int, int>> PIII;
typedef std::pair<ll, ll> Pll;
typedef std::pair<double, double> PDD;
using ld = double long;
const long double eps = 1e-9;
int d1[] = {0, 0, 1, -1};
int d2[] = {1, -1, 0, 0};
const int N = 2e5 + 10, M = N << 1;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
#define ls u << 1
#define rs u << 1 | 1

int n, m, k;
int a[N];

int main(void){
   	std::ios::sync_with_stdio(false);
   	std::cin.tie(0);
   	std::cout.tie(0);
   	
   	int _ = 1;
   	
	std::cin >> _;
	while(_ --) {
		
		std::cin >> n >> m;
	
		for (int i = 1; i <= n; i ++) std::cin >> a[i];
		a[n + 1] = m;
		int mn = 0;
		
		for (int i = 1; i <= n; i ++) 
			mn = std::max(mn, a[i] - a[i - 1]);
		
		mn = std::max(mn, a[n + 1] - a[n] + a[n + 1] - a[n]);
		std::cout << mn << '\n';
		
	}

    return 0;
}

B

**大致题意： 有一个长度为n的单元格，每个单元格上都有一个整数，最开始都是0. 一开始芯片在第一个位置，每当一个回合结束时(最开始也视为一个回合)，芯片所在的单元格的整数+1.每回合结束时我们都有两个操作: **
**操作1:将芯片移动到下一个单元格(例如，如果芯片在 i单元格，则将其移动到 i + 1单元格)。如果芯片在最后一格，则无法进行此操作； **
**操作2:选择任意一个 x单元格，将芯片传送到该单元格。可以选择芯片当前所在的单元格； **

每个单元格都有一个目标整数c[i]你的目标就是让每个单元格上的整数变为c[i]，并且操作尽可能少的操作2，问最少使用多少次操作2可以让单元格上的整数都达成目标。

解题思路： 观察发现如果c[i] >= c[i + 1]那么每次使用操作2传送回 i 的时候能用操作1把格子i + 1也给走了。也就是说如果有这么一个连续子数组c[i] >= c[i + 1] >= c[i + 2] ...答案就是芯片传送回第i个格子的次数。可以将整个数组划分为若干段这样不上升的子数组。一旦c[i] < c[i + 1]就是新的一段的开始。需要注意的细节是我们在走c[i]的时候能把c[i + 1]也给走了，也就是新的一段需要减去上一段的最后一个元素。由于最开始就在第一个位置，所以需要将最开始的上一段置为1方便统计答案。

#include <bits/stdc++.h>
 
#define ll long long
#define db double
typedef std::pair<int, int > PII;
typedef std::pair<int, std::pair<int, int>> PIII;
typedef std::pair<ll, ll> Pll;
typedef std::pair<double, double> PDD;
using ld = double long;
const long double eps = 1e-9;
int d1[] = {0, 0, 1, -1};
int d2[] = {1, -1, 0, 0};
const int N = 2e5 + 10, M = N << 1;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
#define ls u << 1
#define rs u << 1 | 1

int n, m, k;
int a[N];

int main(void){
   	std::ios::sync_with_stdio(false);
   	std::cin.tie(0);
   	std::cout.tie(0);
   	
   	int _ = 1;
   	
	std::cin >> _;
	while(_ --) {
		
		std::cin >> n;
	
		for (int i = 1; i <= n; i ++) std::cin >> a[i];
		
		ll ans = 0;
		
		int i = 1, j = 2;
		int last = 1;
		for (; j <= n; j ++) {
			if (a[j] > a[j - 1]) {
				ans += a[i] - last;
				i = j;
				last = a[j - 1];
			}
		}
		ans += a[i] - last;
		
		std::cout << ans << '\n';
		
	}

    return 0;
}

C

大致题意： 有一个长度为n的数组，你可以进行无数次以下操作：将数组上每个数字加上x(0 <= x <= 1e18)然后除以2（下去整），问最少要多少次可以让数组所有元素相等。

解题思路： 我们关注两个元素t1， t2(t1 < t2)，如果t2 - t1 == 1的话我们只需要操作一次就可以得到答案：1.若t1为偶数：让t1和t2除以2一次就可以让他们两个一样。2.如果t1为奇数：需要先让t1和t2加上1再除以2就可以使他们两个一样。如果t2 - t1 > 1，就变成了如何让(t2 + x) / 2 - (t1 + x) / 2差值更小，此时会发现如果t1为奇数且t2为偶数那么x = 1会让差值更小(写题的时候只需要判断t1是否为奇数即可，就算t2也是奇数那么都加上1之后再除以2这两者的差值大小也是不会变的)。在这个过程中发现无论如何t2的不可能变的比t1小，t1不可能变的比t2大，所以只取数组中的最大值和最小值，只要它们两个变的一样了那么其他所有数字一定和他们两个一样。

#include <bits/stdc++.h>
 
#define ll long long
#define db double
typedef std::pair<int, int > PII;
typedef std::pair<int, std::pair<int, int>> PIII;
typedef std::pair<ll, ll> Pll;
typedef std::pair<double, double> PDD;
using ld = double long;
const long double eps = 1e-9;
int d1[] = {0, 0, 1, -1};
int d2[] = {1, -1, 0, 0};
const int N = 2e5 + 10, M = N << 1;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
#define ls u << 1
#define rs u << 1 | 1

int n, m, k;
int a[N];


int main(void){
   	std::ios::sync_with_stdio(false);
   	std::cin.tie(0);
   	std::cout.tie(0);
   	
   	int _ = 1;
   	
	std::cin >> _;
	while(_ --) {
		std::cin >> n;
	
		for (int i = 1; i <= n; i ++) std::cin >> a[i];
		
		std::sort(a + 1, a + n + 1);
		
		int mn = a[1], mx = a[n];
		
		int ans = 0;
		std::vector<int> tmp;
		while (mn < mx) {
			if (mx - mn == 1) {
				if (mn % 2 == 1) tmp.push_back(1);
				else tmp.push_back(0);
				break;
			}
			if (mn % 2 == 1) {
				mn = (mn + 1) / 2;
				mx = (mx + 1) / 2;
				tmp.push_back(1);
			} else {
				mn = mn / 2;
				mx = mx / 2;
				tmp.push_back(0);
			}
		}
			
		std::cout << tmp.size() << '\n';
		if (tmp.size() <= n && tmp.size()) {
			for (int i = 0; i < tmp.size(); i ++) std::cout << tmp[i] << ' ';
			std::cout << '\n';
		}
		
	}

    return 0;
}