Luogu

BZOJ

分析

神题。

首先,设 $f[i][j]$ 表示前 $i$ 天,第 $i$ 天自信值为 $j$ ,最多能不刷题几天。然后通过简单的$\mathrm{DP}$,可以求出来。

然后设 $d$ 为 $f$ 数组中的最大值,也就是说最多可以拿 $d$ 天出来与大佬斗争。

然后考虑$\mathrm{bfs}$扩展出所有$(\text{天数},\text{讽刺能力})$的状态,把这些状态存起来。这里要注意判重,可以手写哈希表。

现在要考虑的问题是两次怼大佬。

设两次怼大佬的天数分别是 $s_1$ 、 $s_2$ ,讽刺能力分别是 $f_1$ 、 $f_2$ 。

可以列出不等式:( $maxc$ 为 $c$ 数组中最大的)

$\begin{cases}f_1+f-2\leq maxc\\f_1+f_2+(d-s_1-s_2)\geq maxc\end{cases}$

于是可以以$f$为第一关键字,$s$为第二关键字排序,然后维护两个指针 $i$ 和 $j$,保证$f_i+f_j\leq maxc$。

考虑固定 $f_i$,现在要求的是 $f_2-s_2$ 的最大值。

然后发现 $j$ 是单调的,于是就可以做到$O(\text{状态数})$的 $\mathrm{check}$ 了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

template<typename T>
inline void chkmax(T& x,T y) { if (y>x) x=y; }
template<typename T>
inline void chkmin(T& x,T y) { if (y<x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10;
const int MOD=1000007;
const int inf=0x3f3f3f3f;

struct hash_table {
    struct oho { int u,v,nxt; } e[2000000];
    int head[MOD+5],cnt;
    inline void insert(int u,int v) {
        int tmp=(1ll*u*100+v)%MOD;
        e[++cnt]=(oho){u,v,head[tmp]},head[tmp]=cnt;
    }
    inline int query(int u,int v) {
        int tmp=(1ll*u*100+v)%MOD;
        for (re int i=head[tmp];i;i=e[i].nxt)
            if (e[i].u==u&&e[i].v==v) return 1;
        return 0;
    }
} H;

int n,m,mc,d,maxc;
int a[N],w[N],c[N];
int f[N][N];

struct node { int s,F,L; };
struct state { int s,F; } S[2000000];
bool operator <(state a,state b) {
    if (a.F==b.F) return a.s<b.s;
    else return a.F<b.F;
}

int top=0;

inline void bfs() {
    queue<node> Q; Q.push((node){1,1,0});
    while (!Q.empty()) {
        node x=Q.front(); Q.pop();
        int s=x.s,F=x.F,L=x.L;
        if (s<d) {
            Q.push((node){s+1,F,L+1}); //level up
            if (L>1&&1ll*F*L<=1ll*maxc&&!H.query(F*L,s+1)) {
                Q.push((node){s+1,F*L,L}); //atk up
                S[++top]=(state){s+1,F*L};
                H.insert(F*L,s+1);
            }
        }
    }
}

int main() {
    n=read(),m=read(),mc=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=n;++i) w[i]=read();
    for (re int i=1;i<=m;++i) c[i]=read(),chkmax(maxc,c[i]);
    //dp
    for (re int i=1;i<=n;++i)
        for (re int j=a[i];j<=mc;++j) {
            chkmax(f[i][j-a[i]],f[i-1][j]+1);
            chkmax(f[i][min(mc,j-a[i]+w[i])],f[i-1][j]);
        }
    for (re int i=1;i<=n;++i)
        for (re int j=0;j<=mc;++j)
            chkmax(d,f[i][j]);
    //bfs
    bfs();
    //solve
    sort(S+1,S+top+1);
    for (re int i=1;i<=m;++i) {
        if (c[i]<=d) { puts("1"); continue; }
        int ans=0,mn=inf;
        for (re int j=top,k=1;j>=1;--j) {
            while (k<top&&S[j].F+S[k].F<=c[i]) chkmin(mn,S[k].s-S[k].F),++k;
            if (mn+S[j].s-S[j].F+c[i]<=d) { ans=1; break; }
            if (S[j].F<=c[i]&&c[i]-S[j].F+S[j].s<=d) { ans=1; break; }
        }
        printf("%d\n",ans);
    }
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 13 PM