D
题目大意：Akito 厌倦了在银行当普通锁匠的工作，因此他决定进入魔法学院并成为世界上最强的巫师！然而，为了入学，他需要解决考试中的唯一一道题目，而这位雄心勃勃的英雄却未能成功。题目给定一个长度为 $n$ 的数组 $a$。Akito 需要在使用恰好一次咒语后，使数组中的逆序对数量 $^{\text{∗}}$ 最小化。咒语的使用方式很简单：Akito 必须选择两个数 $l$ 和 $r$（满足 $1 \le l \le r \le n$），并对子数组 $[l, r]$ 进行一次向左循环移位。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 2000$，$1 \le a_i \le 2000$，$\sum n^2 \le 4 \cdot 10^6$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
int idx1 = -1, idx2 = -1;
int maxx = INT_MIN;
rep(i, 0, n - 1) {
int tem = 0;
int tem2 = 0;
rep(j, i, n - 1) {
tem += (a[j] < a[i]);
tem2 += (a[j] > a[i]);
if (tem - tem2 > maxx) {
idx1 = i, idx2 = j;
maxx = tem - tem2;
}
}
}
cout << idx1 + 1 << ' ' << idx2 + 1 << endl;
return;
}
|
E
题目大意：Akito 决定学习一个强大的新咒语。由于这个咒语拥有无可估量的力量，它必然需要大量空间和精心准备。为此，Akito 来到了一片空地。我们将这片空地表示为一个笛卡尔坐标系。为了施展咒语，Akito 需要在空地的不同整数坐标处放置 $0 \le n \le 500$ 根法杖，使得恰好存在 $k$ 对 $(i, j)$ 满足 $1 \le i < j \le n$ 且 $\rho(i, j) = d(i, j)$。
数据范围：$1 \le t \le 1000$，$0 \le k \le 10^5$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void solve() {
int k;
cin >> k;
vector<pii> ma;
vl ma2;
rep(i, 2, 499) ma2.emplace_back(i * (i - 1) / 2);
int idx1 = 0, idx2 = 0;
while (k > 0) {
int tem2 = ranges::upper_bound(ma2, k) - ma2.begin() - 1;
rep(i, 0, tem2 + 1) {
ma.emplace_back(idx1, idx2);
idx2++;
}
idx1++;
k -= ma2[tem2];
}
cout << sz(ma) << endl;
for (auto& p : ma) cout << p.first << ' ' << p.second << endl;
return;
}
|
F
题目大意：怪物正在逼近城市，为了保护它，Akito 必须在城市周围创建一个防护场。众所周知，防护场有不同的等级。Akito 选择了等级为 $n$ 的防护场。为了构建这个防护场，需要一个特殊咒语，即伟大魔法三角（表示为二维数组 $T$）的第 $n$ 行。我们将这个数组称为 $T$。魔法三角的定义如下： - 第 $i$ 行包含 $i$ 个整数。- 第一行唯一的整数是 $k$。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 10^6$，$1 \le k < 2^{31}$，$\sum n \le 10^6$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
| void solve() {
int n, k;
cin >> n >> k;
vi a(n);
frep(i, 31, 0) {
if (((k >> i) & 1) == 0) continue;
rep(j, 0, n - 1) { a[j] += (1 << i) * (((n - 1) & j) == j); }
}
rep(i, 0, n - 1) cout << a[i] << ' ';
cout << endl;
return;
}
|
G
题目大意：经过三百年的史莱姆养殖，Akito 终于获得了魔法数字 $n$。当他找到商人准备兑换黄金时，商人却给了他一个任务。商人表示，完成这个任务需要用到技能 $\text{rev}(n, p)$，而 Akito 恰好最近学会了这个技能。$\text{rev}(n, p)$ 表示以下操作流程： 1. 将数字 $n$ 以 $p$ 进制表示，记作 $n = \overline{n_{\ell - 1} \ldots n_1 n_0}$，其中 $\ell$ 是 $n$ 的 $p$ 进制表示的位数长度。2. 反转这个 $p$ 进制表示，得到 $m = \overline{n_0 n_1 \ldots n_{\ell - 1}}$。
数据范围：$1 \le t \le 5000$，$1 \le n \le 3 \cdot 10^5$，$2 \le k \le 10^{18}$。
思路：
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
35
36
37
38
39
40
41
| const ll MOD = 1e9 + 7;
const ll inv2 = 500000004;
const ll inv6 = 166666668;
void solve() {
ll n, k;
cin >> n >> k;
ll ans = 0;
ans += max(k - n, 0LL) % MOD * n % MOD;
int B = (int)sqrt(n);
rep(i, 2, min(k, n)) {
if (i <= B) {
ll res = 0;
ll tem = n;
while (tem) {
res = (res * i % MOD + tem % i) % MOD;
tem /= i;
}
ans = (ans + res) % MOD;
} else {
auto check = [&]() -> void {
for (ll l = i, r; l <= min(k, n); l = r + 1) {
ll v = n / l;
r = min(min(n, k), n / v);
ll cnt = (r - l + 1) % MOD;
ans += n % MOD * (l + r) % MOD * cnt % MOD * inv2 % MOD;
ans = (ans + MOD) % MOD;
ll tem = r * (r + 1) % MOD * (2 * r + 1) % MOD * inv6 % MOD;
ll tem2 = (l - 1) * l % MOD * (2 * l - 1) % MOD * inv6 % MOD;
ans -= v * (tem - tem2 + MOD) % MOD;
ans = (ans + MOD) % MOD;
ans += v * cnt % MOD;
ans %= MOD;
}
};
check();
break;
}
}
cout << ans << endl;
return;
}
|
