B
题目大意：给定长度为 $n$ 的数组 $a$ ，可以任意次把 $a_i$ 变成其前缀最大值，也可以花费一次把某个 $a_i$ 减一。求使数组满足 $a_1 数据范围：$1 \leq t \leq 10^4, 2 \leq n \leq 2 \cdot 10^5, 1 \leq a_i \leq 10^9, \sum n \leq 2 \cdot 10^5$ 思路： 题目大意：给定两个长度为 $n$ 的数组 $a,b$ ，其中本版本有 $b_i=1$ 。每次可以选择一个 $i$ ，令 $a_i$ 加一并支付 $b_i$ ，求使存在一对 $i 数据范围：$1 \leq t \leq 10^4, 2 \leq n \leq 2 \cdot 10^5, 1 \leq a_i \leq 2 \cdot 10^5, b_i=1, \sum n \leq 2 \cdot 10^5$ 思路： 题目大意：给定两个长度为 $n$ 的数组 $a,b$ 。每次可以选择一个 $i$ ，令 $a_i$ 加一并支付 $b_i$ ，求使存在一对 $i 数据范围：$1 \leq t \leq 10^4, 2 \leq n \leq 2 \cdot 10^5, 1 \leq a_i \leq 2 \cdot 10^5, 1 \leq b_i \leq 10^9, \sum n \leq 2 \cdot 10^5$ 思路： 题目大意：给定一棵 $n$ 点树，猫从 $1$ 出发，目标是到达 $n$ 。需要构造长度不超过 $3n$ 的指令序列：指令 $1$ 让猫走向任意相邻点，指令 $2\ u$ 删除点 $u$ 及其 incident edges ，且不能连续执行两条删除指令。要求猫无论如何选择移动方向，最终都会安全到达 $n$ 。 数据范围：$1 \leq t \leq 10^4, 2 \leq n \leq 2 \cdot 10^5, 1 \leq u,v \leq n, \sum n \leq 2 \cdot 10^5$ 思路： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl b(n);
ll pre = LLONG_MIN;
rep(i, 0, n - 1) {
pre = max(pre, a[i]);
if (i % 2 == 1) b[i] = pre;
}
ll ans = 0;
for (int i = 0; i <= n - 1; i += 2) {
ll tem = (i == n - 1 ? LLONG_MAX : b[i + 1]);
ll tem2 = (i == 0 ? LLONG_MAX : b[i - 1]);
ans += max(0LL, a[i] - min(tem, tem2) + 1);
}
cout << ans << endl;
return;
}
C1
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
constexpr int MX = 2e5 + 5;
vector<int> divisors[MX];
auto init = [] {
for (int i = 1; i < MX; i++) {
for (int j = i; j < MX; j += i) {
divisors[j].push_back(i);
}
}
return 0;
}();
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];
map<ll, ll> ma;
rep(i, 0, n - 1) {
for (auto& p : divisors[a[i]]) {
ma[p]++;
}
}
for (auto& [x, y] : ma) {
if (x == 1) continue;
if (y >= 2) {
cout << 0 << endl;
return;
}
}
ll ans = LLONG_MAX;
auto c = b;
ranges::sort(c);
ans = min(ans, c[0] + c[1]);
rep(i, 0, n - 1) {
for (auto& p : divisors[a[i] + 1]) {
if (p > 1 && ma.count(p)) ans = min(ans, b[i]);
}
}
cout << ans << endl;
return;
}
C2
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
// 函数指针在创建时自动调用
constexpr int MX = 2e5 + 5;
int lpf[MX]; // 存储每个数的最小素因子，复杂度O(NloglogN)
auto init = [] {
for (int i = 2; i < MX; i++) {
if (lpf[i] == 0) {
for (int j = i; j < MX; j += i) {
if (lpf[j] == 0) lpf[j] = i;
}
}
}
return 0;
}();
// 质因数分解，返回值为pair<素因子，素因子次幂>，复杂度O(logN)
vector<pair<int, int>> cnt(int x) {
vector<pair<int, int>> res;
while (x > 1) {
int p = lpf[x];
int e = 1;
for (x /= p; x % p == 0; x /= p) {
e++;
}
res.emplace_back(p, e);
}
return 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];
vector<vector<pll>> tem;
map<ll, ll> ma;
rep(i, 0, n - 1) {
auto tem2 = cnt(a[i]);
for (auto& [x, y] : tem2) {
ma[x]++;
}
}
for (auto& [x, y] : ma) {
if (y >= 2) {
cout << 0 << endl;
return;
}
}
auto c = b;
ranges::sort(c);
ll ans = c[0] + c[1];
int idx = -1;
rep(i, 0, n - 1) {
if (idx == -1 || b[i] < b[idx]) idx = i;
}
rep(i, 0, n - 1) {
auto tem2 = cnt(a[i] + 1);
for (auto& [x, y] : tem2) {
auto tem3 = ((a[i] % x == 0) ? 1 : 0);
if (ma[x] >= tem3 + 1) {
ans = min(ans, b[i]);
break;
}
}
}
for (auto& [x, y] : ma) {
ll tem2 = (a[idx] % x == 0 ? 1 : 0);
if (y >= tem2 + 1) ans = min(ans, b[idx] * ((x - a[idx] % x) % x));
}
cout << ans << endl;
return;
}
D
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
void solve() {
ll n, x, y;
cin >> n;
vvl ma(n);
vl deg(n);
rep(i, 0, n - 2) {
cin >> x >> y;
ma[x - 1].push_back(y - 1);
ma[y - 1].push_back(x - 1);
deg[x - 1]++, deg[y - 1]++;
}
queue<ll> q;
vl dis(n, -1);
dis[0] = 0;
q.push(0);
while (!q.empty()) {
auto node = q.front();
q.pop();
for (auto& p : ma[node]) {
if (dis[p] == -1) {
dis[p] = dis[node] + 1;
q.push(p);
}
}
}
queue<ll> qq[2];
rep(i, 0, n - 1) {
if (i != n - 1 && deg[i] == 1) qq[dis[i] % 2].push(i);
}
vector<pll> res;
vl vis(n);
ll cur = 0, cnt = 0;
while (cnt < n - 1) {
res.emplace_back(1, -1);
cur ^= 1;
if (qq[cur ^ 1].empty()) {
res.emplace_back(1, -1);
cur ^= 1;
}
auto node = qq[cur ^ 1].front();
qq[cur ^ 1].pop();
res.emplace_back(2, node + 1);
vis[node] = 1;
cnt++;
for (auto& p : ma[node]) {
if (vis[p]) continue;
if (p != n - 1 && --deg[p] == 1) qq[dis[p] % 2].push(p);
}
deg[node] = 0;
}
cout << sz(res) << endl;
for (auto& p : res) {
if (p.first == 1)
cout << 1 << endl;
else
cout << 2 << ' ' << p.second << endl;
}
return;
}