合肥做网站需要多少钱,简单的seo网站优化排名,工程师网站建设,天门建设局官方网站AT2039 [ARC060C] 高橋君とホテル / Tak and Hotelsproblemsolution - 分块code - 分块solution - 倍增code - 倍增problem
luogu翻译
solution - 分块
肯定刚开始#xff0c;我们很想暴力跳过去。事件复杂度取决于数据。
肯定不做把头拿给别人砍的事
这种跳法#xff0…
AT2039 [ARC060C] 高橋君とホテル / Tak and Hotelsproblemsolution - 分块code - 分块solution - 倍增code - 倍增problem
luogu翻译
solution - 分块
肯定刚开始我们很想暴力跳过去。事件复杂度取决于数据。
肯定不做把头拿给别人砍的事
这种跳法让我想到了是否可以分块。
我又联想到了之前做的一道维护每个点跳出本块的下一个点信息CF1491H。
这里也这么做暴力分块。 首先维护出每个点跳一步能最远跳多少采取二分另一尺取指针做法在倍增板块实现 用来在块内暴力互跳。 然后维护出每个点最少需要跳多少步才能跳出所属块以及跳出的位置。 从每个点开始一步一步跳最多跳块长 n\sqrt{n}n 步就跳出块了。
后面查询的时候先把起点跳到终点的块内这一过程最多暴力跳 n\sqrt{n}n 个整块。
然后再暴力在一个块内跳到终点这一过程最多暴力跳块长也是 n\sqrt{n}n 的。
时间复杂度 O(nlognnnqn)O(n\log nn\sqrt n q\sqrt n )O(nlognnnqn)。
code - 分块
#include bits/stdc.h
using namespace std;
#define maxn 100005
int n, Q, L;
int x[maxn], to[maxn], block[maxn], w[maxn], g[maxn];int find( int pos ) {int l pos 1, r n, ans pos 1;while( l r ) {int mid ( l r ) 1;if( x[mid] - x[pos] L ) ans mid, l mid 1;else r mid - 1;}return ans;
}int main() {scanf( %d, n );for( int i 1;i n;i ) scanf( %d, x[i] );scanf( %d %d, L, Q );for( int i 1;i n;i ) to[i] find( i );int B sqrt( n ), cnt n / B ( n % B ! 0 );for( int i 1;i n;i ) block[i] ( i - 1 ) / B 1;for( int i 1;i n;i ) {int k i, ans 0;while( block[k] block[i] ) k to[k], ans ;w[i] ans, g[i] k;if( i B * ( cnt - 1 ) 1 ) w[i] --, g[i] --;}while( Q -- ) {int u, v, ans 0;scanf( %d %d, u, v );if( u v ) swap( u, v );while( block[u] block[v] ) ans w[u], u g[u];while( u v ) ans , u to[u];printf( %d\n, ans );}return 0;
}solution - 倍增
设 fi,j:if_{i,j}:ifi,j:i 点开始跳 2k2^k2k 步最远能跳到哪儿。
初始化就指针不断尺取扫当 iii 增加时指针只会右移时间是线性的。
fi,j←ffi,j−1,j−1f_{i,j}\leftarrow f_{f_{i,j-1},j-1}fi,j←ffi,j−1,j−1 预处理倍增数组。
后面直接跳就行了。
时间复杂度 O(qlogn)O(q\log n)O(qlogn)。
code - 倍增
#include bits/stdc.h
using namespace std;
#define maxn 100005
int n, L, Q;
int x[maxn];
int f[maxn][20];int main() {scanf( %d, n );for( int i 1;i n;i ) scanf( %d, x[i] );scanf( %d %d, L, Q );for( int i 1, k 1;i n;i ) {while( k n and x[k 1] - x[i] L ) k ;f[i][0] k;}for( int j 1;( 1 j ) n;j )for( int i 1;i ( 1 j ) - 1 n;i )f[i][j] f[f[i][j - 1]][j - 1];while( Q -- ) {int a, b, ans 0;scanf( %d %d, a, b );if( a b ) swap( a, b );for( int i 16;~ i;i -- ) if( f[a][i] and f[a][i] b ) ans ( 1 i ), a f[a][i];printf( %d\n, ans 1 );} return 0;
}
