自动搬运

查看原文

来自洛谷，原作者为

	yybyyb **

搬运于2025-08-24 21:52:03，当前版本为作者最后更新于2018-03-30 21:53:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题好神啊。

首先仔细观察几种操作，发现和自己的自信值有关的只有一个。 因此，自己死不死与怼大佬无关。 所以，相当于拆成两个部分，一个是怼大佬，另外一个是让自己的自信值大于$0$。

所以，我们先做一次$dp$，求出最多可以空出多少天来怼大佬，也就是刷水题的最少次数。

这样，恢复自信与怼大佬两个分开，互相不影响。

现在的问题就变成了给你$N$天，能否怼死大佬？

我们怼大佬只与两个因素有关：天数和嘲讽值。

因此，求出所有的可行的天数和嘲讽值的集合，按照嘲讽值从大到小排序。至于怎么求，暴力$BFS$+$Hash$判重就行了。

不怼或者怼一次解决大佬的情况很容易判断（如果你只判断这个就可以拿到$40$分了。。）

现在要解决的问题是怼两次大佬。

不妨设两次怼大佬花费的天数分别是$d1,d2$，总共可以怼$D$天。嘲讽值分别是$f1,f2$。

我们可以列出不等式：

考虑按照$f$为第一关键字，$d$为第二关键字排序。

现在维护两个指针，分别从大往小和从小往大枚举，每次保证$fi+fj<=C$

因为我们固定了一个方向，不妨固定了$fi$。

所以，此时的定值是$fi,di,D,C$。 那么，这个时候要求的就是$f2-d2$的最大值。

在从小到大扫的过程中，显然是单调的，因此不需要再从头开始扫，直接继承上一次的指针位置继续向后即可。

#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;
}