专栏文章

题解：P15289 「YLLOI-R3-T4」止战之殇

MMoss345512
P15289题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@mlqmyjsr
此快照首次捕获于
2026/02/17 21:25
前天
此快照最后确认于
2026/02/17 21:25
前天
查看原文
原题：P15289

算法分析

考虑四种贪心策略：
  • 一直往左走
  • 一直往右走
  • 往左走到头后一直往右走
  • 往右走到头后一直往左走
只需输出每种策略答案的最大值即可。
这是我的赛时思路，前两种策略可能不需要
设当前在第 tt 对怪兽之间
一直往左走：
由于不用回头，所以可以先在原地待。
  • 第一步：在原地待，直到不能再待了（Ans←Ans+(ct−2)2d,ct←(ct−2) mod 2d\text{Ans}\gets \text{Ans}+\frac{(c_t-2)}{2d},c_t\gets (c_t-2)\bmod 2d）
  • 第二步：判断
    • 如果还能往左跳一格（ct−1≥2d+2c_{t-1}\ge2d+2），就往左跳一格（t←t−1t\gets t-1），回到第一步
    • 否则如果还能往左跳两格（ct−2≥2d+2c_{t-2}\ge2d+2），就往左跳两格（t←t−2t\gets t-2），回到第一步
    • 否则就再也走不了了，退出
一直往右走同理
往左走到头后一直往右走：
往左走：
  • 第一步：判断
    • 如果还能往左跳一格甚至还能在那再待一回合（ct−1≥4d+2c_{t-1}\ge4d+2），就往左跳一格（t←t−1t\gets t-1）
    • 否则如果还能往左跳两格甚至还能在那再待一回合（ct−2≥4d+2c_{t-2}\ge4d+2），就往左跳两格（t←t−2t\gets t-2）
    • 否则如果左边两格都能跳但都不能再待一回合（2d+2≤ct−1≤4d+2,2d+2≤ct−2≤4d+22d+2\le c_{t-1}\le4d+2,2d+2\le c_{t-2}\le4d+2），就往左跳两格（这是为了保证等会能跳回来）
    • 否则判断
      • 如果还能往左跳两格（ct−2≥2d+2c_{t-2}\ge2d+2），就往左跳两格，退出往左走的过程
      • 否则如果还能往左跳一格（ct−1≥2d+2c_{t-1}\ge2d+2），就往左跳一格，退出往左走的过程
      • 否则，直接退出往左走的过程
  • 第二步：在原地待一回合，回到第一步
然后就一直往右走，同上。
往右走到头后一直往左走同理。

程序实现

CPP
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a,t;
long long d,b[1000005],c[1000005],ans,tmp;
int main(){
    scanf("%d %d %lld",&n,&a,&d);
    for(int i=1;i<n;i++)scanf("%lld",&b[i]);

    //LEFT：一直向左
    tmp=0;
    for(int i=1;i<n;i++)c[i]=b[i];
    for(t=a;;){
        // printf("%d ",t);
        tmp+=(c[t]-2)/(2*d);
        c[t]-=(c[t]-2)%(2*d);
        if(t>1 && c[t-1]-2>=2*d)t--; // 跳
        else if(t>2 && c[t-2]-2>=2*d)t-=2; // 跳
        else break;
    }
    // printf("\n");
    ans=max(ans,tmp); // 更新答案

    //RIGHT：一直向右
    tmp=0;
    for(int i=1;i<n;i++)c[i]=b[i];
    for(t=a;;){
        // printf("%d ",t);
        tmp+=(c[t]-2)/(2*d);
        c[t]-=(c[t]-2)%(2*d);
        if(t<n-1 && c[t+1]-2>=2*d)t++; // 跳
        else if(t<n-2 && c[t+2]-2>=2*d)t+=2; // 跳
        else break;
    }
    // printf("\n");
    ans=max(ans,tmp); // 更新答案

    //LEFT->RIGHT：先左后右
    tmp=0;
    for(int i=1;i<n;i++)c[i]=b[i];
    for(t=a;;){
        // printf("%d ",t);
        if(c[t]-2>=4*d)tmp++,c[t]-=2*d;
        if(t>1 && c[t-1]-2>=4*d)t--; // 跳
        else if(t>2 && c[t-2]-2>=4*d)t-=2; // 跳
        else if(t>2 && c[t-2]-2>=2*d && c[t-1]-2>=2*d)t-=2; // 跳
        else break;
    }
    if(t>2 && c[t-2]-2>=2*d)t-=2;
    else if(t>1 && c[t-1]-2>=2*d)t--;
    for(;;){ // 往回跳
        // printf("%d ",t);
        tmp+=(c[t]-2)/(2*d);
        c[t]-=(c[t]-2)%(2*d);
        if(t<n-1 && c[t+1]-2>=2*d)t++; // 跳
        else if(t<n-2 && c[t+2]-2>=2*d)t+=2; // 跳
        else break;
    }
    // printf("\n");
    ans=max(ans,tmp); // 更新答案

    //RIGHT->LEFT：先右后左
    tmp=0;
    for(int i=1;i<n;i++)c[i]=b[i];
    for(t=a;;){
        // printf("%d ",t);
        if(c[t]-2>=4*d)tmp++,c[t]-=2*d;
        if(t<n-1 && c[t+1]-2>=4*d)t++; // 跳
        else if(t<n-2 && c[t+2]-2>=4*d)t+=2; // 跳
        else if(t<n-2 && c[t+2]-2>=2*d && c[t+1]-2>=2*d)t+=2; // 跳
        else break;
    }
    if(t<n-2 && c[t+2]-2>=2*d)t+=2;
    else if(t<n-1 && c[t+1]-2>=2*d)t++;
    for(;;){ // 往回跳
        // printf("%d ",t);
        tmp+=(c[t]-2)/(2*d);
        c[t]-=(c[t]-2)%(2*d);
        if(t<n-1 && c[t+1]-2>=2*d)t++; // 跳
        else if(t<n-2 && c[t+2]-2>=2*d)t+=2; // 跳
        else break;
    }
    // printf("\n");
    ans=max(ans,tmp);

    printf("%lld",ans);
    return 0;
}

评论

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

正在加载评论...