传送门:【codeforces】Codeforces Round #280 (Div. 2)
找到最大的i使得1+2+3+……+i小于等于n,并且输出i。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; typedef long long LL ; #define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i ) #define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i ) #define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i ) #define clr( a , x ) memset ( a , x , sizeof a ) #define ls ( o << 1 ) #define rs ( o << 1 | 1 ) #define lson ls , l , m #define rson rs , m + 1 , r #define root 1 , 1 , cnt #define mid ( ( l + r ) >> 1 ) const int MAXN = 100005 ; int n ; void solve () { int cnt = 0 , i = 1 , sum = 1 ; while ( n >= sum ) { ++ cnt ; n -= sum ; ++ i ; sum += i ; } printf ( "%d\n" , cnt ) ;; } int main () { while ( ~scanf ( "%d" , &n ) ) solve () ; return 0 ; }
排序,然后从两点间距离除以2,第一盏灯到开头,最后一盏灯到结尾的距离中取最大
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; typedef long long LL ; #define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i ) #define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i ) #define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i ) #define clr( a , x ) memset ( a , x , sizeof a ) #define ls ( o << 1 ) #define rs ( o << 1 | 1 ) #define lson ls , l , m #define rson rs , m + 1 , r #define root 1 , 1 , cnt #define mid ( ( l + r ) >> 1 ) const int MAXN = 100005 ; const double eps = 1e-10 ; int n , m ; int a[MAXN] ; int dcmp ( double x ) { return ( x > eps ) - ( x < -eps ) ; } void solve () { For ( i , 1 , n ) scanf ( "%d" , &a[i] ) ; sort ( a + 1 , a + n + 1 ) ; double maxv = max ( a[1] , m - a[n] ) ; rep ( i , 1 , n ) maxv = max ( maxv , ( a[i + 1] - a[i] ) / 2.0 ) ; printf ( "%.10f\n" , maxv ) ; } int main () { while ( ~scanf ( "%d%d" , &n , &m ) ) solve () ; return 0 ; }
排序,然后模拟。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; typedef long long LL ; #define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i ) #define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i ) #define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i ) #define clr( a , x ) memset ( a , x , sizeof a ) #define ls ( o << 1 ) #define rs ( o << 1 | 1 ) #define lson ls , l , m #define rson rs , m + 1 , r #define root 1 , 1 , cnt #define mid ( ( l + r ) >> 1 ) const int MAXN = 100005 ; const double eps = 1e-10 ; struct Node { LL a , b ; bool operator < ( const Node& t ) const { return b < t.b ; } } a[MAXN] ; LL n , r , avg ; int dcmp ( double x ) { return ( x > eps ) - ( x < -eps ) ; } void solve () { LL sum = 0 ; LL ans = 0 ; LL tot = n * avg ; For ( i , 1 , n ) { scanf ( "%I64d%I64d" , &a[i].a , &a[i].b ) ; sum += a[i].a ; } if ( sum >= tot ) { printf ( "0\n" ) ; return ; } sort ( a + 1 , a + n + 1 ) ; LL need = n * avg - sum ; For ( i , 1 , n ) { if ( need <= r - a[i].a ) { ans += need * a[i].b ; printf ( "%I64d\n" , ans ) ; return ; } need -= r - a[i].a ; ans += ( r - a[i].a ) * a[i].b ; } } int main () { while ( ~scanf ( "%I64d%I64d%I64d" , &n , &r , &avg ) ) solve () ; return 0 ; }
1/x,1/y可等价为玩家一每y秒造成一点伤害,玩家二每x秒造成一点伤害。
然后二分时间轴,可以得到恰好打死小怪所需的时间,且这个时间必定是能整除x或y的。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; typedef long long LL ; #define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i ) #define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i ) #define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i ) #define clr( a , x ) memset ( a , x , sizeof a ) #define ls ( o << 1 ) #define rs ( o << 1 | 1 ) #define lson l , m #define rson m + 1 , r #define root 1 , 1 , cnt #define mid ( ( l + r ) >> 1 ) int n , x , y ; void solve () { int a ; For ( i , 1 , n ) { scanf ( "%d" , &a ) ; LL l = 1 , r = 1e15 ; while ( l < r ) { LL m = mid ; LL atk = m / y + m / x ; if ( atk >= a ) r = m ; else l = m + 1 ; } if ( l % x == 0 && l % y == 0 ) printf ( "Both\n" ) ; else if ( l % x == 0 ) printf ( "Vova\n" ) ; else printf ( "Vanya\n" ) ; } } int main () { while ( ~scanf ( "%d%d%d" , &n , &x , &y ) ) solve () ; return 0 ; }
由于gcd(dx,n)=gcd(dy,n)= 1,所以从(0,0)~(0,n-1)中选择一个起点一定能走出互不相交(这里的不相交只的是点不重复使用)的路径,且路径长度一定是n,且x轴和y轴存在一一映射的关系。
当我们求得其中一条路径的时候,我们可以用这条路径来推出其他的路径。
为了方便起见,我们选择模拟的路径为从(0,0)点出发的,设f[x]=y为x在y轴上的映射(也即坐标(x,y)),则f[i*dx%n]=i*dy%n就是(0,0)点出发会遇到的所有点。
那么(0,k)出发的路径为f[x]+k=y+k=y',即k=(y'-f[x]+n)%n。那么所有点我们都可以O(1)的分到它属于的路径中。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; typedef long long LL ; #define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i ) #define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i ) #define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i ) #define clr( a , x ) memset ( a , x , sizeof a ) #define ls ( o << 1 ) #define rs ( o << 1 | 1 ) #define lson l , m #define rson m + 1 , r #define root 1 , 1 , cnt #define mid ( ( l + r ) >> 1 ) const int MAXN = 1000005 ; int f[MAXN] ; int n , m , dx , dy ; int num[MAXN] ; void solve () { int x = 0 , y = 0 , ans , maxv = 0 ; clr ( num , 0 ) ; For ( i , 0 , n ) { f[x] = y ; x = ( x + dx ) % n ; y = ( y + dy ) % n ; } For ( i , 1 , m ) { scanf ( "%d%d" , &x , &y ) ; ++ num[( y - f[x] + n ) % n] ; } rep ( i , 0 , n ) { if ( num[i] > maxv ) { maxv = num[i] ; ans = i ; } } printf ( "%d %d\n" , 0 , ans ) ; } int main () { while ( ~scanf ( "%d%d%d%d" , &n , &m , &dx , &dy ) ) solve () ; return 0 ; }