GYM102576F The Halfwitters 题解
有临项交换和排序可以考虑逆序对。每次交换相邻逆序可以恰好减少一个逆序对，因而恰好逆序对个数次就可以排序完毕。
操作二的实质是将逆序对个数从
因而每个操作仅使用前两个操作的最小代价是好求的。下文称作暴力还原的代价。
接下来引入操作
考虑最后的策略是什么：
- 一直选择操作
，直到当前逆序对个数的最优策略是直接暴力还原为止。
不妨假设
相当于是转一个转盘，一些位置（最优策略是继续转）写着再转一次，剩下位置写的是暴力还原的代价。
令
从刚刚的转转盘的组合意义或者解方程都比较容易得到这个式子。
是转转盘直到不是“再来一次”的代价。
表示剩下暴力还原的期望。
解方程的情况就是，
其中有
我们将所有逆序对个数按照代价排序。假设第
不难猜到一个结论：
引理
：将一个直接还原代价小于当前转转盘代价的逆序对个数直接还原不劣。同样的，将一个直接还原代价大于转转盘的代价的逆序对个数转转盘也不劣。
接下来考虑证明。假设这个元素是
考虑对
直接还原的代价小于
考虑这个式子：
不妨另分子上为
考虑直接还原会产生什么变化。
对于
那么，
我们要比较
分母上显然大于
对于第二个命题的情况，会发现改变的是有
我们接下来还有一个观察。
引理
：最优 集合的选择必然是直接还原的代价大于某个阈值时加入 ，否则加入 。
对于
此时我们就得到了一个做法：一直向
此时根据引理
此时任意让一组直接还原代价小于
假设这个集合是
做差，有
请注意，每一项
另一个命题的证明也类似。
因而不优。证毕。
那么这个策略就是对的了。
[!info]- 参考代码
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118>#include <algorithm>
>#include <array>
>#include <cassert>
>#include <iostream>
>#include <numeric>
>#include <vector>
>using uint = unsigned int;
>using ll = long long;
>using ull = unsigned long long;
>namespace solve {
>struct fraction {
ull a;
ull b;
void reduce() {
ull g = std::gcd(a, b);
a /= g;
b /= g;
}
>};
>std::array<std::vector<ull>, 17> cache;
>void solve() {
uint n, d;
ull a, b, c;
std::cin >> n >> a >> b >> c >> d;
const ull full = n * (n - 1) / 2;
if (cache[n].empty()) {
std::vector<std::vector<ull>> dp(1 << n, std::vector<ull>(full + 1));
dp[0][0] = 1;
for (size_t i = 0; i < 1u << n; i++) {
for (size_t j = 0; j <= full; j++) {
for (size_t nxt = 0; nxt < n; nxt++) {
if (!((i >> nxt) & 1)) {
auto delta = __builtin_popcountll(i) -
__builtin_popcountll(((1 << nxt) - 1) & i);
if (j + delta > full) {
continue;
}
dp[i | (1 << nxt)][j + delta] += dp[i][j];
}
}
}
}
cache[n] = dp.back();
}
std::vector<ull> brute_force(cache[n].size());
std::vector<std::pair<ull, ull>> sorted_bf;
ull total = std::accumulate(cache[n].begin(), cache[n].end(), 0ull);
for (size_t i = 0; i < brute_force.size(); i++) {
brute_force[i] = std::min(i * a, (full - i) * a + b);
sorted_bf.push_back({brute_force[i], cache[n][i]});
}
std::sort(sorted_bf.begin(), sorted_bf.end());
ull less_cnt = 0;
ull sum_cost = 0; // 1e13 * 100 * 1e3，极限可以。
uint sep = 0;
for (size_t i = 1; i <= sorted_bf.size(); i++) {
less_cnt += sorted_bf[i - 1].second;
sum_cost += sorted_bf[i - 1].first * sorted_bf[i - 1].second;
if (i == sorted_bf.size() ||
sorted_bf[i].first * less_cnt > total * c + sum_cost) {
sep = i;
break;
}
}
fraction f{total * c + sum_cost, less_cnt};
f.reduce();
for (size_t i = 0; i < d; i++) {
uint vis = 0;
ull inv = 0;
for (size_t j = 0; j < n; j++) {
uint x;
std::cin >> x;
x--;
inv += j - __builtin_popcount(((1u << x) - 1) & vis);
vis |= (1 << x);
}
assert(inv < brute_force.size());
if (brute_force[inv] > sorted_bf[sep - 1].first) {
std::cout << f.a << "/" << f.b << "\n";
}
else {
std::cout << brute_force[inv] << "/1\n";
}
}
>}
>} // namespace solve
>int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
uint t;
std::cin >> t;
while (t--) {
solve::solve();
}
std::cout << std::flush;
return 0;
>}