A. To Zero

Problem - A - Codeforces

思路：贪心，开始时分n为奇偶分类讨论，每次减能减的最大值即可

#include <iostream>
#include <vector>
#define int long long
using namespace std;


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int t;
	cin >> t;
	while(t --)
	{
		int n, k;
		cin >> n >> k;
		if(n % 2)
		{
			n -= k;
			int cnt = 1;
			if(n % (k - 1) == 0) cout << cnt + (n / (k - 1)) << '\n';
			else cout << cnt + (n / (k - 1)) + 1 << '\n';
		}
		else
		{
			if(n % (k - 1) == 0) cout << n / (k - 1) << '\n';
			else cout << n / (k - 1) + 1 << '\n';
		}
	}
	return 0;
}

B. Array Recoloring

Problem - B - Codeforces

思路：分k是否等于1来分类讨论，如果k不等于1，通过模拟可以发现，就是取最大的k + 1个数，如果k等于1，那就取2个元素，而且第二个元素要么是第一个元素，要么是最后一个元素，遍历一遍即可

#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int t;
	cin >> t;
	while(t --)
	{
		int n, k;
		cin >> n >> k;
		vector<int> a(n, 0);
		for(int i = 0; i < n; i ++) cin >> a[i];
		
		if(k != 1)
		{
			sort(a.begin(), a.end());
			int cnt = 0;
			int pos = n;
			int ans = 0;
			while(cnt < k + 1)
			{
				ans += a[-- pos];
				cnt ++;
			}
			cout << ans << '\n';
		}
		else
		{
			int ans = a[0] + a[n - 1];
			for(int i = 1; i < n - 1; i ++)
			{
				int tmp = max(a[i] + a[0], a[i] + a[n - 1]);
				ans = max(ans, tmp);
			}
			cout << ans << '\n';
		}
		
	}
	return 0;
}

C. Two Colors

Problem - C - Codeforces

思路：我们先将数组给排序，对于数组的每个元素x, 我们要找到一个y使得 x + y >= n, 所以直接用二分查找即可，然后这题的难点在于，我们要观察到 如果x + y >= n，那么这一组数对答案的贡献就是(x + y - n + 1) * 2, 然后因为y这个数已经满足了x + y >= n了，所以y后面的数一定也是满足的，此时如果暴力再去枚举y后面的数是会超时的，所以我们将 [(x + y - n + 1) * 2] 这个式子给拆开（x- n + 1）* 2 + y * 2,那么假设y的位置是p, 那么后面就有m - p + 1个数满足条件，所以我们就会算(m - p + 1)个(x - n + 1)以及2 * ()， 前者是固定的，后者我们用一个后缀和求即可，但是我们要注意如果 y == n 或者 x == n，那我们还要减掉这种情况，所以我们再开个cnt数组记录p位置后面有多少个元素 == n

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define int long long
using namespace std;

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int t;
	cin >> t;
	while(t --)
	{
		int n, m;
		cin >> n >> m;
		vector<int> a(m + 1, 0);
		for(int i = 1; i <= m; i ++) cin >> a[i];
		
		sort(a.begin() + 1, a.begin() + 1 + m);
		
		vector<int> suf(m + 2, 0);
		vector<int> cnt(m + 2, 0); // 记录该位置后面有多少个 a[i] == n
		
		for(int i = m; i >= 1; i --)
		{
			cnt[i] = cnt[i + 1];
			if(a[i] == n) cnt[i] ++;
			suf[i] = suf[i + 1] + a[i];
		}
		
		int ans = 0;
		
		for(int i = 1; i <= m; i ++)
		{
			int pos = lower_bound(a.begin() + 1 + i, a.begin() + 1 + m, n - a[i]) - a.begin();
		//	cout << pos << '\n';
			if(pos == m + 1) continue;
			
			ans += (suf[pos] + (m - pos + 1) * (a[i] - n + 1)) * 2;
			
			ans -= cnt[i + 1] * 2;
			if(a[i] == n) ans -= (m - pos + 1) * 2;
		}
		cout << ans << '\n';
	}
	
}

D. Equalization

Problem - D - Codeforces

思路：直接暴力枚举x和y分别需要右移多少位后相等，然后取一个最小代价即可. 设dp[i][j]表示x右移i位，y右移j位时的最小代价，因为每个k只能用1次，所以我们要和01背包一样，倒着枚举i和j,所以我们先预处理dp数组即可

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	vector<vector<int>> dp(65, vector<int>(65, 1e18));
	
	// dp[i][j] 表示x右移i位， y右移j位的最小代价
	dp[0][0] = 0;
	
	auto init = [&]() -> void{
		for(int k = 1; k <= 60; k ++)
		{
			for(int i = 60; i >= 0; i --)
			{
				for(int j = 60; j >= 0; j --)
				{
					if(i >= k) dp[i][j] = min(dp[i][j], dp[i - k][j] + (1LL << k));
					if(j >= k) dp[i][j] = min(dp[i][j], dp[i][j - k] + (1LL << k));
				}
			}
		}
	};
	
	int t;
	cin >> t;
	
	init();
	
	while(t --)
	{
		int ans = 1e18;
		int x, y;
		cin >> x >> y;
		for(int i = 0; i <= 60; i ++)
		{
			for(int j = 0; j <= 60; j ++)
			{
				int xx = x >> i;
				int yy = y >> j;
				if(xx == yy)
				{
					ans = min(ans, dp[i][j]);
				}
			}
		}
		cout << ans << '\n';
	}
	
}