P3724 [AH2017/HNOI2017]大佬

传送门

发现保持自信和做其他事情互不干扰，可以直接做一次 $dp$ 求出最多能空出几天来怼大佬

然后就变成给你若干天，是否能怼死大佬，考虑求出所有的 天数和输出的嘲讽值集合，因为天数不多，嘲讽值增长很快

所以直接 $BFS$ + $map$ 去重就行了

不怼大佬或者只怼一次的情况容易计算，现在问题是怼两次的情况怎么搞

设两次怼的嘲讽值分别为 $fx,fy$，输出这些嘲讽值需要的天数分别为 $dx,dy$

如果要怼死大佬，只要满足限制 $fx+fy<=C$，$C-fx-fy<=D-dx-dy$，把刚刚得到的集合按 嘲讽值，天数 双关键字排序

考虑维护两个指针 $x,y$，$x$ 从大到小，$y$ 从小到大，在枚举 $x$ 的时候移动 $y$ 使得 $y$ 满足 $fx+fy<=C$

把第二个式子变一下 $C-fx<=D-dx+(fy-dy)$

当我们固定了 $x$ 以后，要求的就是满足 $fx+fy<=C$ 中的 $fy-dy$ 的最大值

因为随着 $fx$ 增加，之前枚举到的 $fy$ 一直满足条件，所以直接搞一个变量维护当前 $fy-dy$ 的最大值即可

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<map>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=,M=1e7+,INF=1e9+;

int n,m,mc,a[N],w[N],C[N];

int f[N][N],D,tot,mx;

struct dat{

    int d,f,l;

    dat (int a=,int b=,int c=) { d=a,f=b,l=c; }

};

queue <dat> Q;

struct datt{

    int f,d;

    datt (int a=,int b=) { f=a,d=b; }

    inline bool operator < (const datt &tmp) const {

        return f!=tmp.f ? f<tmp.f : d<tmp.d;

    }

}T[M];

map <datt,bool> vis;

void BFS()

{

    dat x=dat(,,); Q.push(x);

    while(!Q.empty())

    {

        x=Q.front(); Q.pop(); if(x.d==D) continue;

        Q.push(dat(x.d+,x.f,x.l+));

        if(x.l>&&1ll*x.f*x.l<=mx&&!vis[datt(x.f*x.l,x.d+)])

        {

            Q.push((dat){x.d+,x.f*x.l,x.l});

            T[++tot]=datt(x.f*x.l,x.d+); vis[datt(x.f*x.l,x.d+)]=;

            //只把有用的加入集合

        }

    }

}

int main()

{

    n=read(),m=read(),mc=read();

    for(int i=;i<=n;i++) a[i]=read();

    for(int i=;i<=n;i++) w[i]=read();

    for(int i=;i<=m;i++) C[i]=read(),mx=max(mx,C[i]);

    for(int i=;i<=n;i++)

        for(int j=a[i];j<=mc;j++)

        {

            f[i][j-a[i]]=max(f[i][j-a[i]],f[i-][j]+);

            f[i][min(j-a[i]+w[i],mc)]=max(f[i][min(j-a[i]+w[i],mc)],f[i-][j]);

        }

    for(int i=;i<=n;i++)

        for(int j=;j<=mc;j++) D=max(D,f[i][j]);

    BFS(); sort(T+,T+tot+);

    for(int i=;i<=m;i++)

    {

        if(C[i]<=D) { printf("1\n"); continue; }

        bool flag=; int GG=-INF;

        for(int x=tot,y=;x;x--)

        {

            while(y<=tot && T[x].f+T[y].f<=C[i]) GG=max(GG,T[y].f-T[y].d),y++;

            if( y<=tot && C[i]-T[x].f<=D-T[x].d+GG ) { flag=; break; }

            if(T[x].f<=C[i] && C[i]-T[x].f<=D-T[x].d) { flag=; break; }

        }

        printf("%d\n",flag);

    }

    return ;

}