T1 Attack

1 记录

考场上时懵的，这是个啥？为什么没有部分分？

弃了

2 Solution

结果下来一讨论， T1 时间限制 10s ，这是个啥？

发现自己错过了 A 一道题的机会，难受

言归正传

正解是什么划分数之类的神仙玩意儿，这肯定时看不懂的

但是原题时间限制是 1s ……

我感受到组题人满满的恶意善意

所以直接 $ O(n^2) $ 乱搞时可以的

实际上最朴素的算法是 $O(nm\log(n))$ 的，但是过不了…

随便乱搞把求第 $k$ 大降到 $O(n)$ 就行了

3 Source

#include <cstdio>

#include <algorithm>

const int N = 61000;

struct node {
    int x, y, k, id;    
} a[N];

int n, m;
int b[N];
char op[20];

bool cmp( node a, node b ) { return a.k < b.k; }

int main() {
#ifdef woshiluo
    freopen( "gmoj.2865.in", "r", stdin );
    freopen( "gmoj.2865.out", "w", stdout );
#endif
    scanf( "%d%d", &n, &m );
    for( int i = 1; i <= n; i++ ) {
        scanf( "%d%d%d", &a[i].x, &a[i].y, &a[i].k );
        a[i].id = i;
    }

    std::sort( a + 1, a + n + 1, cmp );

    for( int i = 1; i <= n; i++ ) 
        b[ a[i].id ] = i;

    while( m -- ) {
        scanf( "%s", op );
        if( op[0] == 'S' ) {
            int x, y;
            scanf( "%d%d", &x, &y );
            x ++, y ++;
            std::swap( a[ b[x] ].x, a[ b[y] ].x );
            std::swap( a[ b[x] ].y, a[ b[y] ].y );
            std::swap( a[ b[x] ].id, a[ b[y] ].id );
            std::swap( b[x], b[y] );
        }
        else {
            int x0, y0, x1, y1, k, cnt = 0;
            bool flag = false;
            scanf( "%d%d%d%d%d", &x0, &y0, &x1, &y1, &k );
            if( x0 > x1 )
                std::swap( x0, x1 );
            if( y0 > y1 )
                std::swap( y0, y1 );
            for( int i = 1; i <= n; i++ ) {
                if( a[i].x >= x0 && a[i].x <= x1 && a[i].y >= y0 && a[i].y <= y1 ) {
                    cnt ++;
                    if( cnt == k ) {
                        printf( "%d", a[i].k ); 
                        flag = true;
                        break;
                    }
                }
            }   

            if( !flag ) 
                printf( "It doesn't exist." );
            printf( "\n" );
        }
    }
}

std::swap 真好用

T2 Contra

1 记录

本来是在推 DP 的

但是推锅了，便直接 DFS 跑路，结果二分还被卡了……

又忘记判 0 了

结果只有 10 分

不过这也是我第一次期望类型的题目有分了……

2 Solution

卡精度的毒瘤题目

前置知识: 期望 DP 矩阵乘法

• $ 20\% $ 二分套 DFS $ O(2^n \times log_2(10^9)) $

这个真的不想说……

建议 $ eqs = 10^{-9} $

• $100\%$ 二分套矩阵优化 DP

很容易想到

设

$f_{i,j,k} $ 表示在第 $i$ 关，连击 $j$ 次，有 $k$ 条命的期望

$g_{i,j,k} $ 表示在第 $i$ 关，连击 $j$ 次，有 $k$ 条命的概率

但是因为是两个 DP 转移，纵使是矩阵乘法也救不了你

考虑在状态上优化，易得没有必要计算期望，计算概率即可，则可得到状态转移方程
$$
\begin{align}
f_{i + 1, \min( j + 1, r ) ,\min( k + 1, q ) } & += f_{i,j,k} \times p\\
f_{i + 1, 0, k – 1 } & += f_{i,j,k} \times ( 1 – p ) \\
ans & += f_{i,j,k} \times ( j + 1 ) \times p
\end{align}
$$

构建矩阵

很明显状态是 $(i,j)$ 表示还有 $i$ 条命，连击 $j$ 次

但是有无用状态，若 $i \neq q$ ，则显然 $j \leq i – 1$

即应当对 $(i, j)$ Hash

经过这个优化可以确保举证单边长度在 30 左右

矩阵中 $(i,j)$ 表示 Hash 后的 i，转移到 Hash 后的 $j$ 的概率

自己乘自己即可

3 Source

#include <cstdio>
#include <cstring>

inline double abs( double a ) { return a < 0? ( 0.0 - a ): a; }
inline int Min( int a, int b ) { return a < b? a: b; }
inline int Max( int a, int b ) { return a > b? a: b; }

const double eqs = 0.000000001;

int n, r, q, s, cnt;
int pos[110][110];

// double dfs( int now, int combo, int life, double p ) {
//     if( life == 0 || now == n ) 
//         return 0.0;
//     
//     return p * ( dfs( now + 1, combo + 1, Min( life + 1, q ), p ) + Min( combo + 1, r ) ) + ( 1.0 - p ) * dfs( now + 1, 0, life - 1, p );
// }

struct matrix {
    double mat[110][110];
    matrix( double now = 0.0 ) {
        memset( mat, 0, sizeof(mat) );
        if( now != 0.0 ) {
            for( int i = 0; i < 100; i++ )
                mat[i][i] = now;
        }
    }
    matrix operator* ( matrix b ) {
        matrix res;
        for( int i = 1; i <= cnt; i++ ) {
            for( int j = 1; j <= cnt; j++ ) {
                for( int k = 1; k <= cnt; k++ ) {
                    res[i][j] += mat[i][k] * b[k][j];
                }
            }
        }
        return res;
    }
    double* operator[] ( int now ) { return mat[now]; }
};

matrix ksm( matrix a, int p ) {
    matrix res(1);
    while(p) {
        if( p & 1 ) 
            res = res * a;
        a = a * a;
        p >>= 1;
    }
    return res;
}

bool check( double p ) {
    matrix a;

    a[1][1] = 1; 
    for( int i = 1; i <= q; i++ ) {
        int tmp = ( i == q )? r: Min( i - 1, r );
        for( int j = 0; j <= Max( 0, tmp ); j++ ) {
            int x = pos[i][j], y = pos[ i - 1 ][0], z = pos[ Min( i + 1, q ) ][ Min( j + 1, r ) ];
            if( i > 1 ) 
                a[x][y] = ( 1.0 - p );
            a[x][z] = p;
            a[x][1] = p * (double)Min( j + 1, r );
        }
    }

//    printf("%lf\n", ksm( a, n )[ pos[q][0] ][1]);
    return ( ksm( a, n )[ pos[q][0] ][1] ) > s;
}

int main() {
#ifdef woshiluo
    freopen( "gmoj.2867.in", "r", stdin );
    freopen( "gmoj.2867.out", "w", stdout );
#endif 
    scanf( "%d%d%d%d", &n, &r, &q, &s );

    for( int i = 0; i <= q; i++ ) {
        int tmp = ( i == q )? r: Min( i - 1, r );
        for( int j = 0; j <= Max(0, tmp); j++ ) {
            pos[i][j] = ++ cnt;
        }
    }

    if ( !check(1) ) {
        printf("Impossible.");
        return 0;
    }
    double left = 0, rig = 1, res = 10;
    while( abs( rig - left ) >= eqs ) {
        double mid = ( left + rig ) / 2;
        if( check(mid) ) 
            res = res < mid? res: mid, rig = mid;
        else
            left = mid;
    }

    printf( "%.6lf", res );
}

T3 Bomb

1 记录

考场上三点之间两两曼哈顿距离之和实际上就是框住这三个点的最小长方形的周长了

但是往下想没想到…

2 Solution

最大值显然可以贪心，有关贪心的证明请自行搜索不再赘述

最小值有很多做法，参见 /bomb/Bomb解题报告.pdf

这里讲述分治做法

很明显分治到 $rig – left \leq 12$ 的时候是可以直接 $O(n^3)$ 瞎搞的，在往上合并时候，确认坐标轴之差的绝对值不大于已知结果即可

这里为了防止被卡，将 x, y 坐标交换了，并加上了随机化

3 Source

#include <cstdio>

#include <algorithm>

inline int Aabs( int a ) { return a < 0? ( 0 - a ): a; }
inline int Min( int a, int b ) { return a < b? a: b; }
inline int Max( int a, int b ) { return a > b? a: b; }
inline int Max_3( int a, int b, int c ) { return Max( a, Max( b, c ) ); }
inline int Min_3( int a, int b, int c ) { return Min( a, Min( b, c ) ); }

const int N = 110000;
const int INF = 0x3f3f3f3f;

struct node {
    int x, y;
    bool operator< ( const node &b )const {
        if( x == b.x )
            return this -> y < b.y;
        return this -> x < b.x;
    }
} a[N], tmp[N];

bool cmp( node a, node b ) {
    if( a.y == b.y )
        return a.x < b.x;
    return a.y < b.y;
}

int n, ans = INF;
int minx, maxx, miny, maxy, mins, maxs, _mins, _maxs;

void solve( int left, int rig ) {
    if( rig - left <= 12 ) {
        for( int i = left; i <= rig; i++ ) {
            for( int j = i + 1; j <= rig; j++ ) {
                for( int k = j + 1; k <= rig; k++ ) {
                    ans = Min( ans, Max_3( a[i].x, a[j].x, a[k].x ) - Min_3( a[i].x, a[j].x, a[k].x ) +
                            Max_3( a[i].y, a[j].y, a[k].y ) - Min_3( a[i].y, a[j].y, a[k].y ) );
                }
            }
        }
        return ;
    }
    int mid = ( rig - left <= 100? ( left + rig ) >> 1: left + rand() % ( rig - left + 1 ) );
    std::nth_element( a + left + 1, a + mid + 1, a + rig + 1);

    if( rand() & 1 ) 
        { solve( left, mid ); solve( mid + 1, rig ); }
    else 
        { solve( mid + 1, rig ); solve( left, mid ); }

    int mid_x = a[mid].x, pos = 0;

    for( int i = left; i <= rig; i++ ) {
        if( Aabs( a[i].x - mid_x ) < ans ) 
            tmp[ ++ pos ] = a[i];
    }
    std::sort( tmp + 1, tmp + pos + 1, cmp );

    int p = 1;
    for( int i = 3; i <= pos; i++ ) {
        while( Aabs( tmp[p].y - tmp[i].y ) >= ans ) 
            p ++;
        for( int j = p; j < i; j++ ) {
            for( int k = j + 1 ; k < i; k++ ) {
                ans = Min( ans, Max_3( tmp[i].x, tmp[j].x, tmp[k].x ) - Min_3( tmp[i].x, tmp[j].x, tmp[k].x ) +
                        Max_3( tmp[i].y, tmp[j].y, tmp[k].y ) - Min_3( tmp[i].y, tmp[j].y, tmp[k].y ) );
            }
        }
    }
}

int main() {
#ifdef woshiluo
    freopen( "gmoj.2866.in", "r", stdin );
//    freopen( "gmoj.2866.out", "w", stdout );
#endif
    srand( 125545 );
    scanf( "%d", &n );
    minx = miny = mins = _mins = INF;
    maxx = maxy = maxs = _maxs = -INF;
    for( int i = 1; i <= n; i++ ) {
        int x, y;
        scanf( "%d%d", &x, &y );
        int tp = x; x = y; y = tp;
        minx = Min( minx, x ); maxx = Max( maxx, x );
        miny = Min( miny, y ); maxy = Max( maxy, y );
        mins = Min( mins, x + y ); maxs = Max( maxs, x + y );
        _mins = Min( _mins, x - y ); _maxs = Max( _maxs, x - y );
        a[i] = (node) { x, y };
    }
    int max = 0;
    max = Max( max, maxs - minx - miny );
    max = Max( max, maxx + maxy - mins );
    max = Max( max, _maxs - minx + maxy );
    max = Max( max, maxx - miny - _mins );

    solve( 1, n );

    printf( "%d\n%d\n", max << 1, ans << 1 );
}