KAJIMA CORPORATION CONTEST 2024（AtCoder Beginner Contest 340）(赛上A~E+G，赛后F)

我的知乎blog传送门

A~B

略

C

本题需要：记忆化搜索

时间复杂度< $O(lo{g}^2(n))$

void solve () {
   
    ll n ; cin >> n ;
    std::map < ll , ll > map ;
    auto ans = [ & ] ( auto&& ans , ll n ) -> ll {
   
        if ( n == 1 ) return 0 ;
        if ( map [ n ] ) return map [ n ] ;
        else return map [ n ] = n + ans ( ans , n / 2 ) + ans ( ans , ( n + 1 ) / 2 ) ;
    };
    cout << ans ( ans , n ) << endl ;
}

D

本题需要：最小生成树

$root$ 为0，建图是每个点 $i$ 向 $i+1$ 和 $x_i$ 连边

void solve () {
   
    ll n ; cin >> n ;
    constexpr ll inf = 1e15 ;
    vector < ll > dp ( n , inf ) ;
    priority_queue < pll , vector < pll > , greater < pll > > q ;
    q.emplace ( 0 , 0 ) ;
    std::vector < vector < pll > > map ( n ) ;
    for ( int i = 0 ; i < n - 1 ; ++ i ) {
   
        ll a , b , x ; cin >> a >> b >> x ; -- x ;
        map [ i ].emplace_back ( i + 1 , a ) ;
        map [ i ].emplace_back ( x , b ) ;
    }
    vector < bool > vis ( n ) ;
    dp [ 0 ] = 0 ;
    while ( !q.empty () ) {
   
        auto [ val , v ] = q.top () ;
        q.pop () ;
        if ( vis [ v ] ) continue ;
        dp [ v ] = val ;
        vis [ v ] = 1 ;
        for ( auto [ here , al ] : map [ v ] ) {
   
            if ( vis [ here ] ) continue ;
            if ( dp [ v ] + al < dp [ here ] ) {
   
                q.emplace ( dp [ v ] + al , here ) ;
            }
        }
    }   
    // Debug ( dp ) ;
    cout << dp.back () << endl ;
}

E

本题需要：懒标线段树

对于每一个 $B_i$ ,遍历到她时，读取她对于的球数 $cnt$ 并把它清空，接下来把 cnt 均匀分一下，$\lfloor cnt/n\rfloor$ 是对圈所有元素的贡献， 是对 $cnt\%n$ 后面元素的贡献 （注意是圆环）

# include  <bits/stdc++.h>
# include  <ext/pb_ds/assoc_container.hpp>
# ifdef LOCAL
    # include "C:\Users\Kevin\Desktop\demo\C++_code\debug.h"
#endif
using  namespace  std ;
using  namespace  __gnu_pbds;

namespace predefine {
   
    using ll = long long ;using i64 = long long ;
    using Int = __int128 ;using pll = pair < ll , ll > ;

    # define af( i , a , b ) for ( ll i = a ; i <= b ; ++ i )
    # define df( i , a , b ) for ( ll i = a ; i >= b ; -- i )

    # define endl '\n'
}
using namespace predefine ;

//-----  板子  ---------------------------------------------------------------------------------------------------------
using Splay = tree <i64, int, less<i64>, splay_tree_tag, tree_order_statistics_node_update> ;

template < class Tag , class Info > 
struct LazySegtree {
   
	int n ;
	std::vector < Info > tree ; 
	std::vector < Tag > lazy ;
	LazySegtree (): n(0) {
   }
	LazySegtree ( const int& n , const Info& x = Info () ) {
   
		init ( n , x ) ;
	}
	template < class T >
	LazySegtree ( const std::vector < T >& v ) {
   
		init ( v ) ;
	}
	void init ( int n , const Info& x = Info () ) {
   
		init ( std::vector < Info > ( n , x ) ) ;
	}
	template < class T > 
	void init ( const std::vector < T >& v ) {
   
		n = (int)v.size () ;
        tree.assign(4 << std::__lg(n), Info());
        lazy.assign(4 << std::__lg(n), Tag());
		auto build = [ & ] ( auto&&build , int l , int r , int p ) -> void {
   
			if ( ( r - l ) == 1 ) {
   
				tree [ p ] = v [ l ] ;
				return ;
			}
			int mid = ( r + l ) >> 1 ;
			build ( build , l , mid , p << 1 ) ;
			build ( build , mid , r , p << 1 | 1 ) ;
			pull ( p ) ;
		};
		build ( build , 0 , n , 1 ) ;
	}
	void apply ( int p , const Tag& x ) {
   
		tree [ p ].apply ( x ) ;
		lazy [ p ].apply ( x ) ;
	}
	void push ( int p ) {
   
		apply ( p << 1 , lazy [ p ] ) ;
		apply ( p << 1 | 1 , lazy [ p ] );
		lazy [ p ] = Tag () ;
	}
	void pull ( int p ) {
   
		tree [ p ] = tree [ p << 1 ] + tree [ p << 1 | 1 ] ;
	}
	void range_Change ( int l , int r , const Tag& info ) {
   
		auto range_change = [ & ] ( auto&&range_change , int l , int r , int ls , int rs , int p , const Tag& info ) -> void {
   
			if ( rs <= l || r <= ls ) return ;
			if ( ls <= l && r <= rs ) {
   
				apply ( p , info );
				return ;
			}
			int mid = ( l + r ) >> 1 ;
			push ( p ) ;
			range_change