D
题目大意：这是一个交互式问题。有一个长度为 $n$ 的排列 $p^{\ast}$。某人秘密地选择了两个整数 $l,r$（$1 \le l \le r \le n$），并以如下方式修改了排列： - 对于每一个满足 $l \le i \le r$ 的下标 $i$，将 $p_i := p_i + 1$。记 $a$ 为经过上述修改后得到的数组。给定整数 $n$，表示排列 $p$ 的长度。你可以进行一次查询，每次可以选择两个整数 $l, r$（$1 \le l \le r \le n$），并查询原始排列 $p[l\dots r]$ 的子数组和，或修改后数组 $a[l\dots r]$ 的子数组和。对于该查询，系统会返回对应的整数和。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \cdot 10^4$，$\sum n \le 2 \cdot 10^4$。
思路：
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
| ll ask(ll op2, ll l, ll r) {
cout << op2 << ' ' << l << ' ' << r << '\n';
cout.flush();
ll op;
cin >> op;
return op;
}
void report(ll a, ll b) {
cout << "! " << a << ' ' << b << '\n';
cout.flush();
}
void solve() {
ll n;
cin >> n;
ll tem = ask(2, 1, n) - ask(1, 1, n);
ll l = 1, r = n, ans = 1, mid;
auto check = [&](ll mid) -> bool { return ask(2, 1, mid) - ask(1, 1, mid) >= tem; };
while (l <= r) {
mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else
l = mid + 1;
}
report(ans - tem + 1, ans);
return;
}
|
E
题目大意：我们称一个长度为 $m$ 的数组 $[b_1, b_2, \dots, b_m]$ 为回文数组，当且仅当满足以下条件： - 对所有 $1 \le i \le m$，都有 $b_i = b_{m-i+1}$。换句话说，如果一个数组正着和反着读都是一样的，那么它就是回文数组。你现在有一个包含 $n$ 个整数的数组 $[a_1, a_2, \dots, a_n]$，其中 $1 \le a_i \le n$，以及一个整数 $k$。需要恰好进行 $k$ 次如下操作： - 选择一个整数 $x$，其中 $1 \le x \le n$， - 将 $x$ 添加到数组 $a$ 的末尾。你的目标是，使得最终得到的新数组中回文子数组 $^{\ast}$ 的总数最少。
数据范围：$1 \le t \le 10^4$，$3 \le n \le 2\cdot10^5, 1 \le k \le n$，$1 \le a_i \le n$，$\sum n \le 2\cdot10^5$。
思路：
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
42
43
44
45
46
| void solve() {
ll n, k;
cin >> n >> k;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl cnt(n + 1);
rep(i, 0, n - 1) cnt[a[i]]++;
vl re;
rep(i, 1, n) {
if (!cnt[i]) re.push_back(i);
}
if (sz(re) == 0) {
rep(i, 0, k - 1) {
if (i % 3 == 0)
cout << a[n - 3] << ' ';
else if (i % 3 == 1)
cout << a[n - 2] << ' ';
else
cout << a[n - 1] << ' ';
}
cout << endl;
return;
} else if (sz(re) >= 2) {
rep(i, 0, k - 1) {
if (i % 3 == 0)
cout << re[0] << ' ';
else if (i % 3 == 1)
cout << re[1] << ' ';
else
cout << a[n - 1] << ' ';
}
cout << endl;
return;
}
int tem = (a[n - 2] == a[n - 1] ? a[n - 3] : a[n - 2]);
rep(i, 0, k - 1) {
if (i % 3 == 0)
cout << re[0] << ' ';
else if (i % 3 == 1)
cout << tem << ' ';
else
cout << a[n - 1] << ' ';
}
cout << endl;
return;
}
|
F
题目大意：给定一个整数 $n$ 和 $m$ 个区间。每个区间的形式为 $[l_i, r_i]$，满足 $1 \le l_i \le r_i \le n$。注意，区间可以重复。定义 $p$ 为长度为 $n$ 的一个排列，包含所有整数 $0,1,2,\dots,n-1$，且每个只出现一次。有一个多重集合 $M$，最初为空。对于每个区间 $[l_i, r_i]$： - 考虑子数组 $p[l_i \dots r_i]$， - 计算 $v_i = \operatorname{mex}(p[l_i \dots r_i])$， - 将 $v_i$ 插入到 $M$ 中。
数据范围：$1 \le t \le 1000$，$3 \le n \le 3000$，$1 \le m \le 3000$，$1 \le l_i \le r_i \le n$，$\sum n \le 3000$，$\sum m \le 3000$。
思路：
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
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
| void solve() {
ll n, m;
cin >> n >> m;
vector<pll> ma(m);
rep(i, 0, m - 1) {
cin >> ma[i].first >> ma[i].second;
ma[i].first--, ma[i].second--;
}
ll mixx = LLONG_MIN, maxx = LLONG_MAX;
rep(i, 0, m - 1) {
mixx = max(mixx, ma[i].first);
maxx = min(maxx, ma[i].second);
}
vl res(n);
if (mixx <= maxx) {
res[mixx] = 0;
int idx = 1;
rep(i, 0, n - 1) {
if (i == mixx) continue;
res[i] = idx++;
}
rep(i, 0, n - 1) cout << res[i] << ' ';
cout << endl;
return;
}
ll idx = -1;
rep(i, 0, n - 2) {
bool flag = false;
rep(j, 0, m - 1) {
if (ma[j].second == i) {
flag = true;
}
}
if (!flag) idx = i;
}
if (idx != -1) {
res[idx] = 0;
res[idx + 1] = 1;
int idx2 = 2;
rep(i, 0, n - 1) {
if (i == idx || i == idx + 1) continue;
res[i] = idx2++;
}
rep(i, 0, n - 1) cout << res[i] << ' ';
cout << endl;
return;
}
idx = -1;
rep(i, 1, n - 1) {
bool flag = false;
rep(j, 0, m - 1) {
if (ma[j].first == i) {
flag = true;
}
}
if (!flag) idx = i;
}
if (idx != -1) {
res[idx] = 0;
res[idx - 1] = 1;
int idx2 = 2;
rep(i, 0, n - 1) {
if (i == idx || i == idx - 1) continue;
res[i] = idx2++;
}
rep(i, 0, n - 1) cout << res[i] << ' ';
cout << endl;
return;
}
cout << 0 << ' ' << 2 << ' ' << 1 << ' ';
rep(i, 3, n - 1) cout << i << ' ';
cout << endl;
return;
}
|
G
题目大意：如果一棵树所有边两端点编号乘积之和为完全平方数，则称这棵树是美丽的。给定 $n$，需要构造一棵包含 $n$ 个顶点的美丽树，或判断不存在。
数据范围：$1 \le t \le 10^4$，$2 \le n \le 2\times10^5$，$\sum n \le 2\times10^5$。
思路：
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
| void solve() {
ll n;
cin >> n;
if (n == 2) {
cout << -1 << endl;
return;
}
if (n == 3) {
cout << 1 << ' ' << 3 << endl;
cout << 2 << ' ' << 3 << endl;
return;
}
if (n == 4) {
cout << 1 << ' ' << 2 << endl;
cout << 3 << ' ' << 1 << endl;
cout << 4 << ' ' << 1 << endl;
return ;
}
vvi ma(n + 1);
ma[1].push_back(2);
ma[1].push_back(5);
ma[2].push_back(3);
ma[3].push_back(4);
rep(i, 6, n) {
ma[1].pop_back();
ma[2].push_back(i - 1);
ma[1].push_back(i);
}
rep(i, 1, n) {
for (auto& p : ma[i]) cout << i << ' ' << p << endl;
}
return;
}
|
