网上能免费做网站发布叼,西柳网站建设,网站psd模版,怎样制作免费手机网站CF1550F Jumping Around
题意#xff1a;
数轴上顺次有 n 个点a1a2⋯an。a_1 a_2 \cdots a_n。a1a2⋯an。 有一只小青蛙#xff0c;初始时在asa_sas处。小青蛙有两个参数#xff1a;步长 d 和灵活程度 k。其中#xff0c…CF1550F Jumping Around
题意
数轴上顺次有 n 个点a1a2⋯an。a_1 a_2 \cdots a_n。a1a2⋯an。 有一只小青蛙初始时在asa_sas处。小青蛙有两个参数步长 d 和灵活程度 k。其中步长 d 是确定的而灵活程度 k 是可以调整的
小青蛙可以从某个点跳到另一个点。但这是有要求的小青蛙能从 aia_iai跳到aja_jaj当且仅当 d−k≤∣ai−aj∣≤dkd-k\leq |a_i-a_j|\leq dkd−k≤∣ai−aj∣≤dk
给定 a1,...,ana_1,...,a_na1,...,an和 d。你需要回答 q 次询问每次询问给定一个一个下标 i和灵活程度 k 你需要回答此时的小青蛙能否跳到 aia_iai
保证1≤n,q≤2×1051≤s,i≤n1≤ai,d,k≤106a1a2⋯an。保证 1\leq n,q\leq 2\times 10^51\leq s,i\leq n1\leq a_i,d,k\leq 10^6a_1 a_2 \cdots a_n 。保证1≤n,q≤2×1051≤s,i≤n1≤ai,d,k≤106a1a2⋯an。
题解
我一开始想满足这个式子d−k≤∣ai−aj∣≤dkd-k\leq |a_i-a_j|\leq dkd−k≤∣ai−aj∣≤dk就可以跳那我直接查询区间[l,r]的相邻差值最大值和最小值然后看是否符合式子。但是第二个样例就不对随后我突然明白u不能直接到达v但是u可以先到达其他点x再到达v。 我们现在换个思路想当参数为k时如果我们可以走到一个节点x参数大于k时我们也可以走到该节点。那么我们就开始考虑对于每个节点求出可以走到它的最小的k。 对于这个式子 d−k≤∣ai−aj∣≤dkd-k\leq |a_i-a_j|\leq dkd−k≤∣ai−aj∣≤dk −k≤∣ai−aj∣−d≤k-k\leq |a_i-a_j|-d\leq k−k≤∣ai−aj∣−d≤k ∣∣ai−aj∣−d∣≤k| |a_i-a_j|-d|\leq k∣∣ai−aj∣−d∣≤k 也就是满足这个式子点i就可以到达点j我们可以将∣∣ai−aj∣−d∣| |a_i-a_j|-d|∣∣ai−aj∣−d∣当作边权如果点u可以到达点v那么其路径上的最大值k,为了让u能到达v我们希望路径上最大值最小那不就是跑最小生成树 本题中边的数量是O(n2)O(n^2)O(n2),prim和kruskal都会超时因此要用另一个最小生成树的算法boruvka算法。 这个算法不详细介绍了详情见boruvka算法 算法的关键也是复杂度与边权有关的地方就是找最小边权的边本题中边权是有性质的 现在我们要想∣∣ai−aj∣−d∣≤k| |a_i-a_j|-d|\leq k∣∣ai−aj∣−d∣≤k值最小设aia_iai在连通块内aja_jaj在连通块外那对于每个aia_iai,我们找aja_jaj最接近aida_idaid或者ai−da_i-dai−d的点然后取最小即可 具体操作为 我们可以维护一个set先存所有的a然后对于一个连通块枚举连通块内所有的点把他们从set中删除此时set中所有点都在这个连通块外。然后再枚举连通块内的所有点i用set二分查找距离aida_idaid或者ai−da_i-dai−d的点。直接在set上二分四次就找到了。最后再把所有点加回来。 二分找最小边权的复杂度是O(nlog n) 总复杂度是O(nlog2n)O(nlog^2n)O(nlog2n) 因为我们直到起点把起点当作跟跑一边dfs求出到其他点的路径上的最大值如果询问中k大于这个最大值就是Yes否则就是No
代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn2e69;
int n,m,q,s,d;
setintst;
int fa[maxn];
int a[maxn];
int id[maxn];
vectorPIIg[maxn];
int find(int x){if(fa[x]x)return x;return fa[x]find(fa[x]);
}
int getd(int x,int y){return abs(abs(x-y)-d);
}
void check(int u,int v,int x,int y){if(xINF_int||yINF_int)return ;if(getd(x,y)getd(u,v)){ux;vy;}
}
struct node{int u,v,w;
}e1[maxn2];
vectorintblock[maxn];
void boruvka(){int mn-1;while(m){for(int i1;in;i)block[i].clear();for(int i1;in;i)block[find(i)].push_back(i);int cnt0;for(int i1;in;i){if(find(i)i){//找到一个连通块 int u0,vINF_int;for(int j0;jblock[i].size();j){st.erase(st.find(a[block[i][j]]));//删除连通块内元素 }for(int j0;jblock[i].size();j){check(u,v,a[block[i][j]],*st.lower_bound(a[block[i][j]]d));check(u,v,a[block[i][j]],*(--st.lower_bound(a[block[i][j]]d)));check(u,v,a[block[i][j]],*st.lower_bound(a[block[i][j]]-d));check(u,v,a[block[i][j]],*(--st.lower_bound(a[block[i][j]]-d)));} if(u!0)//如果找到最小边建最下生成树{e1[cnt](node){id[u],id[v],getd(u,v)};} for(int j0;jblock[i].size();j)st.insert(a[block[i][j]]);}}for(int i1;icnt;i){if(find(e1[i].u)!find(e1[i].v)){m--;int ue1[i].u;int ve1[i].v;int we1[i].w;g[u].push_back({v,w});g[v].push_back({u,w});fa[find(u)]find(v);}}}}
int ans[maxn];
void dfs(int u,int fa,int mx){ans[u]mx;for(auto it:g[u]){int vit.first;int wit.second;if(v!fa)dfs(v,u,max(mx,w));}
}
int main()
{//rd_test();cinnqsd;for(int i1;in;i){cina[i];block[i].push_back(i);st.insert(a[i]);fa[i]i;id[a[i]]i;}st.insert(-INF_int);st.insert(INF_int);boruvka();dfs(s,0,0);while(q--){int i,k;cinik;if(ans[i]k)puts(Yes);else puts(No);}return 0;//Time_test();
}
