2020牛客暑期多校训练营（第一场）

发布日期：2021-05-06 15:23:15 浏览次数：28 分类：精选文章

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

A

一、题意

定义一个函数 $B(t_{1}t_{2}\cdots t_{k})=b_{1}b_{2}\cdots b_{k}$ 。

如果存在 $1\leqslant j < i,t_j=t_i$ ，则 $b_i=min_{1\leqslant j<i,t_j=t_i}\{{i-j}\}$

否则 $b_i=0$

二、题解

三、代码

B

一、题意

有一个无穷个节点的树，第 $\dpi{150}i$ 个节点的父亲是 $\frac{i}{mindiv(i)}$ 。

$mindiv(i)$ 是 $i$ 的最小质因子。

选择一个节点 $u$ ，求 $min\left \{ \sum_{i = 1}^{m}w_i \times dis(u , i!) \right \}$ 。

$dis(u,v)$ 表示节点 $u,v$ 之间的边数，也就是距离，认为每条边的长度是 $1$ 。

多组测例。 $\sum m \leqslant 10^6$

数据范围： $1 \leqslant m \leqslant 10^5 , 0 \leqslant w_i \leqslant 10^4$

二、题解

这题很麻烦，反正现在的我做的很别扭，2020.9.1。

显然要建立虚树。

通过画图，观察到下面这几个特性。

（1） $dfn[i!]<dfn[(i+1)!]$

（2） $dep[(i+1)!] = dep[i!] + dep[i+1]$

（3） $dep[lca(i!, (i+1)!]=sum(maxdiv(i+1),n)$

其中 $maxdiv(i+1)$ 表示 $i+1$ 的最大质因子。

$sum(maxdiv(i+1),n)$ 表示 $i!$ 的 $[maxdiv(i+1),n]$ 的质因子个数。

第（3）条性质需要树状数组维护。

通过上面的性质可以建立出虚树。

这题就是求带权重心，贪心发现带权重心必然位于某个 $i!$ ，因此带权重心位于虚树中，构造虚树是正确的。

然后换根求带权重心。

三、代码

#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 ;ll w[maxn] , dp[maxn] ;ll sum[maxn] , S ;int f[maxn] ;int mindiv[maxn] ;ll ans = 1e18 ;void prework(){    rep(i , 2 , 100000)  for(int j = i ; j <= 100000 ; j += i)  if(!mindiv[j])  mindiv[j] = i ;    rep(i , 2 , 100000)  f[i] = f[i / mindiv[i]] + 1 ;}struct BIT{    ll tree[maxn] ; //开 1 倍空间    void init(int n)    {        memset(tree , 0 , sizeof(ll) * (n + 5)) ;    }    int lowbit(int k)    {        return k & -k ;    }    void add(int n , int x , ll k)  // a[x] += k    {        while(x <= n)  //维护的是 [1 , n] 的序列        {            tree[x] += k ;            x += lowbit(x) ;        }    }    ll sum(int x)  // sum[l , r] = sum(r) - sum(l - 1)    {        ll ans = 0 ;        while(x != 0)        {            ans += tree[x] ;            x -= lowbit(x) ;        }        return ans ;    }    ll query(int l , int r)    {        return sum(r) - sum(l - 1) ;    }} bit ;struct Virtual_tree{    vector
      
        vt[maxn] , vq ;    int top , stk[maxn] ;    bool vis[maxn] ;    int dep[maxn] ;    void init()    {        ans = 1e18 ;        dep[1] = 0 ;        rep(i , 2 , n)          {            dep[i] = dep[i - 1] + f[i] ;            int maxdiv = i ; //maxdiv是maxdiv[i]            while(maxdiv != mindiv[maxdiv])  maxdiv /= mindiv[maxdiv] ;            dep[n + i] = bit.query(maxdiv , n) ;            for(int j = i ; j != 1 ; j /= mindiv[j])   bit.add(n , mindiv[j] , 1) ;        }    }    void add(int u , int v)    {        vt[u].pb(v) , vt[v].pb(u) ;    }    void insert(int u)    {        if(top == 1) { stk[++ top] = u ; return ; }        int lc = n + u ; //lca预处理        if(dep[lc] == dep[stk[top]]) { stk[++ top] = u ; return ; }        while(top > 1 && dep[lc] <= dep[stk[top - 1]])  add(stk[top - 1] , stk[top]) , top -- ;        if(lc != stk[top])  add(lc , stk[top]) , stk[top] = lc ;         stk[++ top] = u ;    }    void build()    {        top = 0 , stk[++ top] = 1 ; //1不能在vq里面        rep(i , 2 , n)  insert(i) ;        while(top >= 2)  add(stk[top - 1] , stk[top]) , top -- ;    }    void dfs1(int f , int u)    {        dp[1] += w[u] * dep[u] ;        sum[u] = w[u] ;        for(auto v : vt[u])  if(v != f)  dfs1(u , v) , sum[u] += sum[v] ;    }    void dfs2(int f , int u)    {        for(auto v : vt[u])        {            if(v == f)  continue ;            ll d = dep[v] - dep[u] ;            dp[v] = dp[u] ;            dp[v] -= sum[v] * d ;            dp[v] += (S - sum[v]) * d ;            dfs2(u , v) ;        }        ans = min(ans , dp[u]) ;        cl(vt[u]) ; //清空，不能提前return结束遍历    }} v_tree ;int main(){    ios ;    prework() ;    while(cin >> n)    {        S = 0 ;        rep(i , 1 , n)  cin >> w[i] , w[n + i] = 0 , S += w[i] ;        dp[1] = 0 ;        bit.init(n) ;        v_tree.init() ;        v_tree.build() ;        v_tree.dfs1(1 , 1) ;        v_tree.dfs2(1 , 1) ;        cout << ans << '\n' ;    }    return 0 ;}

C

一、题意

二、题解

三、代码

D

一、题意

二、题解

三、代码

E

一、题意

二、题解

三、代码

F

一、题意

定义 $a^{\infty}$ 是字符串a重复无穷次后的字符串。

判定 $a^{\infty}$ 和 $b^{\infty}$ 的字典序大小。

多组测例，保证 $\sum (\left | a \right | + \left | b \right | ) \leqslant 2*10^6$

数据范围： $1 \leqslant \left | a \right |,\left | b \right |\leqslant 10^5$

二、题解

脑洞题。

判定a+b和b+a的大小。

叉姐的严格证明：

三、代码

#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 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()) ; string a , b , s , t ;int main(){    ios ;    while(cin >> a >> b)    {        s = a + b ;        t = b + a ;        int len = sz(s) ;        int flag = 2 ;        rep(i , 0 , len - 1)             if(s[i] < t[i])  { flag = 0 ; break ; }           else if(s[i] > t[i])  { flag = 1 ; break ; }        if(flag == 0)  cout << "<\n" ;        else if(flag == 1)  cout << ">\n" ;        else  cout << "=\n" ;    }    return 0 ;}

G

一、题意

二、题解

三、代码

H

一、题意

二、题解

三、代码

I

一、题意

$n$ 个点 $m$ 条边的无向图，是否可以从中选择若干条边，使每个点的度数是 $d_i$ 。

多组测例。

数据范围： $1\leqslant n\leqslant 50,1\leqslant m\leqslant 100,1\leqslant d_i\leqslant 2$

二、题解

我参考了，侵删。

对每个度数拆点，对每条边拆点。

对这个测例举例子

4 41 2 1 01 21 42 33 4

为什么是对的？

可以发现有两种匹配边：

（1）拆点后的点与拆边后的点匹配。

（2）拆边后的点与拆边后的点匹配。

种类（1）表示保留原图（拆点前的图）的边。

种类（1）表示删除原图（拆点前的图）的边。

三、代码

#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 pair
    
      pii ;typedef pair
     
       pll ;const int mod = 998244353 ;const int maxn = 3000 + 10 ;const int inf = 0x3f3f3f3f ;const double eps = 1e-6 ;mt19937  rnd(chrono::high_resolution_clock::now().time_since_epoch().count()) ;int n , m ;vector
      
        g[maxn] ;struct blossemtree{    queue
       
         q ;    int fa[maxn] , type[maxn] , lk[maxn] , nxt[maxn] , vis[maxn] ;    int find(int x)    {        if(x == fa[x]) return x ;        return fa[x] = find(fa[x]) ;    }    void addedge(int u , int v)    {        //ddebug(u , v) ;        g[u].pb(v) , g[v].pb(u) ;    }    void combine(int x , int lca)    {        while(x != lca)        {            int u = lk[x] , v = nxt[u] ;            if(find(v) != lca)  nxt[v] = u ;            if(type[u] == 1)  type[u] = 2 , q.push(u) ;            fa[find(x)] = find(u) , fa[find(u)] = find(v) ;            x = v ;        }    }    void contrack(int x , int y)    {        int lca = x ;        memset(vis , 0 , (n + 1) * sizeof(int)) ;        for(int i = x ; i ; i = nxt[lk[i]])  i = find(i) , vis[i] = 1 ;        for(int i = y ; i ; i = nxt[lk[i]])        {            i = find(i) ;            if(vis[i])            {                lca = i ;                break ;            }        }        if(lca != find(x))  nxt[x] = y ;        if(lca != find(y))  nxt[y] = x ;        combine(x , lca) , combine(y , lca) ;    }    void bfs(int s)    {        memset(type , 0 , (n + 1) * sizeof(int)) ;        memset(nxt , 0 , (n + 1) * sizeof(int)) ;        rep(i , 1 , n)  fa[i] = i ;        while(!q.empty())  q.pop() ;        q.push(s) , type[s] = 2 ;        while(!q.empty())        {            int x = q.front() ;            q.pop() ;            for(int y : g[x])            {                if(find(x) == find(y) || lk[x] == y || type[y] == 1)  continue ;                if(type[y] == 2)  contrack(x , y) ;                else if(lk[y])  nxt[y] = x , type[y] = 1 , type[lk[y]] = 2 , q.push(lk[y]) ;                else                {                    nxt[y] = x ;                    int pos = y , u = nxt[pos] , v = lk[u] ;                    while(pos)  lk[pos] = u , lk[u] = pos , pos = v , u = nxt[pos] , v = lk[u] ;                    return ;                }            }        }    }    int maxmatch()    {        int ans = 0 ;        rep(i , 1 , n)  if(!lk[i])  bfs(i) ;        rep(i , 1 , n)  if(lk[i])  ans ++ ;        return ans / 2 ;    }    void init()    {        rep(i , 1 , n)  cl(g[i]) ;        memset(lk , 0 , (n + 1) * sizeof(int)) ;    }} T ;int d[maxn] , in[maxn] ;int a[maxn] , b[maxn] ;pii id[maxn] ;int main(){    ios ;    int tot = 0 ;    ff : ;    while(cin >> n >> m)    {        tot = 0 ;        rep(i , 1 , n)  cin >> d[i] ;        rep(i , 1 , m)  cin >> a[i] >> b[i] , in[a[i]] ++ , in[b[i]] ++ ;        rep(i , 1 , n)          if(d[i] > in[i])          {            rep(i , 1 , n)  in[i] = 0 ;            cout << "No\n" ;            goto ff ;          }          else if(d[i] == in[i])  id[i].fi = -1 , id[i].se = -2 ;          else  id[i].fi = tot + 1 , id[i].se = tot + in[i] - d[i] , tot += in[i] - d[i] ;        rep(i , 1 , m)        {            int u = a[i] , v = b[i] ;            T.addedge(tot + 1 , tot + 2) ;            rep(i , id[u].fi , id[u].se)  T.addedge(tot + 1 , i) ;            rep(i , id[v].fi , id[v].se)  T.addedge(tot + 2 , i) ;            tot += 2 ;        }        n = tot ;        if(T.maxmatch() * 2 == tot)  cout << "Yes\n" ;        else  cout << "No\n" ;        rep(i , 1 , n)  in[i] = 0 ;        T.init() ;    }      return 0 ;}

J

一、题意

计算 $\int_{0}^{1}(x-x^n)dx$ ，答案对 $998244353$ 取模。

多组测例，测例数 $test \leqslant 10^5$

数据范围： $1 \leqslant n \leqslant 10^6$

二、题解

原理是分部积分法 $\int u(x)v^{'}(x)dx = u(x)v(x) - \int u^{'}(x)v(x)dx$

$\dpi{150} \begin{align*} & \int_{0}^{1}(x-x^n)dx \\ &= \int_{0}^{1}\frac{1}{n+1} {(x^{n+1})}^{'} (x-x^n)dx \\ &=\frac{1}{n+1}(x^{n+1}(1-x)^{n}|_{0}^{1} - \int_{0}^{1}x^{n+1} [(1-x)^n]^{'}dx) \\ &= \frac{n*(n-1)*...*1}{(n+1)*(n+2)*(2n)}\int_{0}^{1}x^{2n}dx \\ &= \frac{(n!)^2}{(2n+1)!}\\ \end{align*}$

三、代码

#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 = 2e6 + 10 ;const int inf = 0x3f3f3f3f ;const double eps = 1e-6 ; mt19937  rnd(chrono::high_resolution_clock::now().time_since_epoch().count()) ; struct Easymath{    ll qpow(ll a , ll b) //快速幂    {        if(b < 0)  return 0 ;        ll ans = 1 ;         a %= mod ;        while(b)        {            if(b & 1)  ans = (ans * a) % mod ;            b >>= 1 , a = (a * a) % mod ;        }        return ans % mod ;    }    ll ksc_log(ll x , ll y , ll mod) //快速乘    {        x %= mod , y %= mod ;        ll ans = 0;        while(y)        {            if(y & 1) ans = (ans + x) % mod ;             y >>= 1 ;            x = (x + x) % mod ;        }        return ans;    }    ll ksc_O1(ll x , ll y , ll mod) //快速乘    {        x %= mod , y %= mod ;        ll z = (ld)x * y / mod ;        ll ans = x * y - z * mod ;        if(ans < 0)  ans += mod ;        else if(ans >= mod)  ans -= mod ;        return ans ;    }    int cnt = 0 ;    bool vis[maxn] ;    int prime[maxn] ;    void get_prime(int up) //素数筛    {        memset(vis , 0 , sizeof(vis)) ;        vis[1] = 1 ;        for(int i = 2 ; i <= up ; i ++)        {            if(!vis[i])             prime[++ cnt] = i ;            for(int j = 1 ; j <= cnt && i * prime[j] <= up ; j ++)            {                vis[i * prime[j]] = 1 ;                if(i % prime[j] == 0) break ;            }        }    }    //begin 判定大素数    ll mul(ll a , ll b , ll mod)    {        ll ret = 0 ;        while(b)         {            if(b & 1)  ret = (ret + a) % mod ;            a = (a + a) % mod ;            b >>= 1 ;        }        return ret ;    }    ll pow(ll a , ll b , ll mod)    {        ll ret = 1 ;        while(b)         {            if(b & 1)  ret = mul(ret , a , mod) ;            a = mul(a , a , mod) ;            b >>= 1 ;        }        return ret ;    }    bool check(ll a , ll n)    {        ll x = n - 1 ;        int t = 0 ;        while((x & 1) == 0)         {            x >>= 1 ;            t ++ ;        }        x = pow(a , x , n) ;        ll y ;        rep(i , 1 , t)        {            y = mul(x , x , n) ;            if(y == 1 && x != 1 && x != n - 1)  return 1 ;            x = y ;        }        if(y != 1) return 1 ;        return 0 ;    }    bool Miller_Rabin(ll n)     {        if(n == 2)  return 1 ;        if(n == 1 || !(n & 1))  return 0 ;        const int arr[12] = {2,3,5,7,11,13,17,19,23,29,31,37} ;        rep(i , 0 , 11)         {            if(arr[i] >= n) break ;            if(check(arr[i] , n)) return 0 ;        }        return 1 ;    }    //end 判定大素数    ll get_inv(ll x) //逆元    {       return qpow(x , mod - 2) % mod ;    }    ll inv1[maxn] ;  //乘法逆元    void init1(int up)    {       inv1[1] = 1 ;       for(int i = 2 ; i <= up ; i ++)         inv1[i] = (ll)(mod - mod / i) * inv1[int(mod % (ll)i)] % mod ;    }    ll fac[maxn] ;    ll inv[maxn] ; //阶乘逆元    void init(int up)     {       fac[0] = fac[1] = inv[0] = inv[1] = 1 ;       for(int i = 2 ; i <= up ; i ++)       {         fac[i] = fac[i - 1] * i % mod ;         inv[i] = -inv[mod % i] * (mod / i) % mod ;         while(inv[i] < 0) inv[i] += mod ;       }       for(int i = 2 ; i <= up ; i ++)           inv[i] = inv[i] * inv[i - 1] % mod ;    }} em ;int main(){    ios ;    em.init(2000005) ;    int n ;    while(cin >> n)    {        ll ans = em.fac[n] * em.fac[n] % mod * em.inv[2 * n + 1] % mod ;        cout << ans << '\n' ;    }    return 0 ;}

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

下一篇：codeforces900D 2100分莫比乌斯反演

发表评论

关于作者

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

-- 愿君每日到此一游！

A

一、题意

二、题解

三、代码

B

一、题意

二、题解

三、代码

C

一、题意

二、题解

三、代码

D

一、题意

二、题解

三、代码

E

一、题意

二、题解

三、代码

F

一、题意

二、题解

三、代码

G

一、题意

二、题解

三、代码

H

一、题意

二、题解

三、代码

I

一、题意

二、题解

三、代码

J

一、题意

二、题解

三、代码

发表评论

最新留言

关于作者

推荐文章