P3724 [AH2017/HNOI2017]大佬

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 5.8k | 阅读时长 ≈ 5 分钟

P3724 [AH2017/HNOI2017]大佬

传送门

洛谷

题目描述

人们总是难免会碰到大佬。他们趾高气昂地谈论凡人不能理解的算法和数据结构，走到任何一个地方，大佬的气场就能让周围的人吓得瑟瑟发抖，不敢言语。 你作为一个 $OIER$，面对这样的事情非常不开心，于是发表了对大佬不敬的言论。 大佬便对你开始了报复，你也不示弱，扬言要打倒大佬。

现在给你讲解一下什么是大佬，大佬除了是神犇以外，还有着强大的自信心，自信程度可以被量化为一个正整数 $C$（ $1 \le C \le10^8$）， 想要打倒一个大佬的唯一方法是摧毁 Ta 的自信心，也就是让大佬的自信值等于 $0$（恰好等于$0$，不能小于 $0$）。 由于你被大佬盯上了，所以你需要准备好 $n$($1 \le n \le 100$)天来和大佬较量，因为这 $n$ 天大佬只会嘲讽你动摇你的自信，到了第$n+1$ 天，如果大佬发现你还不服，就会直接虐到你服，这样你就丧失斗争的能力了。

你的自信程度同样也可以被量化，我们用 $mc$ ($1 \le mc \le 100$)来表示你的自信值上限。

在第 $i$ 天（ $i \ge 1$），大佬会对你发动一次嘲讽，使你的自信值减小 $a_i$，如果这个时刻你的自信值小于 $0$ 了，那么你就丧失斗争能力，也就失败了（特别注意你的自信值为 $0$ 的时候还可以继续和大佬斗争）。 在这一天， 大佬对你发动嘲讽之后，如果你的自信值仍大于等于 $0$，你能且仅能选择如下的行为之一：

  1. 还一句嘴，大佬会有点惊讶，导致大佬的自信值 $C$ 减小 $1$。

  2. 做一天的水题，使得自己的当前自信值增加 $w_i$, 并将新自信值和自信值上限 $mc$ 比较，若新自信值大于 $mc$，则新自信值更新为 $mc$。例如， $mc=50$， 当前自信值为 $40$， 若$w_i=5$，则新自信值为 $45$，若 $w_i=11$，则新自信值为 $50$。

  3. 让自己的等级值 $L$ 加 $1$。

  4. 让自己的讽刺能力 $F$ 乘以自己当前等级 $L$，使讽刺能力 $F$ 更新为 $F \times L$。

  5. 怼大佬，让大佬的自信值 $C$ 减小 $F$。并在怼完大佬之后，你自己的等级 $L$ 自动降为 $0$，讽刺能力 $F$ 降为 $1$。由于怼大佬比较掉人品，所以这个操作只能做不超过 $2$ 次。

特别注意的是，在任何时候，你不能让大佬的自信值为负，因为自信值为负，对大佬来说意味着屈辱，而大佬但凡遇到屈辱就会进化为更厉害的大佬直接虐飞你。在第 $1$ 天，在你被攻击之前，你的自信是满的（初始自信值等于自信值上限 $mc$）， 你的讽刺能力 $F$ 是 $1$， 等级是 $0$。

现在由于你得罪了大佬，你需要准备和大佬正面杠，你知道世界上一共有 $m$（ $1 \le m \le 20$ ）个大佬，他们的嘲讽时间都是 $n$ 天，而且第 $i$ 天的嘲讽值都是 $a_i$不管和哪个大佬较量，你在第 $i$ 天做水题的自信回涨都是 $w_i$ 这 $m$ 个大佬中只会有一个来和你较量（ $n$ 天里都是这个大佬和你较量），但是作为你，你需要知道对于任意一个大佬，你是否能摧毁他的自信，也就是让他的自信值恰好等于 $0$。和某一个大佬较量时，其他大佬不会插手。

输入输出格式

输入格式：

第一行三个正整数 $n,m,mc$。分别表示有 $n$ 天和 $m$ 个大佬, 你的自信上限为 $mc$。

接下来一行是用空格隔开的 $n$ 个数，其中第 $i$($1 \le i \le n$)个表示 $a_i$。

接下来一行是用空格隔开的 $n$ 个数，其中第 $i$($1 \le i \le n$)个表示 $w_i$。

接下来 $m$ 行，每行一个正整数，其中第 $k$($1 \le k \le m$)行的正整数 $C_k$表示第 $k$ 个大佬的初始自信值。

输出格式：

共 $m$ 行，如果能战胜第 $k$ 个大佬（让他的自信值恰好等于 $0$），那么第 $k$ 行输出 $1$，否则输出 $0$。

输入输出样例

输入样例#1：

30 20 30
15 5 24 14 13 4 14 21 3 16 7 4 7 8 13 19 16 5 6 13 21 12 7 9 4 15 20 4 13 12
22 21 15 16 17 1 21 19 11 8 3 28 7 10 19 3 27 17 28 3 26 4 22 28 15 5 26 9 5 26
30
10
18
29
18
29
3
12
28
11
28
6 1 6
27
27
18
11
26
1

输出样例#1：

0
1
1
0
1
0
1
1
0
0
0
1
1
1
1
1
1
0
0
1

说明

$20\%$数据保证: $1 \le n \le 10$。

另有 $20\%$数据保证:$1 \le C_i,n,mc \le 30$。

$100\%$数据保证: $1 \le n,mc \le 100,1 \le m \le 20,1 \le a_i,w_i \le mc,1 \le C_i \le10^8$

分析

首先仔细观察几种操作，发现只有一个和自己的自信值有关（操作2）。 因此，自己死不死与怼大佬无关。 所以，相当于拆成两个部分，一个是怼大佬，另外一个是让自己活着。
所以，我们先做一次$dp$，求出最多可以空出多少天来怼大佬，也就是刷水题的最少次数。
我们设$f _ {i,j}$表示在第$i$天，我们的自信值为$j$时刷水题的最少次数。
显然：

第一个方程表示我们硬抗大佬一击换取怼大佬的时间。
第二个方程表示我们刷题补自信值避免被怼死。
这样，恢复自信与怼大佬两个分开，互相不影响。
现在的问题就变成了给你$N$天，能否怼死大佬？
我们怼大佬只与两个因素有关：天数和嘲讽值。
因此，求出所有的可行的天数和嘲讽值的集合，按照嘲讽值从大到小排序。至于怎么求，暴力$BFS$+判重就行了。
不怼或者怼一次解决大佬的情况很容易判断。
怼一次就是$C-f_1 \ge 0$且$C-f_1 \le D-d_1$，不怼就是 $C \ge 0$且$C \le D$。
现在要解决的问题是怼两次大佬。
不妨设两次怼大佬花费的天数分别是$d_1,d_2$，总共可以怼$D$天。嘲讽值分别是$f_1,f_2$。
我们可以列出不等式：

很好理解，显然操作5是一次操作，所以如果$f_1+f_2 > C$，那么大佬的自信值就小于$0$了，凉凉。
第二个操作就是表示我们能够怼死大佬。
但为什么第二个不等式可以大于$C$呢？
因为我们是多次操作，等大佬的自信值等于$0$时就胜利了，不存在小于$0$的情况。
考虑按照$f$为第一关键字，$d$为第二关键字排序。
现在维护两个指针，分别从大往小和从小往大枚举，每次保证$f_1+f_2 \le C$
因为我们固定了一个方向，不妨固定了$f_1$。
所以，此时的定值是$f_1,d_1,D,C$。 那么，这个时候要求的就是$f2-d2$的最大值。
在$f_2$从小到大扫的过程中，显然是单调的，因此不需要再从头开始扫，直接继承上一次的指针位置继续向后即可。

参考资料

yybyyb的洛谷题解 这篇题解绝大部分抄转自yybyyb的洛谷题解。
时钟之门的洛谷题解

代码

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
110
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
#define maxn 110
#define INF 0x7fffffff
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
	read(b...);
}
struct Node
{
	int x;
	int y;
	bool operator < (const Node &b)
	const{
		if(x!=b.x)return x<b.x;
		return y<b.y;
	}
}zt[maxn*maxn*maxn];
struct Data
{
	int x;
	int y;
	int z;
};
int n,m,mc,cnt,D,MC,a[maxn],w[maxn],C[maxn],f[maxn][maxn];
map<Node,int>mp;
void bfs()
{
	queue<Data>Q;
	Q.push((Data){1,1,0});
	while(!Q.empty())
	{
		Data t=Q.front();Q.pop();
		if(t.x==D)continue;
		Q.push((Data){t.x+1,t.y,t.z+1});
		if(t.z>1&&1ll*t.y*t.z<=1ll*MC&&!mp.count((Node){t.x+1,t.y*t.z}))
		{
			zt[++cnt]=(Node){t.y*t.z,t.x+1};
			Q.push((Data){t.x+1,t.y*t.z,t.z});
			mp[(Node){t.x+1,t.y*t.z}]=true;
		}
	}
}
int main()
{
	read(n,m,mc);
	for(int i=1;i<=n;i++)a[i]=read<int>();
	for(int i=1;i<=n;i++)w[i]=read<int>();
	for(int i=1;i<=m;i++)MC=max(MC,C[i]=read<int>());
	for(int i=1;i<=n;i++)
		for(int j=a[i];j<=mc;j++)
		{
			f[i][j-a[i]]=max(f[i][j-a[i]],f[i-1][j]+1);
			f[i][min(mc,j-a[i]+w[i])]=max(f[i][min(mc,j-a[i]+w[i])],f[i-1][j]);
		}
	for(int i=1;i<=n;i++)
		for(int j=0;j<=mc;j++)
			D=max(D,f[i][j]);
	bfs();
	sort(zt+1,zt+1+cnt);
	for(int i=1;i<=m;i++)
	{
		if(C[i]<=D)
		{
			puts("1");
			continue;
		}
		int minn=-INF,flag=false;
		for(int j=cnt,k=1;j>=1;j--)
		{
			if(zt[j].x<=C[i]&&C[i]-zt[j].x<=D-zt[j].y)
			{
				flag=true;
				break;
			}
			while(k<=cnt&&zt[j].x+zt[k].x<=C[i])
				minn=max(minn,zt[k].x-zt[k].y),k+=1;
			if(D-zt[j].y+zt[j].x+minn>=C[i])
			{
				flag=true;
				break;
			}
		}
		puts(flag? "1":"0");
	}
    return 0;
}