做的是第二场。
看别人打的第一场做了 7 题还 100+ 名，一开题感觉一道都不会做，很慌。
最后做出来 5 题，66 名，很开心。
做题顺序：$1\rightarrow 3 \rightarrow 7 \rightarrow 5 \rightarrow 4$
这场显然偶数题比奇数题难。
1. 和
题意
给定一个长为 $n$ 的序列，有 $q$ 次询问，每次询问 $[l,r]$ 区间内最大的 $k$ 个数之和是否 $\ge x$。
$n,q \le 10^5,k\le 10,a_i \le 10^4,x\le 10^8$
做法
第一遍写了莫队，用 set 维护，显而易见 TLE 了。（不过这个我还写了好久 /lh）
由于 $k$ 十分小，所以用线段树维护区间内前 $k$ 小的值，合并什么的总之就是非常暴力。
复杂度 $O(nk \log k+qk\log nk)$。
代码
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
| int a[100005];
int n, q, k, x;
int tree[400005][21], cnt[400005];
void build(int node, int l, int r) {
if (l == r) {
cnt[node] = 1;
tree[node][0] = a[l];
return;
}
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
cnt[node] = 0;
rep(i, cnt[ls])tree[node][cnt[node]++] = tree[ls][i];
rep(i, cnt[rs])tree[node][cnt[node]++] = tree[rs][i];
sort(tree[node], tree[node] + cnt[node]);
reverse(tree[node], tree[node] + cnt[node]);
cnt[node] = min(cnt[node], k);
}
vector<int>ans;
void query(int node, int l, int r, int L, int R) {
if (L <= l && r <= R) {
rep(i, cnt[node])ans.pb(tree[node][i]);
return;
}
int mid = l + r >> 1;
if (mid >= L)query(ls, l, mid, L, R);
if (mid < R)query(rs, mid + 1, r, L, R);
}
int l, r, sum;
void solve() {
cin >> n >> q >> k >> x;
rep(i, n)cin >> a[i];
build(0, 0, n - 1);
while (q--) {
cin >> l >> r;
ans.clear();
query(0, 0, n - 1, l - 1, r - 1);
sum = 0;
sort(ans.begin(), ans.end());
reverse(ans.begin(), ans.end());
rep(i, min((int)ans.size(), k))sum += ans[i];
if (sum >= x)cout << "Y\n";
else cout << "N\n";
}
}
|
3. 逃离这棵树
题意
给定一棵大小为 $n$ 的树，根节点为 $1$，每个点有权重 $p_i$，$i$ 到 $j$ 的边有权重 $q_{i,j}$。
当站在点 $i$ 上时，下一步有 $\frac{p_i}{p_i+\sum q_{i,j}}$ 的概率留在原地，有 $\frac{q_{i,j}}{p_i+\sum q_{i,j}}$ 的概率到 $j$ 节点（$j$ 为 $i$ 的儿子）。
初始时在根节点，问期望多少步后到达叶节点，对 $998244353$ 取模。
$n \le 10^6,p_i,q_{i,j}\le 10$
做法
做法类似于某场 ABC 的 E 题，只是把数轴换成了树。然而我至今没有补掉那个题，但是赛时把这个题切了。
设 $dp_i$ 为 $i$ 期望走多少步到叶节点。
考虑枚举从 $i$ 下一步到达的点 $j$，$j$ 对 $i$ 的答案的贡献是 $\frac{q_{i,j}}{p_i+\sum q_{i,j}} \cdot dp_j$。
另外，$i$ 节点期望要 $\frac{p_i+\sum q_{i,j}}{p_i}$ 步离开原地，所以 $dp_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
| const int MOD = 998244353;
ll qpow(ll x, ll y) {
ll p = 1;
while (y) {
if (y & 1)p = p * x % MOD;
x = x * x % MOD;
y >>= 1;
}
return p;
}
ll inv(ll x) { return qpow(x, MOD - 2); }
int n, p[1000006], q[1000006];
vector<vector<int>>v;
ll dp[1000006];
void dfs(int x) {
if (v[x].empty()) {
dp[x] = 0;
return;
}
ll sum = 0;
for (int y : v[x]) {
dfs(y);
sum += q[y];
}
ll INV = inv(sum);
dp[x] = (sum + p[x]) * INV;
for (int y : v[x])dp[x] = (dp[x] + q[y] * INV % MOD * dp[y] % MOD) % MOD;
}
void solve() {
cin >> n;
rep(i, n) cin >> p[i];
v.resize(n);
repp(i, n - 1) {
int a;
cin >> a >> q[i];
v[a - 1].pb(i);
}
dfs(0);
cout << dp[0];
}
|
4. 通信网络
题意
给定一个 $n$ 个点，$m$ 条边的无向图，一条边 $(u,v,w)$ 表示这条边连接 $u$ 和 $v$，长度为 $w$。有 $q$ 次询问，每次询问给定 $k$ 个关键点，第 $i$ 个关键点为 $p_i$，与这个点的距离 $\le d_i$ 的节点会被打上标记。对于每次询问，输出有多少个点被打上了标记。询问之间独立，也就是每次打上的标记会在下一次询问前清空。
$n \le 10^3,m \le 10^4,q \le 10^5,\sum k \le 10^6,w \le 10^6,d_i \le 10^9$
做法
把询问离线下来，对于每个关键点分别处理。
对于每个询问一个 bitset $ans_i$，$ans_{i,j}$ 表示在第 $i$ 次询问中，$j$ 是否被打上了标记。
对于每个关键点 $x$，把和它有关的询问按照 $d$ 从小到大排序。
维护一个 bitset $res$，$res_i$ 表示 $i$ 与 $x$ 的距离是否 $\le d$。容易发现，由于 $d$ 已经从小到大排序过了，所以 $res$ 中的元素只会从 $0$ 变成 $1$，或者不变。
所以先跑一边 dijkstra，处理出所有点到 $x$ 的距离，然后把所有点按照与 $x$ 的距离排序，单调地往 $res$ 中加入就可以了。处理到第 $i$ 个询问时，把 $ans_i$ 按位或上 $res$，最后答案就是 $ans_i.count()$。
复杂度 $O(n^2\log n+nm \log m+k \log k+\frac{nk}{\omega})$，能过。
代码
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
| int n, m, q, a, b, c;
int dist[1010];
int k;
vector<pair<int, int>>g[1010], v[1010];
bitset<1010>ans[100005], tmp;
priority_queue<pair<int, int>>pq;
int id[1010];
void solve() {
cin >> n >> m >> q;
rep(i, m) {
cin >> a >> b >> c;
a--, b--;
g[a].pb(mp(b, c));
g[b].pb(mp(a, c));
}
rep(i, q) {
cin >> k;
rep(j, k) {
cin >> a >> b;
v[a - 1].pb(mp(b, i));
}
}
rep(i, n) {
if (v[i].empty())continue;
init(dist, 63);
dist[i] = 0;
pq.push(mp(0, i));
while (!pq.empty()) {
int val = -pq.top().fi, x = pq.top().se;
pq.pop();
if (val != dist[x])continue;
if (g[x].size())rep(j, g[x].size()) {
int y = g[x][j].fi, w = g[x][j].se;
if (dist[y] > val + w) {
dist[y] = val + w;
pq.push(mp(-dist[y], y));
}
}
}
tmp.reset();
rep(i, n)id[i] = i;
sort(id, id + n, [&](int x, int y) {return dist[x] < dist[y];});
sort(v[i].begin(), v[i].end());
int p = 0;
rep(j, v[i].size()) {
while (p < n && dist[id[p]] <= v[i][j].fi) {
tmp[id[p]] = 1;
p++;
}
ans[v[i][j].se] |= tmp;
}
}
rep(i, q)cout << ans[i].count() << endl;
}
|
5. 星球联通
题意
给定三维空间内的 $n$ 个点，表示一个点的坐标为 $(x,y,z)$，连接两个点的代价是它们距离的平方。
现在可以免费连接 $k$ 个点，额外再连接 $i$ 个点（即一共连接 $k+i$ 个点）需要花 $c_i$ 的代价。
求将所有点连通起来的最小代价。
$k \le n \le 3000,c_i \le 10^9,x,y,z \le 10^4$
做法
显然枚举额外连接多少个星球，现在问题变成：
给定一张带权完全图，连接其中 $x$ 个点，代价最少是多少。
容易联想到最小生成树的 Kruskal 算法。改一下：
把边按边权从小到大依次检查，如果连接的两个点不在同一个连通分量里，就把这条边加进去。当有 $x-1$ 条边时结束。
这个看上去就很对的算法实际上也是对的，正确性易证，但是我不会证，大概和 Kruskal 的证法差不多。
代码
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
| ll n, k, c[3010], x[3010], y[3010], z[3010], ans, sum, cnt;
vector < pair<ll, pair<int, int>>>v;
int fa[3010];
int getf(int i) {
if (fa[i] == i)return i;
return fa[i] = getf(fa[i]);
}
void solve() {
cin >> n >> k;
repp(i, n - k)cin >> c[i];
rep(i, n)cin >> x[i] >> y[i] >> z[i];
rep(i, n)forr(j, i + 1, n - 1) {
ll X = x[i] - x[j], Y = y[i] - y[j], Z = z[i] - z[j];
ll val = X * X + Y * Y + Z * Z;
v.pb(mp(val, mp(i, j)));
}
sort(v.begin(), v.end());
rep(i, n)fa[i] = i;
ans = c[n - k], sum = 0, cnt = n - k;
rep(i, v.size()) {
int a = v[i].se.fi, b = v[i].se.se;
if (getf(a) == getf(b))continue;
cnt--;
fa[getf(a)] = getf(b);
sum += v[i].fi;
ans = min(ans, sum + c[cnt]);
if (!cnt)break;
}
cout << ans;
}
|
7. 原地传送
题意
有一个 $n\times m$ 的网格图，起点为 $(0,0)$，终点为 $(n,m)$，每次可以从 $(x,y)$ 走到 $(x+1,y)$ 或 $(x,y+1)$。
有 $k$ 个传送门，第 $i$ 个传送门在 $(x_i,y_i)$，碰到传送门就必须要立即移动到另一个传送门（不能原地传送）。
求有多少种恰好传送一次后到达终点的行走方案。
$n,m \le 10^5,k \le 2000$
做法
枚举传送的起点和终点是哪两个传送门，问题转化成：
有多少种方法从起点走到传送门 $i$ / 从传送门 $i$ 走到终点，中途不碰到任何其它的传送门。
考虑从起点走到传送门 $i$ 的情况，另一种同理。
设 $i$ 的答案是 $dp_i$，$cnt(a,b)$ 表示向 $x$ 方向走 $a$ 步，向 $y$ 方向走 $b$ 步的方案数。
易得 $cnt(a,b)=\binom{a+b}{a}$。
如果不考虑 “中途不碰到任何其它的传送门” 这一条件，那么 $dp_i=cnt(x_i,y_i)$。
枚举第一个碰到的传送门 $j$，从起点走到 $j$ （中途不碰到任何其它的传送门）有 $dp_j$ 种方案，从 $j$ 走到 $i$（因为已经确定了第一个碰到的，所以后面就没有限制条件了）有 $cnt(x_i-x_j,y_i-y_j)$ 种方案，所以 $dp_i$ 要减去 $dp_j \cdot cnt(x_i-x_j,y_i-y_j)$。
然后发现只有在 $x_j\le x_i$ 且 $y_j \le y_i$ 时这个转移才有效，所以把所有坐标按照 $x+y$ 从小到大排序，计算 $dp_i$ 时只要考虑所有 $j<i$。
复杂度 $O(n^2)$。
代码
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
| int n, m, r, c, a[20][20];
vector<int>v;
int cost1[20][20], cost2[20], dp[20][20], ans = MAXN;
void solve() {
cin >> n >> m >> r >> c;
rep(i, n)rep(j, m)cin >> a[i][j];
repp(w, (1 << m) - 1) {
v.clear();
rep(i, m)if ((w >> i) & 1)v.pb(i);
if ((int)v.size() != c)continue;
rep(i, n)forr(j, i + 1, n - 1) {
cost1[i][j] = 0;
rep(k, c)cost1[i][j] += abs(a[i][v[k]] - a[j][v[k]]);
}
rep(i, n) {
cost2[i] = 0;
rep(j, c - 1)cost2[i] += abs(a[i][v[j]] - a[i][v[j + 1]]);
}
init(dp, 63);
rep(i, n) {
dp[i][0] = 0, dp[i][1] = cost2[i];
forr(j, 2, i + 1)rep(k, i)dp[i][j] = min(dp[i][j], dp[k][j - 1] + cost1[k][i] + cost2[i]);
ans = min(ans, dp[i][r]);
}
}
cout << ans;
}
|
写在最后
感觉这场比赛都是第一眼很吓人，仔细想想其实还好的题。
大家来了应该都能爆切吧。
QwQ