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

Laisira · 2024-11-17 15:30:16 · 题解

思路

连着两道小签题，梦熊真好心。

一个显然的暴力：

记 f_{i,j} 表示到第 i 个加油站的位置速度为 j 的最小时间，有：

然后在每个询问点上暴力取最小值，由于路程最大值（y_{max}）不超过 10^9，加油时间大于等于 1，所以速度不大于 y_{max}，乘的次数不大于 \lceil\log y_{max}\rceil，时间复杂度 O(n\lceil\log y_{max}\rceil+nm)。

不难发现瓶颈在统计答案，又 x_{i} 只有四种情况（其中一种没用，一种可以被分解成 2\times 2），不妨记 2 和 3 分别被乘了几次，询问离线当成 x_i = 1 去跑，时间复杂度 O(n\lceil\log^2 y_{max}\rceil)。

状态转移与上面大体一致。

UPDATE：少了个 t_i。

代码

#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;
 }