Fork me on GitHub

[POI2015]WIL-Wilcze题解

其实这本来是$QBXT$的$T2$,但是由于毒瘤$zhw$跑得快(雾),导致我们发现这是某$poi$原题。

zhw

首先看题面:题目链接

详细读了一遍之后,其实对于这道题,我的第一反应是贪心(也许是因为我太菜了)。
然后打了一遍,小样例过了,然后被大样例$hack$。

之后我又用命分析了一下。可以发现,因为题目中保证每个数的值全部$>=0$,即每个数都是正整数
所以我们与其选长度不到$d$的区间删除,不如直接选择长度为$d$的区间删除。

那么在一段长度已知的序列中,长度为$d$的子序列个数是已知的,那么我们就可以预处理出每一段长度为$d$的子序列。
然后我们又发现,题目中要求区间的长度不超过p,那么我们很明显的可以想到尺取法

然后我们就可以用单调队列来维护我们预处理出的这些长度为$d$的子序列。然后对于区间长度取$max$就是答案了。

最后怒斥一波出原题的出题人$qaq$….(虽然$zhw$很帅)

代码:

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
#include<cstdio>
#include<deque>
typedef long long ll;
using std::deque;
const ll N=2000010;
ll n,p,d;
ll a[N];
ll sum[N];
ll hea[N];
struct Node
{
ll pos,val;
Node(ll pos,ll val):pos(pos),val(val){}
Node(){}
};
inline void read(ll &x)
{
ll s=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
x=s*w;
return;
}
deque<Node>q;

int main()
{
read(n);read(p);read(d);
for(int i=1;i<=n;i++)read(a[i]),sum[i]=sum[i-1]+a[i];
for(int i=1;i<=n-d;i++)
hea[i]=sum[i+d]-sum[i];
for(int i=n-d+1;i<=n;i++)
hea[i]=sum[n]-sum[i];
ll ans=0;
int l=0;
for(int i=d+1;i<=n;i++)
{
while(!q.empty()&&q.back().val<hea[i-d])q.pop_back();
q.push_back(Node(i-d,hea[i-d]));
while(l<i-d&&sum[i]-sum[l]-q.front().val>p)
{
l++;
while(l>q.front().pos)q.pop_front();
}
ans=std::max(ans,(ll)i-l);
}
printf("%lld",ans);
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:[POI2015]WIL-Wilcze题解

文章作者:KRrrrrrrrr

发布时间:2018年11月02日 - 10:11

最后更新:2019年11月05日 - 08:11

原始链接:http://krrrr.xyz/2018/11/02/POI2015-WIL-Wilcze题解/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。