Codeforces Round 872

發表於 更新於 分類於 ， Disqus： 文章字數： 3.2k 所需閱讀時間 ≈ 11 分鐘
B2(树,数学)C(树上启发式合并)D(离线,线段树,二维前缀和,跳点,线段树维护一次方程)

https://codeforces.com/contest/1824

B2 LuoTianyi and the Floating Islands (Hard Version)

n点边权1的树, 问对于任意k个不同指定点，到这k个指定点距离和最小的点的个数的期望值 mod 1e9+7

k <= n <= 2e5

2s

256mb

我的思路

k = 奇数，显然有唯一重心, 期望为1

k = 偶数，对于点u, 则其所有链接的子树 不能有 > k/2个指定点

合法的方案数 cnt = for u, for v is child of u, (binom(n,k) - sum binom(sz[v],j)binom(n-sz[v],k-j),j <= k/2)

但直接暴力显然TLE

题解

考虑相邻点的距离和变化

任选一个根，记s[u] = 子树u的指定点个数

记w[u]= u到所有指定点的距离和

v是u的子节点，那么w[v] = w[u] - s[v] + (k-s[v])

如果u是好的点，则一定满足任意v,有k - 2s[v] >= 0

所以如果u是好的点，那么它的子节点中，最大的s[v],满足s[v] <= k/2

如果u是好的点，把u选做根, v是u的子节点且 s[v]最大

那么注意到s[v]在除了u以外的所有s[node]中 最大

也就是k-2s[v] 在所有k-2s[node]中最小

且k-2s[v] >= 0

若k-2s[v] > 0 则所有k-2s[node] >= k-2s[v] > 0, 则所有相邻变化(从父向子)全为正, 所以只有根是good节点

若k-2s[v] == 0, 则v也是好的点

如果u和v都是好的点u-pu-..-pv-v

以u为根时, 有s_u[v] <= s_u[pu] <= k/2

以v为根时，有s_v[pv] <= k/2

注意到 s_u[v] + s_v[pv] = k, 所以s_u[v] = s_v[pv] = k/2

因此pv也是好的点

如此反复，u..v路径上的都是好的点

那么这里还有问题是，当任选根时，k - 2s[v] == 0能保证v是好的点吗

对于 root...v来说, 这条路经上的点s[node in root..v] >= s[v] 即 k-2s[node in root..v] <= 0

即对于root..-pv-v

考虑把v换成根，则s_v[pv] = k/2, 则在v为根时,v的子节点最大的s <= k/2, 所以w[v]最小

所以v是好的点

p[v] = 让v在某个指定方案下, 存在选根方案 s[v] = k/2 的概率

这里有个问题是, 例如对于n=7点菊花形状,k=6时，中心是唯一好的点，但是它不满足s[v] = k/2

而这种情况，根据上面的好点路径上的点也是好点，

所以对所有好点取lca,有唯一的lca,且满足它要么是根(s[v] = k)，要么它的父节点不是好点w[fa[lca]] > w[lca]

w[lca] = w[fa[lca]] - s[lca] + (k - s[lca]) < w[fa[lca]]

k-2s[lca] < 0, 它不满足

而对于其它点，都可以通过lca到达，所以除了lca以外的都满足s[v]=k/2

因此：

任选一个根, 对于每种指定点的情况的好点数 = 1+count(s[v] == k/2)

所以总的期望 = 1 + sum(p_u), u = 1..n

而 p[u] = binom(sz[u],k/2)binom(n-sz[u],k/2) / binom(n,k)

代码

https://codeforces.com/contest/1824/submission/205146076

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for(ll i=(a);i<(ll)(n);i++)
#define per(i,a,n) for(ll i=(n);i-->(ll)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}
ll mypow(ll v,ll pwr){
  ll r=1;
  while(pwr){
    if(pwr&1)(r*=v)%=MOD;
    (v*=v)%=MOD;
    pwr/=2;
  }
  return r;
}

vector<int> e[200010];
ll sz[200010];
ll n;
ll k;
ll fac[200010]={1};
ll ifac[200010];
ll binom(int n,int m){
  return (n < m or m < 0)?0:(fac[n]*ifac[m]%MOD*ifac[n-m]%MOD);
}

ll dfs(int u,int fa){
  sz[u]=1;
  ll res=0;
  for(auto v:e[u]) if(v != fa){
    (res += dfs(v, u))%=MOD;
    sz[u] += sz[v];
  }
  return (res + binom(sz[u],k/2)*binom(n-sz[u],k/2)%MOD)%MOD;
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  n=read();
  k=read();
  rep(i,1,n+1) fac[i]=fac[i-1]*i%MOD;
  ifac[n]=mypow(fac[n],MOD-2);
  per(i,0,n) ifac[i]=ifac[i+1]*(i+1)%MOD;

  rep(i,1,n){
    int u=read();
    int v=read();
    e[u].push_back(v);
    e[v].push_back(u);
  }
  if(k%2==1){
    printf("%d\n",1);
  }else{
    printf("%lld\n", (dfs(1,1)*mypow(binom(n,k),MOD-2)+1)%MOD);
  }
  return 0;
}

C LuoTianyi and XOR-Tree

根1,有点值的树，一次操作可以修改一个点的值为任意非负数

求最小操作次数, 让所有root..leaf 路径上的值的xor = 0

n 1e5

ai 1e9

2s

256mb

我的思路

虽然说是根到叶子，但是对于任意点u, 考虑它的多个子分支到叶子

如果u..leaf有不相同的，那么至少一个 需要修改，

一个一定tle的方法是

dp[u][value] = times 计算让u到所有叶子的xor为value的最小操作次数

如果自顶向下 ans = dp[root][0] = ?

dp[u][val] = min( sum dp[v][val^a[u]], 1 + sum dp[v][val^newu])

问题是 newu 如何选择

另一个就是 如果不动root,所有非叶子改成0, 叶子改成v[root], 这就是最多动n-1个点的方案

所以最佳方案中至少有一个点不动

对于

1
2
  u
x x y

如果修改1次，则可以变成u^x, 而如果修改两次，则可以变成任意值

1
2
  u
x y z

如果修改2次，则可以变成u^x / u^y / u^z, 而如果修改3次，则可以变成任意值

所以, 类似的从下向上, 一个点u修改t[u]次可以变成array[leafs], 修改t[u]+1可以变成任意值

所以问题是 找到这个t[u] 和 对应的array[leafs], 注意到如果修改了u,那么说明其所有leaf都相等，所以修改u一定是任意值的次数代价，所以一定不修改u

对于leaf, t[leaf] = 0, array = leafself

所以 首先通过sum t[child of u] 让所有子节点 变成内部一致

然后对于leaf出现最多次数的time[value array[child of u]] 全部变成它

t = (sum t[child of u]) + count(child of u) - max(t)

array = a[u] ^ array[ value array(max)]

[x y] + [y z] + [y z] + [w t] = [x y z] + 2次

问题是, 合并过程 直接暴力 复杂度是多少?

目测是 所有leaf向上的path数量, 如果是一个很偏的树，则是O(n^2)

所以想法是 能否 做重儿子，然后轻儿子来合并，这样合并过程中，如果没有次数 > 1 则 直接塞进去

如果有次数 > 1则新的结果大小 < sum(轻儿子)

那么就是如何稳定的表示 leaf,最直接的肯定是 leafid/leafvalue

又注意到如果选择leaf, 那么它们之前的一定没被修改，所以xor 可以用树上前缀xor来记录

似乎就可以做了?

写了半个小时，然后TLE 第73个点了 https://codeforces.com/contest/1824/submission/205154650

然后，不是按照初始大小，而是按照leaf记录个数的轻重儿子就过了？？？？ https://codeforces.com/contest/1824/submission/205156402 为啥？？？？？？？？？？

我懂了。。。。。。sz[u]+=sz[v] 写成 sz[v]+=sz[u] 了

代码

https://codeforces.com/contest/1824/submission/205158975

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for(ll i=(a);i<(ll)(n);i++)
#define per(i,a,n) for(ll i=(n);i-->(ll)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}

int a[100010];
int prea[100010]; // xor from root
int sz[100010];
vector<int> e[100010];

void dfs(int u,int f,int val){
  sz[u]=1;
  prea[u] = val^a[u];
  // printf("prea[%d] = %d\n",u,prea[u]);
  rep(i,0,size(e[u])) if(e[u][i] == f){ // remove father
    swap(e[u][i],e[u].back());
    e[u].pop_back();
    break;
  }
  // printf("sz[%d]= %d\n",u,(int)size(e[u]));
  for(auto v:e[u]){
    dfs(v,u,prea[u]);
    sz[u]+=sz[v]; // fuck !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  }
  // heavy child
  rep(i,0,size(e[u])) if(sz[e[u][i]] > sz[e[u][0]]) swap(e[u][i],e[u][0]);
}

unordered_set<int> cnt[100010];
int ans[100010];

void f(int u){
  // printf("f(%d)\n",u);
  if(e[u].size()==0){ // leaf
    // printf("leaf %d\n",u);
    cnt[u].insert(prea[u]);
    // ans[u] = 0;
    return ;
  }
  f(e[u][0]);
  ans[u] += ans[e[u][0]];
  swap(cnt[u],cnt[e[u][0]]);
  unordered_map<int,int> res={};
  int maxc = 1;
  rep(i,1,size(e[u])){
    int v=e[u][i];
    f(v);
    ans[u] += ans[v];
    for(auto val:cnt[v]){
      if(!res.count(val)){// 首次出现在轻儿子
        if(cnt[u].count(val)){ // 重儿子有
          res[val]++;
        }else{ // 重儿子没有
          cnt[u].insert(val);
        }
      }
      res[val]++;
      maxc = max(maxc,res[val]);
    }
    cnt[v] = {};
  }
  if(maxc > 1){
    cnt[u] = {};
    for(auto [val,c]:res) if(c == maxc) cnt[u].insert(val);
  }
  ans[u] += e[u].size() - maxc;
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  int n=read();
  rep(i,0,n) a[i]=read();
  rep(i,1,n){
    int u=read()-1;
    int v=read()-1;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  dfs(0,0,0);
  f(0);
  printf("%d\n",ans[0] + (!cnt[0].count(0)));
  return 0;
}

D. LuoTianyi and the Function

给长n数组 a

g(i,j) = x, 满足(找最短的区间[x,j], 使得 a[x..j] 的值的集合 包含 a[i..j]的值的集合)

g(i,j) = 0, 若i > j

Q个询问, 每次给定l,r,x,y 计算 $\sum_{i \in [l,r]} \sum_{j\in [x,y] } g(i,j)$

n,q <= 1e6

ai \in [1,n]

7s

1024mb

我的思路

可以离线,

对于给定j, i<=j时，g(i,j) 随着i非严格单调递增

问题是连 g(i,j) 暴力都是O(n^2)会TLE,

然后如果用二维前缀, ans(l,r,x,y) = presum(1,r,1,y) - presum(1,r,1,x-1) - presum(1,l-1,1,y) + presum(1,l-1,1,x-1)

所以如果能计算 快速计算二维前缀就好了，同时本身二维前缀也可以作为直接的询问

g(i,j) = x

g(i-1,j) = x or i-1, 因为如果a[i-1]在[i..j]中出现，则在[x..j]中出现

那么就是要 next[i-1] > j

也就是对于 所有next[p] > j 和 p = j, g(p,j) = p

而next[p] <= j,g(p,j) = g(p+1,j)

通过离线，考虑 for j, for i

当j增大1时

找所有a[pos]=j+1的位置

它们原来对应[left[pos],pos]

现在区间和右侧合并，修改为右侧的值

每次区间修改, 和区间和查询?

问题是前缀i 的和如何计算?

題解

一样的思路，离线，二维前缀，看成区间修改

不过这里是for i, for j

维护的区间是 g(i)[j]

这样随着i从大到小

1
2
3
4
5
6
7
8
9
             x
            x
           x
          xx
         xx
        xx
       xxxxx
i/
/j

问题变成 每次 求区间 到顶部的矩形和

单独看一列

1
2
3
4
5
6
7
8
9
10
11
12
13
大
           ?
           ?
i[k] --> v[k]
         v[k]
         v[k]
i[j] --> v[j]
         v[j]
         v[j]
         v[j]
t    --> v[j]

小

也就是一列的和 可以看成t的函数, 而为了减少修改，所以看成变化时对函数表达式修改

f(t) = (lastidx - t + 1) * lastval + lastsum

而这里在j之前的k时是 f_k(t)=(i[k]-t+1) * v[k] + s[k]

在j之后是 f_j(t) = (i[j]-t+1) * v[j] + s[j]

在这个题目里，注意到 时刻i[j] 和 值v[j] 总是一样

所以 f_j(t) = (s[j] + v[j] * v[j]) - (t-1) * v[j]

其中 s[j] = f_k(i[j]+1) = (i[k]-i[j]) * v[k] + s[k]

因此可以通过数据结构维护 一次方程的 0次和1次系数的和

f_k => (s[k]+i[k]*v[k]+v[k], -v[k])

f_j => (s[j]+i[j]*v[j]+v[j], -v[j]) = ((i[k]-i[j]) * v[k] + s[k]+i[j]*v[j]+v[j], -v[j]) = (s[k] + i[k]*v[k] - i[j] * v[k] + i[j]*v[j]+v[j], -v[j])

其中 作为覆盖掉的部分，采取 (-i[j]*v[k],+v[k])的增量

所有部分采取 (i[j]*v[j]+v[j],-v[j])的增量

https://codeforces.com/contest/1824/submission/205279374

总结

B2

有点换根dp的感觉，就是考察相邻的变化 与0的关系

依次证明(选根最多影响s,而不会影响是否为好点)

  • 通过指定好点u为根，u的子节点v子树的s[v] <= k/2
  • 通过指定好点u为根,好点u的子节点v子树满足s[v] = k/2 则v也是好点
  • 好点u和v的路径上的点也是好点
  • 任选点为根，则s[v] = k/2的点是好点
  • 任选点为根，则始终存在且唯一存在一个好点不满足s[v] = k/2

所以就是要推出这个好点的性质

我似乎推到的和noimi想的一样的 https://twitter.com/noimi_kyopro/status/1655580879387779080 ,虽然当时也有考虑过相邻点的变化想法但是没有深入，还在想如何加速计算

C

赛时没看，赛后写了半个小时TLE,但是换了结果的轻重儿子就过了，为啥，感觉原来的也可以啊?

看了官方题解，思路和我的一样的啊???

总体比B简单很多，就是TLE没懂为啥

我懂了。。。。。。sz[u]+=sz[v] 写成 sz[v]+=sz[u] 了

D

大方向和几个点的感觉都没问题，第一次做这种一维维护的同时求二维的和，看上去更像是二维平面有O(n) ?个内部值等的矩形?

感觉题目还可以改得更“复杂”一点??

给一个初始0的数组

每个时刻对区间[li..ri] 改成vi

多个询问 [tl..tr]时间段的[li..ri]的所有值的和

参考

官方题解