2023牛客寒假算法基础集训营2 ABCDEFHJKL

比赛链接

知识点：数学。

用 n 减去区间1的端点得到匹配的一个区间，求一下与区间2的交集。

一个小公式，两区间 [L1,R1] 和 [L2,R2] 的交集长度为 max(0,min(R1,R2)−max(L1,L2)+1) 。

时间复杂度 O(1)

空间复杂度 O(1)

#include <bits/stdc++.h>using ll = long long;using namespace std; bool solve() { int n; cin >> n; int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2; int y = n - l1, x = n - r1; cout << max(0, min(y, r2) - max(x, l2) + 1) << '\n'; return true;} int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0;}

知识点：数学。

用 n 减去区间1的端点得到匹配的一个区间，求一下与区间2的交集。

一个小公式，两区间 [L1,R1] 和 [L2,R2] 的交集长度为 max(0,min(R1,R2)−max(L1,L2)+1) 。

时间复杂度 O(1)

空间复杂度 O(1)

#include <bits/stdc++.h>using ll = long long;using namespace std; bool solve() { int n; cin >> n; int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2; int y = n - l1, x = n - r1; cout << max(0, min(y, r2) - max(x, l2) + 1) << '\n'; return true;} int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0;}

知识点：枚举，差分，前缀和。

枚举每个区间 [L,R] 的匹配区间 [n−R,n−L] ，匹配区间的每个点被其他区间覆盖的次数总和。

我们可以预处理出每个点被区间覆盖的次数 di ，可以用差分再前缀和得到。对此，再做一次前缀和，就可以快速得到 [n−R,n−L] 每个点被所有区间覆盖的次数总和， dn−L−dn−R−1 。

再减去与 [L,R] 重合部分的一段，可以用公式 max(0,min(R,n−L)−max(L,n−R)+1) 。

要注意先特判 n−R>2×105 和 n−L<0 的无交集情况。

之后，再处理 n−L>2×105 和 n−R<1 的越界情况。

时间复杂度 O(2⋅105⋅m)

空间复杂度 O(2⋅105+m)

#include <bits/stdc++.h>using ll = long long;using namespace std; const int P = 998244353;int L[400007], R[400007];ll d[200007];int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, m; cin >> n >> m; for (int i = 1;i <= m;i++) { cin >> L[i] >> R[i]; d[L[i]]++; d[R[i] + 1]--; } for (int i = 1;i <= 2e5;i++) d[i] += d[i - 1]; for (int i = 1;i <= 2e5;i++) d[i] += d[i - 1]; ll ans = 0; for (int i = 1;i <= m;i++) { int y = n - L[i], x = n - R[i]; if (y <= 0 || x > 2e5) continue; x = max(x, 1); y = min(y, 200000); ans = ans + d[y] - d[x - 1] - max(0, min(y, R[i]) - max(x, L[i]) + 1); ans %= P; } cout << ans << '\n'; return 0;}

知识点：贪心。

一个节点的深度就是这个节点的能量能被获取的次数，显然深度越大的节点能量应该越大，所以直接求完深度从小到大排序，能量也从小到大排序，乘在一起加起来就行。

因为 1≤fi≤i−1 ，所以可以直接求出每个点的深度，不需要树形dp。

时间复杂度 O(nlogn)

空间复杂度 O(n)

#include <bits/stdc++.h>using ll = long long;using namespace std; const int N = 200007; int a[N];int dep[N]; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; dep[1] = 1; for (int i = 2;i <= n;i++) { int f; cin >> f; dep[i] = dep[f] + 1; } for (int i = 1;i <= n;i++) cin >> a[i]; sort(a + 1, a + n + 1); sort(dep + 1, dep + n + 1); ll ans = 0; for (int i = 1;i <= n;i++) { ans += 1LL * dep[i] * a[i]; } cout << ans << '\n'; return 0;}

知识点：数学，二分。

通过一些不容易的证明，可以知道全局最小值一定出现在 ⌊√n⌋,⌈√n⌉ 两个点。

具体的，我们考虑 g(x)=nx+x−1 容易知道 √n 就是最小值点，但对于 f(x)=⌊nx⌋+x−1 ，考虑 √n 两边的变化率。若 x∈Z+ ， √n 右侧 nx 的减量小于 x 的增量，所以 ⌊nx⌋ 的减量小于等于 x 增量；左侧 nx 的增量大于 x 的减量，所以 ⌊nx⌋ 的增量大于等于 x 减量，所以全局最小值一定出现在 ⌊√n⌋,⌈√n⌉ 两个点，就可以比较得出最小值所在点了。

设全局最小值点为 x ，若 L≥x 显然答案为 L 。

否则，考虑区间 [L,R] 的局部最小值点，因为 [1,x] 递减，所以局部最小值点为 t=min(R,x) ，我们在 [1,t] 内二分找到最左侧的最小值点即可。

注意这道题直接三分不行，考虑三分：

2211222|2222222|22222222222222|2222222|2221122

显然此时我们就无法判断是向左还是向右收缩。当然可以动用人类智慧，三分找到个局部点左右枚举 1000 个数qwq。

时间复杂度 O(logn)

空间复杂度 O(1)

#include <bits/stdc++.h>using ll = long long;using namespace std; ll n, L, R;ll x;ll f(ll x) { return n / x + x - 1;} bool check(ll mid) { return f(mid) - f(x) > 0;} bool solve() { cin >> n >> L >> R; x = sqrt(n); x = f(x) <= f(x + 1) ? x : x + 1;//全局最小值点 if (L >= x) cout << L << '\n'; else { x = min(R, x);//[L,R]的最小值点 ll l = L, r = x; while (l <= r) { ll mid = l + r >> 1; if (check(mid)) l = mid + 1; else r = mid - 1; } cout << l << '\n'; } return true;} int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0;}

知识点：BFS。

找到同时能到起点和终点的点即可，于是从起点和终点分别搜索。

时间复杂度 O(n)

空间复杂度 O(n)

#include <bits/stdc++.h>using ll = long long;using namespace std; int n, k;bool dt[500007][10]; struct node { int x, y;};queue<node> q;void bfs(node st, vector<vector<int>> &vis, vector<vector<int>> &dir) { vis[st.x][st.y] = 1; q.push(st); while (!q.empty()) { node cur = q.front(); q.pop(); for (int i = 0;i < 2;i++) { int xx = cur.x + dir[i][0]; int yy = cur.y + dir[i][1]; if (xx <= 0 || xx > n || yy <= 0 || yy > 3 || vis[xx][yy] || dt[xx][yy]) continue; vis[xx][yy] = 1; q.push({ xx,yy }); } }} bool solve() { cin >> n >> k; for (int i = 1;i <= n;i++) dt[i][1] = dt[i][2] = dt[i][3] = 0; for (int i = 1;i <= k;i++) { int x, y; cin >> x >> y; dt[x][y] ^= 1; } vector<vector<int>> vis1(n + 1, vector(4, 0)); vector<vector<int>> vis2(n + 1, vector(4, 0)); vector<vector<int>> dir1 = { {1,0},{0,1} }; vector<vector<int>> dir2 = { {-1,0},{0,-1} }; bfs({ 1,1 }, vis1, dir1); bfs({ n,3 }, vis2, dir2); if (!vis1[n][3]) cout << 0 << '\n'; else { int ans = 0; for (int i = 1;i <= n;i++) { for (int j = 1;j <= 3;j++) { if (vis1[i][j] && vis2[i][j]) ans++; } } cout << ans - 1 << '\n'; } return true;} int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0;}

知识点：枚举，差分，贪心。

因为分成子序列，因此可以随意分配，我们优先把一个数字分在一个序列里，剩下的分在同一个。

因此，我们可以先求出每个数字的出现次数，再考虑出现次数对答案的贡献：

我们发现规律 k<cnt 时为 k−1 ，否则为 cnt 。

我们对此进行两次差分得到表格：

我们在 ans2,anscnt 处加 1 ， anscnt+1 处减一即可。

最后前缀和两次，就是答案了。

时间复杂度 O(n+105)

空间复杂度 O(n+105)

知识点：枚举，贪心，前缀和，二分。

利用上面发现的规律：

k<cnt 时为 k−1 ，否则为 cnt 。

我们先求出每个数字出现的次数，然后按照次数从小到大排序，随后枚举 k 。

我们用二分找到 cnt>k 的位置，于是 cnt≤k 的部分为 cnt 用前缀和得到总和，否则就是个数乘 k−1 。

时间复杂度 O(nlog105)

空间复杂度 O(n+105)

#include <bits/stdc++.h>using ll = long long;using namespace std; int cnt[100007];int ans[100007];bool solve() { int n; cin >> n; for (int i = 1;i <= 1e5;i++) ans[i] = cnt[i] = 0; for (int i = 1;i <= n;i++) { int x; cin >> x; cnt[x]++; } for (int i = 1;i <= 1e5;i++) { if (!cnt[i]) continue; ans[2]++; ans[cnt[i]]++; ans[cnt[i] + 1] -= 2; } for (int i = 1;i <= n;i++) ans[i] += ans[i - 1]; for (int i = 1;i <= n;i++) ans[i] += ans[i - 1]; for (int i = 1;i <= n;i++) cout << ans[i] << '\n'; return true;} int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0;}

#include <bits/stdc++.h>using ll = long long;using namespace std; int cnt[100007];int sum[100007];bool solve() { int n; cin >> n; for (int i = 1;i <= 1e5;i++) cnt[i] = 0; for (int i = 1;i <= n;i++) { int x; cin >> x; cnt[x]++; } sort(cnt + 1, cnt + 100000 + 1); for (int i = 1;i <= 1e5;i++) sum[i] = sum[i - 1] + cnt[i]; for (int i = 1;i <= n;i++) { int idx = upper_bound(cnt + 1, cnt + 100000 + 1, i) - cnt; cout << sum[idx - 1] + (100000 - idx + 1) * (i - 1) << '\n'; } return true;} int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0;}

知识点：数学。

分类讨论：

综上 max(|ai−aj|,|ai+aj|)=|ai|+|aj| 。

时间复杂度 O(n)

空间复杂度 O(1)

#include <bits/stdc++.h>using ll = long long;using namespace std; bool solve() { int n; cin >> n; ll ans = 0; for (int i = 1;i <= n;i++) { int x; cin >> x; ans += abs(x); } ans *= 2 * n; cout << ans << '\n'; return true;} int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0;}

知识点：图论建模，枚举。

题目可以转化为 n 个点 m 条边的一张无向图。 q 次询问，每次选出 k 个点，求这些点构成的最大子图的边数。

直接枚举的最坏复杂度是 O(m∑k) ，显然不可行，问题出在有些点的边可能很多。

此时我们利用平衡思想。因为边的方向不重要，所以可以给边定向，减少某些点的边数。我们考虑一条边的两个点 x,y 的度数 dx,dy ，当其满足 dx≤dy 时，建 x→y 的边；否则，建 y→x 的边。这种操作能将边数平衡到 O(√m) 的复杂度。

设 x 的出边个数为 cntx ，则有 cnt2x≤cntxdx≤∑dy≤2m ，因此可以证明 cntx≤√2m 。

时间复杂度 O(√m∑k)

空间复杂度 O(n+m)

#include <bits/stdc++.h>using ll = long long;using namespace std; struct Graph { struct edge { int v, nxt; }; int idx; vector<int> h; vector<edge> e; Graph(int n, int m):idx(0), h(n + 1), e(m + 1) {} void init(int n) { idx = 0; h.assign(n + 1, 0); } void add(int u, int v) { e[++idx] = edge{ v,h[u] }; h[u] = idx; }};const int N = 2e5 + 7, M = 2e5 + 7;Graph g(N, M); int feat[N];bool vis[N];int deg[N]; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, m, q; cin >> n >> m >> q; vector<pair<int, int>> edge(m + 1); for (int i = 1;i <= m;i++) { int u, v; cin >> u >> v; edge[i] = { u,v }; deg[u]++; deg[v]++; } for (int i = 1;i <= m;i++) { auto [u, v] = edge[i]; if (deg[u] < deg[v]) g.add(u, v); else g.add(v, u); } while (q--) { int k; cin >> k; for (int i = 1;i <= k;i++) cin >> feat[i], vis[feat[i]] = 1; int ans = 0; for (int i = 1;i <= k;i++) { for (int j = g.h[feat[i]];j;j = g.e[j].nxt) { int v = g.e[j].v; if (!vis[v]) continue; ans++; } } cout << ans << '\n'; for (int i = 1;i <= k;i++) vis[feat[i]] = 0; } return 0;}

知识点：数论，枚举。

考虑先将 ai⋅ajmodp 和 akmodp 的值的个数统计到 cnta 和 cntb 中。

随后 ansx=∑(i+j)modp=xcntai⋅cntbj ，但此时我们没考虑 i=k 或 j=k 的情况，我们只要单独把 (ai⋅aj+ai)modp 的答案减去 2 即可，代表减掉 (i,j,i),(j,i,i) 两组。

时间复杂度 O(n2+p2)

空间复杂度 O(n+p)

#include <bits/stdc++.h>using ll = long long;using namespace std; int a[5007];int cnta[5007], cntb[5007];ll ans[5007];int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, p; cin >> n >> p; for (int i = 1;i <= n;i++) cin >> a[i]; for (int i = 1;i <= n;i++) cnta[a[i] % p]++; for (int i = 1;i <= n;i++) for (int j = 1;j <= n;j++) if (i != j) cntb[1LL * a[i] * a[j] % p]++; for (int i = 0;i < p;i++) for (int j = 0;j < p;j++) ans[(i + j) % p] += 1LL * cnta[i] * cntb[j]; for (int i = 1;i <= n;i++) for (int j = 1;j <= n;j++) if (i != j) ans[(1LL * a[i] * a[j] + a[i]) % p] -= 2; for (int i = 0;i < p;i++) cout << ans[i] << " \n"[i == p - 1]; return 0;}