分类
OI

中山纪念中学 Day 21 2019.08.21 解题报告 & 题解

T1 数字 Number

1 记录

考场上疯狂肝这道题目,结果少个特判

2 Solution

很明显,$n$ 只有三种情况

  1. $n$ 就是结尾
  2. 中间有一段是一个数字,这个情况 $O(\log^3(n))$ 枚举即可
  3. 中间切一刀,左边是一个不完整的数字,右边也是一个不完整的数字,枚举中间即可

所以直接暴力即可

所以这是一道毒瘤模拟题目

3 Source

#include <cstdio>
#include <cmath>

inline int _ws( long long now ) { 
    if( now == 0 ) 
        return 0; 
    return ( (int)std::log10(now) ) + 1; 
}

int t;
long long n, ans;
long long pow_10[20] = { 1, 1 };

long long check( int st, int ed, long long val ) {
    long long res = val;
    long long ed_val, tmp = val - 1;
    while( st && tmp >= 0 ) {
        if( st < _ws( tmp ) ) { 
            tmp %= pow_10[st];

            if( _ws( tmp ) < st )
                return false;
        }
        res = ( tmp * pow_10[ _ws(res) ] ) + res;
        st -= _ws( tmp );
        tmp --;
    }   

    if( st )
        return false;

    tmp = val + 1;
    while( ed && tmp >= 0 ) {
        if( ed < _ws( tmp ) ) {
            ed_val = tmp;
            tmp /= pow_10[ _ws( tmp ) - ed ];
        }
        else 
            ed_val = tmp;
        if( tmp <= 0 )
            return false;
        res = ( res * pow_10[ _ws( tmp ) ] ) + tmp;
        ed -= _ws( tmp );
        tmp ++;
    }

    if( res == n ) 
        return ed_val;
    else 
        return false;
}

int main() {
    freopen( "number.in", "r", stdin );
    freopen( "number.out", "w", stdout );
    scanf( "%d", &t );
    for( int i = 1; i <= 18; i ++ )
        pow_10[i] = pow_10[ i - 1 ] * 10LL;

    while( t -- )  {
        scanf( "%lld", &n );
        ans = n;
        int ws = _ws( n );

        for( int st = 0; st <= ws; st ++ ) {
            for( int len = 1; len <= ws - st; len ++ ) {
                if( long long tmp = check( st, ws - st - len, ( n % pow_10[ ws - st ] ) / pow_10[ ws - st - len ] ) ) {
                    ans = ans < tmp? ans: tmp;
                }
            }
        }

        for( int ed_p = 1; ed_p < ws; ed_p ++ ) {
            long long fir = n / pow_10[ ws - ed_p ], sec = n % pow_10[ ws - ed_p ], res;
            if( _ws( sec ) < ws - ed_p )
                continue;
            fir ++;
            if( _ws( fir ) > ed_p ) {
                fir %= pow_10[ ed_p ];
            }
            res = ( sec * pow_10[ ed_p ] ) + fir;
            for( int pin = 1; pin <= ed_p; pin ++ ) {
                sec /= 10;  
                if( sec == 0 ) 
                    break;
                long long tmp = ( sec * pow_10[ ed_p ] ) + fir;
                if( ( ( ( tmp - 1 ) % pow_10[ ed_p ] ) * pow_10[ ws - ed_p ] + tmp / pow_10[ _ws(tmp) - ( ws - ed_p ) ] ) == n ) 
                    res = res < tmp? res: tmp;
            }
            ans = ans < res? ans: res;
        }

        printf( "%lld\n", ans );
    }

    fclose( stdin );
    fclose( stdout );
}

T2 Maja

1 记录

全去肝 T1 去了

2 Solution

很容易得到,路径一定是在某一个地方开始,朝另一个点左右横跳

并且左右横跳的的距离不会超过 2

即设 $f[k][i][j]$ 表示 $k$ 步 走到 $(i,j)$ 的最大结果

在做到 $f[j][i][j]$ 的时候顺便维护全局最大值即可

$k$ 最大是 $\min( \frac{k}{2}, n \times m)$

滚动 $k$ 即可

3 Source

#include <cstdio>
#include <cstring>

#include <algorithm>

template <typename T> T Max( T a, T b ) { return a > b? a: b; }
template <typename T> T Min( T a, T b ) { return a < b? a: b; }

const int N = 110;

int n, m, A, B, k, a[N][N], max[N][N];
long long f[2][N][N], ans;
int dx[4] = { 0, 0, +1, -1 };
int dy[4] = { +1, -1, 0, 0 };

int main() {
    freopen( "maja.in", "r", stdin );
    freopen( "maja.out", "w", stdout );
    scanf( "%d%d%d%d%d", &n, &m, &A, &B, &k );
    for( int i = 1; i <= n; i ++ ) {
        for( int j = 1; j <= m; j ++ ) {
            scanf( "%d", &a[i][j] );
        }
    }

    for( int i = 1; i <= n; i ++ ) {
        for( int j = 1; j <= m; j ++ ) {
            int res = 0;
            if( i != n )
                res = Max( res, a[ i + 1 ][j] );
            if( i != 1 ) 
                res = Max( res, a[ i - 1 ][j] );
            if( j != m ) 
                res = Max( res, a[i][ j + 1 ] );
            if( j != 1 ) 
                res = Max( res, a[i][ j - 1 ] );
            max[i][j] = res;
        }
    }

    memset( f, -1, sizeof( f ) );
    int cur = 0, next = 1;
    int max_k = Min( k >> 1, n * m );
    f[next][A][B] = a[A][B];
    for( int o = 0; o < max_k; o ++ ) {
        std::swap( cur, next );
        for( int i = 1; i <= n; i ++ ) {
            for( int j = 1; j <= m; j ++ ) {
                if( f[cur][i][j] == -1 ) 
                    continue;
                for( int z = 0; z < 4; z ++ ) {
                    int tx = i + dx[z];
                    int ty = j + dy[z];

                    if( tx < 1 || tx > n || ty < 1 || ty > m )
                        continue;

                    f[next][tx][ty] = Max( f[next][tx][ty], f[cur][i][j] + a[tx][ty] );
                    int tmp = ( ( k - ( o << 1 ) ) >> 1 );
                    ans = Max( ans, ( f[cur][i][j] * 2 ) + ( 1LL *  max[i][j] * tmp ) + ( 1LL * a[i][j] * ( tmp - 1 ) ) );
//                    printf( "%d %d %d %lld\n", o, i, j, ans );
                }
            }
        }
    }

    printf( "%lld\n", ans );

    fclose( stdin );
    fclose( stdout );
}

T3 djq的朋友圈 Friends

1 记录

考场上完全没有看懂题目的说

下来看了好久才看懂

2 Solution

这个数据范围不是状压就是爆搜的感觉

结果他不仅仅是个状压,还很神仙

考虑将于 $1$ 节点直接连接的称为 $A$ 类点,相连但是并不直接的是 $B$ 类点

设 $dp[i]$ ,其中 $i$ 是状压状态,表示取了哪些 $A$ 类点

复杂度 $O(2^A \times A)$

看起来一切都好

然后发现出题人搞我们,这个方法并不能 AC

反向思考,我们也可以枚举$B$

这样一来,复杂度就是 $ O( 2^{\min(A,B)} \times A ) $

3 Source

#include <cstdio>
#include <cstring>

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

template <typename T> T lowbit( T now ) { return now & ( - now ); }
template <typename T> T full_bit ( T a ) { return ( 1LL << a ) - 1LL; }
int get_1( long long now ) {
    int res = 0;
    while( lowbit(now) ) 
        res ++, now -= lowbit(now);
    return res;
}

inline int Max( int a, int b ) { return a > b? a: b; }

int n, m, ans, a_cnt, b_cnt, dp[ 1 << 23 ];
int f[N][N], id[N];
long long hf[N], ok[N];

int main() {
    freopen( "friends.in", "r", stdin );
    freopen( "friends.out", "w", stdout );
    memset( f, -1, sizeof(f) );
    memset( id, -1, sizeof(id) );
    scanf( "%d%d", &n, &m );
    for( int i = 1, u, v, w; i <= m; i ++ ) {
        scanf( "%d%d%d", &u, &v, &w );
        f[u][v] = f[v][u] = w;
    }

    for( int i = 2; i <= n ; i ++ ) {
        if( f[1][i] == -1 ) 
            continue;
        id[i] = ++ a_cnt;
        ans += ( f[1][i] == 0 );
        for( int j = 2; j <= n; j++ ) {
            if( f[1][j] == -1 && f[i][j] != -1 ) {
                if( id[j] == -1 ) 
                    id[j] = ++ b_cnt;
                hf[ id[i] ] |= 1LL << ( id[j] - 1LL );
                ok[ id[i] ] |= ( (long long)( f[1][i] == f[i][j] ) ) << ( id[j] - 1LL );
            }
        }
    }

    if( a_cnt <= 20 ) {
        for( int i = 0; i <= full_bit( a_cnt ); i ++ ) 
            dp[i] = -INF;
        dp[0] = 0;
        for( int i = 0; i <= full_bit( a_cnt ); i ++ ) {
            if( dp[i] < 0 ) 
                continue;
            long long now = 0;

            for( int j = 1; j <= a_cnt; j ++ ) 
                if( ( i >> ( j - 1 ) ) & 1 ) 
                    now |= hf[j];

            for( int j = 1; j <= a_cnt; j ++ ) {
                if( ( i >> ( j - 1 ) ) & 1 ) 
                    continue;
                int next = i | ( 1 << ( j - 1 ) );

                dp[next] = Max( dp[next], dp[i] + get_1( ok[j] & ( ~now ) ) );
            }
        }
        printf( "%d\n", dp[ full_bit( a_cnt ) ] + ans );
        return 0;
    }

    for( int i = 0; i <= full_bit( b_cnt ); i ++ ) 
        dp[i] = -INF;
    dp[0] = 0;
    for( int i = 0; i <= full_bit( b_cnt ); i ++ ) {
        if( dp[i] < 0 )
            continue;
        for( int j = 1; j <= a_cnt; j ++ ) {
            if( ( i | hf[j] ) == i ) 
                continue;
            int next = i | hf[j];

            dp[next] = Max( dp[next], dp[i] + get_1( ok[j] & ( ~ i ) ) );
        }
    }

    printf( "%d", ans + dp[ full_bit( b_cnt ) ] );

    fclose( stdin );
    fclose( stdout );
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注