网站开发方案书博客,网站建设一流公司,专业做动漫的网站,书籍封面设计网站[CCO 2019] Sirtetdescriptionsolutioncodedescription
题目链接
solution
很巧妙地将差分约束隐藏起来
问题的关键在于求出每一个sand停止运动的时间#xff0c;这样很容易填涂出最后的答案#xff08;向下平移即可#xff09;
不妨设 ti,jt_{i,j}ti,j 表示 (i,j)(i…
[CCO 2019] Sirtetdescriptionsolutioncodedescription
题目链接
solution
很巧妙地将差分约束隐藏起来
问题的关键在于求出每一个sand停止运动的时间这样很容易填涂出最后的答案向下平移即可
不妨设 ti,jt_{i,j}ti,j 表示 (i,j)(i,j)(i,j) 位置上的 sand\text{sand}sand 停止运动的时间 如果 (i1,j1)(i_1,j_1)(i1,j1) 和 (i2,j2)(i_2,j_2)(i2,j2) 的 sand\text{sand}sand 是连在一起的则 ti1,j1ti2,j2t_{i_1,j_1}t_{i_2,j_2}ti1,j1ti2,j2 转化成差分约束的形式即 ti1,j1−ti2,j2≤0,ti2,j2−ti1,j1≤0t_{i_1,j_1}-t_{i_2,j_2}\le 0,t_{i_2,j_2}-t_{i_1,j_1}\le 0ti1,j1−ti2,j2≤0,ti2,j2−ti1,j1≤0 显然这是具有传递性的【在代码实现中我选择了同一连通块缩点的方法利用并查集】 如果 (i1,j1)(i_1,j_1)(i1,j1) 和 (i2,j2)(i_2,j_2)(i2,j2) 的 sand\text{sand}sand 不是连在一起的显然只有 j1j2j_1j_2j1j2 【同一列】的 sand\text{sand}sand 会相互影响 假设 i1i2i_1i_2i1i2 显然最多经过 i2−i1−1i_2-i_1-1i2−i1−1 的时间后就一定会碰上【可能i1i_1i1所属的连通块的某个 sand\text{sand}sand 会与其余连通块先撞上】即 ti1,j1−ti2,j2≤i2−i1−1t_{i_1,j_1}-t_{i_2,j_2}\le i_2-i_1-1ti1,j1−ti2,j2≤i2−i1−1 注意同一列只需要相邻的两个不同连通块的 sand\text{sand}sand 进行连边【具有传递性】且最下面的 sand\text{sand}sand 与空【定义为000】的距离为 n−in-in−i
最后求不同连通块之间的最短路即可
code
#include queue
#include cstdio
#include vector
using namespace std;
#define maxn 1000005
#define Pair pair int, int
priority_queue Pair, vector Pair , greater Pair q;
vector Pair G[maxn];
int n, m;
char **ch, **ans;
int *lst;
int dis[maxn], f[maxn];
bool vis[maxn];int find( int x ) { return f[x] x ? x : f[x] find( f[x] ); }void merge( int u, int v ) {u find( u ), v find( v );if( u v ) return;else f[v] u;
}void addedge( int u, int v, int w ) { u find( u ), v find( v );G[u].push_back( { v, w } );
}int id( int x, int y ) { return ( x - 1 ) * m y; }int main() {scanf( %d %d, n, m );ch new char * [n 5];lst new int [m 5];for( int i 1;i n;i ) {ch[i] new char[m 5];scanf( %s, ch[i] 1 );}for( int i 1;i n * m;i ) f[i] i;for( int i 1;i n;i ) {for( int j 1;j m;j ) {lst[j] 0; if( ch[i][j] # ) {if( i 1 and ch[i - 1][j] # ) merge( id( i, j ), id( i - 1, j ) );if( i n and ch[i 1][j] # )merge( id( i, j ), id( i 1, j ) );if( j 1 and ch[i][j - 1] # )merge( id( i, j ), id( i, j - 1 ) );if( j m and ch[i][j 1] # )merge( id( i, j ), id( i, j 1 ) );}}}for( int i 1;i n;i )for( int j 1;j m;j )if( ch[i][j] # ) {if( lst[j] ) addedge( id( i, j ), id( lst[j], j ), i - lst[j] - 1 );lst[j] i;}for( int i 1;i m;i ) if( lst[i] ) addedge( 0, id( lst[i], i ), n - lst[i] );for( int i 1;i n * m;i ) dis[i] 0x3f3f3f3f;q.push( { 0, 0 } );while( ! q.empty() ) {int u q.top().second; q.pop();if( vis[u] ) continue;vis[u] 1;for( int i 0;i G[u].size();i ) {int v G[u][i].first, w G[u][i].second;if( dis[v] dis[u] w ) {dis[v] dis[u] w;q.push( { dis[v], v } );}}}ans new char * [n 5];for( int i 1;i n;i ) {ans[i] new char [m 5];for( int j 1;j m;j ) ans[i][j] .;}for( int i 1;i n;i )for( int j 1;j m;j )if( ch[i][j] # ) ans[i dis[find( id( i, j ) )]][j] #;for( int i 1;i n;i ) {for( int j 1;j m;j )printf( %c, ans[i][j] );printf( \n );}return 0;
}
