ZROI十一集训Day2
1.添
开局几何懵逼题.
内心:WOC,这什么毒瘤题?
冷静分析\(\times 1:\)好像答案不会超过\(3?\)
冷静分析\(\times 2:\)这好像是对的...
冷静分析\(\times 3:\)完蛋,举出反例了.
冷静分析\(\times 4:\)哦,着三线共点了,不合法.
冷静分析\(\times 5:\)好像,分类讨论就好了,分有几种斜率,特判两种斜率时是否只有两条直线即可
冷静分析\(\times 6:\)求斜率...精度问题怎么办...好像,用一个\(pair\)存最简分数形式就好了,用\(map\)叭
冷静分析\(\times 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.罐装
这题好难...是个贪心叭,看起来好像国王游戏.
推一推昂\(:\)
\[
\begin{array}{c}{\left(T-t-t_{i}\right) \cdot p_{i}+\left(T-t-t_{i}-t_{j}\right) \cdot p_{j} \geq\left(T-t-t_{j}\right) \cdot p_{j}+\left(T-t-t_{i}-t_{j}\right) \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}
\]
按照这个排序好了.(除法可能出现一些意想不到的问题,所以我们移项变为乘法排序.)噫好!我会了! 哎哎哎...这题怎么还带修啊...这咋做啊,让不让人活了啊.
先暴力交上去算了(事实上比赛当场就是交了暴力...)
冷静分析\(\times 1:\)修改好像只需要考虑贡献即可.
考虑一个元素的修改,我们可以等价为删除一个数,再插入一个数.
考虑删除的贡献:
显然,对该元素的前缀并没有影响.只需要考虑对后面的影响和对自身的影响.
首先,减去自己的贡献,我们发现它自己的贡献就是时间的前缀和\(\times\)自己的分数.
减去即可.
考虑对后缀的影响:
后缀的所有元素的贡献从\((T-sum_i)*p_i\)变成了\((T-sum_i+t_{pos})*p_i\).
其中\(pos\)是要删除的元素,\(i\)是当前考虑的元素.
所以,贡献是加上分数的后缀和\(\times\)当前时间.
插入一个元素的分析于此并无不同,只需贡献的符号反转即可.
冷静分析\(\times 2:\)这东西显然平衡树可以维护.
冷静分析\(\times 3:\)好像,离散化之后直接线段树也可做.
冷静分析\(\times 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\n" , 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\n" , ans ) ;
}
return 0 ;
}3.三千米
⑧会.写的\(\Theta(T\times length \times \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\n" , ans ) ;
}
return 0 ;
}