1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> cnt(n);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
x--;
cnt[x]++;
}
int maxx = 0;
for (int i = 0; i < n; i++) {
maxx = max(maxx, cnt[i]);
}
cout << (n - maxx) << endl;
}
return 0;
}
|
每个数只会交换一次，模拟所有交换然后判断是否合法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 1; i < n; i++) {
if (a[i] == a[i - 1] - 1) {
swap(a[i], a[i - 1]);
}
}
cout << (is_sorted(a.begin(), a.end()) ? "YES" : "NO") << endl;
}
return 0;
}
|
偶数的答案显然。对于奇数，必然有一个数出现三次，其下标之差是勾股数，最小的勾股数是 $3^{2}+4^{2}=5^{2}$，最靠近的三个下标是 $1,10,26$，因此如果 $n$ 是小于 $27$ 的奇数就无解。
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
| #include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
if (n % 2 == 0) {
for (int i = 0; i < n / 2; i++) {
cout << (i + 1) << " " << (i + 1) << " ";
}
cout << endl;
} else if (n < 27) {
cout << "-1\n";
} else {
cout << "1 2 3 3 1 ";
for (int i = 0; i < 6; i++) {
cout << (i + 4) << " " << (i + 4) << " ";
}
cout << "2 ";
for (int i = 0; i < 4; i++) {
cout << (i + 10) << " " << (i + 10) << " ";
}
cout << "2 ";
for (int i = 0; i < (n - 27) / 2; i++) {
cout << (i + 14) << " " << (i + 14) << " ";
}
cout << endl;
}
}
return 0;
}
|
对于某两个相邻连通块 $L,R$，如果 $L$ 的最大值比 $R$ 的最小值小，那么 $R$ 的任意点就能够走到 $L$ 的任意点。连通 $L,R$，并将 $R$ 的答案更新为 $L$ 的最大值。
用并查集维护所有的连通块。由于每个连通块都是区间，也可以用栈维护。时间复杂度 $\Theta(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
| #include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<array<int, 3>> stk;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
auto [minn, maxx, len] = array{ x, x, 1 };
while (!stk.empty() && stk.back()[1] > minn) {
minn = min(minn, stk.back()[0]);
maxx = max(maxx, stk.back()[1]);
len += stk.back()[2];
stk.pop_back();
}
stk.push_back({ minn, maxx, len });
}
for (auto [minn, maxx, len] : stk) {
for (int i = 0; i < len; i++) {
cout << maxx << " ";
}
}
cout << "\n";
}
return 0;
}
|
设 $u$ 子树对应的二叉树最低高度为 $h_{u}$。
因此转移方程为
维护所有 $2$ 的幂次，模拟加法。时间复杂度 $\Theta(n\log 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
| #include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> p(n);
for (int i = 1; i < n; i++) {
cin >> p[i];
p[i]--;
}
vector<priority_queue<int, vector<int>, greater<>>> Q(n);
vector<int> h(n);
for (int i = n - 1; i >= 0; i--) {
while (Q[i].size() > 1) {
int x = Q[i].top(); Q[i].pop();
int y = Q[i].top(); Q[i].pop();
Q[i].push(max(x, y) + 1);
}
h[i] = max(h[i], Q[i].empty() ? 0 : Q[i].top());
if (i) {
Q[p[i]].push(h[i]);
h[p[i]] = max(h[p[i]], h[i] + 1);
}
}
cout << h[0] << endl;
}
return 0;
}
|
