非常的生气啊，本来可以一把开六道题爽爽地回蓝的，结果前缀和数组忘记开long long了，还碰上weak pretest了，于是D被hack，以后写前缀和必须开ll！。
至少证明了我是有1600的水平的，呜呜呜~
E
题目大意：黑板上写有 $n$ 个 $1 \sim n$ 的数，每次允许选用其中任意一个元素进行乘法，求对于 $i \in [1,n],$ 最终乘积为 $i$ 的最小元素数。
数据范围： $1 \leq n \leq 3 \cdot 10^5$
思路：这题可以看出是调和级数的模版题，可以使用bfs建图和dp求解，但是注意需要提前退出以及对 $a_i$ 去重。
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
|
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i <= n - 1; i++) cin >> a[i];
vector<int> b;
for (int& p : a) {
if (p != 1) b.push_back(p);
}
ranges::sort(b);
b.erase(unique(b.begin(), b.end()), b.end());
vector<int> dp(n + 1, -1);
queue<int> q;
for (int& p : b) {
q.push(p);
dp[p] = 1;
}
while (!q.empty()) {
int x = q.front();
q.pop();
for (int& p : b) {
ll tem = 1LL * x * p;
if (tem > n) break;
if (dp[tem] == -1) {
dp[tem] = dp[x] + 1;
q.push(tem);
}
}
}
if (*min_element(a.begin(), a.end()) == 1)
cout << 1 << ' ';
else
cout << -1 << ' ';
for (int i = 2; i <= n; i++) {
cout << dp[i] << ' ';
}
cout << endl;
return;
}
void solve() {
int n;
cin >> n;
vector<int> a(n);
vector<int> dp(n + 1, INT_MAX / 2);
for (int i = 0; i <= n - 1; i++) {
cin >> a[i];
dp[a[i]] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j += i) {
dp[j] = min(dp[j], dp[i] + dp[j / i]);
}
}
for (int i = 1; i <= n; i++) {
if (dp[i] == INT_MAX / 2) dp[i] = -1;
cout << dp[i] << ' ';
}
cout << endl;
return;
}
|
F
题目大意： 需要从 $(ax,ay)$ 开始送披萨到 $n$ 个地点，然后回到 $(bx,by)$ ，每次可以向上、向下、向右走一步，问最少需要走多少步。
数据范围： $1 \leq n \leq 2 \cdot 10^5$ ， $ax < x_i < bx, 1 \leq y_i \leq 10^9$
思路：这道题是非常典的典题，只需考虑对于相同的横坐标，最终停在最上面还是最下面，并进行状态机DP即可。
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
|
void solve() {
int n, ax, ay, bx, by;
cin >> n >> ax >> ay >> bx >> by;
vector<pair<int, int>> ma(n);
for (int i = 0; i <= n - 1; i++) cin >> ma[i].first;
for (int i = 0; i <= n - 1; i++) cin >> ma[i].second;
ranges::sort(ma);
map<int, vector<int>> s;
map<int, vector<ll>> s2;
s[ax].push_back(ay);
s2[ax].push_back(0);
s[bx].push_back(by);
s2[bx].push_back(LLONG_MAX);
for (auto& [x, y] : ma) {
s[x].push_back(y);
s2[x].push_back(LLONG_MAX);
}
for (auto it = s.begin(); it != s.end(); it++) {
auto itt = it;
itt++;
if (itt == s.end()) break;
int tem = it->second.size();
int tem2 = itt->second.size();
int x = it->first;
int x2 = itt->first;
ll d = x2 - x;
ll d2 = 1LL * abs(itt->second[tem2 - 1] - itt->second[0]);
s2[x2][0] = min(s2[x2][0], s2[x][0] + d + 1LL * abs(it->second[0] - itt->second[tem2 - 1]) + d2);
s2[x2][0] = min(s2[x2][0], s2[x][tem - 1] + d + 1LL * abs(it->second[tem - 1] - itt->second[tem2 - 1]) + d2);
s2[x2][tem2 - 1] = min(s2[x2][tem2 - 1], s2[x][0] + d + 1LL * abs(it->second[0] - itt->second[0]) + d2);
s2[x2][tem2 - 1] = min(s2[x2][tem2 - 1], s2[x][tem - 1] + d + 1LL * abs(it->second[tem - 1] - itt->second[0]) + d2);
}
cout << s2[bx][0] << endl;
return;
}
|
G
题目大意：交互题，给定一棵 $n$ 个点的树的结构，图中有 $u,v$ 两个可能相同的隐藏节点，每次查询 $(x,y)$ 将会返回 $(x,y)$ 之间的路径与 $(u,v)$ 之间的路径是否相交（0或1），要求在 $\lfloor \frac{n}{2} \rfloor +1$ 次查询内找到 $(u,v)$ 路径上的至少一个顶点。
数据范围： $2 \leq n \leq 2 \cdot 10^5$
思路：这道题先介绍一个知识点：DFS序，即DFS的遍历顺序。
这个知识点是干啥的呢？首先，在一棵树上，设 $x$ 的DFS序为 $dfn[x]$ ，以 $x$ 为根节点的子树大小为 $siz[x]$ ，则 $[dfn[x],dfn[x]+siz[x]-1]$ 则为$x$ 的整棵子树范围，可以用于判断子树，并结合数据结构对整棵子树进行操作。
同时，如果 $x+1=y$ ，那么要么 $x$ 是 $y$ 的父节点，要么 $y$ 是 $x$ 回溯后遍历的下一个节点，这也是这题我们要用到的关键。
首先看这题的数据范围，一个 $\lfloor \frac{n}{2} \rfloor$ 非常明显地表示是要通过两两配对进行查询。
那么，怎么两两配对呢？赛时我想的是不断查询叶子，但是这样其实是错的。
正解则是对DFS序相邻的两个节点进行查询，如果这两个节点位于路径上，那么若它们是相邻的，则查其中一个节点即可，若它们不相邻，则这两个点路径上的其他节点必然已经被查询过了，因此还是只查询这两个节点就可以。最后，当 $n$ 为奇数时，由于之前的所有节点都被查过了，因此最后一个节点必然为答案。
所以，DFS序在思考树上问题时，还是非常重要的。
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
|
void solve() {
int n, op;
cin >> n;
vector<vector<int>> ma(n);
vector<int> dfn(n);
vector<int> fdfn(n);
vector<int> siz(n);
int cnt = 0;
int x, y;
for (int i = 0; i < n - 1; i++) {
cin >> x >> y;
ma[x - 1].push_back(y - 1);
ma[y - 1].push_back(x - 1);
}
auto dfs = [&](this auto&& dfs, int x, int pa) -> int {
dfn[x] = cnt;
fdfn[cnt] = x;
cnt++;
int tem = 1;
for (int& p : ma[x]) {
if (p == pa) continue;
tem += dfs(p, x);
}
siz[x] = tem;
return tem;
};
dfs(0, -1);
for (int i = 0; i < n - 1; i += 2) {
ask(fdfn[i] + 1, fdfn[i + 1] + 1);
cin >> op;
if (op == 1) {
ask(fdfn[i] + 1, fdfn[i] + 1);
cin >> op;
if (op == 1)
report(fdfn[i] + 1);
else
report(fdfn[i + 1] + 1);
return;
}
}
report(fdfn[n - 1] + 1);
return;
}
|
