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 );
}
Orz
Orz
%%%