南昌网站建设方式,麦包包的网站建设,表白网页制作模板,广州域名备案题目连接
题意
题目已经说的hin明确了。
题解
我们要求出从每个点出发#xff0c;小A要走的城市和小B要走的城市。
我们把ii以后的所有点的海拔加入到set role=presentation style=position: relative;setset#xff0c;然后拿H[i]H[…题目连接
题意
题目已经说的hin明确了。
题解
我们要求出从每个点出发小A要走的城市和小B要走的城市。
我们把iii以后的所有点的海拔加入到set" role="presentation" style="position: relative;">setsetset然后拿H[i]H[i]H[i]到set里面去lower_bound,找到比H[i]大的两个地点和比H[i]小的两个地点并把这四个地点与H[i]的差值加入到新的排序数组中排个序找到差值最小的两个点分别就是小B要选的目的地和小A要选的目的地。 在这里注意一点就是当差值最小的两个值相等的时候小B走的是海拔较低的那个点涉及到第二关键字的问题我们可以用一个比较省事的方法那就是给海拔低的点计算差值时候乘以99999999海拔较高的点计算差值时候乘以100000000。
定义需要的状态
nxt1[i]nxt1[i]nxt1[i]代表从iii出发，小B的目的地。
nxt2[i]" role="presentation" style="position: relative;">nxt2[i]nxt2[i]nxt2[i]代表从iii出发，小A的目的地。
nxt3[i][j]" role="presentation" style="position: relative;">nxt3[i][j]nxt3[i][j]nxt3[i][j]代表从iii出发，(小A走完、小B走完)2j" role="presentation" style="position: relative;">2j2j2^{j}轮所达到的目的 地。
DP1[i][j]DP1[i][j]DP1[i][j]代表从i出发(小A走完、小B走完)2j2j2^{j}轮小B所经过的距离。
DP2[i][j]DP2[i][j]DP2[i][j]代表从i出发(小A走完、小B走完)2j2j2^{j}轮小A所经过的距离。
nxt3,DP1,DP2可以用类似于处理ST表的方法求出来。
函数解释
一轮代表小A走一次小B走一次。 getdp(int S,int len,ll ans1,ll ans2) 从S出发走len轮返回ans1为小B走过的路程返回ans2为小A走过的路程并且把S改变为len轮以后到达的点。 getmx(int S,ll X) 从S出发总路程不能超过X返回最大能走几轮。
回答询问
给出SiSiSi和XiXiXi用二分的方法求出从Si出发小A和小B最长能走的长度。 代码
// luogu-judger-enable-o2
#include iostream
#include cstdio
#include algorithm
#include set
using namespace std;
typedef long long ll;
typedef pairll,int pll;
setpll::iterator it;
const int maxn 500007;
int nxt1[maxn],nxt2[maxn],nxt3[maxn][30];
int N,LOG,X0,M;
ll H[maxn],H2[maxn],H1[maxn],DP2[maxn][30],DP1[maxn][30];
pll tmpsort[7];
void getdp(int S,int len,ll ans1,ll ans2){int cnt 0;while(len){if(len 1){ans1 DP1[S][cnt];ans2 DP2[S][cnt];S nxt3[S][cnt];}len 1;cnt;if(!S) break;}return ;
}
int getmx(int S,ll X){int l 0,mid,r N1;while(r - l 1){mid (lr)/2;int nS S;ll ans1 0,ans2 0;getdp(nS,mid,ans1,ans2);if(ans1ans2 X || !nS)r mid;else l mid;}return l;
}
int main(){setpll st;cinN;int tmp 1;while(tmp N/3)LOG,tmp 1;for(int i 1;i N;i){scanf(%lld,H[i]);st.insert(make_pair(H[i],i));}for(int i 1;i N;i){int ct 0;st.erase(make_pair(H[i],i));it st.lower_bound(make_pair(H[i],i));if(it ! st.end()){tmpsort[ct] make_pair(abs(H[i]-(*it).first)*100000000,(*it).second); it;}if(it ! st.end()){tmpsort[ct] make_pair(abs(H[i]-(*it).first)*100000000,(*it).second); } it st.lower_bound(make_pair(H[i],i));if(it ! st.begin()) {--it;tmpsort[ct] make_pair(abs(H[i]-(*it).first)*99999999,(*it).second); if(it ! st.begin()){--it;tmpsort[ct] make_pair(abs(H[i]-(*it).first)*99999999,(*it).second); }}sort(tmpsort,tmpsortct);if(ct 0)nxt1[i] tmpsort[0].second;if(ct 1)nxt2[i] tmpsort[1].second;}for(int i 1;i N;i)nxt3[i][0] nxt1[nxt2[i]];for(int i 1;i N;i){if(nxt1[i])H1[i] abs(H[nxt1[i]] - H[i]);if(nxt2[i]){H2[i] abs(H[nxt2[i]] - H[i]);DP2[i][0] abs(H[nxt2[i]] - H[i]);}if(nxt1[nxt2[i]])DP1[i][0] abs(H[nxt1[nxt2[i]]] - H[nxt2[i]]);}for(int j 1;j LOG;j){for(int i 1;i N;i){nxt3[i][j] nxt3[nxt3[i][j-1]][j-1];DP1[i][j] DP1[i][j-1] DP1[nxt3[i][j-1]][j-1];DP2[i][j] DP2[i][j-1] DP2[nxt3[i][j-1]][j-1];}}int mf1 0,mf2 1,mh 0;int ans1 1;cinX0M;for(int i 1;i N;i){ll f1 0,f2 0;int nS i;int mxl getmx(i,X0);getdp(nS,mxl,f1,f2);if(nxt2[nS] H2[nS]f1f2 X0)f2 H2[nS];if(!f2) continue;if(mf1*f2 f1*mf2){mf1 f1;mf2 f2;ans1 i;mh H[i];}else if(mf1*f2 mf2*f1 H[i] mh){mf1 f1;mf2 f2;ans1 i;mh H[i];}}coutans1endl;for(int i 0;i M;i){int Si,nSi;ll Xi;scanf(%d %lld,Si,Xi);nSi Si;int mxl getmx(Si,Xi);ll f1 0,f2 0;getdp(nSi,mxl,f1,f2);if(nxt2[nSi] H2[nSi]f1f2 Xi)f2 H2[nSi];printf(%lld %lld\n,f2,f1);}return 0;
}
