小白月赛99FG

huweixiang / 2024-08-27 / 原文

F-自爆机器人_牛客小白月赛99 (nowcoder.com)

假设从个点中的某个点$\color{#50F}{a_k}$设立墙，将机器人往左弹，中间过程不考虑，其一定会回到$\color{#50F}{m}$点，称其为$\color{#50F}{k}$点的一个往返，其距离为 $\color{#50F}{a_k - a_{i} , i \in [ 1 , k -1]}$ , 每个点都可以有多个往返，现在考虑中间的过程不难发现中间的过程也是又很多个往返组成，由于往返的位移为零，题目要求位移为$\color{#50F}{n}$所以还要加上一个向右的大小为$\color{#50F}{n}$的位移，所以总共的伤害为$\color{#50F}{min(\Sigma_{i = 1}^{k}f(a_i) + n, t) , f(a_i) 为a_i往返距离和}$

$\color{#50F}{k}$的每个往返必定包含 $\color{#50F}{a_k - a_{k-1}}$ , 所以每个往返可以只统计$\color{#50F}{a_k - a_{k-1}}$，其余距离留计算其他往返时统计，列如$\color{#50F}{a_5 - a_{1},可以拆成 a_5 - a_4 , a_4 - a_3 , a_3 - a_2 , a_2 - a_1 } 将5的往返拆成了 5 ， 4 ， 3 ， 2 ，1 的距离为a_x - a_{x-1}往返$

很容易就能想到用完全背包解决，但我看$\color{#50F}{m}$的范围是$\color{#50F}{[1 , 2*1e^5]}$ 算得复杂度为$\color{#50F}{m* n}$迟迟不敢写，后来看题解发现$\color{#50F}{a_k - a_{k-1}}$两两不相同也最多只有$\color{#50F}{\sqrt[2]{n}}$种可能，所以复杂度为$\color{#50F}{\sqrt[2]{n}* m}$

#include "bits/stdc++.h"
using namespace std ;
#define int long long 
#define pll pair<int , int>
const int N = 1e6 + 9 ;
int n , m , t ;
void solve( ) {
    cin >> n >> m >> t ;
    vector< int > c , d ;
    vector< bool > vis( t + 9) ;
    vis[0] = 1 ;
    for( int i = 1 ; i <= m ; i ++ ) {
        int x ;
        cin >> x ;
        c.push_back(x) ;
    }
    sort(c.begin() , c.end()) ;
    for( int i = 1 ; i < m ;i ++ ) {
        d.push_back(c[i] - c[i-1]) ;
    }
    sort(d.begin() , d.end()) ;
    d.erase(unique(d.begin() , d.end()) ,d.end()); 
    for( auto x : d ) {
        for( int i = x ; i <= t ; i ++ ) {
            vis[i] = max( vis[i - x] , vis[i]) ;
        }
    }
    int ans = 0 ;
    for( int i = t ; i >= 0 ; i -- ) {
        if( vis[i] && (i *2 + n <= t )) {
            ans = i*2 + n ;
            break;
        }
    }
    cout << ans << '\n' ;
}

signed main( ) {
    ios::sync_with_stdio(false) ,cin.tie(0) ,cout.tie(0) ;
    int _ = 1 ;
    cin >> _ ;
    while( _ -- ) {
        solve( ) ;
    }
}

G-大鱼吃小鱼_牛客小白月赛99 (nowcoder.com)

离散化，统计每个时间鱼种类，用递推的思想，假设当前时间为 i ，并且统计好了鱼的种类，计算时间为i +1时鱼的种类时只要减去右端点为l的鱼，加上左端点为l的鱼，即可

#include "bits/stdc++.h"
using namespace std ;
#define lbt(x) x & -x 
#define int long long 
#define pll pair<int , int>
const int N = 1e6 + 9 ;
int n , w , su[N] ;
struct fish{
    int l , r , a ;
}x[N] ;
void add( int i  ,int r ) {
    while( i < n*2 ) su[i] += r , i += lbt(i) ;
}
int sum( int i ) {
    int res = 0 ;
    while( i ) res += su[i] , i -= lbt(i) ;
    return res ;
}
void solve( ) {
    vector<int>c ;// 离散化 质量
    vector<int>s ;//离散化 时间点
    cin >> n >> w ;
    memset( su , 0 , sizeof(int)*(n*2) ) ;
    vector<vector<int>> r( n*3) ; 
    vector<vector<int>> l( n*3) ; 
    for( int i = 1 ; i <= n ; i ++ ){
        cin >> x[i].l >> x[i].r >> x[i].a , c.push_back(x[i].a);
        s.push_back(x[i].l) ;
        s.push_back(x[i].r) ;
    }
    sort( c.begin() , c.end() ) ;
    c.erase(unique(c.begin() , c.end()) , c.end()) ;
    sort( s.begin() , s.end() ) ;
    s.erase(unique(s.begin() , s.end()) , s.end()) ;
    auto find = [](vector<int> &c , int x ) -> int {
        return lower_bound(c.begin(), c.end() , x ) - c.begin() + 1;
    } ;
    for( int i = 1 ; i <= n ;i ++ ) {
        x[i].l = find( s , x[i].l ) ;
        x[i].r = find( s , x[i].r ) ;
        r[x[i].r].push_back(x[i].a) ;
        l[x[i].l].push_back(x[i].a) ;
    }
    set<int , greater<int> >f ;
    map<int , int > g ;
    int ans = w ;
    for( int i = 1 ; i <= n*2 ;i ++ ) {
        for( auto x : l[i] ) {
            f.insert(x) ;
            g[x] ++ ;
            add( find( c, x) , x ) ;
        }
        for( auto x : r[i] ) {
            g[x] -- ;
            if(g[x] == 0) {
                f.erase(x);
                g.erase(x);
            }
            add( find( c, x) , -x ) ;
        }
        int v = w ;
        while( true ) {
            if(f.lower_bound(v) == f.end()) break;
            int x = find( c , *f.lower_bound(v));
            if( v == sum(x) + w ) break; 
            v = sum(x) + w;
        }
        ans = max( ans , v ) ;
    }
    cout << ans << '\n' ;
}

signed main( ) {
    ios::sync_with_stdio(false) ,cin.tie(0) ,cout.tie(0) ;
    int _ = 1 ;
    cin >> _ ;
    while( _ -- ) {
        solve( ) ;
    }
}