BZOJ4828: [Hnoi2017]大佬

142 阅读 0 评论 94 点赞

我是靠谱客的博主陶醉抽屉，这篇文章主要介绍BZOJ4828: [Hnoi2017]大佬，现在分享给大家，希望可以做个参考。

首先我们每一回合不选择苟活（刷水题）的话，我们能做的事和这是第几个回合无关
那我们肯定希望有尽量多的回合做苟活之外的事
先DP一下我们在存活的情况下，最多有多少个回合有空
然后这些回合里，我们可以打1，升级或发大招
然后…我们最多操作n次，C<=1e8（题解说）状态数是不多的
（用bfs+hash，实测100次时搜出的状态是700w+）
然后对于这m个大佬，每个可以 $O(n)$ 判断这些状态两两组合能不能凑出C（加入0状态，设s为伤害，i为需要的回合数，k为可以操作的回合数，那么C-s1-s2+i1+i2<=k，所以C+(-s1+i1)-s2+i2<=k，记录一下左指针历史(-s1+i1)的最小值，和当前的右指针判是否可行）

总复杂度 $O(n*mc+bfs+nm)$

code：

复制代码

#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

inline void up(int &x,const int &y){if(x<y)x=y;}
const int maxm = 22;
const int maxn = 110;
const ll inf = 1e8;
const int maxh = 8000000;
const int hashmod = 7160117;

int n,m,mc,C;
int a[maxn],w[maxn];
int f[maxn][maxn];

int q[maxh],tail;
struct Hash
{
    int s,x,i;
    Hash(){s=0;}
    Hash(const int _s,const int _x,const int _i){s=_s;x=_x;i=_i;}
}h[maxh],s[maxh];
inline int get_hash(const int s,const int x){return ((ll)s*233333+x)%hashmod;}
void ins(const int s,const int x,const int i)
{
    int hi=get_hash(s,x);
    while(h[hi].s)
    {
        if(h[hi].s==s&&h[hi].x==x) return;
        hi++;
        if(hi==maxh) hi=0;
    }
    h[hi].s=s; h[hi].x=x; h[hi].i=i; q[++tail]=hi;
}
inline bool cmp(const Hash x,const Hash y){return x.s==y.s?x.i<y.i:x.s<y.s;}

int main()
{
    scanf("%d%d%d",&n,&m,&mc);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);

int mx=0;
    memset(f,-1,sizeof f);
    f[0][mc]=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=mc;j++) if(f[i][j]!=-1)
            if(j-a[i+1]>=0) 
                up(f[i+1][j-a[i+1]],f[i][j]+1),
                up(f[i+1][min(mc,j-a[i+1]+w[i+1])],f[i][j]);
    }
    for(int i=1;i<=n;i++) for(int j=0;j<=mc;j++) up(mx,f[i][j]);

h[q[tail=1]=1]=Hash(1,0,1);
    for(int i=1;i<=tail;i++)
    {
        const int x=q[i];
        if((ll)h[x].s*h[x].x>inf||h[x].i>=mx) continue;

if(h[x].x) ins(h[x].s*h[x].x,h[x].x,h[x].i+1);
        ins(h[x].s,h[x].x+1,h[x].i+1);
    }
    //printf("%dn",tail);
    for(int i=1;i<=tail;i++) s[i]=h[q[i]];
    sort(s+1,s+tail+1,cmp);
    int hn=0;
    s[0].s=s[1].s-1;
    for(int i=1;i<=tail;i++)
        if(s[i].s!=s[i-1].s) h[++hn]=s[i];
    h[0]=Hash(0,0,0);

while(m--)
    {
        scanf("%d",&C);
        int p1=0,p2=hn;
        bool flag=false; int mn=INT_MAX;
        for(;h[p1].s<=C;p1++)
        {
            if(p1>p2) break;
            while(h[p1].s+h[p2].s>C) p2--;
            int tk=h[p1].i-h[p1].s;
            if(mn>tk) mn=tk;
            int k=C+mn-h[p2].s+h[p2].i;
            if(k<=mx) { flag=true; break; }
        }
        if(flag) puts("1");
        else puts("0");
    }

return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

inline void up(int &x,const int &y){if(x<y)x=y;}
const int maxm = 22;
const int maxn = 110;
const ll inf = 1e8;
const int maxh = 8000000;
const int hashmod = 7160117;

int n,m,mc,C;
int a[maxn],w[maxn];
int f[maxn][maxn];

int q[maxh],tail;
struct Hash
{
    int s,x,i;
    Hash(){s=0;}
    Hash(const int _s,const int _x,const int _i){s=_s;x=_x;i=_i;}
}h[maxh],s[maxh];
inline int get_hash(const int s,const int x){return ((ll)s*233333+x)%hashmod;}
void ins(const int s,const int x,const int i)
{
    int hi=get_hash(s,x);
    while(h[hi].s)
    {
        if(h[hi].s==s&&h[hi].x==x) return;
        hi++;
        if(hi==maxh) hi=0;
    }
    h[hi].s=s; h[hi].x=x; h[hi].i=i; q[++tail]=hi;
}
inline bool cmp(const Hash x,const Hash y){return x.s==y.s?x.i<y.i:x.s<y.s;}

int main()
{
    scanf("%d%d%d",&n,&m,&mc);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);

    int mx=0;
    memset(f,-1,sizeof f);
    f[0][mc]=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=mc;j++) if(f[i][j]!=-1)
            if(j-a[i+1]>=0) 
                up(f[i+1][j-a[i+1]],f[i][j]+1),
                up(f[i+1][min(mc,j-a[i+1]+w[i+1])],f[i][j]);
    }
    for(int i=1;i<=n;i++) for(int j=0;j<=mc;j++) up(mx,f[i][j]);

    h[q[tail=1]=1]=Hash(1,0,1);
    for(int i=1;i<=tail;i++)
    {
        const int x=q[i];
        if((ll)h[x].s*h[x].x>inf||h[x].i>=mx) continue;

        if(h[x].x) ins(h[x].s*h[x].x,h[x].x,h[x].i+1);
        ins(h[x].s,h[x].x+1,h[x].i+1);
    }
    //printf("%dn",tail);
    for(int i=1;i<=tail;i++) s[i]=h[q[i]];
    sort(s+1,s+tail+1,cmp);
    int hn=0;
    s[0].s=s[1].s-1;
    for(int i=1;i<=tail;i++)
        if(s[i].s!=s[i-1].s) h[++hn]=s[i];
    h[0]=Hash(0,0,0);

    while(m--)
    {
        scanf("%d",&C);
        int p1=0,p2=hn;
        bool flag=false; int mn=INT_MAX;
        for(;h[p1].s<=C;p1++)
        {
            if(p1>p2) break;
            while(h[p1].s+h[p2].s>C) p2--;
            int tk=h[p1].i-h[p1].s;
            if(mn>tk) mn=tk;
            int k=C+mn-h[p2].s+h[p2].i;
            if(k<=mx) { flag=true; break; }
        }
        if(flag) puts("1");
        else puts("0");
    }

    return 0;
}