P1081 [NOIP2012 提高组] 开车旅行
思路：首先令 \(nxt1_i\) 表示右侧最近的城市距离（\(id1_i\) 为编号），令 \(nxt2_i\) 表示右侧第二近的城市编号（\(id2_i\) 为编号）；可以使用 set 找出离这个城市最近的 \(4\) 个城市（前面两个，后面两个）。
定义：
[*]\(f_{i,j}\) 表示从 \(i\) 点出发走 \(2^j\) 轮最后到达的位置。
[*]\(dp1_{i,j}\) 表示从 \(i\) 点出发走 \(2^j\) 轮最后 A 走过的距离。
[*]\(dp2_{i,j}\) 表示从 \(i\) 点出发走 \(2^j\) 轮最后 B 走过的距离。
初始化：
\
\
\
状态转移方程为：
\
\
\
此时对于询问 \(1\) 和询问 \(2\)：
[*]本质上是求出从每个城市出发后 \(A\) 走的距离与 \(B\) 走的距离。
[*]那么考虑从高位到低位贪心，即设当前跳到了 \(s\) 点，若 \(dp1_{s,i} + dp2_{s,i} \le x\)，可以从 \(s\) 跳到 \(f_{s,i}\)，需要令 \(x \gets x - (dp1_{s,i} + dp2_{s,i})\)，然后继续遍历 \(i-1\) 位。
[*]因为是 A 先开车，所以 A 可能会在最后一轮结束后还能再开上一次，需要特判。
时间复杂度为 \(O((N+Q) \log N)\)。
完整代码：
#include#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=1e5+10,M=18,INF=1e18;inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c 这个好，看起来很实用 感谢分享，下载保存了，貌似很强大 东西不错很实用谢谢分享 感谢分享，下载保存了，貌似很强大 懂技术并乐意极积无私分享的人越来越少。珍惜 谢谢分享，辛苦了 yyds。多谢分享 感谢分享，学习下。 懂技术并乐意极积无私分享的人越来越少。珍惜 很好很强大我过来先占个楼 待编辑 用心讨论，共获提升！ 鼓励转贴优秀软件安全工具和文档！ 过来提前占个楼 感谢，下载保存了 谢谢分享，辛苦了 很好很强大我过来先占个楼 待编辑 谢谢分享，试用一下 不错，里面软件多更新就更好了 不错，里面软件多更新就更好了
页:
[1]
2