分类
OI

中山纪念中学 Day 10 2019.08.10 解题报告 & 题解

T1 数学题 Math

1 记录

真就数学题目呗

考场企图推正解,结果最后只推出了 60 分的,哭了

正解参见 欧几里得算法的应用.pdf

这是真的类欧几里得算法

2 Source

#include <cstdio>


inline long long pf( long long x ) { return x * x; }

void calc( int a, int b, int c, int d, int &x, int &y ) {
    long long dot = a * c + b * d;

    if( dot < 0 ) {
        calc( a, b, -c, -d, x, y );
        y = - y;
        return ;
    }

    long long ab = a * a + b * b, cd = c * c + d * d;

    if( ab > cd ) {
        calc( c, d, a, b, y, x );
        return ;
    }
    if( ( dot * dot * 4 ) <= ab * cd ) {
        x = 1, y = 0;
        return ;
    }

    long long k = dot / ab;

    if( dot + dot <= ab * ( 2 * k + 1 ) ) {
        calc( a, b, c - k * a, d - k * b, x, y );
        x -= k * y;
        return ;
    }
    else {
        calc( a, b, c - ( k + 1 ) * a, d - ( k + 1 ) * b, x, y );
        x -= ( k + 1 ) * y;
        return ;
    }

}

int main() {
    freopen( "math.in", "r", stdin );
    freopen( "math.out", "w", stdout );
    int a, b, c, d, x = 0, y = 0;
    while( scanf( "%d%d%d%d", &a, &b, &c, &d ) != EOF ) {
        calc( a, b, c, d, x, y );
        printf( "%lld\n", pf( 1LL * a * x + 1LL * c * y ) + pf( 1LL * b * x + 1LL * d * y ) );
    }
}

T2 挖宝藏 Treasure

咕了,两天后没更记得提醒我

udp: 2019/08/11 鸽子已经被红烧了,组织放心

1 记录

考场上觉得是个暴搜,就没敢碰……

2 Solution

事实证明我还是 Too young, Too simple

这道题目是 WC 2008 中一道题目的加强版

在 $h = 1$ 的时候 头插 DP 联通性 DP 可解

但是因为这道题目加强了

所以 连通性 DP 只有部分分……

正解是这样的

定义 $f[i,j,k]$ 表示现在到达 $(i,j)$ ,$k$ 是一个压缩后的状态,其二进制第 $i$ 位表示第 $i$ 个宝藏是否取得,$f[i,j,k]$ 表示最优解

转移方程显然可得
$$
f[i,j,k] =
\begin{cases}
f[i – 1, j, k] + a[i,j]\\
f[i + 1, j, k] + a[i,j]\\
f[i, j – 1, k] + a[i,j]\\
f[i, j + 1, k] + a[i,j]\\
\min{f[i,j,t] + f[i,j,s] – a[i][j] | s \text{ and } t = k }
\end{cases}
$$
这里的 $\text{and}$ 指按位和

转移方程具有后效性,前 $4$ 个式子可以使用最短路算法松弛,后面一个式子可以预处理出来

层与层之间怎么转移?

多转压一个数,即
$$
f[h,i,j,1] = f[h-1,i,j, 2^{k_i + 1} – 1]
$$
复杂度玄学,$O(nm3^k)$

3 Source

#include <cstdio>
#include <cstring> 

#include <queue>

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

inline int Min( int a, int b ) { return a < b? a: b; }
inline int pow_2( int now ) { return 1 << now; }
inline int full_bit( int now ) { return pow_2( now ) - 1; }

struct node {
    int x, y;
} tre[N][N];

struct que {
    int x, y;
};

std::queue<que> q;

int h, n, m, ans = INF;
int a[N][N][N], f[N][N][ 1 << (13) ], p[N];
bool vis[N][N];
int dx[4] = { +1, -1, 0, 0 };
int dy[4] = { 0, 0, +1, -1 };

int main() {
    freopen( "treasure.in", "r", stdin );
    freopen( "treasure.out", "w", stdout );
    scanf( "%d%d%d", &h, &n, &m );
    for( int i = 1; i <= h; i++ ) {
        for( int j = 1; j <= n; j ++ ) {
            for( int k = 1; k <= m; k ++ ) {
                scanf( "%d", &a[i][j][k] );
            }
        }
    }
    for( int i = 1; i <= h; i ++ ) {
        scanf( "%d", &p[i] );
        for( int j = 1; j <= p[i]; j ++ ){
            scanf( "%d%d", &tre[i][j].x, &tre[i][j].y );
        }
        p[i] ++;
    }

    for( int z = 1; z <= h; z ++ ) {
        for( int x = 1; x <= n; x ++ ) {
            for( int y = 1; y <= m; y ++ ) {
                f[x][y][1] = ( ( z == 1 ) ? 0: f[x][y][ full_bit( p[ z - 1 ] ) ] ) + a[z][x][y];
                for( int i = 2; i < pow_2( p[z] ); i++ ) 
                    f[x][y][i] = INF;
            }
        }
        for( int i = 1; i < p[z]; i ++ ) {
            f[ tre[z][i].x ][ tre[z][i].y ][ pow_2(i) ] = a[z][ tre[z][i].x ][ tre[z][i].y ];
        }

        for( int s = 1; s < pow_2( p[z] ); s ++ ) {
//            head = tail = 0;
            for( int x = 1; x <= n; x ++ ) {
                for( int y = 1; y <= m; y ++ ) {
                    for( int t = s & ( s - 1 ); t; t = s & ( t - 1 ) )
                        f[x][y][s] = Min( f[x][y][s], f[x][y][t] + f[x][y][ s ^ t ] - a[z][x][y] ); 
                    if( f[x][y][s] < INF ) {
                        q.push( (que) { x, y } );
                        vis[x][y] = true;
                    }
                }
            }
            while( ! q.empty() ) {
                que top = q.front(); q.pop();
                for( int i = 0; i < 4; i++ ) {
                    que tmp = top;
                    tmp.x += dx[i], tmp.y += dy[i];
                    if( tmp.x <= 0 || tmp.x > n || tmp.y <= 0 || tmp.y > m ) 
                        continue;
                    if( f[ top.x ][ top.y ][s] + a[z][ tmp.x ][ tmp.y ] < f[ tmp.x ][ tmp.y ][s] ) {
                        f[ tmp.x ][ tmp.y ][s] = f[ top.x ][ top.y ][s] + a[z][ tmp.x ][ tmp.y ];
                        if( vis[ tmp.x ][ tmp.y ] == false ) {
                            vis[ tmp.x ][ tmp.y ] = true;
                            q.push( tmp );
                        }
                    }
                }
                vis[ top.x ][ top.y ] = false;
            }
        }
//        for( int i = 1; i <= n; i ++ ) {
//            for( int j = 1; j <= m; j ++ ) {
//                printf( "%d ", f[i][j][ full_bit( p[z] ) ] );
//            }
//            printf( "\n" );
//        }
    }

    for( int i = 1; i <= n; i++ ) {
        for( int j = 1; j <= m; j++ ) {
            ans = Min( ans, f[i][j][ full_bit( p[h] ) ] );
        }
    }

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

T3 理想城市 City

1 记录

考场上建出树来了

但是统计方法略有问题

2 Solution

从某种程度上来说,也算是套路题了……

首先是树上统计路径和

对每条边,其贡献是左边节点数乘上右边节点数

然后是进行横向的剖分,将处在同一行并连续的格子压缩成一个节点,如果不同行的两个连续段有公共边界,则将对应的两个节点连边。容易发处理后是个树结构,然后套上面就行了

3 Source

#include <cstdio>
#include <cstring>

#include <map>
#include <algorithm>

const int N = 1e5 + 1e4;
const int mod = 1e9;

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

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

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

int n, cnt, ans, col[N], son[N], col_cnt;
std::map< std::pair< int, int >, int > mp;

// Graph Start 
struct edge {
    int to, next;
} e[ N << 1 ];
int ehead[N], ecnt;

inline void add_edge( int now, int to ) {
    ecnt ++;
    e[ecnt].to = to;
    e[ecnt].next = ehead[now];
    ehead[now] = ecnt;
}

inline void add_edge_maybe( int now, int to ) {
    if( e[ ehead[now] ].to == to )
        return;
    add_edge( now, to );
    add_edge( to, now );
}

void dfs( int now, int fa ) {
    //printf( "%d %d\n", now, fa );
    for( int i = ehead[now]; i; i = e[i].next ) {
        if( e[i].to == fa ) 
            continue;
        dfs( e[i].to, now );
        son[now] += son[ e[i].to ];
        ans = ( ans + ( 1LL * son[ e[i].to ] * ( n - son[ e[i].to ] ) ) % mod ) % mod;
    }
}
// Graph End

int main() {
    freopen( "city.in", "r", stdin );
    freopen( "city.out", "w", stdout );
    scanf( "%d", &n );
    for( int i = 1; i <= n; i++ ) {
        scanf( "%d%d", &a[i].x, &a[i].y );
        mp[ std::make_pair( a[i].x, a[i].y ) ] = ++ cnt;
    }

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

    for( int i = 1; i <= n; i++ ) {
        if( a[ i - 1 ].x == a[i].x && a[ i - 1 ].y + 1 == a[i].y ) 
            son[ col[ mp[ std::make_pair( a[i].x, a[i].y ) ] ] = col[ mp[ std::make_pair( a[ i - 1 ].x, a[ i - 1 ].y ) ] ] ] ++;
        else 
            son[ col[ mp[ std::make_pair( a[i].x, a[i].y ) ] ] = ++ col_cnt ] ++;
    }

    for( int i = 1; i <= n; i++ ) {
        if( mp.count( std::make_pair( a[i].x + 1, a[i].y ) ) ) {
            add_edge_maybe( col[ mp[ std::make_pair( a[i].x + 1, a[i].y ) ] ], col[ mp[ std::make_pair( a[i].x, a[i].y ) ] ] ); 
        }
    }

    dfs( 1, 0 );
    // Init
    ecnt = col_cnt = 0;
    memset( ehead, 0, sizeof( ehead ) );
    memset( son, 0, sizeof( son ) );
    memset( col, 0, sizeof( col ) );

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

    for( int i = 1; i <= n; i++ ) {
        if( a[ i - 1 ].y == a[i].y && a[ i - 1 ].x + 1 == a[i].x ) 
            son[ col[ mp[ std::make_pair( a[i].x, a[i].y ) ] ] = col[ mp[ std::make_pair( a[ i - 1 ].x, a[ i - 1 ].y ) ] ] ] ++;
        else 
            son[ col[ mp[ std::make_pair( a[i].x, a[i].y ) ] ] = ++ col_cnt ] ++;
    }

    for( int i = 1; i <= n; i++ ) {
        if( mp.count( std::make_pair( a[i].x, a[i].y + 1 ) ) ) {
            add_edge_maybe( col[ mp[ std::make_pair( a[i].x, a[i].y + 1 ) ] ], col[ mp[ std::make_pair( a[i].x, a[i].y ) ] ] ); 
        }
    }

    dfs( 1, 0 );

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

发表评论

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