B
题目大意：这是该问题的简单版本。不同之处在于本题中只有一个特殊下标（$k=1$）。只有在你解决了所有版本的问题后，你才能进行 hack。给定一个长度为 $n$ 的二进制数组 $a$ 以及 $k$ 个特殊下标 $p_1, p_2, \ldots, p_k$（$1 \le p_i \le n$）。已知所有特殊下标处的元素值相同，即 $a_{p_1} = a_{p_2} = \ldots = a_{p_k}$。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \cdot 10^5$，$0 \le a_i \le 1$，$1 \le p_1 < p_2 < \ldots < p_k \le n$，$\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
| void solve() {
int n, k;
cin >> n >> k;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
vi p(k);
rep(i, 0, k - 1) {
cin >> p[i];
p[i]--;
}
int tem = p[0];
int las = tem;
int ans = 0;
rep(i, tem + 1, n - 1) {
if (a[i] != a[tem] && a[i] != a[i - 1]) ans++;
}
las = tem;
int ans2 = 0;
frep(i, tem - 1, 0) {
if (a[i] != a[tem] && a[i] != a[i + 1]) ans2++;
}
int maxx = max(ans, ans2);
cout << 2 * maxx << endl;
return;
}
|
C
题目大意：Prakul 一直在为 Codecraft 设计算法题而努力工作。当他陷入沉思时，他喜欢以奇怪但特定的方式在房间里跳来跳去。一段时间后，他想知道，这样的跳跃方式能否覆盖他房间里的所有瓷砖。Prakul 的房间可以被视作一个 $A$ 矩阵，共有 $n$ 行 $m$ 列。他从 $A_{1,1}$ 开始。如果他现在在 $A_{i,j}$，他可以选择以下两种方式中的一种跳跃： - 向右跳 $b$ 步到 $A_{i,\;((j+b-1)\bmod m)+1}$； - 向下跳 $a$ 步到 $A_{((i+a-1)\bmod n)+1,\;j}$。有一个特殊的限制条件：他可以用任意一种方式作为第一步，但之后必须交替进行两种跳跃。注意，他的房间非常特殊，是环绕的。
数据范围：$1 \le t \le 10^4$，$1 \leq n, m, a, b\leq 10^{9}$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void solve() {
ll n, m, a, b;
cin >> n >> m >> a >> b;
if (__gcd(n, a) != 1 || __gcd(m, b) != 1) {
cout << "NO" << endl;
return;
}
if (__gcd(n, m) > 2) {
cout << "NO" << endl;
return;
}
cout << "YES" << endl;
return;
}
|
D
题目大意：这是本题的困难版本。不同版本的区别在于，本题中可能存在多个特殊下标（$1 \le k \le n$）。只有当你完成所有版本的本题后才能进行 hack。给定一个长度为 $n$ 的二进制数组 $a$，以及 $k$ 个特殊下标 $p_1, p_2, \ldots, p_k$（$1 \le p_i \le n$）。已知所有特殊下标上的元素值都相同（即 $a_{p_1} = a_{p_2} = \ldots = a_{p_k}$）。
数据范围：$1 \le t \le 10^4$，$1 \le k \le n \le 2 \cdot 10^5$，$0 \le a_i \le 1$，$1 \le p_1 < p_2 < \ldots < p_k \le n$，$\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
| void solve() {
int n, k;
cin >> n >> k;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
vi p(k);
rep(i, 0, k - 1) {
cin >> p[i];
p[i]--;
}
vi tem;
rep(i, 0, k - 1) {
if (i == 0) {
int ans = 0;
frep(j, p[i] - 1, 0) {
if (a[j] != a[p[i]] && a[j] != a[j + 1]) ans++;
}
tem.push_back(ans);
}
if (i == k - 1) {
int ans = 0;
rep(j, p[i] + 1, n - 1) {
if (a[j] != a[p[i]] && a[j] != a[j - 1]) ans++;
}
tem.push_back(ans);
} else {
int idx = p[i], idx2 = p[i + 1];
int ans = 0;
int ans2 = 0;
rep(j, p[i] + 1, p[i + 1]) {
if (a[j] != a[p[i]] && a[j] != a[j - 1]) ans++;
}
tem.push_back(ans);
}
}
int ans = 0;
int maxx = 0;
rep(i, 0, k) {
ans += tem[i];
maxx = max(maxx, tem[i]);
}
cout << max(ans, maxx * 2) << endl;
return;
}
|
E
题目大意：给定一个由 $1$ 到 $n$ 组成的排列 $p$。对于任意长度为 $n$ 的排列 $q$，我们称下标 $j$ 支配下标 $i$ 当且仅当满足以下所有条件： - $j > i$， - $p_j > p_i$，并且 - $q_j > q_i$。另有一个长度为 $n$ 的数组 $d$，其中 $d_i$ 表示支配下标 $i$ 的下标数的个数。需要构造一个 $1$ 到 $n$ 的排列 $q$，使得对于每一个 $i$（$1 \le i \le n$），支配下标 $i$ 的下标数量恰好等于 $d_i$。如果存在这样的 $q$，请输出任意一个合法的 $q$。
数据范围：$1 \le t \le 1000$，$1 \le n \le 5000$，$0 \le d_i \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
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
| template <typename T = long long>
class Tree {
vector<T> tree;
public:
// 构造函数：初始化大小为 n 的树状数组，初始所有元素值为 val（外部表现为 0-based）
Tree(int n, T val = 0) : tree(n + 1) {
for (int i = 1; i <= n; i++) {
tree[i] += val;
int nxt = i + (i & -i);
if (nxt <= n) {
tree[nxt] += tree[i];
}
}
}
// 构造函数：使用给定的 vector 在 O(N) 时间内快速初始化建树
Tree(const vector<T>& data) {
int n = data.size();
tree.resize(n + 1);
for (int i = 1; i <= n; i++) {
tree[i] += data[i - 1]; // data是 0-based
int nxt = i + (i & -i);
if (nxt <= n) {
tree[nxt] += tree[i];
}
}
}
// 单点修改：将 0-based 下标 i 处的元素增加 val
void add(int i, T val = 1) {
for (++i; i < tree.size(); i += i & (-i)) {
tree[i] += val;
}
}
// 前缀求和：计算 0-based 下标区间 [0, i] 内的所有元素之和
T pre(int i) const {
T res = 0;
for (++i; i > 0; i &= i - 1) {
res += tree[i];
}
return res;
}
// 区间求和：计算 0-based 下标区间 [l, r] 内的所有元素之和
T query(int l, int r) const {
if (r < l) {
return 0;
}
return pre(r) - pre(l - 1); // 当 l=0 时, pre(-1) 会合理地返回 0
}
// 树上二分查找：返回满足前缀和 >= val 的最小 0-based 下标
int lower_bound(T val) const {
int w = bit_width(tree.size() - 1);
int res = 0;
T s = 0;
for (int i = w - 1; i >= 0; i--) {
int nxt = res + (1 << i);
if (nxt < tree.size() && tree[nxt] + s < val) {
res += (1 << i);
s += tree[nxt];
}
}
return res; // 返回 0-based 下标：内部 1-based 下标为 res + 1，因此 0-based 为 res
}
};
void solve() {
int n;
cin >> n;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
vi d(n);
rep(i, 0, n - 1) cin >> d[i];
Tree tree(n + 1);
Tree tree2(n + 1, 1);
vi res(n, INT_MAX);
frep(i, n - 1, 0) {
int tem2 = n - 1 - i - tree.pre(a[i]);
if (tem2 < d[i]) {
cout << -1 << endl;
return;
}
tree.add(a[i], 1);
}
vi res2;
frep(i, n - 1, 0) {
vi tem3;
rep(j, 0, sz(res2) - 1) {
if (a[res2[j]] > a[i]) {
tem3.push_back(res2[j]);
}
}
int tem2 = sz(tem3) - d[i];
if (tem2 == 0)
res2.insert(res2.begin(), i);
else {
int tem4 = tem3[tem2 - 1];
int idx = -1;
rep(j, 0, sz(res2)) {
if (tem4 == res2[j]) {
idx = j;
break;
}
}
res2.insert(res2.begin() + idx + 1, i);
}
}
rep(i, 0, n - 1) res[res2[i]] = i + 1;
for (int& p : res) cout << p << ' ';
cout << endl;
return;
}
|
