[HNOI2017]大佬

C++14(g++5.4) 解法, 执行用时: 318ms, 内存消耗: 28772K, 提交时间: 2019-10-29 22:08:10

// luogu-judger-enable-o2
//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;
}

C++11(clang++ 3.9) 解法, 执行用时: 516ms, 内存消耗: 31496K, 提交时间: 2020-04-03 11:59:25

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 111
#define ft(i) zt[i].first
#define sd(i) zt[i].second
inline int read()
{
	RG int x=0,t=1;
	RG char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') t=-1,ch=getchar();
	while(ch<='9'&&ch>='0') x=x*10+ch-48,ch=getchar();
	return x*t;
}
int f[MAX][MAX];
int n,m,MC,Day,a[MAX],w[MAX],C[MAX];
struct Node
{
	int i,F,L;
};
pair<int,int> zt[1111111];
int tot,mx;
int MOD=1000007;
struct Hash
{
	struct Line
	{
		int x,y,next;
	}e[1111111];
	int h[1000007+1],cnt;
	void Add(int x,int y)
	{
		int pos=(1ll*x*101+y)%MOD;
		e[++cnt]=(Line){x,y,h[pos]};
		h[pos]=cnt;
	}
	bool Query(int x,int y)
	{
		int pos=(1ll*x*101+y)%MOD;
		for(int i=h[pos];i;i=e[i].next)
		if(e[i].x==x&&e[i].y==y) return true;
		return false;
	}
}Map;
void BFS()
{
	queue<Node> Q;
	Q.push((Node){1,1,0});
    while(!Q.empty())
    {
    	Node u=Q.front();
    	Q.pop();
    	if(u.i==Day) continue;
    	Q.push((Node){u.i+1,u.F,u.L+1});
    	if(u.L>1&&1ll*u.F*u.L<=1ll*mx&&!Map.Query(u.F*u.L,u.i+1))
    	{
    		Q.push((Node){u.i+1,u.F*u.L,u.L});
    		zt[++tot]=make_pair(u.F*u.L,u.i+1);
    		Map.Add(u.F*u.L,u.i+1);
		}
	}
}
int 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();
	for(int i=1;i<=m;++i)
	mx=max(mx,C[i]=read());
	for(int i=1;i<=n;++i)
	for(int j=a[i];j<=MC;++j)
	{
		f[i][j-a[i]]=max(f[i-1][j]+1,f[i][j-a[i]]);
		f[i][min(j-a[i]+w[i],MC)]=max(f[i-1][j],f[i][min(j-a[i]+w[i],MC)]);
	}
	for(int i=1;i<=n;++i)
	for(int j=1;j<=MC;++j)
	Day=max(Day,f[i][j]);
	BFS();
	sort(&zt[1],&zt[tot+1]);
	for(int i=1;i<=m;++i)
	{
		if(C[i]<=Day) 
		{
			puts("1");
			continue;
		}
		bool fl=false;
		int mm=1e9;
		for(int j=tot,k=1;j;--j)
		{
			while(k<tot&&ft(k)+ft(j)<=C[i])
			mm=min(mm,sd(k)-ft(k)),++k;
			if(mm+C[i]-ft(j)<=Day-sd(j))
			{
				fl=true;
				break;
			}
			if(ft(j)<=C[i]&&C[i]-ft(j)<=Day-sd(j))
			{
				fl=true;
				break;
			}
		}
		fl? puts("1"):puts("0");
	}
	return 0;
}

详情