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

 给出一个长为n的数组，对于每个长度为k的连续数组，它的代价是变为回文数组的最小修改次数。求所有长度为k的数组代价之和。

思路：正向思考并不容易算，我们可以考虑反着来。可以对于每一对数字的贡献计算，在全部的对数中减去不做出贡献的数对。因为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