Codeforces Round 861 (Div. 2)（A~D）

A. Lucky Numbers

给出边界l和r，在区间[l, r]之间找到幸运值最大的数字。一个数字的幸运值被定义为数位差的最大值，即数字中最大的数位和最小的数位的差。

思路：因为涉及到至少两位，即个位和十位变化最快，最容易得到相差最多的两个数位，所以我们只需要暴力判断几百个数即可，因为在100个数之内两个数一定遍历过了所有情况，这样额复杂度也是可以通过的。

AC Code：

#include <bits/stdc++.h>

typedef long long ll;
const int N = 2e5 + 5;
int t, l, r;

int getans(int x) {
	int max = 0, min = 100;
	while(x) {
		int num = x % 10;
		max = std::max(max, num);
		min = std::min(min, num);
		x /= 10;
	}
	return max - min;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin >> t;
	while(t --) {
		std::cin >> l >> r;
		int max = -1, ans;
		for(int i = l; i <= std::min(l + 300, r); i ++) {
			if(max < getans(i))
				max = getans(i), ans = i;
		}
		std::cout << ans << '\n';
	}
	return 0;
}

 B. Playing in a Casino

给出n个数组，对于每对数组，计算题目中给出的值的和。

思路：观察计算操作，我们需要对于每一列进行操作，而且可以发现排序完成后每个数对于结果的贡献是(n - i) * a[i] - (i - 1) * a[i]，其中i是该数的索引，n是数字个数。这样遍历一遍计算结果即可。

AC Code：

#include <bits/stdc++.h>

typedef long long ll;
const int N = 2e5 + 5;
int t, n, m;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin >> t;
	while(t --) {
		std::cin >> n >> m;
		ll a[n + 1][m + 1], b[m + 1][n + 1];
		for(int i = 1; i <= n; i ++) {
			for(int j = 1; j <= m; j ++) {
				std::cin >> a[i][j];
			}
		}
		ll ans = 0;
		for(int j = 1; j <= m; j ++) {
			for(int i = 1; i <= n; i ++) {
				b[j][i] = a[i][j];
			}
			std::sort(b[j] + 1, b[j] + 1 + n, std::greater<ll>());
			for(int i = 1; i <= n; i ++) {
				ans += (n - 2 * i + 1) * b[j][i];
			}
		}
		std::cout << ans << '\n';
	}
	return 0;
}

 C. Unlucky Numbers

题目大意与A一样，但是在这个题要求我们求幸运值最小的数字。

思路：其实看到这个题，很容易会想到对于每一位进行操作，这样的操作是在时间复杂度的允许范围内的， 也是属于比较普遍的做法。考虑这样一种做法，目标数字的高位与l或r相同，后面的几位都是相同的，这样可以尽可能缩小后面几位的差别对结果的影响，具体见代码。

AC Code：

#include <bits/stdc++.h>

typedef long long ll;
const int N = 2e5 + 5;
int t;
ll l, r;

int getans(ll x) {
	ll max = 0, min = 10;
	while(x) {
		max = std::max(max, x % 10);
		min = std::min(min, x % 10);
		x /= 10;
	}
	return max - min;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin >> t;
	while(t --) {
		std::cin >> l >> r;
		if(l < 10 || l == r) {
			std::cout << l << '\n';
			continue;
		}
		int a[20], b[20];
		int len1 = 0, len2 = 0;
		ll num = l;
		while(num) a[++ len1] = num % 10, num /= 10;
		num = r;
		while(num) b[++ len2] = num % 10, num /= 10;
		int ans = 10;
		ll val = -1;
		int sum = getans(l);
		if(sum < ans)
			val = l, ans = sum;
		sum = getans(r);
		if(sum < ans)
			val = r, ans = sum;
		ll x = 0;
		for(int i = len1; i >= 1; i --) {
			for(int j = 0; j <= 9; j ++) {
				ll tt = x;
				for(int k = i; k >= 1; k --) {
					tt = tt * 10 + j;
				}
				if(tt < l || tt > r) continue;
				int res = getans(tt);
				if(res < ans)
					ans = res, val = tt;
			}
			x = x * 10 + a[i];
		}
		x = 0;
		for(int i = len2; i >= 1; i --) {
			for(int j = 0; j <= 9; j ++) {
				ll tt = x;
				for(int k = i; k >= 1; k --) {
					tt = tt * 10 + j;
				}
				if(tt < l || tt > r) continue;
				int res = getans(tt);
				if(res < ans)
					ans = res, val = tt;
			}
			x = x * 10 + b[i];
		}
		std::cout << val << '\n';
	}
	return 0;
}

D. Petya, Petya, Petr, and Palindromes

思路：正向思考并不容易算，我们可以考虑反着来。可以对于每一对数字的贡献计算，在全部的对数中减去不做出贡献的数对。因为k一定是奇数，所以对称的位置的奇偶性都是相同的，我们可以对于每个数计算与它可以配对的数量，具体做法可以在区间内二分找到配对的个数。

AC Code：

#include <bits/stdc++.h>

typedef long long ll;
#define int long long
const int N = 2e5 + 5;
int n, k;
std::vector<int> vec[N][2];

signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin >> n >> k;
	if(k == 1) {
		std::cout << 0 << '\n';
		return 0;
	}
	ll ans = (n - k + 1) * (k / 2);
	for(int i = 1; i <= n; i ++) {
		int x;
		std::cin >> x;
		vec[x][i & 1].push_back(i);
	}
	auto get = [&](const std::vector<int> &v, int l, int r) {
		return upper_bound(v.begin(), v.end(), r) - lower_bound(v.begin(), v.end(), l);
	};
	for(int i = 0; i < 2; i ++) {
		for(int j = 1; j <= 200000; j ++) {
			for(auto u : vec[j][i]) {
				int l = std::max((k - 1) + 2 - u, u - k + 1);
				int r = std::min(u - 2, 2 * n - (k - 1) - u);
				if(l <= r) ans -= get(vec[j][i], l, r);
			}
		}
	}
	std::cout << ans << '\n';
	return 0;
}

 os：学着写一下匿名函数，，感觉很方便但是总是记不住格式QWQ