2020牛客暑期多校训练营（第七场）待补题

发布日期：2021-05-06 15:23:20 浏览次数：11 分类：技术文章

本文共 7867 字，大约阅读时间需要 26 分钟。

A

一、题意

二、题解

三、代码

B

一、题意

二、题解

三、代码

C

一、题意

$n$ 个点的树，树上第 $i$ 个点的权值是 $f[i]$ 。初始时 $f[i]=0$ 。

$m$ 个操作。有 $3$ 种操作。

操作 $1$ ：输入两个整数 $x,w(1\leqslant x \leqslant n , 0 \leqslant w \leqslant 10000)$ 。

对于树上每个节点 $y$ ， $f[y] = f[y] + w-dis(x,y)$ 。

操作 $2$ ：输入一个整数 $x(1\leqslant x \leqslant n)$ 。

$f[x]=min(f[x] , 0)$

操作 $3$ ：输入一个整数 $x(1\leqslant x \leqslant n)$ 。

输出 $f[x]$ 。

多组测例。 $1\leqslant T \leqslant 5$

数据范围： $1 \leqslant n,m \leqslant 5 \times 10^4$

二、题解

对于操作 $1$ ： $f[y]=w-dis(1,x)-dis(1,y)+2\times dis(1,lca(x,y))$

$w,dis(1,x),dis(1,y)$ 可以直接维护。

$dis(1,lca(x,y))$ 可以直接在对 $x$ 进行操作 $1$ 时把根节点到 $x$ 的点 $val$ 都加 $1$ ，最后查询 $f[y]$ 时查询根节点到 $x$ 的点 $val$ 的和，就是 $dis(1,lca(x,y))$ ，用树剖维护。 $val$ 初始时都是 $0$ 。

对于操作 $2$ ：查询 $f[x]$ ，如果 $f[x] > 0$ ， $delta[x] = delta[x] - f[x]$ 。 $delta$ 初始时都是 $0$ 。

对于操作 $3$ ： $f[y] = sum - dep[y] * num + 2 * val(1 , y) + delta[y]$

$sum$ 是操作 $1$ 的 $w-dis(1,x)$ 的和。

$num$ 是操作 $1$ 的次数。

$val(1,y)$ 是根节点到 $y$ 的 $val$ 的和。

三、代码

#include
   
    #define pb push_back#define fi first#define se second#define sz(x)  (int)x.size()#define cl(x)  x.clear()#define all(x)  x.begin() , x.end()#define rep(i , x , n)  for(int i = x ; i <= n ; i ++)#define per(i , n , x)  for(int i = n ; i >= x ; i --)#define mem0(x)  memset(x , 0 , sizeof(x))#define mem_1(x)  memset(x , -1 , sizeof(x))#define mem_inf(x)  memset(x , 0x3f , sizeof(x))#define debug(x)  cerr << #x << " = " << x << '\n'#define ddebug(x , y)  cerr << #x << " = " << x << "   " << #y << " = " << y << '\n'#define ios std::ios::sync_with_stdio(false) , cin.tie(0)using namespace std ;typedef long long ll ;typedef long double ld ;typedef pair
    
      pii ;typedef pair
     
       pll ;typedef double db ;const int mod = 998244353 ;const int maxn = 2e5 + 10 ;const int inf = 0x3f3f3f3f ;const double eps = 1e-6 ; int n ;vector
      
        g[maxn] ;int w[maxn] , wt[maxn] , son[maxn] , dfn[maxn] , fa[maxn] ;int cnt = 0 ;int dep[maxn] , siz[maxn] , top[maxn] ;int delta[maxn] ;struct seg_tree{    int sum[maxn << 2] , add[maxn << 2] ;        int ls(int x){ return x << 1 ; }    int rs(int x){ return x << 1 | 1 ; }    void push_up(int p){ sum[p] = sum[ls(p)] + sum[rs(p)] ; }    void build(int id , int l , int r)    {        add[id] = 0 ;        if(l == r) {sum[id] = 0 ; return ;}        int mid = (l + r) >> 1 ;        build(ls(id) , l , mid) ;        build(rs(id) , mid + 1 , r) ;        push_up(id) ;    }     void f(int id , int l , int r , int k)    {        add[id] = add[id] + k ;        sum[id] = sum[id] + k * (r - l + 1) ;    }    void push_down(int id , int l , int r)    {        int mid = (l + r) >> 1 ;        f(ls(id) , l , mid , add[id]) ;        f(rs(id) , mid + 1 , r , add[id]) ;        add[id] = 0 ;    }    void iadd(int id , int l , int r , int x , int y , int k)    {        if(x > y || x > r || y < l)  return ; //避免越界。        if(x <= l && r <= y)        {            sum[id] += k * (r - l + 1) ;            add[id] += k ;            return ;        }        push_down (id , l , r) ;        int mid = (l + r) >> 1 ;        if(x <= mid) iadd(ls(id) , l , mid , x , y , k) ;        if(y > mid)  iadd(rs(id) , mid + 1 , r , x , y , k) ;        push_up(id) ;    }    int iquery(int id , int l , int r , int x , int y)    {        if(x > y || x > r || y < l)  return 0 ; //避免越界。        int ans = 0 ;        if(x <= l && r <= y) return sum[id] ;         int mid = (l + r) >> 1 ;        push_down(id , l , r) ;        if(x <= mid) ans += iquery(ls(id) , l , mid , x , y) ;        if(y > mid)  ans += iquery(rs(id) , mid + 1 , r , x , y) ;        return ans ;    }} seg ;void dfs1(int x , int f , int deep){   dep[x] = deep ;    fa[x] = f ;    siz[x] = 1 ;    son[x] = 0 ;   int maxson = -1 ;    for(auto y : g[x])   {     if(y == f) continue ;      dfs1(y , x , deep + 1) ;      siz[x] += siz[y] ;      if(siz[y] > maxson)     son[x] = y , maxson = siz[y] ;   }}void dfs2(int x , int topf){   dfn[x] = ++ cnt ;   wt[cnt] = w[x] ;   top[x] = topf ;    if(!son[x]) return ;    dfs2(son[x] , topf) ;   for(auto y : g[x])   {     if(y == fa[x] || y == son[x]) continue ;     dfs2(y , y) ;    }}void upd_range(int x , int y , int k){   while(top[x] != top[y])   {     if(dep[top[x]] < dep[top[y]])     swap(x , y) ;     seg.iadd(1 , 1 , n , dfn[top[x]] , dfn[x] , k) ;     x = fa[top[x]] ;   }   if(dep[x] > dep[y])   swap(x , y) ;   seg.iadd(1 , 1 , n , dfn[x] , dfn[y] , k) ;}int q_range(int x , int y){   int ans = 0 ;   while(top[x] != top[y])   {     if(dep[top[x]] < dep[top[y]])     swap(x , y) ;     ans += seg.iquery(1 , 1 , n , dfn[top[x]] , dfn[x]) ;     x = fa[top[x]] ;   }   if(dep[x] > dep[y])   swap(x , y) ;   ans += seg.iquery(1 , 1 , n , dfn[x] , dfn[y]) ;   return ans ;}int sum = 0 , num = 0 ;int query(int x){    int ans = (q_range(1 , x) << 1) ;    ans += sum ;    ans -= dep[x] * num ;    ans += delta[x] ;    return ans ;}void update1(int x , int w){    sum += w - dep[x] ;    num ++ ;    upd_range(1 , x , 1) ;}void update2(int x){    int ans = query(x) ;    if(ans > 0)  delta[x] -= ans ;}int main(){    ios ;    int T ;    cin >> T ;    while(T --)    {        int m ;        cin >> n >> m ;        rep(i , 1 , n)  cl(g[i]) , delta[i] = 0 ;        sum = 0 , num = 0 ;        rep(i , 1 , n - 1)        {            int u , v ;            cin >> u >> v ;            g[u].pb(v) , g[v].pb(u) ;        }        cnt = 0 ;        dfs1(1 , 1 , 1) ;        dfs2(1 , 1) ;        seg.build(1 , 1 , n) ;        while(m --)        {            int op ;            cin >> op ;            if(op == 1)            {                int x , w ;                cin >> x >> w ;                update1(x , w) ;            }            else if(op == 2)            {                int x ;                cin >> x ;                update2(x) ;            }            else            {                int x ;                cin >> x ;                cout << query(x) << '\n' ;            }        }    }    return 0 ;}

D

一、题意

二、题解

三、代码

E

一、题意

二、题解

三、代码

F

一、题意

二、题解

三、代码

G

题解有三种图，但是一个dp[i][j]就表示出来了，我表示不解。

一、题意

二、题解

三、代码

H

一、题意

二、题解

三、代码

I

一、题意

二、题解

三、代码

J

一、题意

有如下元素的定义：

（1）a,b,c...是对象

（2）A,B,C... 和 A.a , A.b .... 和 a.a,a.b ....是指针。

有如下语句的定义：

（1）A = x 指针A可以访问对象x

（2）A = B 指针A可以访问指针B可以访问的对象。

（3）A.f = B 如果指针A指向对象o，指针o.f可以访问指针B可以访问的对象。

（4）A = B.f 如果指针B指向对象o，那么指针A可以指向指针o.f可以访问的对象。

二、题解

直接模拟就行了。

这其实是一个有向图，但是你重复模拟几十次就不用建图了。

三、感想

禁止套娃

四、代码

#include
   
    #define pb push_back#define fi first#define se second#define sz(x)  (int)x.size()#define cl(x)  x.clear()#define all(x)  x.begin() , x.end()#define rep(i , x , n)  for(int i = x ; i <= n ; i ++)#define per(i , n , x)  for(int i = n ; i >= x ; i --)#define mem0(x)  memset(x , 0 , sizeof(x))#define mem_1(x)  memset(x , -1 , sizeof(x))#define mem_inf(x)  memset(x , 0x3f , sizeof(x))#define debug(x)  cerr << '*' << x << '\n'#define ddebug(x , y)  cerr << '*' << x << ' ' << y << '\n'#define ios std::ios::sync_with_stdio(false) , cin.tie(0)using namespace std ;typedef long long ll ;typedef long double ld ;typedef pair
    
      pii ;typedef pair
     
       pll ;const int mod = 998244353 ;const int maxn = 2e5 + 10 ;const int inf = 0x3f3f3f3f ;const double eps = 1e-6 ; mt19937  rnd(chrono::high_resolution_clock::now().time_since_epoch().count()) ; vector
      
        o[30] , t[30] , th[30][30] , l[30][30] ;vector
       
         f[30] ;string s[3] ;bool ans[30][30] ;void solve1(){    rep(A , 0 , 25)  rep(f , 0 , 25)  for(auto B : th[A][f])  rep(o , 0 , 25)  if(ans[A][o])  rep(x , 0 , 25)  if(ans[B][x])  l[o][f].pb(x) ;}void solve2(){    rep(i , 0 , 25)  for(auto u : f[i])    {        int B = u.fi ;        int f = u.se ;        rep(o , 0 , 25)  if(ans[B][o])  for(auto x : l[o][f])  ans[i][x] = 1 ;    }}int main(){    ios ;    int n ;    cin >> n ;    while(n --)    {        rep(i , 0 , 2)  cin >> s[i] ;        if(sz(s[0]) == 1 && sz(s[2]) == 1)        {            if(s[2][0] >= 'a' && s[2][0] <= 'z')  o[s[0][0] - 'A'].pb(s[2][0] - 'a') ; //1            else  t[s[0][0] - 'A'].pb(s[2][0] - 'A') ; //2        }        else if(sz(s[0]) == 3)  th[s[0][0] - 'A'][s[0][2] - 'a'].pb(s[2][0] - 'A') ; //3        else  f[s[0][0] - 'A'].pb({s[2][0] - 'A' , s[2][2] - 'a'}) ; //4    }    rep(pp , 0 , 51)    {        rep(A , 0 , 25)  for(auto x : o[A])  ans[A][x] = 1 ;        rep(A , 0 , 25)  for(auto B : t[A])  rep(x , 0 , 25)  if(ans[B][x])  ans[A][x] = 1 ;        solve1() ;        solve2() ;    }    rep(i , 0 , 25)    {        cout << char('A' + i) << ": " ;        rep(j , 0 , 25)  if(ans[i][j])  cout << char('a' + j) ;        if(i < 25)  cout << '\n' ;    }    return 0 ;}

上一篇：2020牛客暑期多校训练营（第八场）

下一篇：2020牛客暑期多校训练营（第五场）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

A

一、题意

二、题解

三、代码

B

一、题意

二、题解

三、代码

C

一、题意

二、题解

三、代码

D

一、题意

二、题解

三、代码

E

一、题意

二、题解

三、代码

F

一、题意

二、题解

三、代码

G

一、题意

二、题解

三、代码

H

一、题意

二、题解

三、代码

I

一、题意

二、题解

三、代码

J

一、题意

二、题解

三、感想

四、代码

发表评论

最新留言

关于作者

推荐文章