B
题目大意：构造一个包含 $4 \cdot n$ 个整数的数组，要求满足以下条件： - 每个数字 $1, 2, \dots, n$ 在数组中恰好出现 $4$ 次； - 设 $p_{x, i}$ 表示数字 $x$ 在数组中第 $i$ 次出现的位置。那么对于每个 $x$（$1 \leq x \leq n$），数列 $(p_{x, 2} - p_{x, 1}),\ (p_{x, 3} - p_{x, 2}),\ (p_{x, 4} - p_{x, 3})$ 必须两两不同。
数据范围：$1 \leq t \leq 200$，$2 \leq n \leq 200$。
思路：
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() {
ll n;
cin >> n;
if (n == 1) {
cout << -1 << endl;
return;
}
if (n == 2) {
cout << "1 2 1 1 2 2 1 2" << endl;
return;
}
if (n == 3) {
cout << "1 1 2 1 2 3 1 3 2 2 3 3" << endl;
return;
}
vl res(4 * n);
rep(i, 0, 3) { rep(j, i * n, i * n + n - 1) res[j] = j % n + 1; }
rep(i, 1, 3) {
ll tem = i * (i + 1) / 2;
rep(j, 0, n - 1) res[i * n + j] = (j - tem % n + n) % n + 1;
}
rep(i, 0, 4 * n - 1) cout << res[i] << ' ';
cout << endl;
return;
}
|
C
题目大意：定义任意括号序列的“代价”为其最长子序列是“正规括号序列”$^{\text{∗}}$的长度。给定一个括号字符串 $s$ 和一个整数 $k$，需要从字符串 $s$ 中删除至多 $k$ 个字符，使得最终得到的字符串的代价尽可能小。
数据范围：$1 \le t \le 10^3$，$1 \le n \le 5000$，$0 \le k \le n$，$\sum n \le 5000$。
思路：
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
| using i128 = __int128_t;
void solve() {
ll n, k;
cin >> n >> k;
string s;
cin >> s;
ll tem = 0;
int idx = 0;
ll mixx = 0;
vector<bool> vis(n, true);
rep(i, 0, n - 1) {
tem += (s[i] == '(' ? 1 : -1);
if (tem < mixx) {
mixx = tem;
idx = i + 1;
}
}
vl tem2;
rep(i, 0, idx - 1) {
if (s[i] == '(') tem2.push_back(i);
}
rep(i, idx, n - 1) {
if (s[i] == ')') tem2.push_back(i);
}
string res;
rep(i, 0, n - 1) res.push_back('0');
rep(i, 0, min(1LL * sz(tem2), k) - 1) res[tem2[i]] = '1';
cout << res << endl;
return;
}
|
D
题目大意：在超市中，相同类型的商品通常会被放在一起，这样可以让货架看起来整齐，也方便顾客找到所需的商品。用一个长度为 $n$ 的数组 $a$ 描述货架，其中 $a_i$ 表示第 $i$ 个位置的商品类型。如果对于所有满足 $1 \le i < j \le n$ 且 $a_i = a_j$ 的位置，下面的条件成立，则称货架排列是正确的：对于从 $i$ 到 $j$ 之间的每个 $k$，都有 $a_k = a_i$。换句话说，每种类型的商品在货架上都必须形成一个连续的块。你可以至多选择两个不同的位置并交换这两处商品，也可以选择不交换。请判断是否可能通过至多一次交换操作后，使得货架排列正确。
数据范围：$1 \le t \le 10^4$，$2 \le n \le 2 \cdot 10^5$，$1 \le a_i \le 10^9$，$\sum n \le 2 \cdot 10^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
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
| using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
map<ll, vl> ma;
rep(i, 0, n - 1) ma[a[i]].push_back(i);
ll tem = 0;
vl tem2;
for (auto& [x, y] : ma) {
if (y[sz(y) - 1] - y[0] + 1 != sz(y)) {
tem++;
tem2.push_back(x);
}
}
if (tem == 0) {
cout << "YES" << endl;
return;
}
if (tem > 2) {
cout << "NO" << endl;
return;
}
set<pll> s;
for (auto& p : tem2) {
ll m = sz(ma[p]);
if (ma[p][m - 1] - ma[p][1] + 1 <= m) {
rep(i, 0, 1) {
ll cnt = 0;
ll idx = -1;
if (i == 0) {
if (ma[p][1] + m - 1 >= n) continue;
rep(j, ma[p][1], ma[p][1] + m - 1) {
if (a[j] != p) {
cnt++;
idx = j;
}
}
if (cnt != 1 || idx == -1) continue;
} else {
if (ma[p][m - 1] - m + 1 < 0) continue;
rep(j, ma[p][m - 1] - m + 1, ma[p][m - 1]) {
if (a[j] != p) {
cnt++;
idx = j;
}
}
if (cnt != 1 || idx == -1) continue;
}
s.insert(make_pair(min(ma[p][0], idx), max(ma[p][0], idx)));
}
}
if (ma[p][m - 2] - ma[p][0] + 1 <= m) {
rep(i, 0, 1) {
ll cnt = 0;
ll idx = -1;
if (i == 0) {
if (ma[p][0] + m - 1 >= n) continue;
rep(j, ma[p][0], ma[p][0] + m - 1) {
if (a[j] != p) {
cnt++;
idx = j;
}
}
if (cnt != 1 || idx == -1) continue;
} else {
if (ma[p][m - 2] - m + 1 < 0) continue;
rep(j, ma[p][m - 2] - m + 1, ma[p][m - 2]) {
if (a[j] != p) {
cnt++;
idx = j;
}
}
if (cnt != 1 || idx == -1) continue;
}
s.insert(make_pair(min(ma[p][m - 1], idx), max(ma[p][m - 1], idx)));
}
}
}
for (auto& [x, y] : s) {
swap(a[x], a[y]);
map<ll, ll> ma2;
bool flag = true;
rep(i, 0, n - 1) {
if (i == 0 || a[i] != a[i - 1]) {
if (ma2.count(a[i])) {
flag = false;
break;
}
}
ma2[a[i]]++;
}
if (flag) {
cout << "YES" << endl;
return;
}
swap(a[x], a[y]);
}
cout << "NO" << endl;
return;
}
|
E1
题目大意：这是该题的简单版本。在本版本中，$n$ 的上限以及所有测试用例中 $n$ 的总和都不超过 $2\,000$；此外，测试用例的最大数量为 $200$。有一个长度为 $n$ 的排列 $p$ $^{\text{∗}}$。它通过某个通信信道被传送，方法如下：首先，将排列中每个数字 $p_{i}$ 的所有 $0$ 位的对应比特按顺序拼接为长度为 $n$，只含 $0$ 和 $1$ 的字符串；接着同理将所有 $1$ 位拼接成一个字符串，依此类推直到数字 $n$ 的最高有效位。你收到了全部这些字符串，但每行对应的是第几位的信息顺序已经丢失。也就是说，这些字符串被乱序接收。在上述例子中，收到的顺序可能是 “1010”、 “0001” 和 “1100”。
数据范围：$1 \le t \le 200$，$1 \le n \le 2\,000$，$\sum n \le 2\,000$。
思路：
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
| using i128 = __int128_t;
constexpr int MX = 21;
ll F[MX]; // 预处理阶乘
ll INV_F[MX]; // 预处理逆元
auto init = [] {
F[0] = 1;
for (int i = 1; i < MX; i++) F[i] = F[i - 1] * i; // 预处理阶乘
return 0;
}();
void solve() {
ll n;
cin >> n;
ll m = 0;
while ((1LL << m) <= n) m++;
vector<string> a(m);
rep(i, 0, m - 1) cin >> a[i];
vl cnt(m);
rep(i, 1, n) {
rep(j, 0, m - 1) {
if (i >> j & 1) cnt[j]++;
}
}
map<ll, vl> ma;
rep(i, 0, m - 1) ma[cnt[i]].push_back(i);
map<ll, vl> ma2;
rep(i, 0, m - 1) {
ll tem = 0;
rep(j, 0, n - 1) tem += (a[i][j] == '1');
ma2[tem].push_back(i);
}
for (auto& [x, y] : ma) {
if (!ma2.count(x) || sz(ma2[x]) != sz(y)) {
cout << 0 << endl;
return;
}
}
vl tem(m);
for (auto& [x, y] : ma2) {
rep(i, 0, sz(y) - 1) tem[ma[x][i]] = y[i];
}
vb vis(n + 1, false);
rep(i, 0, n - 1) {
ll tem2 = 0;
rep(j, 0, m - 1) {
if (a[tem[j]][i] == '1') tem2 += (1LL << j);
}
if (tem2 <= 0 || tem2 > n || vis[tem2]) {
cout << 0 << endl;
return;
}
vis[tem2] = true;
}
ll ans = 1;
for (auto& [x, y] : ma2) {
ans *= F[sz(y)];
map<string, ll> ma3;
for (auto& p : y) ma3[a[p]]++;
for (auto& [a, b] : ma3) ans /= F[b];
}
cout << ans << endl;
return;
}
|
E2
题目大意：这是该问题的困难版本。在本版本中，$n$ 的上限以及所有测试用例中 $n$ 的总和为 $2 \cdot 10^5$；此外，测试用例的最大数量为 $10^4$。有一个长度为 $n$ 的排列 $p$ $^{\text{∗}}$。它被通过如下的通信信道发送：首先，将排列中每个数 $p_{i}$ 的第 $0$ 位二进制比特拼成一个长度为 $n$ 的 $01$ 字符串发送；然后，同样方法发送第 $1$ 位比特……依次直到 $n$ 的最高有效二进制位。你收到了所有这些字符串，但它们关于每行对应第几比特的信息丢失了，也就是说，这些字符串的顺序被打乱。在上述例子中，字符串可能以 “1010”、“0001” 和 “1100” 的顺序到达。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \cdot 10^5$，$\sum n \le 2 \cdot 10^{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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| using i128 = __int128_t;
constexpr int MX = 21;
ll F[MX]; // 预处理阶乘
ll INV_F[MX]; // 预处理逆元
auto init = [] {
F[0] = 1;
for (int i = 1; i < MX; i++) F[i] = F[i - 1] * i; // 预处理阶乘
return 0;
}();
void solve() {
ll n;
cin >> n;
ll m = 0;
while ((1LL << m) <= n) m++;
vector<string> a(m);
rep(i, 0, m - 1) cin >> a[i];
vl cnt(m);
rep(i, 1, n) {
rep(j, 0, m - 1) {
if (i >> j & 1) cnt[j]++;
}
}
map<ll, vl> ma;
rep(i, 0, m - 1) ma[cnt[i]].push_back(i);
map<ll, vl> ma2;
rep(i, 0, m - 1) {
ll tem = 0;
rep(j, 0, n - 1) tem += (a[i][j] == '1');
ma2[tem].push_back(i);
}
for (auto& [x, y] : ma) {
if (!ma2.count(x) || sz(ma2[x]) != sz(y)) {
cout << 0 << endl;
return;
}
}
vl tem(m);
for (auto& [x, y] : ma2) {
rep(i, 0, sz(y) - 1) tem[ma[x][i]] = y[i];
}
vb vis(n + 1, false);
rep(i, 0, n - 1) {
ll tem2 = 0;
rep(j, 0, m - 1) {
if (a[tem[j]][i] == '1') tem2 += (1LL << j);
}
if (tem2 <= 0 || tem2 > n || vis[tem2]) {
cout << 0 << endl;
return;
}
vis[tem2] = true;
}
ll ans = 1;
for (auto& [x, y] : ma2) {
ans *= F[sz(y)];
map<string, ll> ma3;
for (auto& p : y) ma3[a[p]]++;
for (auto& [a, b] : ma3) ans /= F[b];
}
cout << ans << endl;
return;
}
|
