中国优秀企业网站,山西高端网站建设,免费制作一个企业网站,wordpress主题windows同余最短路是用来解决一类 ∑i1naixi∈[L,R]\sum_{i1}^n a_ix_i\in[L,R]∑i1naixi∈[L,R] 问题的方法。
其中 L,RL,RL,R 值非常大#xff0c;而 nnn 不是很大#xff0c;大概是接受 O(n2)O(n^2)O(n2) 的范围#xff0c;xix_ixi 是自定义的系数。
先差分一下#…同余最短路是用来解决一类 ∑i1naixi∈[L,R]\sum_{i1}^n a_ix_i\in[L,R]∑i1naixi∈[L,R] 问题的方法。
其中 L,RL,RL,R 值非常大而 nnn 不是很大大概是接受 O(n2)O(n^2)O(n2) 的范围xix_ixi 是自定义的系数。
先差分一下变成 ∑i1naixi∈[0,R]−∑i1naixi∈[0,L−1]\sum_{i1}^na_ix_i\in [0,R]-\sum_{i1}^na_ix_i\in [0,L-1]∑i1naixi∈[0,R]−∑i1naixi∈[0,L−1]。
我们选中其中 aia_iai 最小的作为标准 a0a_0a0。
显然每个数都能表示成 xa0rxa_0rxa0r 的形式rrr 是余数 a0a_0a0。
然后我们将所有的数按照 rrr 分类分出了 a0a_0a0 个类编号 0∼a0−10\sim a_0-10∼a0−1。
考虑当我们能够凑出一个数 t∈[L,R]t\in [L,R]t∈[L,R] 中那么 ta0,t2a0,...ta_0,t2a_0,...ta0,t2a0,... 都能被凑出来。
且不难发现这些数都属于一个余数类中。
如果我们能求出每个余数类中最小被表示出来的数 t0t_0t0那么就可以用 ⌊R−t0a0⌋1\lfloor\frac{R-t_0}{a_0}\rfloor1⌊a0R−t0⌋1 算出这个类中的 ∈[0,R]\in[0,R]∈[0,R] 的合法数。
所以现在还需要快速求出每个类中的 t0t_0t0。
因为我们计算类中的个数就是无限制地用了 a0a_0a0所以不妨在这里就不再使用。即我们使用若干个除 a0a_0a0 外的所有 aia_iai 来构造出。
假设我们能构造出某个余数类中的数 ttt那么我们就能构造出编号为 (tai)moda0(ta_i)\mod a_0(tai)moda0 余数类中的数 taita_itai。
发现这个关系可以看作一条边而整个过程我们无非是在求到一个点余数类的最短路最小能表示出的数。
具体而言将每个余数类建成一个点然后点 xxx 向 (xai)moda0(xa_i)\mod a_0(xai)moda0 点连边边权为 aia_iai然后求最短路。
从 000 点开始初始化 dis(0)0\text{dis}(0)0dis(0)0 即可。因为最小的可以被构造出来的数肯定是 000什么数都不用即可。
跳楼机
luogu-P3403
注意楼层是从 111 开始的。我们整体往下移动一个单位即可。这题还不用差分虽然差分没有任何难度。
#include bits/stdc.h
using namespace std;
#define int long long
#define Pair pair int, int
vector Pair G[100005];
int h;
int a[5], dis[100005];
priority_queue Pair, vector Pair , greater Pair q;void addedge( int u, int v, int w ) {G[u].push_back( make_pair( v, w ) );
}void dijkstra() {q.push( make_pair( dis[0] 0, 0 ) );while( ! q.empty() ) {int u q.top().second, w q.top().first; q.pop();if( dis[u] ^ w ) continue;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 )q.push( make_pair( dis[v] dis[u] w, v ) );}}
}signed main() {scanf( %lld, h );for( int i 1;i 3;i ) scanf( %lld, a[i] );sort( a 1, a 4 );if( a[1] 1 ) return ! printf(%lld\n, h );for( int i 0;i a[1];i ) {addedge( i, ( i a[2] ) % a[1], a[2] );addedge( i, ( i a[3] ) % a[1], a[3] );}memset( dis, 0x3f, sizeof( dis ) );dijkstra();int ans 0;for( int i 0;i a[1];i )if( dis[i] h - 1 )ans ( h - 1 - dis[i] ) / a[1] 1;printf( %lld\n, ans ); return 0;
}[国家集训队]墨墨的等式
luogu-P2371
#include bits/stdc.h
using namespace std;
#define int long long
#define Pair pair int, int
int n, l, r;
int dis[500005], a[15];
priority_queue Pair, vector Pair , greater Pair q;
vector Pair G[500005];void addedge( int u, int v, int w ) {G[u].push_back( make_pair( v, w ) );
}void dijkstra() {q.push( make_pair( dis[0] 0, 0 ) );while( ! q.empty() ) {int u q.top().second, w q.top().first; q.pop();if( dis[u] ^ w ) continue;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 )q.push( make_pair( dis[v] dis[u] w, v ) );}}
}int query( int n ) {int ans 0;for( int i 0;i a[1];i )if( dis[i] n )ans ( n - dis[i] ) / a[1] 1;return ans;
}signed main() {scanf( %lld %lld %lld, n, l, r );for( int i 1;i n;i ) scanf( %lld, a[i] );sort( a 1, a n 1 );for( int i 0;i a[1];i )for( int j 2;j n;j )addedge( i, ( i a[j] ) % a[1], a[j] );memset( dis, 0x3f, sizeof( dis ) );dijkstra();printf( %lld\n, query( r ) - query( l - 1 ) );return 0;
}
