专栏文章

题解：P11290 【MX-S6-T2】「KDOI-11」飞船

LLaisira
P11290题解参与者 4已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mir48936
此快照首次捕获于
2025/12/04 15:29
3 个月前
此快照最后确认于
2025/12/04 15:29
3 个月前
查看原文

思路

连着两道小签题，梦熊真好心。
一个显然的暴力：
记 fi,jf_{i,j} 表示到第 ii 个加油站的位置速度为 jj 的最小时间，有：
fi,j=min⁡(fi−1,j+pi−pi−1j,fi−1,jxi+xi(pi−pi−1)j+ti)f_{i,j} = \min(f_{i-1,j}+\frac{p_{i}-p_{i-1}}{j},f_{i-1,\frac{j}{x_i}}+\frac{x_i(p_{i}-p_{i-1})}{j}+t_i)
然后在每个询问点上暴力取最小值，由于路程最大值（ymaxy_{max}）不超过 10910^9，加油时间大于等于 11，所以速度不大于 ymaxy_{max}，乘的次数不大于 ⌈log⁡ymax⌉\lceil\log y_{max}\rceil，时间复杂度 O(n⌈log⁡ymax⌉+nm)O(n\lceil\log y_{max}\rceil+nm)。
不难发现瓶颈在统计答案，又 xix_{i} 只有四种情况（其中一种没用，一种可以被分解成 2×22\times 2），不妨记 22 和 33 分别被乘了几次，询问离线当成 xi=1x_i = 1 去跑，时间复杂度 O(n⌈log⁡2ymax⌉)O(n\lceil\log^2 y_{max}\rceil)。
状态转移与上面大体一致。
UPDATE：少了个 tit_i。

代码

CPP
#include<bits/stdc++.h>
#define int long long 
#define double long double 
#define m2 30
#define m3 25
using namespace std;
double f[2][m2][m3];
int fac[2][31];
struct node {
	int op,p,t,x;
	bool operator<(const node&is) {
		return p == is.p?op < is.op:p < is.p;
	}
} t[1000005];
double ans[100005];
double get(double x,double y) {
	return (double)x/y;
}
const double inf = 1e14;
const int INF = 1e13;
signed main()
{
//	freopen("ship4.in","r",stdin);
//	freopen("ship.out","w",stdout);
	int n,q,tot = 0;
	cin>>n>>q;
	for(int i=1;i<=n;i++) {
		int x,y,z;
		cin>>x>>y>>z;
		if(z == 1)continue;
		t[++tot] = {0,x,y,z};
	} 
	
	for(int i=1;i<=q;i++) {
		int x;
		cin>>x;
		t[++tot] = {i,x,0,1};
	} 
	
	sort(t+1,t+1+tot);
	
	for(int i=0;i<m2;i++)
		for(int j=0;j<m3;j++) {
			f[0][i][j] = inf;
			f[1][i][j] = inf;
		}
	f[0][0][0] = 0;
	
	fac[0][0] = fac[1][0] = 1;
	for(int i=1;i<m2;i++)
		fac[0][i] = fac[0][i-1]*2;
	for(int i=1;i<m3;i++)
		fac[1][i] = fac[1][i-1]*3;
	
	int res2 = 0,res3 = 0;
	
	for(int i=1;i<=tot;i++) {
		for(int j=0;j<=res2;j++) {
			for(int k=0;k<=res3;k++) {
				__int128 cnt = (__int128)fac[0][j]*fac[1][k]*t[i].x;
				if(cnt >= INF)break;
				f[(i&1)][j][k] = min(f[(i&1)][j][k],f[(i&1)^1][j][k]+get(t[i].p-t[i-1].p,fac[0][j]*fac[1][k]));
				if(t[i].x == 1)f[(i&1)][j][k] = f[(i&1)^1][j][k]+get(t[i].p-t[i-1].p,fac[0][j]*fac[1][k]);
				if(t[i].x == 2)f[(i&1)][j+1][k] = min(f[(i&1)^1][j+1][k]+get(t[i].p-t[i-1].p,fac[0][j+1]*fac[1][k]),f[(i&1)^1][j][k]+get(t[i].p-t[i-1].p,fac[0][j]*fac[1][k])+t[i].t);
				if(t[i].x == 3)f[(i&1)][j][k+1] = min(f[(i&1)^1][j][k+1]+get(t[i].p-t[i-1].p,fac[0][j]*fac[1][k+1]),f[(i&1)^1][j][k]+get(t[i].p-t[i-1].p,fac[0][j]*fac[1][k])+t[i].t);
				if(t[i].x == 4)f[(i&1)][j+2][k] = min(f[(i&1)^1][j+2][k]+get(t[i].p-t[i-1].p,fac[0][j+2]*fac[1][k]),f[(i&1)^1][j][k]+get(t[i].p-t[i-1].p,fac[0][j]*fac[1][k])+t[i].t);
			}
		}
		if(t[i].x == 2)res2 ++;
		if(t[i].x == 3)res3 ++;
		if(t[i].x == 4)res2 += 2;
		if(res2 > m2-1)res2 = m2-1;
		if(res3 > m3-1)res3 = m3-1;
		if(t[i].op) {
			double res = inf;
			for(int j=0;j<=res2;j++)
				for(int k=0;k<=res3;k++)
					res = min(res,f[(i&1)][j][k]);
			ans[t[i].op] = res;
		}
		for(int j=0;j<=res2;j++)
			for(int k=0;k<=res3;k++)
				f[(i&1)^1][j][k] = inf;
	} 
	for(int i=1;i<=q;i++)printf("%.7Lf\n",ans[i]);
	return 0;
 }

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...