Educational Codeforces Round 141

發表於 更新於 分類於 ， Disqus： 文章字數： 2.3k 所需閱讀時間 ≈ 8 分鐘
F(排列,二分图)G(线段树, 树的直径)

https://codeforces.com/contest/1783

F. Double Sort II

给你两个 1~n的排列a,b

每次操作可以任选一个i, 交换 a[i] 和 a[?]=i, 交换 b[i] 和 b[?]=i

求最小操作次数 的一个具体方案 让 a,b 有序

范围

n 3000

2s

512mb

我的思路

又是排列问题, 排列的交换就是和 i -> a[i] 建立的环相关, 每次交换不同的值,环变化都是1(+1/-1),

如果单独看 a,

每次只要不是操作 swap(ai,ai), 都是 环+1

所以问题变成:

找尽量少的 下标集合, 使得a,b 中的 环中被选中的个数 >= 所在环点的个数-1

3000 似乎希望n^2 的样子

考虑 如果把一个变有序

(x-x-x-x) (x-x-x) ...

另一个怎么转移

1
2
a: 1-2 3-4 5-6-7-8
b: 1-2-3-4 5-6 7-8

题解

也是说用 i -> pi 构成环来考虑

也是, 排序后的 都是一个个自环

也是, 每次 的操作 = 环+1 , 或者自己交换等于没效果, 也是单独排序每个环操作 长度-1次

修改题目: 最大化不被选的点, 让任意两个不被选的点不在同一个环上(哦 我没想到反过来

如果希望i不被选. 在a和b的i所在环中其它的都被选了. 如果a,b 的 两个环 有相同的点, 可以让它不被选, 其它的点则必选. 构建二分图, 左边点 表示a中的环, 右边点表示b中的环. 每个i是一条从左向右的边. 所以选边和不选点i就对应上了, 而选了以后 左右两侧的都不能再备选, 这就是二分图最大匹配

代码

https://codeforces.com/contest/1783/submission/188644065

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)

int read(){int r;scanf("%d",&r);return r;}

int a[3010];
int b[3010];
int ca[3010]; // ca[i]=> circle id
int cb[3010]; // cb[i]=> circle id

vector<pair<int,int>> g[6010]; // g[u] = {v, edge id}
int v2e[6010]; // u->edge id->v : v2e[v] = edge id
int vis[6010];

int e2u(int eid){ return ca[eid]-1; }

bool f(int u){
  if(vis[u])return false;
  vis[u] = true;
  for(auto [v,eid]:g[u]) if(!vis[v]){ // try u->v
    vis[v]=true;
    if(!v2e[v] or f(e2u(v2e[v]))){
      v2e[v]=eid;
      return true;
    }
  }
  return false;
}

int main(){
  int n=read();
  rep(i,1,n+1) a[i]=read();
  rep(i,1,n+1) b[i]=read();

  int xa=0;
  rep(i,1,n+1) if(ca[i]==0){
    xa++;
    for(int t=i;ca[t]==0;t=a[t]) ca[t] = xa;
  }
  int xb=0;
  rep(i,1,n+1) if(cb[i]==0){
    xb++;
    for(int t=i;cb[t]==0;t=b[t]) cb[t] = xb;
  }

  auto e2v=[&](int eid){ return xa+cb[eid]-1;};

  // left:[0..xa-1] right:[xa..xa+xb-1]
  rep(i,1,n+1) g[e2u(i)].push_back({e2v(i),i});

  rep(i,0,xa) {
    fill(vis,vis+xa+xb,false);
    f(i);
  }
  vector<int> ans(n+1,true);
  rep(i,xa,xa+xb) ans[v2e[i]]= false;
  int cnt=0;
  rep(i,1,n+1) cnt+=ans[i];
  printf("%d\n",cnt);
  rep(i,1,n+1) if(ans[i]) printf("%d ",i);
  printf("\n");
  return 0;
}

G. Weighed Tree Radius

有点权a[i]的n个点树

距离 d(u,v) = u..v路径上边的个数

带权 距离 w(u,v) = d(u,v) + a[v], 注意没有对称性 w(u,v) 不一定等于 w(v,u)

e(u) = max w(u, …)

r = min e(…)

m 个操作, 每次 修改一个点的权a, 并输出修改后的r

范围

n 2e5

ai [0,1e6]

m 1e5

6s

512mb

我的思路

对于每个u, 连出a[u]条边 得到新的点u’,

那么e(u) = max d(u,?’)

r = min e(…)

u..v’ 被选做为 r, 且 u-pu-…v’, pu 也是原始点

那么 其它的 u..?’ 的最大长度不小于 r-1, 否则 可以选pu 得到更小的r

所以 半径 = (直径+1)整除/2

所以 r = max((max(d(…’,…’))+1)/2, max(a[…]))

问题是 a[i] 很大不能真的建立, 就算要 那就是改边权, 去点权,

另一个就是如何维护直径, 如果能维护直径, 那么就是多和 a[…] 取个max而已

并不会维护直径

只能感觉到 当 a[u] 小于一个值val时 跟它无关, 而当大于val时, 就是 它增1, 直径增1, 但是这个val是由树和其它a[…]决定的, 并不是只于树有关

始终都感觉, 改一个, 都在变

既没有一个批量更改的办法, 也没找到一个不变量

题解

定义 路径 wpath(u,v) = a[u] + d(u,v) + a[v], 有 wpath(u,u) = 2a[u]

那么直径是 最大的wpath(… , …)

那么 e = 直径/2 向上取整数

观察 a[u] 变化 对 直径的影响

a[u] 增加

所有以u结尾的 都增加, 可能的新的直径为

  1. wpath(u,u) = 2a[u]
  2. wpath(u,v) = a[u] + d(u,v) + a[v] <= a[u] + max(d(u,x) + a[x])

d(u,v) = dep[u]+dep[v] - 2 dep[lca(u,v)]

a[u] 减少

使用 DCP(dynamic connectivity problem)

track 每个a[v], 每个可能的a[v] , 某个 v 会active 在某个 [l,r) 询问, m询问, 因此总共会有 n+m 个 区间

assign av=x on some segment of queries [l,r) ,这样 之前的a[v] 为0, 只需要处理 增加的问题

线段树维护

总结就是

当一个树的目前直径是 x—-y 时, 现在把u 延长到u’

那么 新的直径可能是

  1. u’…u’
  2. u’…x
  3. u’…y
  4. x…y

那么, 延长好处理的话

对于时刻i

就是把 所有 相关的从0 延长到 a[u]

但是这样的话是 m * m的复杂度

但是从 a[u] = val 的是一个时间区间, 所以 区间就可以用线段树维护

每次处理区间的 0 -> a[u] 后, 向子树传递 当前的 x,y,d(x,y) 即可

代码

https://codeforces.com/contest/1783/submission/188799117

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)

#define SEG_ROOT 0,0,m
#define SEG_L ((o<<1)+1)
#define SEG_R ((o<<1)+2)
#define mid (l+r)/2
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid,r

int read(){int r;scanf("%d",&r);return r;}

const int INF = 0x3f3f3f3f;

int n;
vector<int> g[200010];
struct Lca {
  vector<int> log2;
  vector<int> tin; // 遍历首次访问的时刻
  vector<vector<int>> hs; // 倍增st表 [pwr][包裹序id] = dep

  void dfs(int v, int p/*父节点*/, int dep, int &T) {
    hs[0][tin[v]=T++] = dep;
    for (int u: g[v]) if(u!=p) {
      dfs(u, v, dep+1, T);
      hs[0][T++] = dep; // v u0 v u1 v u2 v
    }
  }

  void init() {
    log2=vector(2*n, 0);
    rep(i, 2, size(log2)) log2[i] = log2[i/2] + 1;
    hs.assign(log2.back()+1, vector<int>(2*n, INF));
    tin=vector(n,0);
    int T = 0;
    dfs(0,-1,0,T);
    assert(T==2*n-1);
    rep(pw,0,size(hs)-1) rep(i,0,T-(1<<pw)) hs[pw+1][i] = min(hs[pw][i], hs[pw][i+(1<<pw)]); // 计算倍增表lca
  }

  int lcadep(int u, int v) { // lca 的 dep
    if (tin[u] > tin[v]) swap(u, v);
    int len = log2[tin[v] + 1 - tin[u]];
    return min(hs[len][tin[u]], hs[len][tin[v]+1-(1<<len)]);
  }

  int getDist(int u, int v){return hs[0][tin[u]]+hs[0][tin[v]]-2*lcadep(u,v);}// dep[u]+dep[v]-2dep[lca(u,v)]
} lcaST;

int getFarthest(int s) { // 与a无关
  vector vis(n, false);
  vector<int> q = {s};
  vis[s] = true;
  for(int i=0;i<(int)q.size();i++){
    int v = q[i];
    for(int u: g[v]) if(!vis[u]) {
      vis[u] = true;
      q.push_back(u);
    }
  }
  return q.back();
}

vector<pair<int,int>> ops[800010]; // [ [操作时刻l,r) ]=>array{点id,值},每个操作被切割成log个,所以一共m log m个op

// [l,r), set [ql,qr)
void setOp(int o, int l, int r, int ql, int qr, const pair<int,int> &op) {
  if (ql <= l && r <= qr) return ops[o].push_back(op); // void
  if (ql < mid) setOp(SEG_L_CHILD, ql, qr, op); // [l,mid)
  if (qr > mid) setOp(SEG_R_CHILD, ql, qr, op); // [mid,r)
}

vector<int> a;
vector<int> ans;

void calcDiams(int o, int l, int r, array<int,3> dst /*当前直径,直径端点s,t*/) { // [l,r)
  for (auto &op : ops[o]) {
    auto [v,val] = op;
    assert(a[v] == 0);
    a[v] = val; // a[v] 在一个时刻只能是一个值, 所以每次都相当于 从 0 -> a[v]

    auto [d,s,t]=dst;
    array<pair<int,int>,3> cds = {{ {s, v}, {v, t}, {v, v} }}; // 可能的3种情况, 剩下就还是curD
    for (auto [x,y]: cds) dst = max(dst,array<int,3>{a[x]+lcaST.getDist(x, y)+a[y],x,y});
  }
  if (r-l > 1) {
    calcDiams(SEG_L_CHILD, dst);
    calcDiams(SEG_R_CHILD, dst);
  } else { // l+1==r
    ans[l] = (dst[0]+1) / 2; // r=(d+1)/2
  }

  for (auto [v,val] : ops[o]) a[v]=0; // O(m log m)
}

int main() {
  n=read();
  a.resize(n);
  rep(i,0,n) a[i]=read();
  rep(i,0,n-1) {
    int u=read()-1;
    int v=read()-1;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  lcaST.init();
  int s = getFarthest(0);
  int t = getFarthest(s); // 标准直径算法, 与a无关

  int m=read();
  vector<int> lst(n, 0); // 上次询问的时刻lst[u]
  rep(i,0,m) {
    int v=read()-1;
    int x=read(); // a[v] = x
    if(lst[v]<i) setOp(SEG_ROOT, lst[v], i, {v, a[v]}); // SEG_ROOT, [上次时刻, 本次时刻), {点v, 上次的值}
    lst[v] = i;
    a[v] = x;
  }
  rep(v,0,n) setOp(SEG_ROOT, lst[v], m, {v, a[v]}); // SEG_ROOT, [上次时刻, m时刻), {点v, 最终值}

  ans.resize(m, -1);
  a.assign(n, 0); // 全部初始为0
  calcDiams(SEG_ROOT, {lcaST.getDist(s, t),s,t}); // 初始所有为0, 所以当前直径为与a无关的直径

  rep(i,0,m) printf("%d\n",ans[i]);
  return 0;
}

总结

F

基本的排列 环的感觉是有的, 最后推不下去了, 没想到反过来, 还是太菜了

G

能想到 去变成 (直径+1)/2, 但不会维护,

这个 跳点+线段树, 有点意思, 特别是这里从0 到 正的维护

树的直径维护, 感觉还是 完全没想到 x—y 为直径时, u增加长度会带来的变化

参考

官方