比赛题目选讲（2023）
5 月
NOIP 2018 模拟 Day2：
ending：给定一棵 \(n\) 个点的树，边权 \(w\in\{0,1\}\)。求出有多少个三元组 \((i,j,k)\)，满足 \(dist(i,j),dist(i,k)>0\)。\(1\le n\le 10^5\)。
题解：
若 \(w(i,j)=0\)，则将 \(i,j\) 合并进一个连通块内。对于一个连通块，设其大小为 \(size\)，则对于该连通块内的一个节点 \(i\)，满足 \(dist(i,j)=0\) 或 \(dist(i,k)=0\) 的三元组 \((i,j,k)\) 的数量为 \((size-1)(size-2)+2(size-1)(n-size)\)。
那么 \(ans=n(n-1)(n-2)-\sum size((size-1)(size-2)+2(size-1)(n-size))\)。
时间复杂度 \(O(n\log n)\)。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define int long long
const int N = 1e5+10;
int n, ans, p[N], siz[N];
int check(int w) {
while (w) {
if (w % 10 != 4 && w % 10 != 7) return 0;
w /= 10;
}
return 1;
}
int find(int x) {
if (p[x] != x) return find(p[x]);
return x;
}
void merge(int u, int v) {
int fu = find(u), fv = find(v);
if (fu == fv) return ;
siz[fv] += siz[fu], p[fu] = fv;
return ;
}
signed main() {
// freopen("ending.in", "r", stdin);
// freopen("ending.out", "w", stdout);
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) p[i] = i, siz[i] = 1;
int u, v, w;
for (int i = 1; i < n; ++i) {
scanf("%lld%lld%lld", &u, &v, &w);
w = check(w);
if (!w) merge(u, v); // 分割成内部不能到达的连通块
}
for (int i = 1; i <= n; ++i) {
if (i != find(i) || siz[i] < 2) continue ;
int size = siz[i];
ans += size*(size-1)*(size-2) + size*(size-1)*(n-size)*2;
}
printf("%lld\n", n*(n-1)*(n-2)-ans);
return 0;
}
/*
10
1 2 8
1 3 7
3 4 47
5 7 23
4 6 4
6 10 747
8 6 57
9 3 447
9 5 88
566
*/
6 月
Codeforces Round 878 (Div. 3)：
CF1840A
CF1840B：给定 \(n,k\)，计算 \(0\sim n\) 中有多少个数可以用不超过 \(k\) 位二进制数表示。\(1\le n,k\le 10^9\)。多测，\(1\le t\le 1000\)。
题解：
\(k\) 位二进制数能表示的最大数为 \(2^{k}-1\)。当 \(n>2^k-1\) 时，\(ans=2^k\)；否则 \(ans=n+1\)。时间复杂度 \(O(t)\)。
CF1840C：给定一个数组 \(a\)，求出其中有多少个区间 \([l,r]\) 满足 \(\max_{l\le i\le r}\{a_i\}\le q\) 且 \(r-l+1\ge k\)。\(1\le k\le n\le 2\times 10^5,-10^9\le a_i,q\le 10^9\)。多测，\(1\le t\le 10^4\)。
题解：
预处理 \(a\) 中所有 \(>q\) 的数的位置，扔到一个 vector 中。正序扫描 \(a\)，对于 \(a_i\)，二分查找其后第一个 \(>q\) 的位置 \(pos\)，若 \(pos-i+1\ge k\) 则 \(a_i\) 对答案的贡献为 \(pos-i+1-k\)。
CF1840D：给定一个数组 \(a\)，求出 \(\max_{1\le i\le n}\{\min\{|a_i-x|,|a_i-y|,|a_i-z|\}\}\)。\(1\le n\le 2\times 10^5,1\le a_i\le 10^9\)。多测，\(1\le t\le 10^4\)。
题解：二分答案即可。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5+10;
int t, n, a[N];
bool check(int num) {
int x = 1, cnt = 0;
// printf("%d\n", num);
while (x <= n && cnt < 3) {
// printf("%d ", x);
x = upper_bound(a+1, a+n+2, a[x]+2*num) - a, cnt ++;
}
// printf("%d\n", x);
if (x > n) return 1;
return 0;
}
int main() {
scanf("%d", &t);
while (t -- ) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
a[n+1] = 1000000000;
sort(a+1, a+n+2);
int l = 0, r = 1000000000;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid+1;
}
printf("%d\n", l);
}
return 0;
}
CF1840E：赛后待补。