Codeforces Round 740

發表於 更新於 分類於 ， Disqus： 文章字數： 3.3k 所需閱讀時間 ≈ 11 分鐘
B(DP优化) D(插入排序 反向 组合数 树状数组) E(二分 图论 数学 bfs)

B

题意

n <= 4e6, 1e8<mod<1e9, mod is prime, 时间6s，内存128MB

$f(1) = 1$

$f(x) = \sum_{y=1}^{x-1}f(y) + \sum_{z=2}^{x}f(\lfloor \frac{x}{z} \rfloor)$

给定n和mod, 求f(x)%mod

先看时间复杂度

虽然题目给了6s, 但是 这里n已经是4e6了

显然左边可以前缀和

$ f(x) = presumf(x-1) + \sum_{z=2}^{x}f(\lfloor \frac{x}{z} \rfloor)$

左边 O(1)了

右边，注意到$\lfloor \frac{x}{z} \rfloor$ 的取值个数是$O(\sqrt{n})$ 的

这一块即使用了连续段的优化依然整个是$O(n^{1.5})$的复杂度

剩余我没想到的题解部分

考虑 S(x+1) 和 S(x) 的差别

对于加法，多一个 S(x+1-1 = x),

对于除法，多一个 S((x+1)/(x+1) = 1)

对于 i > 1, 可能 S(x+1) 中是 S(i) 而 S(x)中是 S(i-1)

举例

1
2
3
4
5
6
10:的除序列
5,3,2,2,1,1,1,1,1
11:的除序列
5,3,2,2,1,1,1,1,1,1(多)
12:的除序列
6(变),4(变),3(变),2,2(变),1,1,1,1,1,1(多)

$\lfloor \frac{x+1}{i} \rfloor \neq \lfloor \frac{x}{i} \rfloor $ , 原始值变化为$\frac{1}{i} \leq 1$

$\lfloor \frac{x+1}{i} \rfloor = 1 + \lfloor \frac{x}{i} \rfloor $

$\frac{1}{i}$ 的增加在跨越一个整数时必定是整数

$ x+1 = ki $

所以 $i$ 是 x的约数时才会变

约数看成倍数, 计算到x时 -> diff[kx] += f[x]-f[x-1]

直接 变成递推，时间$O(n \log n)$, 空间$O(n)$

Code

on codeforces

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
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i,a,n) for (int i=a;i<n;i++)
 
int n;
 
ll MOD;
 
// 计算之前的是结果，之后的是差异
ll f[4000010];
 
 
int main(){
    cin>>n>>MOD;
    f[1] = 1;
    rep(i,2,n+1){
        if(i == 2){
            // 特殊 没有第一个 f[i-1]
            f[i] = 2;
        }else{
            (f[i] += f[i-1] + (f[i-1] + f[1]))%=MOD;
        }
        rep(j,2,n+1){
            ll ij=i*j;
            if(ij > n)break;
            (f[ij] += f[i]-f[i-1])%=MOD;
        }
    }
    printf("%lld\n",(f[n]+MOD)%MOD);
    return 0;
}

总结

关键点在 直接换个思路，换成计算差异，然后这里的差异能从 整数部分不同推导到 刚好是约数时会变，从而就能完成效率优化

D

题意

t <= 1e5 组测试

每组

0 <= m < n <= 2e5

所有组m保证 sum{m} <= 2e5, 不对n有相应保证

每次是长度为n的数组(不提供具体值)，告诉你m个操作，每次操作x,y (y < x) ，意思是把位置在x移动到y(一次插入排序的操作,也就是 y 是 最大的插入位置)

例如

1 2 3 2

如果把 最后一个2 ，可以插入在2前，也可以是3前，这里只能选择3前, 所以给的(x y)是 (4 3)

问原始序列所有值在[1~n]之间的合法方案数, MOD 998244353

题解

首先 n 不限制，那么可能会有离散化相关的内容

假设序列开始是[a0 a1 a2 …] 那么根据m次操作，有唯一的移动结果,因为每次都指定的x和y

对于移动以后，必定 非严格单调递增

那么问题变成了两个，找到可能一样的值的组（通过能确定的不一样的值做切分），这些组如何得到答案

换个计数法

令c表示，在最终序列中,相邻值“一定不同”的个数（也就是有c个小于号(来源交换推导出的大小关系)）,而最终序列中剩余的相邻的位置，可能相同可能不同

那么把这c个一定不同的位置-1，变成了 所有相邻位置可能相同可能小于， 范围由n变为了n-c

也就是 n个数，范围在[1~ n-c]中，非严格单调递增的方案数

也就是 n 个相同的球，放入 n-c 个不同盒子中（可以空盒子）

也就是 n+n-c 个相同的球，放入 n-c 个不同盒子中（不能空盒子）

挡板法,有 2n-c-1 个间隙

显然方案数 C(2n-1-c,n)

也就有了，如果能的到c就能得到答案

计算必定小于个数

离线+倒序

维护一个位置集合S,初始含有1到n

按照插入的倒序，(知道xi是单调递减的)

对于(xi,yi),

1
2
3
4
5
6
7
// 操作前 （反向操作会让 [xi~n]这部分之后再也不会使用）
[1....yi-1][yi...xi-1][xi][xi+1...n]
// 操作后
[1....yi-1][xi][yi...xi-1][xi+1...n]
// 因为我们是反向操作，所以 关注的是这两个
            !   !                    
            p   q

p = S中第yi小的

q = S中第yi+1小的

标记q是 前面相邻被拆入过值的,然后删除p (因为xi是单调递减，xi 到n，在倒序处理过程中，都不再回用到，和把p变成n+1一样效果

而找第k小和移除一个数，这种可以通过线段树，树状数组来完成

效率

注意到不要做成 O(n log n), 要是O(m log n), 一个办法是，首次建立足够大的树状数组/线段树。 每轮询问结束后，再回滚，这样建树 O( max n ), 操作都是 O ( m log n )

这样 算法+效率问题都解决了

代码

狗都不手写平衡树

倒序+树状数组+二分法查找第k大+组合数

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

typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);

const int N = 400000;
ll fac[N+10];

ll pwr(ll v,ll mi){
  ll r =1;
  while(mi){
    if(mi%2) (r*=v)%=MOD;
    (v*=v)%=MOD;
    mi/=2;
  }
  return r;
}

ll inv(ll v){
  return pwr(v,MOD-2);
}

ll C(ll n,ll m){
  return (((fac[n]*inv(fac[m]))%MOD)*inv(fac[n-m]))%MOD;
}

int n,m;

ll ta [2*N+10];

ll lowbit(ll v){
  return v & -v;
}

void tinit(){
  rep(i,1,2*N+1){
    ta[i] = lowbit(i);
  }
}

void tadd(int i,int v){
  for(;i < 2*N+1;i+=lowbit(i)){
    ta[i] += v;
  }
}

ll tpre(int i){
  ll s = 0;
  for(;i!=0;i-=lowbit(i)){
    s+=ta[i];
  }
  return s;
}

ll getk(int k){
  ll l = 0;
  ll r = N+1;
  while(l+1 < r){
    int mid = (l+r)/2;
    ll p = tpre(mid) ;
    if(p>=k)r=mid;
    else l=mid;
  }
  return r;
}



ll getc(vector<int>&ys){
  set<int> used ;
  vector<int> rm;
  per(i,0,m){
    int y = ys[i];
    used.insert(getk(y+1));
    int rmi = getk(y);
    rm.pb(rmi);
    tadd(rmi,-1);
  }
  int r = used.size();
  per(i,0,m){
    tadd(rm[i],1);
  }

  return r;
}

int main(){
  fac[0]=1;
  rep(i,1,N+1){
    fac[i] = (fac[i-1]*i)%MOD;
  }
  tinit();
  int t;
  cin>>t;
  while(t--){
    vector<int> ys;
    scanf("%d %d",&n,&m);
    rep(i,0,m){
      int x,y;
      scanf("%d %d",&x,&y);
      ys.pb(y);
    }
    ll c= getc(ys);
    printf("%lld\n",C(2*n-c-1,n));

  }
  return 0;
}

Ext

pbds

对于 题解提到的 Policy-Based Data Structures 见下面洛谷日报，总之是在std以外，c++的一个扩展库里提供了对应的平衡树实现，可以不用自己去写平衡树

Rope

1
2
#include<ext/rope>
using namespace __gnu_cxx;
1
rope<变量类型>变量名称;

简单来说 rope是个超级string 内部实现平衡树，也就是可以不用上面的所有知识，直接正着做XD, 本意可能是用作巨大文本编辑时使用

crope = rope<char>

https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/ext/rope

复杂度 看https://www.geeksforgeeks.org/stl-ropes-in-c/ 里说 操作都是log，所以总的复杂度应该是 m log n

Ref

官方题解

洛谷日报39期 pbds

gnu online doc pbds

E

题意

无向连通图

保证每点出度大于2

无自环和重边

点<=1000

边<=2000

每个点有 1<= a[i],b[i] <= 1e9

初始值x, 从点1出发, 每次首次经过一个点，需要满足 当前x > a[i],首次经过该点后会 x+=b[i]

可以重复走边走点

额外限制，走完一条边以后不能立刻重走该边, 也就是不能 a->b->a

求能够经过所有点的最小的x

每次100组测试，每次 测试内容的 sum{n}<=1000 sum{m}<=2000

题解

显然，x单调递增，也就是如果我们能超过最大点，则所有点都能走，那么x的下界是 max{最大a点的a-sum{其它b},1点相邻点的最小a}+1

上界 直接最大值+1

所以如果给定一个值，我们能校验其合法性的话， 那么可以二分 [既然是2分了，其实不考虑上下界 直接[1~1e9+1]开始二分也行]

定义set表示已经访问过的集合, 我们找寻两种增广路径

  1. 到set以外的一些点的简单路径，并返回到set中， set中的点a->out->out->out…->set中的点b,我们把这些out的点加入到set中。注意因为首先我们知道set中的点任意两点至少有一条简单路径，现在能通过外部建立一条简单路径，那么必定可以仅在set中任意的行走，走到任意的点, 对于点a点b是同一个点，就更显然，我们有一个环，能在set中走环上任意点，然后即可走到set上任意点

  2. 不一定返回原来的set中，但是能在外部走成环 set中的点->out->out->out->out中出现过的点, 同上加入set中，我们又可达任意的点

以上两种都解决了不能立刻原路返回的限制

上面两种是必要的方法，但是充分性需要证明一下，也就是没有其它的方案

如果从set中走出，无法达成上面两种，则所有出走都是死路，因为连通性和度保证不会因为边的路径限制而是死路，只会因为 不能立刻回头+a[i] 的限制而成死路，因为每走一步，既不成环也不回到set，那么out没走过的必然-1，数量离散有下界，单调递减，必有界，

证明如果全是死路，则当前set无法完成，如果全是死路，则所有路径均不会消耗所有点，且无法扩展，出走后无法行走，如果消耗完所有点，那么说明x比所有a都打，必定可以成环矛盾

再证 每次增广的顺序不会影响，初始set，

对于一个可行的x和可行的增广顺序，显然x单调递增，如果有不同的方案导致死路，那么死路前的set，可以按照合法的增广顺序操作，每一次操作的x值都大于等于 原合法顺序的值，必定可行，所以增广的顺序和初始x值是否可行没有关系,

同时 一个 set的 最终x = sum{b}+初始x

那么问题就变成

对于给定的x，通过上述两种方案增广直到全覆盖，或者全死路为止

O(效率 log(max(a)))

那么 v->out->out->u(out) ，记录到u的时x的值 , 那么如果有另一条路径 到达u,两条路径中大x的值向小x值走动,那么可以和它构成环, 所以dfs即可

代码

暴力bfs过了，没缩点 时间复杂度， 每次 bfs( O(m+n) ), 增广次数O(n), 所以 总时间复杂度 O(n(m+n)log(max(a)))

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

typedef long long ll;
#define t3 1000+10
#define t4 10000+10
#define t5 100000+10
#define t6 1000000+10
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);

int n,m;

ll a[1010];
ll b[1010];

vector<int> p2[1010];


vector<ll> get_circle(ll x ,vector<ll> & vis, vector<ll> bfs){
  vector<ll> cur = vector(1010,(ll)0);
  vector<ll> fa = vector(1010,(ll)0);
  int st = 0;
  while(st < bfs.size()){
    int p = bfs[st];
    for(auto item:p2[p]){
      if(item == fa[p])continue; // 不能立即返回
      // item set 内
      if(vis[item]){
        // p set 内
        if(vis[p]){
          continue;
        }
        vector<ll> ret ;
        while(p && !vis[p]){
          ret.pb(p);
          p = fa[p];
        }
        assert(ret.size());
        return ret;
      }
      // item非set内
      if(cur[item] != 0){ // 访问过
        // p->item <- old
        // 这个比较有必要吗，因为 cur[x] > a[x] 是肯定的, 所以最小值一定在a中出现，必定至少成立一个不等式
        // if(cur[item] > a[p] // old->item -> p -> ...
        //   || max(cur[p],x) > a[item]) { // p->item -> old
          vector<ll> ret ;
          while(p && !vis[p]){
            ret.pb(p);
            p = fa[p];
          }
          p = item;
          while(p && !vis[p]){
            ret.pb(p);
            p = fa[p];
          }
          assert(ret.size());
          return ret;
        // }
      }else{
        // 未访问过 且可达
        if( max(cur[p],x) > a[item] ){
          bfs.pb(item);
          cur[item] = max(cur[p],x) + b[item];
          fa[item] = p;
        }
      }
    }
    st++;
  }
  return {};
}

bool test(ll startx){
  vector<ll> vis = vector(1010,(ll)0);
  vector<ll> s; // set 中的点
  s.pb(1);
  vis[1] =  1;
  int cnt = 1;
  while(true){
    auto r = get_circle(startx, vis,s);

    if(!r.size()){
      return false;
    }
    for(auto item:r){
      if(!vis[item]){
        // TODO 缩点
        vis[item] = 1;
        s.pb(item);
        cnt++;
        startx += b[item];
      }
    }
    if(cnt == n){
      return true;
    }
  }
}


int main(){
  int t;
  cin>>t;
  while(t--){
    scanf("%d %d",&n,&m);
    rep(i,2,n+1){
      scanf("%lld",a+i);
    }
    rep(i,2,n+1){
      scanf("%lld",b+i);
    }
    rep(i,0,m){
      int u,v;
      scanf("%d %d",&u,&v);
      p2[u].pb(v);
      p2[v].pb(u);
    }
    ll l = 0;
    ll r = 1'000'000'001;
    while(l+1 < r){
      ll mid = (l+r)/2;
      if(test(mid)){
        // printf("%lld ok\n",mid);
        r = mid;
      }else{
        // printf("%lld not ok\n",mid);
        l = mid;
      }
    }
    printf("%lld\n",r);
    // clear;
    rep(i,1,n+1){
      p2[i] = {};
    }
  }
  return 0;
}