Codeforces Round 808

發表於 更新於 分類於 ， Disqus： 文章字數： 4.1k 所需閱讀時間 ≈ 14 分鐘
C(最小生成树,LCA,树上差分)D(组合数,树上DP,DP,前缀和)E(数学,倍增)

C

https://codeforces.com/contest/1707/problem/C

给你个n点,m边的连通图,边两两不等

有个错误的dfs算法, 每次找未选择的点中最短边进行dfs

问,从哪些点开始dfs,能得到正确的最小生成树

范围

n 1e5

m [n-1,2e5]

2s

256MB

题解

我的思路

首先边两两不等,说明正确的最小生成树唯一

第二以一个点作为根, 按正确的最小生成树建树, 那么树边以外的其它边都是回边,没有跨边,则这个点做dfs合法

但这样每次枚举就是 O(n^2), TLE

题解

先找到最小生成树

如果有连接 u v的非树边

那么 通过树边的简单路径 u—–v 通过树边的中间的点, 不可能, 且沿着树边扩展的点也不可能

变成了树上染色问题

然后剩下就LCA,树上差分了

LCA + 树上差分 思想就是

初始是对不可能的+1

然后因为批量+1 复杂度大

变成了记录每个数和它父节点的差(根节点表示自身的值), 就是树上差分了

那么对于 u,v 是非祖先关系, c[根]+=1,c[u]-=1,c[v]-=1

u和v是祖先关系, 假设u是v的祖先

c[u向v的子节点]+=1, c[v]-=1

最后还原差分成真实树即可, 判断 > 0?

代码

https://codeforces.com/contest/1707/submission/164711832

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
#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;)
#define pb push_back
const int POWER = 20;
const int N = 100000;
const int M = 200000;

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

int n;
int m;
vector<int>p2[N+10]; // MST
pair<int,int> e[M+10]; // 边
bool treee[M+10]; // tree edge

int f[N+10]; // 并查集
int find(int v) {return f[v]==v?v:(f[v] = find(f[v]));}
void link(int u,int v){ f[find(v)] = find(u);}

ll x[N+10]; // 差分 和最终值
int fa[N+10][POWER]; // 树上倍增
int d[N+10]; // 深度
// 一级父节点 和 深度
void build(int u,int p = 1,int dep = 1){
  fa[u][0] = p;
  d[u] = dep;
  for(auto v:p2[u]) if(v != p) build(v,u,dep+1);
}
// 还原差分
void dfs(int u, int p = 1, int s = 0){
  x[u] += s;
  for(auto v:p2[u]) if(v != p) dfs(v,u,x[u]);
}
// 最近公共祖先
int lca(int u,int v){
  if(d[u] < d[v])swap(u,v); // d[u] > d[v]
  per(i,0,POWER) if(d[u] - d[v] >= (1 << i)) u = fa[u][i];
  if(u == v) return u;
  per(i,0,POWER) {
    if(fa[u][i] != fa[v][i]){
      u = fa[u][i];
      v = fa[v][i];
    }
  }
  return fa[u][0];
}
// u 向上走d步
int fa_d(int u,int d){
  per(i,0,POWER) if(d >= (1 << i)) {
    d -= (1<<i);
    u = fa[u][i];
  }
  return u;
}

int main(){
  // read
  n = read();
  m = read();
  rep(i,0,m){
    int u = read();
    int v = read();
    e[i] = {u,v};
  }
  // MST
  iota(f+1,f+n+1,1);
  rep(i,0,m){
    auto [u,v] = e[i];
    if(find(u) != find(v)) {
      treee[i] = true;
      link(u,v);
      p2[u].pb(v);
      p2[v].pb(u);
    }
  }
  // 建立倍增
  build(1); // 深度 和 1级父节点
  rep(pwr,1,POWER) rep(i,1,n+1) fa[i][pwr] = fa[fa[i][pwr-1]][pwr-1];

  // 树上差分
  rep(i,0,m) if(!treee[i]){
    auto [u,v] = e[i];
    if(d[u] > d[v]) swap(u,v); // d[u] < d[v];
    int r = lca(u,v);
    if(u == r){
      int w = fa_d(v, d[v] - d[u] - 1);
      x[w]++;
      x[v]--;
    } else {
      x[1]++;
      x[u]--;
      x[v]--;
    }
  }
  // 差分还原成值
  dfs(1);
  // 输出答案
  rep(i,1,n+1) printf("%d", (int)(x[i] == 0));
  return 0;
}

D

https://codeforces.com/contest/1707/problem/D

题目

n 点 根为1树

初始 U = 1..n 点集合

一次操作, 取点集T, T 是U的部分虚树(T是U的真子集, 且T中任意两点的LCA也属于T), 令U=T

求 恰好k次操作后 集合只有根节点的操作路径有多少种

方案数 mod p

要求 k=1,2,…,n-1 所有的结果

范围

n 2000

p [1e8+7 ~ 1e9+9] 是 质数

2s

256mb

题解

我的思路

可能可以倒过来

初始只有根,每次增加至少一个点, 增加后要满足LCA的在集合中的关系, 一共k次

考虑一个叶子节点, 它可以任意时候被加入

一个非叶子只有一个分支的节点, 它也是任意时刻被加入

一个非叶子,多分支节点那么它加入的时机 需要 早于或等于 它的第二个被加入的子树

换句话说, 假设点i为多叉点,在t时刻被加入,那么 1..t-1 中至多只能存在点i 的其中一个子树中的点

f(t..k, all子树)

  • f(1..k, 子树1, 至少一个在[1..t-1]) * f(t..k, all子树-子树1) +

  • f(1..k, 子树2, 至少一个在[1..t-1]) * f(t..k, all子树-子树2) +

  • …

但似乎 注意到一个子树放在区间至于区间长度有关, 这样至少后面一半状态上是nk的

前面一节, 可以变成f(1..k,子树1) - f(t..k, 子树1) 这样剩下的至少一个不属于(t..k)

f(根u, 长度l) = for t = 1..l

转移还要n, 这样n^3, 而且还有k, 一眼TLE

考虑到本来状态就是 f(根u, 长度l) 也就是对于不同k可以复用, 那么问题来到了如何把转移优化到 log或者常数级别, 或者均摊常数级别

f(u,l) = f(v0, k - t + 1) * f(v1)

如果干掉这个t就好了

题解

如果每次点数不严格下降结果为f,原答案为ans

有 $f_i=\sum_{j=0}^i\binom{i}{j}ans_j$, 因为j步意味着j+1个不同的集合, 要用这j+1个不同的集合按原顺序,可重复的产生i+1个集合, 那么其实就是选择每个开始的位置

既然是带系数前缀和,那也可以从 f反向推ans, 所以问题怎么球不严格下降的结果

然后又是来到和我讨论类似的对删除时间的讨论

当一个节点u有分叉时

那么它的删除时间就会受到 子树的限制

  1. 子树里所有节点 早于等于 u

  2. u的某个子树以外的子树都删完了 早于等于 u, 早于剩下的子树最后一个节点

状态 dp[u][t] , u以及它的子树,恰好第i次操作后删除完的方案数

转移 $dp_{u,t}$

$C_u$ 是 $u$ 的子节点集合

前缀 $S_{u,t} = \sum_{i\le t} dp_{u,i}$

$u$子集前缀关于$t$的乘积 $M_{u,t} = \prod_{v \in C_u} S_{v,t}$

  1. $u$在$t$时刻删, 则 剩下的都在$[1,t]$时刻删

$M_{u,t}$

  1. $u$在$t_0 < t$ 时刻删, 因为要恰好, 则至少有个在$t$时刻删, 其它在$[1,t_0]$时刻删

$ \sum_{v\in C_u} (dp_{v,t} \cdot \prod_{w \in C_u, w \neq v}^N S_{w,t_0})$

$ = \sum_{v\in C_u} (dp_{v,t} \cdot \frac{\prod_{w\in C_u} S_{w,t_0}}{S_{v,t_0}})$

$ = \sum_{v\in C_u} dp_{v,t} \cdot \frac{M_{u,t_0}}{S_{v,t_0}}$

对于所有$t_0 \in [1..t-1]$ 加和

$ = \sum_{t_0 = 1}^{t-1} (\sum_{v\in C_u} dp_{v,t} \cdot \frac{M_{u,t_0}}{S_{v,t_0}})$

$ = \sum_{v\in C_u} (dp_{v,t} \cdot (\sum_{t_0 = 1}^{t-1} \cdot \frac{M_{u,t_0}}{S_{v,t_0}}))$

综上

$ dp_{u,t} = M_{u,t} + \sum_{v\in C_u} (dp_{v,t} \cdot (\sum_{t_0 = 1}^{t-1} \cdot \frac{M_{u,t_0}}{S_{v,t_0}}))$

每个$S_{u,t}$, 均摊只需要O(1), $S$总状态$O(n^2)$, 所以时间复杂度$O(n^2)$

然后每个$M_{u,t}$ 均摊需要$O(|C_u|)$, 对于所有$u$的$|C_u|$和为 节点数,所以时间复杂度也是$O(n^2)$

再看 $\sum_{t_0 = 1}^{t-1} \cdot \frac{M_{u,t_0}}{S_{v,t_0}}$

注意和$u,v,t$ 有关,但v只能是u的子节点集, 所以状态数为$O(|C_u|n)$, 总状态数依然是$O(n^2)$, 同样通过t的前缀和, 均摊$O(1)$, 所以总时间复杂度也是$O(n^2k)$

最后$dp_{u,t}$, 状态显然$O(n^2)$, 时间复杂度$O(|C_u|)$, 所以总时间复杂度$O(n^2)$;

可做……….

咦,看起来和我的很像啊, 是不是我的那个t也可以干掉

可能不一定,别人通过恰好来简化了转移方便了前缀和实现

最后的最后, 通过$ans_i = f_i - \sum_{j=0}^{i-1} \binom{i}{j} ans_j $反推即可

实际写起来有几点坑,

  1. 时间卡得紧, 不要频繁的用费马小定理 计算inv, TLE11

  2. Wa31 第31个点 会出现S是MOD的倍数…..

然后Wa31需要小学数学, 因为本身是乘法, 变成除法只是为了简化运算, 所以本身不会有除0, 但 变化后 加上mod 就可能除以0

注意到这里其实就是M和S之间,所以统计一下M中少乘一个零的结果, 当S=0时取那个结果即可

然后 因为量级很大, 不能去 大量做mod除法, 所以一个办法是记录 分子分母, 另一个办法是

M/S也变成前缀+后缀的形式来算, 当然前缀+后缀形式会常数更小

代码

分数+除法 857ms 158MB

https://codeforces.com/contest/1707/submission/164894672

前后缀 + longlong 733ms 81MB

https://codeforces.com/contest/1707/submission/164900140

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
#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;)
#define pb push_back

int MOD = -1;

ll read(){ll r;scanf("%lld",&r);return r;} // read
ll mpow(ll v,ll mi){ll r = 1;while(mi){if(mi%2)(r*=v)%=MOD;(v*=v)%=MOD;mi>>=1;};return r;} // quick power with MOD

int n;

vector<int> e[2010];

void dfs(int u,int fa){
  vector<int> arr = {};
  for(auto v: e[u]) if(v != fa) arr.pb(v);
  e[u] = arr;
  for(auto v: e[u]) dfs(v, u);
}

struct ModInt{
  int v;
  ModInt(ll val = 0) :v(val) { }
};

ll real(const ModInt & v0){
  return (v0.v + MOD) % MOD;
}

ModInt operator+(const ModInt & v0, const ModInt &v1){
  return (v0.v + v1.v) % MOD;
}

ModInt operator-(const ModInt & v0, const ModInt &v1){
  return (v0.v - v1.v) % MOD;
}

ModInt operator*(const ModInt & v0, const ModInt &v1){
  return ((ll)v0.v * (ll)v1.v) % MOD;
}

ModInt dp[2010][2010];
vector<ModInt> preMu[2010]; // 每次只会具体 u 可以复用
vector<ModInt> sufMu[2010];
ModInt S[2010][2010];
ModInt W[2010][2010];

ModInt fac[2010] = {1};
ModInt invv[2010] = {1};
ModInt invfac[2010] = {1};
ModInt C(int n,int m) { return fac[n] * invfac[m] * invfac[n-m]; }

ModInt ans[2010];

int main(){
  n = read();
  MOD = read();
  rep(i,1,n){
    int u = read();
    int v = read();
    e[u].pb(v);
    e[v].pb(u);
  }

  // 30 ms
  rep(i,1,n+1) fac[i] = fac[i-1] * i;
  invv[1] = 1;
  rep(i,2,n+1) invv[i] = (MOD-MOD/i) * invv[MOD % i];
  rep(i,1,n+1) invfac[i] = invfac[i-1] * invv[i];

  dfs(1, 1);
  // 61ms
  // bfs on tree
  vector<int> vorder = {1};
  rep(i, 0, vorder.size()) {
    int u = vorder[i];
    for(auto v: e[u]) vorder.pb(v);
  }
  reverse(vorder.begin(), vorder.end());

  for(auto u: vorder) {
    rep(t,1,n) {
      ModInt &dput = dp[u][t] = 1; // 叶子
      if(!e[u].empty()) {
        // 优化成 前后缀
        preMu[t] = vector<ModInt> (e[u].size() + 1, 1);
        sufMu[t] = vector<ModInt> (e[u].size() + 1, 1);
        rep(i,0,e[u].size()){
          auto v = e[u][i];
          preMu[t][i+1] = preMu[t][i] * S[v][t];
        }
        per(i,0,e[u].size()){
          auto v = e[u][i];
          sufMu[t][i] = sufMu[t][i+1] * S[v][t];
        }
        dput = preMu[t][e[u].size()];
        if(t > 1) rep(i,0,e[u].size()) {
          auto v = e[u][i];
          ModInt &Wvt = W[v][t-1] = ((t-1 > 1) ? W[v][t-2] : 0) + (preMu[t-1][i] * sufMu[t-1][i+1]);
          dput = dput + dp[v][t] * Wvt;
        }
      }
      S[u][t] = ((t > 1) ? S[u][t-1] : 0) + dput;
    }
  }

  rep(t,1,n) ans[t] = preMu[t][e[1].size()];
  rep(t,1,n) rep(t0,1,t) ans[t] = ans[t] - ans[t0] * C(t,t0) ;
  rep(t,1,n) printf("%lld ", real(ans[t]));
  return 0;
}

E

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

题目

长度n数组 a

$ai \in [1,n]$

f((l,r)) = (min(a[l..r]) , max(a[l..r])), 传入区间范围, 返回最小值和最大值

每次调用 (l,r) = f((l,r))

q个询问

每次问如果初始 li,ri, 需要反复调用 多少次 让l和r 最终变成(1,n) 或不可能

范围

q 1e5

n 1e5

题解

我的思路

显然对于给定l,r 输出的f是一定的

所以对于所有的输入, 全部成环

那么f( (1,n) ) 一定要等于 (1,n), 否则 只有直接传入1,n 才会满足

想倒着找, 但是显然有最坏情况, 2 3 4 5 6, 这样一共有$O(n^2)$种不同输入和结果

题解

如果 区间A 包含于区间B

那么 f(A) 包含于 f(B)

证明, min(B) <= min(A) <= max(A) <= max(B)

并且高阶f也有这个包含关系

因此如果 [l,r] = ([l,r0] 并 [l0,r]), 其中 (l0 <= r0)

那么 f(l,r) 包含 (f(l,r0) 并 f(l0,r)),

注意到 f(l,r0) 包含 f(l0,r0), f(l0,r) 也包含 f(l0,r0)

所以 f(l,r0) 和 f(l0,r) 本身就重叠, 所以 f(l,r0) 并 f(l0,r) = 连续的区间

那么 f(l,r) 的最小值 至少包含于 f(l,r0) 和 f(l0,r) 的其中一个, 最大值也是, 所以最小值最大值都存在,且连续, 包含于 f(l,r)

综上 f(l,r0) 并 f(l0,r) = f(l,r)

同样高阶也满足

例如2阶段, f(f(l,r)) = f(f(l,r0)) 并 f(f(l0,r)) , 思路同上, 包含于关系, 最小 最大值, 连续 推出相等

注意到 一旦能到整个长度,那么一定 f(1,n) = (1,n)

如果链很长, 根据状态数 可能达到n^2

那么 办法就是倍增, 倍增到> n^2 如果还不行那就真不行了

可以的话就二分倍增的倍数

为了效率, 用倍增记录每个位置开始的长度的 多少轮跳跃的结果

然后实现上几点注意, 别二分, 每次二分会导致 长度不是幂次 依然需要log, 多层log过不了

找结果依然是倍增的找

然后就是cpu缓存和tlb机制, 注意循环顺序访问顺序和数组定义顺序

这导致常数影响非常明显, tle的代码和600+ms过的代码 就是把顺序换了换

然后我看有人 长度开的2^18 也过了!!!, 不知道数学上是否有办法证明或者找反例

代码

https://codeforces.com/contest/1707/submission/164951002

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
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
#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;)
#define pb push_back
 
ll read(){ll r;scanf("%lld",&r);return r;} // read
 
const int N = 100000;
const int PLEN = 19; // power length math.log(100000) / math.log(2) 16.609640474436812
const int POP = 35; // power operation math.log(4999950000) / math.log(2) 32.219266521851075
 
ll n;
 
int L[POP][PLEN][N+10]; // 次数不用记录零次
int R[POP][PLEN][N+10];
 
int LG2[N+10]; // 0 和 1 都对应0次方, 需要减的 1<<LG2[r-l]的偏移量
 
int a[N+10];
 
inline pii f(int l,int r,int p1){
  if(l == r) return {
    L[p1][0][l],
    R[p1][0][r]
  };
  int sz = LG2[r-l];
 
  return {
    min(L[p1][sz+1][l],L[p1][sz+1][r-(1<<sz)]),
    max(R[p1][sz+1][l],R[p1][sz+1][r-(1<<sz)])
  };
}
 
inline int query(int l,int r){
  if(l == 1 && r == n) return 0;
  if(l == r) return -1;
  // 不要二分, 二分是 log(n^2) = 2 log(n) * log(n)
  // 直接binary 倍增做, log(r-l+1)*O(1) < log(n)
  ll ret = 0;
  per(i, 0, POP){
    // printf("%d = %d\n",r-l,p0);
    int l0, r0;
    tie(l0, r0) = f(l, r, i);
    if(l0 != 1 || r0 != n){
      // checklrk(l, r, 1ll << i, l0, r0);
      l = l0;
      r = r0;
      ret += (1ll << i);
      if(l == r) return -1;
    }
  }
  tie(l,r) = f(l, r, 0);
  return (l == 1 && r == n) ? (ret + 1) : -1;
}
 
int main(){
  n = read();
  rep(i,2,N) LG2[i] = LG2[i/2] + 1;
  int q = read();
  rep(i,1,n+1) L[0][0][i] = R[0][0][i] = a[i] = read();
  {
    const int p1 = 0;
    rep(p0,1,PLEN) rep(i,1,n+1) {
      L[p1][p0][i] = min(L[p1][p0-1][i],L[p1][p0-1][min(n,i+(1ll << max(0ll, p0-2)))]);
      R[p1][p0][i] = max(R[p1][p0-1][i],R[p1][p0-1][min(n,i+(1ll << max(0ll, p0-2)))]);
      // check(i,p0,p1);
    }
  }
  rep(p1, 1, POP) rep(p0, 0, PLEN) rep(i,1,n+1){
    tie(
        L[p1][p0][i] ,
        R[p1][p0][i]
       ) = f(
         L[p1 - 1][p0][i],
         R[p1 - 1][p0][i],
         p1 - 1
         );
  }
 
  while(q--){
    int l = read();
    int r = read();
    printf("%d\n", query(l,r));
  }
  return 0;
}

总结

C

有想到, 环的最大边的 两点以外的点不可能,但是有反例, 就是没有把最小生成树 和 这个合在一起考虑

后面LCA和树上差分倒是没啥问题掌握了

D

感觉真有可能能做出来, 多习惯在dp时 分别恰好,和 小于等于 ,以及 前缀和方程与逆方程之间的联系

被小学数学教育了$a \neq \frac{a\cdot b}{b}$

然后就是 大量的inv还是不要, 一个办法就是 分数表示, 一个办法是想办法消除掉除法

E

数学推出性质以后 就是倍增倍增倍增了

实现上也有一些坑

参考

官方