本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-17 22:22:01

题传

题意

有一艘飞船，在一条射线上飞行，初始速度为 $0$，共有 $n$ 个加油站，分别在 $p_i$ 的位置上，每加一次油花费 $t_i$ 的时间，飞船的速度乘上油的类型 $x_i$，可以选择加或者不加，飞行不消耗油，$q$ 次询问，每次给出一个位置 $y_i$，让你回答从起点到 $y_i$ 的最短时间。

$1 \le n \le 10^5$，$1 \le q \le 10^5$，$p_i \le 10^9$，$t_i \le 10^9$，$1 \le x_i \le 4$，$1 \le y_i \le 10^9$。

思路

首先注意到精度要求 $10^{-6}$，而询问最多到 $10^9$，因此，速度大于 $10^{15}$ 是没有意义的，输出 $0$ 即可。

然后我们发现，$x_i$ 的值域很小，只有 $4$，只包含 $2$ 和 $3$ 两个质因子，在 $10^{15}$ 下，分别只有 $50$ 和 $32$ 次方，于是我们可以用质因子记录下来到每个加油站达到某个的速度的最短时间，设 $f_{i,j,k}$ 表示到了 $i$ 这个点，速度为 $2^j \times 3^k$ 的最短时间，设 $s2$ 表示当前点的 $x_i$ 质因子 $2$ 的个数，$s3$ 表示质因子 $3$ 的个数，那么达到这个速度要么是在之间的加油站已经达到了，要么是新加的油，转移方程即为 $f_{i,j,k}=\min{f_{i-1,j,k}+(p_i-p_{i-1})/(2^j \times 3^k),f_{i,j-s2,k-s3}+(p_i-p_{i-1})/(2^{j-s2} \times 3^{k-s3})+t_i}$。 需要注意边界和初始值。注意要预处理出来乘方。

把 $f$ 预处理完之后，现在我们来处理询问，对于每次询问，我们可以找到它前一个加油站（位置严格小于它），枚举到那一个加油站的速度，计算出最短时间。

但是还没完，如果你精心计算，你会发现 $f$ 数组的空间巨大，我们可以将询问离线下来，排序，这样就可以压掉第一维的位置，空间完全可以接受。

令 $2$ 的最大次幂为 $V$，$3$ 的最大次幂为 $B$，时间复杂度即为 $O(VBn+m)$，完全可以接受。

可结合代码食用。

Code

#include<bits\/stdc++.h>
#define int long long
#define endl '\n'
#define fi first
#define se second
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
const double eps=1e-6;
struct Node
{
	int p,t,x;
}sta[N];
int n,q;
pair<int,int> qry[N];
double f[50][32];
double ans[N];
double mi2[50],mi3[32];
signed main()
{
\/\/	freopen("ship.in","r",stdin);
\/\/	freopen("ship.out","w",stdout);
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>sta[i].p>>sta[i].t>>sta[i].x;
	mi2[0]=mi3[0]=1;
	for(int i=1;i<=49;i++) mi2[i]=mi2[i-1]*2;
	for(int i=1;i<=31;i++) mi3[i]=mi3[i-1]*3;
	for(int i=1;i<=q;i++)
	{
		cin>>qry[i].fi;
		qry[i].se=i;
	}
	sort(qry+1,qry+q+1);
	int pos=1;
	for(int i=49;i>=0;i--)
	{
		for(int j=31;j>=0;j--)
		{
			f[i][j]=1e10;
		}
	}
	f[0][0]=0;
	sta[0]={0,0,0};
	for(int i=1;i<=q;i++)
	{
		while(pos<=n&&sta[pos].p<qry[i].fi)
		{
			int s1=0,s2=0;
			if(sta[pos].x==2) s1=1;
			if(sta[pos].x==3) s2=1;
			if(sta[pos].x==4) s1=2;
			for(int j=49;j>=0;j--)
			{
				for(int k=31;k>=0;k--)
				{
					f[j][k]=f[j][k]+1.0*(sta[pos].p-sta[pos-1].p)\/mi2[j]\/mi3[k];
					if(j-s1<0||k-s2<0||f[j-s1][k-s2]==1e10) continue;
					f[j][k]=min(f[j][k],f[j-s1][k-s2]+sta[pos].t+1.0*(sta[pos].p-sta[pos-1].p)\/mi2[j-s1]\/mi3[k-s2]);
				}
			}
			pos++;
		}
		double cnt=1e10;
		for(int j=49;j>=0;j--)
		{
			for(int k=31;k>=0;k--)
			{
				if(f[j][k]==1e10) continue;
				cnt=min(cnt,f[j][k]+1.0*(qry[i].fi-sta[pos-1].p)\/mi2[j]\/mi3[k]);
			}
		}
		ans[qry[i].se]=cnt;
	}
	for(int i=1;i<=q;i++) cout<<fixed<<setprecision(9)<<ans[i]<<endl;
	return 0;
}