ZROI十一集训Day2

ZROI十一集训Day2

比赛链接

1.添

开局几何懵逼题.
内心:WOC,这什么毒瘤题?
冷静分析( imes 1:)好像答案不会超过(3?)
冷静分析( imes 2:)这好像是对的...
冷静分析( imes 3:)完蛋,举出反例了.
冷静分析( imes 4:)哦,这三线共点了,不合法.
冷静分析( imes 5:)好像,分类讨论就好了,分有几种斜率,特判两种斜率时是否只有两条直线即可
冷静分析( imes 6:)求斜率...精度问题怎么办...好像,用一个(pair)存最简分数形式就好了,用(map)叭
冷静分析( imes 7:)噫好!我(A)了.

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define one first
#define two second
#define rint read<int>
#define rll read<LL>
#define LL long long
#define pb push_back
#define db double
#define mid ( ( l + r ) >> 1 )

using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;
using std::map ;
using std::__gcd ;

template < class T >
    inline T read () {
        T x = 0 , f = 1 ; char ch = getchar () ;
        while ( ch < '0' || ch > '9' ) {
            if ( ch == '-' ) f = - 1 ;
            ch = getchar () ;
        }
        while ( ch >= '0' && ch <= '9' ) {
            x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
            ch = getchar () ;
        }
        return f * x ;
    }

const int N = 1e6 + 100 ;

struct Poi {
    int x , y ;
    friend Poi operator + (Poi a , Poi b) { return (Poi){ a.x + b.x , a.y + b.y } ; }
    friend Poi operator - (Poi a , Poi b) { return (Poi){ a.x - b.x , a.y - b.y } ; }
} ;

struct seg { Poi a , b , vec ; } p[N] ;

map < pii , bool > mk ;
int T , n , cnt , tot ;

int main () {
    T = rint () ;
    while ( T -- ) {
        n = rint () ; cnt = 0 ; tot = 0 ; mk.clear () ;
        rep ( i , 1 , n ) {
            Poi u , v , vec ;
            u.x = rint () ; u.y = rint () ;
            v.x = rint () ; v.y = rint () ;
            int A = u.y - v.y , B =  u.x - v.x ;
            vec = v - u ; int d = __gcd ( A , B ) ;
            A /= d ; B /= d ;
            if ( mk[{A,B}] ) continue ;
            mk[{A,B}] = true ;
            p[++cnt] = (seg){ u , v , vec } ;
        }
        if ( cnt <= 1 ) puts ("0") ;
        else if ( cnt == 2 && n > 2 ) puts ("2") ;
        else if ( cnt == 2 && n <= 2 ) puts ("1") ;
        else puts ("3") ;
    }
    return 0 ;
}

2.罐装

这题好难...是个贪心叭,看起来好像国王游戏.
推一推昂(:)

[egin{array}{c}{left(T-t-t_{i} ight) cdot p_{i}+left(T-t-t_{i}-t_{j} ight) cdot p_{j} geqleft(T-t-t_{j} ight) cdot p_{j}+left(T-t-t_{i}-t_{j} ight) cdot p_{i}} \ {t_{j} p_{i} geq t_{i} p_{j}} \ {cfrac{p_{i}}{t_{i}} geq cfrac{p_{j}}{t_{j}}}end{array} ]

按照这个排序好了.(除法可能出现一些意想不到的问题,所以我们移项变为乘法排序.)
噫好!我会了! 哎哎哎...这题怎么还带修啊...这咋做啊,让不让人活了啊.
先暴力交上去算了(事实上比赛当场就是交了暴力...)

冷静分析( imes 1:)修改好像只需要考虑贡献即可.
考虑一个元素的修改,我们可以等价为删除一个数,再插入一个数.
考虑删除的贡献:
显然,对该元素的前缀并没有影响.只需要考虑对后面的影响和对自身的影响.
首先,减去自己的贡献,我们发现它自己的贡献就是时间的前缀和( imes)自己的分数.
减去即可.
考虑对后缀的影响:
后缀的所有元素的贡献从((T-sum_i)*p_i)变成了((T-sum_i+t_{pos})*p_i).
其中(pos)是要删除的元素,(i)是当前考虑的元素.
所以,贡献是加上分数的后缀和( imes)当前时间.

插入一个元素的分析于此并无不同,只需贡献的符号反转即可.

冷静分析( imes 2:)这东西显然平衡树可以维护.
冷静分析( imes 3:)好像,离散化之后直接线段树也可做.
冷静分析( imes 4:)分析个毛,线段树莽一棵.

[2000 : years : later ]

噫好,我(A)了.
(Code:)

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define one first
#define two second
#define rint read<int>
#define int long long
#define pb push_back
#define db double
#define mid ( ( l + r ) >> 1 )

using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;

template < class T >
    inline T read () {
        T x = 0 , f = 1 ; char ch = getchar () ;
        while ( ch < '0' || ch > '9' ) {
            if ( ch == '-' ) f = - 1 ;
            ch = getchar () ;
        }
       while ( ch >= '0' && ch <= '9' ) {
            x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
            ch = getchar () ;
       }
       return f * x ;
}

const int N = 1e5 + 100 ;
const pii e = { 0ll , 0ll } ;
struct prob { int p , t , pos ; } v[N] , id[N<<1] , q[N] ;
struct seg { pii data ; int ls , rs , left , right ; } t[N<<2] ;
int n , m , T , pos[N<<1] , cnt = 1 , tot , ans ;

inline pii operator + (pii a , pii b) { return { a.one + b.one , a.two + b.two } ; }

inline void pushup (int rt) { t[rt].data = t[t[rt].ls].data + t[t[rt].rs].data ; return ; }

inline void build (int rt , int l , int r) {
    t[rt].left = l ; t[rt].right = r ;
    if ( l == r ) { t[rt].data = e ; return ; }
    t[rt].ls = ++ cnt ; build ( t[rt].ls , l , mid ) ;
    t[rt].rs = ++ cnt ; build ( t[rt].rs , mid + 1 , r ) ;
    pushup ( rt ) ; return ;
}

inline void insert (int rt , int pos , pii key) {
    int l = t[rt].left , r = t[rt].right ;
    if ( l == r ) { t[rt].data = key ; return ; }
    if ( pos <= mid ) insert ( t[rt].ls , pos , key ) ;
    else insert ( t[rt].rs , pos , key ) ;
    pushup ( rt ) ; return ;
}

inline void remove (int rt , int pos) {
    int l = t[rt].left , r = t[rt].right ;
    if ( l == r ) { t[rt].data = e ; return ; }
    if ( pos <= mid ) remove ( t[rt].ls , pos ) ;
    else remove ( t[rt].rs , pos ) ;
    pushup ( rt ) ; return ;
}

inline pii query (int rt , int ll , int rr) {
    int l = t[rt].left , r = t[rt].right ;
    if ( ll == l && r == rr ) return t[rt].data ;
    if ( rr <= mid ) return query ( t[rt].ls , ll , rr ) ;
    else if ( ll > mid ) return query ( t[rt].rs , ll , rr ) ;
    else return query ( t[rt].ls , ll , mid ) + query ( t[rt].rs , mid + 1 , rr ) ;
}

inline bool cmp (prob a , prob b) { return a.p * b.t > a.t * b.p ; }

signed main (int argc , char * argv[]) {
    n = rint () ; m = rint () ; T = rint () ;
    rep ( i , 1 , n ) { 
        v[i].p = rint () ; v[i].t = rint () ;
        v[i].pos = i ; id[++tot] = v[i] ;
    }

    rep ( i , 1 , m ) {
        q[i].pos = rint () ; q[i].p = rint () ; q[i].t = rint () ; ++ tot ;
        id[tot] = (prob){ q[i].p , q[i].t , tot } ;
    }

    sort ( id + 1 , id + tot + 1 , cmp ) ; rep ( i , 1 , tot ) pos[id[i].pos] = i ; build ( 1 , 1 , tot ) ;

    rep ( i , 1 , n ) insert ( 1 , pos[i] , { v[i].p , v[i].t } ) ; sort ( v + 1 , v + n + 1 , cmp ) ;

    int now = 0 ; rep ( i , 1 , n ) { now += v[i].t ; ans += ( T - now ) * v[i].p ; } printf ("%lld
" , ans ) ;

    rep ( i , 1 , m ) {
        int cur = pos[q[i].pos] , tmp = query ( 1 , 1 , cur ).two ; ans -= id[cur].p * ( T - tmp ) ;
        if ( cur + 1 <= tot ) tmp = query ( 1 , cur + 1 , tot ).one ; else tmp = 0 ;
        ans += id[cur].t * tmp ; remove ( 1 , cur ) ;

        cur = pos[n+i] ; insert ( 1 , cur , { q[i].p , q[i].t } ) ;
        tmp = query ( 1 , 1 , cur ).two ; ans += q[i].p * ( T - tmp ) ;
        if ( cur + 1 <= tot ) tmp = query ( 1 , cur + 1 , tot ).one ; else tmp = 0 ;
        ans -= q[i].t * tmp ; pos[q[i].pos] = cur ; printf ("%lld
" , ans ) ;
    }
    return 0 ;
}

3.三千米

⑧会.写的(Theta(T imes length imes log_2{max_{value}})).
过了(30pts).
(Code:)

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define one first
#define two second
#define rint read<int>
#define rll read<LL>
#define int long long
#define pb push_back
#define db double
#define mid ( ( l + r ) >> 1 )

using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;

template < class T >
    inline T read () {
        T x = 0 , f = 1 ; char ch = getchar () ;
        while ( ch < '0' || ch > '9' ) {
            if ( ch == '-' ) f = - 1 ;
            ch = getchar () ;
        }
        while ( ch >= '0' && ch <= '9' ) {
            x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
            ch = getchar () ;
        }
        return f * x ;
    }

int T , L , R , l , r ;

inline bool check (int x) {
    int res = 1 ;
    while ( x ) {
        res *= ( x % 10 ) ;
        x /= 10 ;
    }
    return res >= l && res <= r ;
}

signed main() {
    T = rint () ;
    while ( T -- ) {
        L = rint () ; R = rint () ;
        l = rint () ; r = rint () ; int ans = 0 ;
        rep ( i , L , R ) if ( check ( i ) ) ++ ans ;
        printf ("%lld
" , ans ) ;
    }
    return 0 ;
}