整体不是很难，要不是E被自己的大份思路卡了，赛时也许有时间AK。
感觉F « E，反正打的小号，无所谓了。
B
题目大意：给定一个长度为 $n$ 的数列，可以进行最多一次以下操作：选定一个 $a$ 的子序列，给这个子序列的每个元素加上一个相同的数，问是否能将这个数列转化成非递减的？
数据范围： $2 \leq n \leq 2 \cdot 10^5, 1 \leq a_i \leq 10^9$
思路：首先考虑加上的这个数怎么处理，不难想到，它肯定要大于等于所有前大于后的位置的相邻差值。
随后就是简单的贪心思路，不难看出，如果前面的数不知道要不要加，那么首先考虑不加，不然会给后面相邻的数带来压力，所以维护一个变量tem，表示前面的数加了没有，分类逐项贪心，在合适时候更新tem即可。
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
|
void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vi tem;
ll tem2 = LLONG_MIN;
rep(i, 0, n - 2) {
if (a[i] > a[i + 1]) {
tem2 = max(tem2, a[i] - a[i + 1]);
}
}
if (tem2 == LLONG_MIN) {
cout << "YES" << endl;
return;
}
int tem3 = 0;
rep(i, 0, n - 2) {
if (a[i] > a[i + 1]) {
if (tem3) {
cout << "NO" << endl;
return;
}
tem3 = 1;
} else {
if (tem3 && a[i + 1] >= a[i] + tem2) {
tem3 = 0;
}
}
}
cout << "YES" << endl;
return;
}
|
C
题目大意：给定一个数列，每次可以对该数列中的某个数进行一次以下操作：若 $x$ 是偶数，将其除以2，否则将其加一。请求出所有数均相等时的最小操作次数。
数据范围： $1 \leq n \leq 10^5, 1 \leq a_i \leq 10^9$
思路：这道题有个明显的结论，那就是对每个数进行操作，最终一定会收敛到 $2,1,2,1$ 这个操作序列。
但是，相同的数不止这两个，所以需要求出每个数的操作序列，由定义不难看出是 $O(\log V)$ 的，然后对所有出现次数为 $n$ 的数计数，记录到达它的总操作次数。
不过，如果用set或者unordered_set或者unordered_map，似乎会被神秘卡常，此时联想到我们在力扣中使用过的方法，将所有状态存进数组，排序后做滑窗，检验当前条件下滑窗内元素个数为 $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
|
void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vector<pii> tem3;
rep(i, 0, n - 1) {
if (a[i] == 1) {
tem3.emplace_back(1, 0);
tem3.emplace_back(2, 1);
continue;
}
ll tem = a[i];
ll tem2 = 0;
while (tem != 1) {
tem3.emplace_back(tem, tem2);
if (tem % 2 == 0)
tem /= 2;
else
tem++;
tem2++;
}
tem3.emplace_back(tem, tem2);
}
ll ans = LLONG_MAX;
int m = sz(tem3);
sort(all(tem3));
int i = 0;
while (i < m) {
ll tem2 = 0;
int j = i;
while (j < m && tem3[j].first == tem3[i].first) {
tem2 += tem3[j].second;
j++;
}
if (j == i + n) ans = min(ans, tem2);
i = j;
}
cout << ans << endl;
return;
}
|
D
题目大意：给定一个二进制字符串 $S$ 和一个数列 $a_i$ ，注意 $s_i=1$ 表示当前下标的 $a_i$ 是已知的，而 $s_i=0$ 表示当前下标的 $a_i$ 是未知的，现在再给定全部 $c_i = \max\limits_{1 \leq j \leq i}\sum\limits_{k=1}^{j}a_k$ ，请你还原出可能的 $a$ ，或者报告它不存在。
数据范围： $1 \leq n \leq 2 \cdot 10^5, -10^6 \leq a_i \leq 10^6, -2 \cdot 10^{11} \leq c_i \leq 2 \cdot 10^{11}$
思路：感觉CF考烂了，甚至赛时觉得肯定哪里的原改的。
原题其实给了 $b_i$ 的定义，方便引导思路，也就是 $b_i=\sum\limits_{j=1}^{i}a_j$ 。考虑维护当前 $b_i$ 的可行区间，正着递推，如果 $b_{i-1}$ 的可行区间为 $[l,r]$ ， $s_i=1$ 时，则有 $b_i$ 的可行区间为 $[l+a_i,r+a_i]$ ，否则没有限制。
但是此时还有一个限制，那就是 $c_{i-1}$ 和 $c_i$ 的关系，显然 $c_i$ 是非递减的，如果给出的 $c_i$ 出现递减，那么可以首先判为不存在，同时，如果 $c_i>c_{i-1}$ ，那说明当前 $b_i=c_i$ ，也就是 $b_i$ 是确定的， 否则 $b_i$ 只有上界 $c_i$ ，没有下界性质。
综合上述两段思路，我们可以得出初步的 $b_i$ 区间，如果对于某个 $b_i$ ，它完全没有可行区间，那么依旧是不存在。然后由于是正着递推，必然是反着推回去比较好，由于已经有存在性，贪心地将所有不确定的 $b_i$ 均取为其上界，而已经确定 $a_i$ 的则显然可以由 $b_{i+1}$ 得到值。
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
|
void solve() {
int n;
cin >> n;
string s;
cin >> s;
vl a(n + 1);
rep(i, 1, n) cin >> a[i];
vl c(n + 1);
vl b(n + 1);
rep(i, 1, n) cin >> c[i];
vector<pll> ma(n + 1);
rep(i, 1, n - 1) {
if (c[i + 1] < c[i]) {
cout << "No" << endl;
return;
}
}
if (s[0] == '1') {
if (a[1] != c[1]) {
cout << "No" << endl;
return;
}
}
ma[1].first = ma[1].second = c[1];
rep(i, 2, n) {
ll l, r;
if (c[i] == c[i - 1]) {
l = LLONG_MIN / 3;
r = c[i];
} else {
l = c[i];
r = c[i];
}
if (s[i - 1] == '1') {
ma[i].first = max(ma[i - 1].first + a[i], l);
ma[i].second = min(ma[i - 1].second + a[i], r);
} else {
ma[i].first = l;
ma[i].second = r;
}
}
rep(i, 1, n) {
if (ma[i].first > ma[i].second) {
cout << "No" << endl;
return;
}
}
b[n] = ma[n].second;
frep(i, n, 1) {
if (s[i - 1] == '1') {
b[i - 1] = b[i] - a[i];
} else
b[i - 1] = ma[i - 1].second;
}
frep(i, n, 1) a[i] = b[i] - b[i - 1];
cout << "Yes" << endl;
rep(i, 1, n) cout << a[i] << ' ';
cout << endl;
return;
}
|
E
题目大意：给定一棵大小为 $n$ 的树，现在要求计算以下无序三元组 $(a,b,c)$ 的个数，使得 $a,b,c$ 构成的最小连通子图大小为给定数 $d$ 。
数据范围： $3 \leq d \leq n \leq 2000$
思路一：这是我赛时的思路。
首先将大小为 $d$ 转化为易于求解的距离和为 $d-1$ 格式。
那么考虑以下两种组织形式：
1.退化为链，也就是这三个点位于同一条链上，那么最远两个点之间的距离为 $d-1$ 。
2.形成三叉型，那么它们会在某个中心点 $v$ 处汇合，此时三个点距离 $v$ 点的距离和为 $d-1$ 。
此时考虑首先预处理 $tem[i][len]$ 为距离 $i$ 为 $len$ 的点数，以及 $tem2[len]$ 为所有距离为 $len$ 的点对。
接着，需要考虑的是，对于中心点 $x$ 而言，需要计算距离为 $len$ ，它们之间的路径经过 $x$ ，但是 $x$ 不是端点的数对数量，记为 $cro[x][len]$ ，从而直接得到了第一种情况的答案。
对于第二种情况，只需要枚举中心点和它的某个分支，计算 $temp_j$ 为当前分支中距离它为 $j$ 的点数，也就是思路二中的 $dep_j$ ，从而使用容斥计算不在当前分支内，分属两个其他分支的两个点，经过 $v$ 距离和为 $d-1-j$ 的数目，也就是需要扣掉经过当前 $v$ 到自己儿子这条边的，经过 $v$ 距离和为 $d-1-j$ 的数目，也就是要预处理 $cro2[x][len]$ ，表示经过 $x$ 的父边（0为根），距离和为 $d-1-j$ 的数对数，不过还会扣掉一种极端情况，也就是 $(v,i)$ 这条路径， $v$ 作为端点的情况，因为它在 $cro[v]$ 中没有，但是在 $cro2[v]$ 中出现，要加回来。
而上面讲的都是需要预处理的东西，预处理当前需要计算任意两点之间的距离（后面很多需要用到），从而可以计算出 $tem[i][len]$ 和 $tem2[len]$ 。
接着，由于上文中有提到子树关系，就考虑基于深度对原来的点进行排序再计算，要计算 $cro$ 和 $cro2$ 的话，就要进行树上差分，分为点差分和边差分两种来做，然后从深到浅累加即可，而上文中很多LCA跟dis都可以直接从HLD板子内得到，所以就拉了。
最后，对于一个三叉型，它的节点数会被枚举三次，因此这部分得到的答案需要除以3。
时间复杂度 $O(n^2 \log n+nd)$ ，这题不建议学习这个做法。
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
// 重链剖分 HLD
// 用法：HLD hld(n); hld.add_edge(x, y); hld.work(root);
// hld.lca(x, y) 查询 LCA；hld.get_path(x, y) 返回若干段 DFS 序区间。
// hld.dfn[x]..hld.dfn[x]+hld.siz[x]-1 是 x 的子树区间。
struct HLD {
int n, tim = 0;
vector<vi> g;
vi fa, dep, siz, son, top, dfn, rnk;
HLD(int n = 0) { init(n); }
void init(int n_) {
n = n_;
g.assign(n, {});
fa.assign(n, -1);
dep.assign(n, 0);
siz.assign(n, 0);
son.assign(n, -1);
top.assign(n, 0);
dfn.assign(n, 0);
rnk.assign(n, 0);
tim = 0;
}
void add_edge(int x, int y) {
g[x].push_back(y);
g[y].push_back(x);
}
void work(int root = 0) {
auto dfs1 = [&](auto&& self, int x, int p) -> void {
fa[x] = p;
siz[x] = 1;
for (int y : g[x]) {
if (y == p) continue;
dep[y] = dep[x] + 1;
self(self, y, x);
siz[x] += siz[y];
if (son[x] == -1 || siz[y] > siz[son[x]]) son[x] = y;
}
};
auto dfs2 = [&](auto&& self, int x, int tp) -> void {
top[x] = tp;
dfn[x] = tim;
rnk[tim++] = x;
if (son[x] != -1) self(self, son[x], tp);
for (int y : g[x]) {
if (y == fa[x] || y == son[x]) continue;
self(self, y, y);
}
};
dfs1(dfs1, root, -1);
dfs2(dfs2, root, root);
}
int lca(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
x = fa[top[x]];
}
return dep[x] < dep[y] ? x : y;
}
int dist(int x, int y) {
int z = lca(x, y);
return dep[x] + dep[y] - 2 * dep[z];
}
vector<pii> get_path(int x, int y) {
vector<pii> res;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
res.push_back({dfn[top[x]], dfn[x]});
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
res.push_back({dfn[x], dfn[y]});
return res;
}
};
void solve() {
int n, d, x, y;
cin >> n >> d;
vvi ma(n);
HLD hld(n);
ll ans = 0;
rep(i, 1, n - 1) {
cin >> x >> y;
ma[x - 1].push_back(y - 1);
ma[y - 1].push_back(x - 1);
hld.add_edge(x - 1, y - 1);
}
hld.work(0);
auto is_ancestor = [&](int x, int y) -> bool { return hld.dfn[x] <= hld.dfn[y] && hld.dfn[x] + hld.siz[x] - 1 >= hld.dfn[y]; };
vvi dis(n, vi(n));
rep(i, 0, n - 1) {
rep(j, 0, n - 1) { dis[i][j] = hld.dist(i, j); }
}
vvl tem(n, vl(d));
vector<vector<pii>> tem2(d);
rep(i, 0, n - 1) {
rep(j, 0, n - 1) {
if (dis[i][j] < d) tem[i][dis[i][j]]++;
}
}
rep(i, 0, n - 1) {
rep(j, i + 1, n - 1) {
if (dis[i][j] < d) tem2[dis[i][j]].emplace_back(i, j);
}
}
vvl cro(n, vl(d));
vvl cro2(n, vl(d));
vi ord(n);
rep(i, 0, n - 1) ord[i] = i;
sort(all(ord), [&](const int& x, const int& y) { return hld.dep[x] > hld.dep[y]; });
rep(i, 1, d - 1) {
vl temp(n);
vl temp2(n);
for (auto& [a, b] : tem2[i]) {
int tem3 = hld.lca(a, b);
temp[a]++, temp[b]++, temp[tem3]--;
if (hld.fa[tem3] != -1) temp[hld.fa[tem3]]--;
temp2[a]++, temp2[b]++, temp2[tem3] -= 2;
}
rep(j, 0, n - 1) {
if (hld.fa[ord[j]] == -1) continue;
temp[hld.fa[ord[j]]] += temp[ord[j]];
temp2[hld.fa[ord[j]]] += temp2[ord[j]];
}
rep(j, 0, n - 1) {
cro[j][i] = temp[j] - tem[j][i];
if (hld.fa[j] != -1) cro2[j][i] = temp2[j];
}
}
rep(i, 0, n - 1) { ans += cro[i][d - 1]; }
ll ans2 = 0;
rep(i, 0, n - 1) {
for (int& p : ma[i]) {
vl temp(d);
rep(j, 0, n - 1) {
if (hld.fa[p] == i) {
if (is_ancestor(p, j) && dis[i][j] < d) temp[dis[i][j]]++;
} else {
if (!is_ancestor(i, j) && dis[i][j] < d) temp[dis[i][j]]++;
}
}
rep(j, 1, d - 1) {
if (!temp[j]) continue;
int tem3 = (hld.fa[p] == i ? p : i);
ans2 += temp[j] * (cro[i][d - 1 - j] - cro2[tem3][d - 1 - j] + temp[d - 1 - j]);
}
}
}
cout << ans + ans2 / 3 << endl;
return;
}
|
思路二：
这个是赛后看别人代码补的思路，顺便学了一下FFT。
首先将大小转化为距离 $d-1$ ，仍然看中心点 $v$ ，考虑以下两种情况：
-
$v$ 本身是这三个点的其中一个，也就是这三个点呈现一个链状，此时只需要维护两个分支内加起来深度为 $d-1$ 的数量，考虑枚举右维护左，从而只需要维护 $tem_i$ 作为之前深度为 $i$ 的点数，和 $dep_i$ ，当前深度为 $i$ 的点数并合并。
-
$v$ 不是这三个点的其中一个，而是这三个点之间的中心点，此时需要维护 $tem2_i$ 表示之前的两个分支内到 $v$ 距离为 $i$ 的点对数，仍然考虑枚举右维护左，但是它的合并比较麻烦。
朴素的合并，只需要枚举 $i,j$ ，然后 $tem2_{i+j}=tem_i*dep_j$ ，时间复杂度为 $O(d^2)$ ，太慢。
而此时可以采用FFT，将它看成多项式的系数卷积形式，转化为 $O(d \log d) $ 的合并，具体细节此时不介绍。
于是就能完成计数了，时间复杂度 $O(n^2+ nd \log 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
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
|
// FFT求卷积，适合普通整数系数；如果需要取模且模数友好，优先用NTT。
// convolution_ll(a, b)返回c，其中c[k]=sum(a[i]*b[j])，i+j=k
using cd = complex<double>;
const double PI = acos(-1.0);
void fft(vector<cd>& a, bool inv) {
int n = sz(a);
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
double ang = 2 * PI / len * (inv ? -1 : 1);
cd wlen(cos(ang), sin(ang));
for (int i = 0; i < n; i += len) {
cd w(1);
rep(j, 0, len / 2 - 1) {
cd u = a[i + j];
cd v = a[i + j + len / 2] * w;
a[i + j] = u + v;
a[i + j + len / 2] = u - v;
w *= wlen;
}
}
}
if (inv) {
for (cd& x : a) x /= n;
}
}
vl convolution_ll(vl a, vl b) {
if (a.empty() || b.empty()) return {};
int need = sz(a) + sz(b) - 1;
int n = 1;
while (n < need) n <<= 1;
vector<cd> fa(all(a)), fb(all(b));
fa.resize(n);
fb.resize(n);
fft(fa, false);
fft(fb, false);
rep(i, 0, n - 1) fa[i] *= fb[i];
fft(fa, true);
vl res(need);
rep(i, 0, need - 1) res[i] = llround(fa[i].real());
return res;
}
void solve() {
int n, x, y, d;
cin >> n >> d;
d--;
vvi ma(n);
rep(i, 1, n - 1) {
cin >> x >> y;
ma[x - 1].push_back(y - 1);
ma[y - 1].push_back(x - 1);
}
ll ans = 0;
rep(i, 0, n - 1) {
vl tem(d + 1), tem2(d + 1);
for (int& p : ma[i]) {
vl dep(d + 1);
auto dfs = [&](this auto&& dfs, int x, int pa, int dd) -> void {
if (dd > d) return;
dep[dd]++;
for (int& q : ma[x]) {
if (q == pa) continue;
dfs(q, x, dd + 1);
}
return;
};
dfs(p, i, 1);
rep(j, 1, d - 1) {
ans += dep[j] * tem[d - j];
ans += dep[j] * tem2[d - j];
}
vl tem3 = convolution_ll(dep, tem);
rep(j, 0, min(d, sz(tem3) - 1)) { tem2[j] += tem3[j]; }
rep(j, 1, d) tem[j] += dep[j];
}
}
cout << ans << endl;
return;
}
|
F
题目大意：给定 $1…n$ 这些点，两个点 $i,j$ 之间有边当且仅当 $abs(j-i)$ 是平方数，现在给定 $q$ 个查询，每个查询给出 $x,y$ ，问 $x$ 到 $y$ 的最短路长度是多少。
数据范围： $2 \leq n \leq 2 \cdot 10^5,1 \leq q \leq 10^5, 1 \leq x < y \leq n$
思路：一道很明显的数学题。
首先需要的是拉格朗日四平方和定理，也就是对于任意非负整数 $n$ ，存在四个非负整数， $n$ 能被表示为这四个整数的平方和。
代入本题，也就是最短路的长度至多为 $4$ ，又由于 最短路长度为 $0$ 和 $1$ 的情况容易排除，因此只需要考虑 $2$ 和 $3$ 时的情况即可。
考虑最短路长度为 $2$ 的情况，一种是 $x<z<y$ ，同时有 $y-z$ 和 $z-x$ 为平方数，还有一种是 $z<x<y$ 或 $x<y<z$ ，满足 $abs(z-x)$ 和 $abs(z-y)$ 是平方数。
由于 $n$ 较小，我们可以预处理一下 $1-MAXN$ 中能被表示为两数平方和跟两数平方差的数，但是由于平方差的情况还需要保证 $1 \leq z \leq n$ ，因此需要记录 $d=y^2-x^2$ 中， $x$ 的长度，防止超出。
然后就可以根据预处理的结果，以及 $x,y$ 跟边界的距离，判断是否是两步之内就能到达对方。
而三步则可以简化为两步加一步，由于枚举第一步是 $O(\sqrt{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
|
const ll MX = 2e5 + 5;
vi is_square(MX, 0);
vi sum(MX, 0);
vi mixx(MX, INT_MAX);
vi square;
auto init = [] {
for (int i = 1; i * i <= MX; i++) {
square.push_back(i * i);
is_square[i * i] = 1;
}
for (auto& p : square) {
for (auto& q : square) {
if (p + q >= MX) break;
sum[p + q] = 1;
}
}
int m = sz(square);
rep(i, 0, m - 1) {
rep(j, i + 1, m - 1) {
if (square[j] - square[i] < MX) mixx[square[j] - square[i]] = min(mixx[square[j] - square[i]], square[i]);
}
}
return 0;
}();
void solve() {
int n, q, x, y;
cin >> n >> q;
auto check = [&](int x, int y) -> bool {
if (y == x) return true;
if (y < x) swap(y, x);
if (y - x == (int)sqrt(y - x) * (int)sqrt(y - x)) return true;
if (sum[y - x]) return true;
int tem = max(x - 1, n - y);
if (mixx[y - x] <= tem) return true;
return false;
};
auto check2 = [&](int x, int y) -> bool {
if (y < x) swap(x, y);
for (int& p : square) {
int tem = x + p;
if (tem <= n && check(tem, y)) return true;
tem = x - p;
if (tem >= 1 && check(tem, y)) return true;
}
return false;
};
rep(i, 0, q - 1) {
cin >> x >> y;
if (x > y) swap(x, y);
if (x == y) {
cout << 0 << endl;
continue;
}
int tem = (int)sqrt(y - x);
if (tem * tem == y - x) {
cout << 1 << endl;
continue;
}
if (check(x, y)) {
cout << 2 << endl;
continue;
}
if (check2(x, y)) {
cout << 3 << endl;
continue;
}
cout << 4 << endl;
}
return;
}
|
