题解：P14384 [JOISC 2017] 烟花棒 / Sparklers

· · 题解

复习双序列拓展。

满足单调性，二分 s。

结论：

  1. 点燃（包括烧完的）的人是一个区间。

  2. 未点燃的人始终朝向点燃的人行进。

  3. 一个人只在燃烧结束时传递火。

考虑还在追赶的人，俩人朝向后面的人行进，一定更优。或者同步前进，一定不劣。

  1. 场上同时只会有一个人被点燃。

根据 3 得出，同位置一直跟着就好。

转化：

JOI 君初始在 K，可以不断地以 2s 的速度移动，注意 JOI 君往某方向移动时另一方向距离不会增加。

JOI 君有计数器 t，初始为 T，每秒 t\gets t-1，JOI 君每草似一个人就会令 t\gets t+T，t 不能 <0，问 JOI 君能否草飞所有人。

一个区间 [l,r] 合法当且仅当 b_l=(2Tsr-x_r)\ge b_r=(2Tsl-x_l)。

而我们现在要在网格上找一个 (k,k) 到 (1,n) 路径（左上方向），一直满足 b_l\le b_r。

分解问题，首先左侧最大/最小值比右侧最大/最小值大一定不合法。

现在转化为从 (K,K)\to (x,y),(x,y)\to (1,n)，这一部分中，我们当前的左右端点 (x,y) 总是满足任意的 (x,r) 或 (l,y) 都是合法区间。

则我们现在不断推进 x 或者 y 即可。

写成代码即：

bool solve1(int x,int y){//(K,K) to (x,y)
    if(x==K||y==K)return 1;
    if(a[klmx[x]]<=a[krmx[y-1]])
        return solve1(x,krmx[y-1]);
    if(a[klmn[x+1]]<=a[krmn[y]])
        return solve1(klmn[x+1],y);
    return 0;
}

bool solve2(int x,int y){//(x,y) to (1,n)
    if(x==1||y==n)return 1;
    if(a[pmx[x]]<=a[smx[y+1]])
        return solve2(x,smx[y+1]);
    if(a[pmn[x-1]]<=a[smn[y]])
        return solve2(pmn[x-1],y);
    return 0;
}

直接拿原来的做为什么不行？因为 (K,K) 不满足对于任意端点都是合法区间。