D
题目大意：给定一个长度为 $n$ 的序列 $b$，要求构造出另一个长度为 $n$ 的序列 $a$，使得对于新序列中每个元素 $a_i$，满足 $a_i$ 在 $a$ 中的出现次数恰好为 $b_i$。要求 $1 \le a_i \le n$。
数据范围：$T (1 \le T \le 10^4)$，$n (1 \le n \le 2 \cdot 10 ^ 5)$，$b_i (1 \le b_i \le n)$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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);
vl b(n);
int idx = 1;
for (auto& [x, y] : ma) {
if (sz(y) % x != 0) {
cout << -1 << endl;
return;
}
for (int i = 0; i < sz(y); i += x) {
for (int j = i; j <= i + x - 1; j++) b[y[j]] = idx;
idx++;
}
}
rep(i, 0, n - 1) cout << b[i] << ' ';
cout << endl;
return;
}
|
E
题目大意：给定一个长度为 $n$ 的数组 $a$ 和一个整数 $k$，执行如下操作 $k$ 次： - 对于每个元素 $a_i$，令 $a_i$ 的值为 $\operatorname{mex}(a_1,a_2,...,a_{i-1},a_{i+1},a_{i+2},...,a_n)$。即：令 $a_i$ 的值为其他所有元素的 $\operatorname{mex}$。该计算是对所有元素同时进行的。
数据范围：$t \leq 10^4$，$2 \leq n \leq 2\times10^5$，$1 \leq k \leq 10^9$，$0 \leq a_i \leq 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| void solve() {
ll n, k;
cin >> n >> k;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
int cnt = 0;
map<ll, ll> ma;
rep(i, 0, n - 1) ma[a[i]]++;
while (ma.count(cnt)) cnt++;
vl b(n);
rep(i, 0, n - 1) {
if (a[i] < cnt && ma[a[i]] == 1)
b[i] = a[i];
else
b[i] = cnt;
}
ll ans = 0;
if (k == 1) {
rep(i, 0, n - 1) ans += b[i];
cout << ans << endl;
return;
}
ma.clear();
vl c(n);
int cnt2 = 0;
rep(i, 0, n - 1) ma[b[i]]++;
while (ma.count(cnt2)) cnt2++;
rep(i, 0, n - 1) {
if (b[i] < cnt2 && ma[b[i]] == 1)
c[i] = b[i];
else
c[i] = cnt2;
}
vl d(n);
int cnt3 = 0;
ma.clear();
rep(i, 0, n - 1) ma[c[i]]++;
while (ma.count(cnt3)) cnt3++;
rep(i, 0, n - 1) {
if (c[i] < cnt3 && ma[c[i]] == 1)
d[i] = c[i];
else
d[i] = cnt3;
}
rep(i, 0, n - 1) ans += (k % 2 == 0 ? c[i] : d[i]);
cout << ans << endl;
return;
}
|
F
题目大意：给定两个长度均为 $m$ 的数组 $x$ 和 $y$，设 $z$ 是另一个长度为 $m$ 的数组，且 $z$ 每个位置的前缀最大值与 $x$ 对应位置的前缀最大值相同。形式化地说，需满足对所有 $1 \leq i \leq m$，都有 $\max(x_1,x_2,\ldots,x_i) = \max(z_1,z_2,\ldots,z_i)$。定义 $f(x,y)$ 为：在所有满足上述条件的数组 $z$ 中，$z_i = y_i$ 的位置的最大数量。
数据范围：$1 \leq t \leq 10^4$，$1 \leq n \leq 2 \times 10^5$，$1 \leq a_i \leq 2 \cdot n$，$1 \leq b_i \leq 2 \cdot 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
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
| 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) {
for (; i > 0; i -= lowbit(i)) {
tree[i] = max(tree[i], val);
}
}
// 前缀求和：计算 0-based 下标区间 [0, i] 内的所有元素之和
T pre(int i) const {
T res = 0;
for (; i < tree.size(); i += lowbit(i)) {
res = max(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() {
ll n;
cin >> n;
vl a(n), b(n);
rep(i, 0, n - 1) cin >> a[i];
rep(i, 0, n - 1) cin >> b[i];
Tree tree(2 * n + 1);
ll ans = 0;
rep(i, 0, n - 1) {
if (a[i] == b[i])
ans += (n - i) * (i + 1);
else
ans += (n - i) * tree.pre(max(a[i], b[i]));
tree.add(a[i], i + 1);
}
cout << ans << endl;
return;
}
|
G
题目大意：存在一个包含 $n$ 个节点和 $m$ 条边的有向无环图。所有节点初始时均为蓝色。定义“趣味图游戏”（fun graph game）规则如下： 1. 初始时，将一枚令牌放置在节点 $s$ 上。2. Cry 和 River 轮流将令牌移动到一个满足“存在从当前节点指向该节点的有向边”的节点上，其中 Cry 先手。3. 若令牌在任一玩家的回合后到达一个无出边的节点，则 Cry 获胜。4. 若令牌在任一玩家的回合后到达一个红色节点，则 River 获胜。5. 特殊规则：若玩家到达一个“既为红色又无出边”的节点，则 River 获胜。由于该图是有向无环图，可证明游戏一定会在有限回合内结束。
数据范围：$1 \leq t \leq 10^4$，$2 \leq n \leq 2 \times 10^5$，$1 \leq m,q \leq 2 \times 10^5$，$1 \leq u,v \leq n$，$1 \leq x \leq 2$，$1 \leq u \leq n$，$\sum n \le 2 \times 10^5$，$\sum m \le 2 \times 10^5$，$\sum q \le 2 \times 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
| void solve() {
ll n, m, q, x, y;
cin >> n >> m >> q;
vvl ma(n);
vvl ma2(n);
vl deg(n);
rep(i, 0, m - 1) {
cin >> x >> y;
ma[x - 1].push_back(y - 1);
deg[x - 1]++;
ma2[y - 1].push_back(x - 1);
}
vector<array<ll, 2>> dp(n), cnt(n);
rep(i, 0, n - 1) { dp[i] = {1, 1}, cnt[i] = {deg[i], deg[i]}; }
rep(i, 0, q - 1) {
cin >> x >> y;
y--;
if (x == 1) {
queue<pll> q;
if (dp[y][0]) {
dp[y][0] = 0;
q.emplace(0, y);
}
if (dp[y][1]) {
dp[y][1] = 0;
q.emplace(1, y);
}
while (!q.empty()) {
auto [op, st] = q.front();
q.pop();
for (auto& p : ma2[st]) {
cnt[p][op]--;
if (op == 0) {
if (dp[p][1]) {
dp[p][1] = 0;
q.emplace(1, p);
}
} else {
if (dp[p][0] && deg[p] > 0 && cnt[p][op] == 0) {
dp[p][0] = 0;
q.emplace(0, p);
}
}
}
}
} else {
cout << (dp[y][0] ? "YES" : "NO") << endl;
}
}
return;
}
|
