Educational Codeforces Round 140

發表於 更新於 分類於 ， Disqus： 文章字數： 2.4k 所需閱讀時間 ≈ 8 分鐘
E(meet-in-the-middle,bitmask)F(树链剖分,莫队,根号分治,dsu on tree)

https://codeforces.com/contest/1767

E. Algebra Flash

长n的 染色格子

每次只能走 i+1 或 i+2

颜色要激活才能走(一次激活所有同色), 求最小代价, 让1到n是通的

范围

n 3e5

颜色种类 m [1,40]

激活代价 [1,1e7]

2s

256mb

我的思路

只感受到 i如果不激活, 那么i-1 和i+1必定要激活, 这样有一定的 约束性, 不知道能不能2-sat, 但感觉2-sat 出来的强联通块的意义 也不明

m 40 的话, 就没法直接bitmask

题解

显然 如果提前买, 很容易检测 通, 但枚举太多

没法在过程中dp购买, 信息状态太大,

也是 相邻至少一个被买

就变成点覆盖问题

相当于 相邻就是边, 而颜色为点,也就是 选价值最小的点覆盖, 让每条边的两端至少一个被选

这是np-hard, (无法多项式时间)

一个办法是 枚举 mask, 遍历边 检查, O(2^m m^2), 显然TLE

考虑 前半 mask 和 后半mask

边有3种: 两端都在前半, 两端都在后半, 一端在前一端在后

两端在同一半的 mask 容易检查,

一前一后的, 反过来看 前半未选的, 决定了后半的必选 子mask

for mask2 in 后半:
if mask2 双端后半 ok

for mask1 in 前半:
if 双端前半 ok:
submask = f(前半-mask1)
ans = min(ans, cost(mask1) + min(后半ok 且 包裹submask 的))

代码

https://codeforces.com/contest/1767/submission/186167586

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

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

ll read(){ll r;scanf("%lld",&r);return r;}

int main() {
  int n=read();
  int m=read();
  vector<int> c(n); // color 0-index
  rep(i,0,n) c[i]=read()-1;
  vector<int> x(m); // cost
  rep(i,0,m) x[i]=read();

  vector<ll> g(m); // g[color] = 相邻颜色的 bitmask (边的两端)
  rep(i,0, n-1){
    g[c[i]]   |= (1ll << c[i+1]);
    g[c[i+1]] |= (1ll << c[i]);
  }
  g[c[0]]     |= (1ll << c[0]); // 1和n 必定要选
  g[c[n - 1]] |= (1ll << c[n - 1]);

  int l = m / 2; // meet-in-the-ldle
  vector<int> dp(1<<l, 1e9); // 左侧 dp[mask] = 最小 右侧代价
  auto chmin=[](auto &a,auto &b){a=min(a,b);};
  rep(mask,0, 1<<(m-l)){ // 右侧
    ll chk = 0; // 左侧必选的mask
    int tot = 0; // 代价
    rep(i,0, m-l){
      if ((mask >> i) & 1) tot += x[i + l];
      else chk |= g[i + l]; // 左侧必选mask
    }
    if (((chk >> l) | mask) != mask) continue; // 两端都在 右侧 的检查
    chk &= ((1ll << l) - 1); // 只考虑左侧
    dp[chk] = min(dp[chk], tot); // 更新最小值
  }
  // 收集 子mask 的min
  rep(i,0, l) rep(mask,0, 1<<l) if (!((mask >> i) & 1)) chmin(dp[mask | (1 << i)],dp[mask]);
  int ans = 1e9;
  rep(mask,0, 1 << l){
    ll chk = 0;
    int tot = 0;
    rep(i,0, l){
      if ((mask >> i) & 1) tot += x[i];
      else chk |= g[i];
    }
    chk &= ((1ll << l) - 1);
    if ((chk | mask) != mask) continue; // 两端都在左侧检查
    ans = min(ans, dp[mask] + tot); // 自身 加上 合法子集对应右侧最小代价
  }
  printf("%d\n", ans);
  return 0;
}

F. Two Subtrees

n点,根1树, 点上有数 v[i]

q个询问, 每次ui,vi, 考虑所有 u的子树或v的子树的点 w, (同时是u和v的子树则计算两次, 找出现最多次数的值, 如果有多个则找最小的

范围

n 2e5

vi [1,2e5]

q 2e5

9s

1024mb

我的思路

树可以展开到线段上

问, 两个线段上,出现次数最多的最小值为多少, 依然不会做?

感觉是4个 指针, 有办法莫队吗?

题解

先解决一个简单的问题

维护可重复集合, 处理3种询问

  1. 增加值到集合
  2. 删除某个值一次
  3. 计算可重集合的mode, 维护cnt[值]记录次数, mode = cnt最大的 最左侧下标

考虑cnt 通过 sqrt-decomposition 构造

每个块, 记录最大值, 和一个最大值的下标数组, 这样每次增删 最大值变化不超过1, cnt数组就暴力更新, 这样每次 询问是O(sqrt(max value))

回到题目, 一样的想法, 树可以展开到线段上, 考虑先序遍历, 记录每个点的出入时刻, 这样子树就是一个ie区间

sz[u] = u的子树大小, 取某个整数 B, 如果sz < B则称作轻, 否则称作重

[lv,rv],[lu, ru]

考虑 lv <= lu

之考虑 v的大小

轻(v轻,u任意) 询问:

用 small-to-large 技术来维护 可重集合

有关于点w的可重集合, 来回答所有 轻询问 ui=w

取所有vi子树的 节点, 计算现在可重集合的mode, 通过增删来复用

O(n log n 维护u对应的w(莫队) + q B 枚举小节点 + q sqrt(A) 回答询问)

这里树上拍扁 的 u对应的区间 (()())() 也和直接区间不同,

重(v重,u任意) 询问

把重点 分割成不相交的 点路径

那么两个点, 同一个路径, 有子树 的差异不超过B个点

这样的路径数是 O(n/B)

如果满足地一个条件, 标记所有路径上的点被用. 只要有未使用的重点, 就反复这样

  1. 如果当前路径包含root, root没有父节点, 路径会终止, 至多一条路径
  2. 如果 路径中最后一个节点 的 父节点 只有1个重儿子(最后一个节点), 路径中点个数 + 孩子外部重儿子子树最后一个点父节点 > B, 这样路径数不会超过 n/B
  3. 路径最后一个节点的父节点 有多个重儿子. leave only 重节点在树中(重节点的父节点一定是重节点), 这树 包含至多n/b个叶子, 计算树中总度, 至多 n/b个额外孩子, 这样的路径之多n/B

把vi的子树分割成路径, 和轻 询问 类似

at the very beginning, we add to the multiset all the vertices of the subtree of the initial vertex of the path and mentally remove these vertices from the subtrees of vi vertices

加所有点O(n)

small-to-large O(n log n),

回答一个询问 due to condition on vertices from one path we have to add at most B vertices, O(n^2 log n /b + qb + q sqrt(A)),

重节点构成的链, 不只是重链, 而且要同链上的点 child[u] - child[v] < B, 这样再按链id排序, 做莫队

链的个数 < n/b

代码

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#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;}

const int A = 2e5 + 10;
const int N = 2e5 + 10;
const int B = 2000;
const int SQRTA = 500;

int val[N]; // 点上值
vector<int> g[N]; // 图
int fa[N]; // 父节点
int sz[N]; // 子树大小

int tin[N], tout[N]; // 点 -> 线段区间
int et[N]; // 线段 -> 点

// 记录父节点,子树大小,重儿子
void dfs1(int v, int f) {
  fa[v] = f;
  sz[v] = 1;
  int mx = 0; // 最大重儿子
  rep(i,0,g[v].size()) if(g[v][i]!=f) {
    int u = g[v][i];
    dfs1(u, v);
    sz[v] += sz[u];
    if(sz[g[v][mx]] < sz[u]) mx = i;
  }
  if(mx) swap(g[v][mx], g[v][0]);
}

// 树 子树 与 线段展开
void dfs2(int v,int &T) {
  et[T] = v;
  tin[v] = T++;
  for(int u : g[v]) if(u != fa[v]) dfs2(u, T);
  tout[v] = T;
}

int cnt[A]; // [值] = 次数
int v2b[A]; // [值] = block
int bmx[A]; // 块最大值
int v2c[A / SQRTA + 13][A]; // [块block][次数] = 个数


int main() {
  int n=read();
  rep(i,0,n)val[i]=read();

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

  dfs1(0, -1);

  vector<pair<int,int> > ord(n); // size index
  rep(i,0,n) ord[i] = {sz[i], i}; // 点从小到大
  sort(ord.begin(), ord.end());

  vector<int> gr(n,-1); // [点] 链id
  int cur = 0; // 链id
  for(auto [siz,v]:ord) if(siz >= B and gr[v] == -1){ // 重 点
    int u = v;
    while(gr[u] == -1 && sz[u] - sz[v] < B) { // u....v 都是重点, u的子节点而非v的子节点个数 < B
      gr[u] = cur;
      u = fa[u];
    }
    cur++;
  }

  int T=0;
  dfs2(0,T);

  rep(i,0,n) if(sz[i] < B) gr[i] = cur + tin[i] / B; // 轻点 分组

  int q=read();
  vector<array<int,6> > Q(q); // block, lv rv, lu ru, ans index
  rep(i,0,q){
    int v =read()-1;
    int u =read()-1;

    int lv = tin[v];
    int rv = tout[v];
    int lu = tin[u];
    int ru = tout[u];

    if(lv > lu) { // lv <= lu
      swap(v,u);
      swap(lv, lu);
      swap(rv, ru);
    }
    Q[i] = {gr[v],lu,ru,lv,rv,i};
  }

  sort(begin(Q),end(Q)); // 先b 后lu

  int lv = 0, rv = 0, lu = 0, ru = 0;
  rep(i,0,A) v2b[i] = i / SQRTA;
  auto insert=[&](int i) {
    int x=val[et[i]];
    v2c[v2b[x]][cnt[x]]--;
    cnt[x]++;
    v2c[v2b[x]][cnt[x]]++;
    if(cnt[x] > bmx[v2b[x]]) bmx[v2b[x]]++;
  };
  auto erase=[&](int i) {
    int x=val[et[i]];
    if(cnt[x] == bmx[v2b[x]] && v2c[v2b[x]][cnt[x]] == 1) bmx[v2b[x]]--;
    v2c[v2b[x]][cnt[x]]--;
    cnt[x]--;
    v2c[v2b[x]][cnt[x]]++;
  };

  auto  get_mode=[&]() {
    int mx = 0;
    rep(i,0,A/SQRTA+1) mx = max(mx, bmx[i]);
    for(int i = 0; ; i++)  if(bmx[i] == mx)  for(int j = i * SQRTA; ; j++)  if(cnt[j] == mx) return j;
  };
  vector<int> ans(q);
  for(auto [b,qlu,qru,qlv,qrv,idx]:Q){
    if(b < cur) { // 重块
      while(rv < qrv) insert(rv++);
      while(lv > qlv) insert(--lv);
      while(rv > qrv) erase(--rv);
      while(lv < qlv) erase(lv++);
    } else {
      while(rv > lv) erase(--rv); // 枚举 替代 平移
      lv = qlv;
      rv = lv;
      while(rv < qrv) insert(rv++);
    }

    while(ru < qru) insert(ru++);
    while(lu > qlu) insert(--lu);
    while(ru > qru) erase(--ru);
    while(lu < qlu) erase(lu++);

    ans[idx] = get_mode();
  }

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

总结

E

meet-in-the-middle

感觉看到 40 要能向 bitmask + meet-in-the-middle 去想了

F

子树 = 展开线段上的区间的想法有了,

这也能 轻-重 处理, 完全想不到

树链剖分(从根到某一点的路径上，不超过O(logN)条轻边，不超过O(logN)条重路径。)

然后就是 树上拍扁的区间 比 直接区间多一些特性

参考

官方

https://baike.baidu.com/item/%E6%A0%91%E9%93%BE%E5%89%96%E5%88%86/10524122

https://www.luogu.com.cn/problem/solution/CF1767F