D
题目大意：给定两个整数数组 $a_1, a_2, \ldots, a_n$ 和 $b_1, b_2, \ldots, b_n$。可以保证从 $1$ 到 $2 \cdot n$ 的每个整数恰好出现在其中一个数组中。您需要执行一定数量的操作（可能为零），以同时满足以下两个条件： - 对于每个 $1 \leq i < n$，满足 $a_i < a_{i + 1}$ 和 $b_i < b_{i + 1}$。- 对于每个 $1 \leq i \leq n$，满足 $a_i < b_i$。在每个操作过程中，您只能执行以下三个操作之一： 1. 选择索引 $1 \leq i < n$ 并交换 $a_i$ 和 $a_{i + 1}$。
数据范围：$t(1 \leq t \leq 100)$，$n(1 \leq n \leq 40)$，$a_1, a_2, \ldots, a_n(1 \leq a_i \leq 2 \cdot n)$，$1 \leq b_i \leq 2 \cdot n$。
思路：
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
| using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
vl a(n), b(n);
rep(i, 0, n - 1) cin >> a[i];
rep(i, 0, n - 1) cin >> b[i];
vector<pll> res;
rep(i, 0, n - 2) {
rep(j, 0, n - 2) {
if (a[j] > a[j + 1]) {
res.emplace_back(1, j + 1);
swap(a[j], a[j + 1]);
}
}
}
rep(i, 0, n - 2) {
rep(j, 0, n - 2) {
if (b[j] > b[j + 1]) {
res.emplace_back(2, j + 1);
swap(b[j], b[j + 1]);
}
}
}
frep(i, n - 1, 0) {
if (a[i] >= b[i]) {
res.emplace_back(3, i + 1);
swap(a[i], b[i]);
}
}
cout << sz(res) << endl;
for (auto& p : res) cout << p.first << ' ' << p.second << endl;
return;
}
|
E
题目大意：对于两个整数 $a$ 和 $b$，我们定义 $f(a, b)$ 为 $a$ 和 $b$ 的十进制表示中，相同位置上数字相同的位数。现在给定两个十进制表示长度相同的整数 $l$ 和 $r$，考虑所有满足 $l \leq x \leq r$ 的整数 $x$。需要求出 $f(l, x) + f(x, r)$ 的最小值。
数据范围：$1 \leq t \leq 10^4$，$1 \leq l \leq r < 10^9$。
思路：
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
| using i128 = __int128_t;
void solve() {
string num1, num2;
cin >> num1 >> num2;
int n = num2.length();
int dif = n - num1.length();
map<pair<int, int>, ll> ma;
auto dfs = [&](this auto&& dfs, int cnt, int s, bool limit_low, bool limit_high) -> int {
if (cnt == n) return s;
if (!limit_low && !limit_high && ma.count({cnt, s})) return ma[{cnt, s}];
int res = INT_MAX;
int lo = limit_low && cnt >= dif ? num1[cnt - dif] - '0' : 0;
int hi = limit_high ? num2[cnt] - '0' : 9;
int d = lo;
for (; d <= hi; d++) {
int tem = 0;
if (cnt >= dif && d == num1[cnt - dif] - '0') tem++;
if (d == num2[cnt] - '0') tem++;
res = min(res, dfs(cnt + 1, s + tem, limit_low && d == lo, limit_high && d == hi));
}
if (!limit_high && !limit_low) ma[{cnt, s}] = res;
return res;
};
cout << dfs(0, 0, true, true) << endl;
return;
}
|
