P3724 大佬 题解

· · 题解

部分分

仔细理解题意，发现实际上有五个操作，你可以选择五个操作中的任意一种，问最后能不能在大佬打死你之前把大佬打死。
考场上第一眼没什么思路，但是发现数据范围不是很大，可以直接考虑暴力dfs。
将所有参数都传进去直接搜就可以获得 40pts 。 

bool dfs(int day,int hp,int c,int f,int l,int k)
{
    if(hp<0)return 0;
    if(c<0)return 0;
    if(k<0)return 0;
    if(day>n)return 0;
    if(c==0)return 1;
    if(hp<a[day+1])return 0;
    if(dfs(day+1,hp-a[day+1],c-1,f,l,k)||
       dfs(day+1,min(hp-a[day+1]+w[day+1],mc),c,f,l,k)||
       dfs(day+1,hp-a[day+1],c,f,l+1,k)||
       dfs(day+1,hp-a[day+1],c,f*l,l,k)||
       dfs(day+1,hp-a[day+1],c-f,1,0,k-1))
    return 1;
   return 0;
}

正解

1.dp天数

发现在什么时候进行攻击的伤害都一样，只是自己回血和大佬伤害不一样，其实活下来和怼大佬是相互分离的，所以可以分开考虑。
分析一下会发现不让自己死一定不会劣，因为假如今天不回血会死，回血能多活一天，那么你与其今天不要命怼大佬不如先奶自己一口然后明天接着干，所以可以简单的dp求出在 n 天最多有几天不刷水题怼大佬。
设 f_{i,j} 表示在第 i 天，剩 j 滴血的时候最多用于攻击大佬的天数 。
避免边界问题可以采用刷表转移：

dp_{i+1,j-a_{i+1}}=\max(dp_{i,j-a_{i+1}},dp_{i,j}+1) dp_{i+1,j-a_{i+1}+w_{i+1}}=\max(dp_{i+1,j-a_{i+1}+w_{i+1}},dp_{i,j})

初始化 dp_{0,mc}=0，其余为负无穷。

inline int gandp()
{
    memset(dp,128,sizeof(dp));
    dp[0][mc]=0;
    for(int i=0;i<n;i++)
    {
        for(int j=a[i+1];j<=mc;j++)
        {
            dp[i+1][j-a[i+1]]=max(dp[i+1][j-a[i+1]],dp[i][j]+1);
            dp[i+1][min(j-a[i+1]+w[i+1],mc)]=max(dp[i+1][min(j-a[i+1]+w[i+1],mc)],dp[i][j]);
        }
    }
    int day=0;  
    for(int i=1;i<=n;i++)
     for(int j=1;j<=mc;j++)
      day=max(day,dp[i][j]);    
    return day;
}

注意题目中说每回合大佬先攻击，所以只有这一轮不死才能接着操作，所以内层 j 循环从 a_{i+1} 开始。

2.bfs搜索状态

由于规定最多只能怼两次大佬，所以可以从每一次的伤害入手，处理出当前在每天可以利用大招打出多少伤害。
没有什么别的办法，参考暴力的dfs，可以将当前的等级 L，伤害 F，天数 d，拿出来枚举，在不开大的情况下，每天只有两种选择：升级或升伤害，所以可以bfs。
总的状态比较多，直接枚举至少 10^8 数量级，由于我们只想知道最终有多少符合条件的二元组 F,d 可以用来打伤害，所以对它开一个 set 进行去重就行。
然而这样还是容易超时，发现不能让大佬生命为负，一个小减枝是如果当前伤害已经超过了大佬生命值，肯定不合法，不用接着搜。
进一步思考，对于一种 伤害 F ，我们一定希望用尽量少的时间把它打出来，因为剩下的时间是你的，你可以普攻输出也可以不打，一定不劣，所以对于一个 F ，只需要保存它对应最小的 d 就行，这个可以用map实现，这样状态总数就只有 10^6 级别了。 

struct p{int l,f,d;};
queue <p> q;set <pair<int,int> >s; 
pair <int,int> h[4000050];int num;
int ma[4000050];
map <int,int> mp;
inline void bfs()
{
    q.push((p){0,1,0});
    while(q.size())
    {
        p x=q.front();q.pop();
        if(x.d==day-1)continue;//还有一天要用来打伤害
        int ga=max(x.f,x.l*x.f);//处理一下L等于0的情况
        if(x.f*x.l<=1e8&&s.find(make_pair(ga,x.d+1))==s.end())
        {
            s.insert(make_pair(ga,x.d+1));int t;
            if(mp.find(ga)==mp.end())t=++num,mp[ga]=t,h[t].first=ga,h[t].second=x.d+1;
            else t=mp[ga],h[t].second=min(h[t].second,x.d+1);//状态去重
            q.push((p){x.l+1,x.f,x.d+1});
            if(x.l>1)q.push((p){x.l,ga,x.d+1});
        }
    }
}

3.分类讨论答案

首先如果c<=day可以直接平A干掉大佬，这个可以直接判断。
然后是怼一次大佬，能打死需要满足：

F<=c F+day-1-d>=c

由于我bfs时候算的是伤害提升到 F 需要的时间，还要一天把伤害打出去，所以减一。 这个直接枚举一边也能判断。
最恶心的是怼两次大佬，首先我们把式子列出来,设两次攻击分别为 i,j:

F_i+F_j<=c F_i+F_j+day-2-d_i-d_j>=c

我们先对处理出来的二元组按 F 从小到大排序，那么我们会发现，对于满足第一个条件的 i 从小到大递增时，j 一定单调不升，所以可以每次从小到大枚举 i,同时维护单调指针 j，处理出 j 的最右段点 p，那么问题就转化成 1-p 中是否存在一个符合条件的点满足第二个式子，发现肯定是越大越优，所以对上面得到的 h 数组做一个前缀最大值就能直接判断了，复杂度为状态数，可以通过。 完整代码： 

#include <bits/stdc++.h>
using namespace std;
#define int long long 
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
int n,m,mc,c,day;
int a[105],w[105];
int dp[105][105];
inline int gandp()
{
    memset(dp,128,sizeof(dp));
    dp[0][mc]=0;
    for(int i=0;i<n;i++)
    {
        for(int j=a[i+1];j<=mc;j++)
        {
            dp[i+1][j-a[i+1]]=max(dp[i+1][j-a[i+1]],dp[i][j]+1);
            dp[i+1][min(j-a[i+1]+w[i+1],mc)]=max(dp[i+1][min(j-a[i+1]+w[i+1],mc)],dp[i][j]);
        }
    }
    int day=0;  
    for(int i=1;i<=n;i++)
     for(int j=1;j<=mc;j++)
      day=max(day,dp[i][j]);    
    return day;
}

struct p{int l,f,d;};
queue <p> q;set <pair<int,int> >s; 
pair <int,int> h[4000050];int num;
int ma[4000050];
map <int,int> mp;
inline void bfs()
{
    q.push((p){0,1,0});
    while(q.size())
    {
        p x=q.front();q.pop();
        if(x.d==day-1)continue;
        int ga=max(x.f,x.l*x.f);
        if(x.f*x.l<=1e8&&s.find(make_pair(ga,x.d+1))==s.end())
        {
            s.insert(make_pair(ga,x.d+1));int t;
            if(mp.find(ga)==mp.end())t=++num,mp[ga]=t,h[t].first=ga,h[t].second=x.d+1;
            else t=mp[ga],h[t].second=min(h[t].second,x.d+1);
            q.push((p){x.l+1,x.f,x.d+1});
            if(x.l>1)q.push((p){x.l,ga,x.d+1});
        }
    }
    sort(h+1,h+num+1);
    for(int i=1;i<=num;i++)ma[i]=max(ma[i-1],h[i].first-h[i].second);
}
inline bool gan0()
{
    if(c<=day)return 1;
    return 0;
}
inline bool gan1()
{
    for(int i=1;i<=num;i++)
    {
        if(h[i].first>c)break;
        if(h[i].first+day-1-h[i].second>=c)return 1;
    }
    return 0;
}
inline bool gan2()
{
    int i=1,j=num;
    for(int i=1;i<=num;i++)
    {   
        if(h[i].first>c)break;
        while(h[i].first+h[j].first>c)j--;
        int p=c-(day-2)-(h[i].first-h[i].second);
        if(ma[j]>=p)return 1;
    }
    return 0;
}
signed main()
{
    n=read();m=read();mc=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)w[i]=read();
    day=gandp();bfs();
    while(m--)
    {
        c=read();
        if(gan0()||gan1()||gan2())puts("1");
        else puts("0");
    }
    return 0;
}