P4803 【[CCO 2015]太阳能飞行】

说实话,这道题是我随机跳到的。初看觉得不难,结果在码代码的时候遇到很多问题。最后,八WA之后终见AC。这一定是我太蒟了

题意

我觉得本题题意也是一大难点,所以在看题目时要逐字,多看几遍。我在做的过程中,看错了两遍题目(前车之鉴),可能是本人的语文不好

本题的意思大概就是,在一个坐标系中,有n架飞机直线飞行(当然不是匀速),给定X坐标范围,又给定每架飞机的起始高度和终止高度。(其实就相当于n条一次函数的图象)。每架飞机还有一个干扰值,表示影响它正下方的飞机太阳吸收能力的强弱。现有Q个问题,请你求出区间[Si,Si+K]中,第Pi架飞机的太阳能板吸收的太阳光减少的值。我所说的难理解的地方就在这里。这里要求的并不是只要在该区间范围内能出现在第Pi架飞机上方的飞机。而是要求该区间中的每一时刻的减少的值中的最大值(可以这么理解)。

$\large\mathcal{Solution}$

刚开始真的无从下手,然后就看到。。。

这才有点眉目。

对于n架飞机,我们可以预处理出每两架飞机航线(相当于一次函数)之间的关系(要么相交,要么不相交)。而只要两架飞机不在相交点上,就一定存在其中一架飞机对另外一家飞机有影响。也就是说,任何一架飞机对于一架它可以影响的飞机,影响的范围只可能是 [0,相交点),(相交点,X](相交的情况)、[0,X](不相交的情况)。

知道了可影响范围的计算,于是一个奇妙的想法萌发,前缀和!因为对于一架飞机而言,它的被影响的值只有在经过一个交点后才会改变(因为飞机的相对位置就改变了)。因此,就可以记录下每个影响范围的起点和终点,利用区间加值的方法(这个,相信一般人都会吧)。这时候就可以利用前缀和,造一个前缀和数组,这样就可以得出每架飞机每一个时刻的被影响值。

最后回答问题的时候,只要先利用二分找出起点,然后往后跳,直到终点,中途用一个变量记录最大值即可。(不清楚的请看代码注解)

这样,这道题就解决了。

:

  • 这是本蒟蒻的第一篇题解,望支持。如有错误或有更优解,请告知。

  • CCO官网上有数据 传送门

  • 这是一篇之前blog搬过来的文章,码风勿喷 嘤嘤嘤

$\large\mathcal{Code}$

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
//本代码中的快读和快输均是之前尝试时加的,没有应该问题不大
//代码中有些地方可能写的有些复杂,可以多考虑考虑
#include<bits/stdc++.h>
#define ff(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
struct xx{
double x;
long long val;
}a[2010][2010],f[2010][2010]; //f 前缀数组
int x,kk,n,Q,b[2010],y[2010],c[2010],l[2010];
long long sum[2010];
double k[2010];
bool cmp(xx s,xx t){
return s.x<t.x;
}
inline int read(){ //优化读入
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void write(long long x) { //优化输出
int cnt=0;
if(x>9) write(x/10);
putchar(x%10+'0');
}
int main(){
x=read();kk=read();n=read();Q=read();
ff(i,1,n) b[i]=read(),y[i]=read(),c[i]=read(),k[i]=1.0*(y[i]-b[i])/x; // y[]、b[]对应一次函数y=kx+b中的k、b
ff(i,1,n-1)
ff(j,i+1,n){
int ii=i,jj=j;
if((b[ii]>b[jj]&&y[ii]<y[jj])||(b[ii]<b[jj]&&y[ii]>y[jj])){ //相交的情况
if(b[ii]<b[jj]&&y[ii]>y[jj]) swap(ii,jj);
double dx=1.0*(b[ii]-b[jj])/(k[jj]-k[ii]); //计算交点(基本操作)
a[jj][++l[jj]].val=-c[ii];a[jj][l[jj]].x=dx;sum[jj]+=c[ii]; //区间加,并记录下交点,sum数组相当于x=0时的前缀数组的值
a[ii][++l[ii]].val=c[jj];a[ii][l[ii]].x=dx;
}else{ //不相交的情况
if(b[ii]>b[jj]) swap(ii,jj);
sum[ii]+=c[jj]; //同上
}
}
ff(i,1,n){
sort(a[i]+1,a[i]+l[i]+1,cmp); //排序
long long cc=0;
int ll=l[i];
l[i]=0;
ff(j,1,ll){
cc+=a[i][j].val;
if(!(abs(a[i][j].x-a[i][j+1].x)<=1e-7)) f[i][++l[i]].x=a[i][j].x,f[i][l[i]].val=cc+f[i][l[i]-1].val,cc=0; //造前缀数组,并去重
}
}
ff(i,1,Q){
int ll,rr;
x=read();ll=read();
int l1=1,r1=l[x],st=0;
rr=ll+kk;
while(l1<=r1){ //二分找起点
int mid=(l1+r1+1)/2;
if(f[x][mid].x<=ll) st=mid,l1=mid+1; else r1=mid-1;
}
long long ans=0;
for(;st<=l[x]&&f[x][st].x<rr;st++) if(f[x][st].val+sum[x]>ans) ans=f[x][st].val+sum[x]; //点往后跳,找最大值
write(ans);
printf("\n");
}
return 0;
}


$\Huge{祝大家RP++!!!}$