Educational Codeforces Round 129

發表於 更新於 分類於 ， Disqus： 文章字數： 1.3k 所需閱讀時間 ≈ 4 分鐘
E(rmq 倍增)F(树上同值跳点,切割联通块大小)

E - Labyrinth Adventures

题目

https://codeforces.com/contest/1681/problem/E

n行n列的迷宫

1
2
3
4
5
55555
44445
33345
22345
12345

左下角第一层,然后它八临的第二层,再8临第三层

不同层之间有墙隔着,部分墙的位置有门, 每两层之间有恰好两个门, 一个是上下方向,一个是左右方向, 门是双向通的

q个询问两点之间最少的移动步数

范围

n 1e5

q 2e5

6s

512MB

题解

n很大显然无法建立图

但我们可以考虑如果是图会怎么做

首先如果没有任何阻挡,那么两点之间的曼哈顿距离为 走个直角, 因此如果两个同色,那么必然答案就是曼哈顿距离

那么就是考虑不同颜色

显然也不会 一个色不连续的走到,否则这段路径直接同色最短, 综上 如果 a < b , 那么a->b 的距离 = a->某个门-> a+1->某个门->a+2 ->某个门 -> ... -> b

再改改

位置pos -> 门(a,0) -> 门(b-1,0) -> 位置dst

位置pos -> 门(a,0) -> 门(b-1,1) -> 位置dst

位置pos -> 门(a,1) -> 门(b-1,0) -> 位置dst

位置pos -> 门(a,1) -> 门(b-1,1) -> 位置dst

如果我们能快速求两个门之间的最短距离就好了

直接考虑rmq的办法, 记录 (位置i,0/1号门, 2的幂次j距离, 0/1号门) 的最小距离

这样复杂度为$O(n \cdot log(n) )$ 的初始化和 $O( log(n))$ 的单次查询

代码

无

会的, 不想写了

F

题目

https://codeforces.com/contest/1681/problem/F

给到一个n个点的树, 边上有整数

记f(u,v) = 点u到点v简单路径上 只出现了一次的数字的个数

求对于所有u < v 的点对, f(u,v)的总和

边的值[1..n] 不需要自己离散化了

范围

n 5e5

6s

1024mb

题解

显然假设一条边上写的是 x

那么从贡献角度来讲, 它对答案的贡献是,左侧端点不再经过值为x边的点数 乘上 右侧端点不再经过值为x边的点数

问题呢, 如果我们通过叶子统计汇总,那么每个叶子上需要记录O(n)个值的出现次数, 那显然就n 方了

那么我们考虑对于一个d, 在dfs时,不要影响到其它的块的办法

任意选一个点作为根,先考虑 dfs过程中经过了两个边为d

分别是(u0,v0,d) 和 (u1,v1,d)

那么 (u1,v1) 的贡献 = 以v0为根的d断开的联通块大小 乘上 以v1为根的d断开的联通块大小

而 以v为根的d断开的联通块大小 = v为根的子树大小 - sum{最近的d断开的 以v1/v2/v3/v4… 为根的树的大小}

这样 辅助数组 记录深搜过程中 上一个同边对应的点即可, 空间就是O(n),

还有一个问题, 如果是 dfs中首次出现的呢

这里的方法是对于每一个d 假装树的根的父节点连出去的就是d,即可

代码

https://codeforces.com/contest/1681/submission/158413431

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
const int N = 5e5;
int idx;
tuple<int,int,int> e[N*2 + 10]; // {u,v,d}
vector<pair<int,int> > u2vi[N+10]; // [u] = vector<{v,i}>
int loc[N*2+10]; // [d] = 深搜过程中 当前深搜链上 边为d的叶向端点
int lst[N*2+10]; // lst[v] = v作为叶节点父边为d , 通向根的链上,最近一个边为d的叶向节点 //上一个v'
int sz[N+10]; // 子树大小, 纯的树统计,不考虑边值
ll f[N*2+10]; // 考虑边值有效的树的大小
int n;
void dfs(int u, int fa) { // 点, 父节点
  sz[u] = 1; // 纯的子树大小
  for(auto [v,ei]: u2vi[u]){
    int d = get<2>(e[ei]);
    if (v == fa) continue;
    lst[v] = loc[d]; // 即帮助深搜恢复loc[d], 也自己记录了它到根的简单路径上最近的 边为d的叶向节点
    loc[d] = v; // 当前的深搜的链上 边为d的叶向端点
    dfs(v, u);
    loc[d] = lst[v]; // 恢复上一次的 loc[d]
    sz[u] += sz[v];
  }
  // 原理就很简单了 对于 u->v, 边为d 来说, 以v为根的连通块大小 = 它的子树大小 - sum{它子树中紧邻的边d的根为v' 的子树大小}
  f[u] += sz[u];
  f[lst[u]] -= sz[u];
}

int main() {
  cin >> n;
  rep(i,1,n){
    int u, v, d;
    scanf("%d %d %d",&u,&v,&d);
    e[i] = {u,v,d};
    u2vi[u].push_back({v,i});
    u2vi[v].push_back({u,i});
  }
  // 初始化f 和 loc
  rep(i,1,n+1){
    f[i + n] = n;
    loc[i] = i + n; // 初始化为每个值 对应虚拟节点为 value+n
  }
  dfs(1, -1);
  ll ans = 0;
  rep(i,2,n+1){
    ans += (f[i] * f[lst[i]]);
  }
  printf("%lld\n",ans);
  return 0;
}

总结

其实相当于线性数组的变性, 靠值来记录上一个同样值的位置, 不同的是线性可以直接坐标差得到中间的联通块, 而 树状可以dfs知道 到根最近的同样的值在哪, 而联通块的信息直接表示在根上

参考

官方