洛谷P2895、P8818 两题的题解

25分

先看最简单的情况。就是当A、B数组均为正数的时候，直接输出A的最大值和最小值的乘积。

#include <bits/stdc++.h>
using namespace std;
long long n,m,q,x[1005],y[1005];
int main()
{
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
{
cin>>x[i];
}
for(int i=1;i<=m;i++)
{
cin>>y[i];
}
while(q—)
{
long long l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
long long maxn=–1e17,minn=1e17;//long long 类型，不能开-1e8和1e8
for(long long i=l1;i<=r1;i++) maxn=max(maxn,x[i]);
for(long long i=l2;i<=r2;i++) minn=min(minn,y[i]);
cout<<maxn*minn<<endl;
}
return 0;
}

60分

不算0。
有以下这几种情况，分别对应要求的最值是什么：

十分复杂，但是思路简单，也很细节，直接给代码：

#include <bits/stdc++.h>
using namespace std;
long long n,m,q,a[1005],b[1005];
long long check(int l1,int r1,int l2,int r2){
int typea0=0,typeb0=0;
int typea=0,typeb=0;
long long maxaz=0,minaz=1e17,maxaf=–1e17,minaf=0;
long long maxbz=0,minbz=1e17,maxbf=–1e17,minbf=0;
long long ans=0;
for(int i=l1;i<=r1;i++){
if(a[i]<0){
maxaf=max(maxaf,a[i]);
minaf=min(minaf,a[i]);
}else if(a[i]>0){
maxaz=max(maxaz,a[i]);
minaz=min(minaz,a[i]);
}else typea0=1;
if(typea==3) continue;
if(a[i]>0&&typea==2) typea=3;
else if(a[i]>0&&typea==0) typea=1;
else if(a[i]<0&&typea==0) typea=2;
else if(a[i]<0&&typea==1) typea=3;
}
for(int i=l2;i<=r2;i++){
if(b[i]<0){
maxbf=max(maxbf,b[i]);
minbf=min(minbf,b[i]);
}else if(b[i]>0){
maxbz=max(maxbz,b[i]);
minbz=min(minbz,b[i]);
}else typeb0=1;
if(typeb==3) continue;
if(b[i]>0&&typeb==2) typeb=3;
else if(b[i]>0&&typeb==0) typeb=1;
else if(b[i]<0&&typeb==0) typeb=2;
else if(b[i]<0&&typeb==1) typeb=3;
}
if(typea==1){
if(typeb==1) ans=maxaz*minbz;
else if(typeb==2) ans=minaz*minbf;
else ans=minaz*minbf;
}else if(typea==2){
if(typeb==1) ans=maxaf*maxbz;
else if(typeb==2) ans=minaf*maxbf;
else ans=maxaf*maxbz;
}else{
if(typeb==1) ans=maxaz*minbz;
else if(typeb==2) ans=minaf*maxbf;
else ans=max(minaz*minbf,maxaf*maxbz);
}
if(typea0) ans=max(ans,0ll);
if(typeb0) ans=min(ans,0ll);
return ans;
}
int main()
{
cin>>n>>m>>q;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
while(q—){
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
cout<<check(l1,r1,l2,r2)<<endl;
}
return 0;
}

100分

前面是用循环去找区间的极值的，这里改用st表。

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+5;
const int LOG=17;//17约=log1e5
const ll INF=1e17;
int n,m,q,a[100005],b[100005];
ll lg2[MAXN];
ll stazmax[LOG][MAXN];
ll stazmin[LOG][MAXN];
ll stafmax[LOG][MAXN];
ll stafmin[LOG][MAXN];
ll stbzmax[LOG][MAXN];
ll stbzmin[LOG][MAXN];
ll stbfmax[LOG][MAXN];
ll stbfmin[LOG][MAXN];
ll pa[MAXN];
ll pb[MAXN];
void initlog(int n)//预处理lg2
{
lg2[1]=0;
for(int i=2;i<=n;i++)
{
lg2[i]=lg2[i/2]+1;
}
}
void buildst(ll stmax[LOG][MAXN],ll stmin[LOG][MAXN],int len)//建表
{
for(int k=1;(1<<k)<=n;k++)
{
int h=1<<(k–1);
for(int i=1;i+(1<<k)–1<=len;i++)
{
stmax[k][i]=max(stmax[k–1][i],stmax[k–1][i+h]);
stmin[k][i]=min(stmin[k–1][i],stmin[k–1][i+h]);
}
}
}
ll qmax(ll st[LOG][MAXN],int l,int r)//查询
{
int k=lg2[r–l+1];
return max(st[k][l],st[k][r–(1<<k)+1]);
}
ll qmin(ll st[LOG][MAXN],int l,int r)//查询
{
int k=lg2[r–l+1];
return min(st[k][l],st[k][r–(1<<k)+1]);
}
ll check(int l1,int r1,int l2,int r2)
{
bool typea0=0,typeb0=0;
int typea=0,typeb=0;
ll maxaz=0,minaz=INF,maxaf=–INF,minaf=0;
ll maxbz=0,minbz=INF,maxbf=–INF,minbf=0;
ll ans=0;
//查询A
maxaz=qmax(stazmax,l1,r1);
minaz=qmin(stazmin,l1,r1);
maxaf=qmax(stafmax,l1,r1);
minaf=qmin(stafmin,l1,r1);
typea0=(pa[r1]–pa[l1–1]>0);
bool haz=(maxaz!=0&&minaz!=INF);
bool haf=(maxaf!=–INF&&minaf!=0);
if(!haz&&!haf) return 0;//A全是0
if(haz&&!haf) typea=1;
else if(!haz&&haf) typea=2;
else if(haz&&haf) typea=3;
else typea=0;
//查询B
maxbz=qmax(stbzmax,l2,r2);
minbz=qmin(stbzmin,l2,r2);
maxbf=qmax(stbfmax,l2,r2);
minbf=qmin(stbfmin,l2,r2);
typeb0=(pb[r2]–pb[l2–1]>0);
bool hbz=(maxbz!=0&&minbz!=INF);
bool hbf=(maxbf!=–INF&&minbf!=0);
if(!hbz&&!hbf) return 0;//B全是0
if(hbz&&!hbf) typeb=1;
else if(!hbz&&hbf) typeb=2;
else if(hbz&&hbf) typeb=3;
else typeb=0;
//分类讨论
if(typea==1)
{
if(typeb==1) ans=maxaz*minbz;
else if(typeb==2) ans=minaz*minbf;
else ans=minaz*minbf;
}
else if(typea==2)
{
if(typeb==1) ans=maxaf*maxbz;
else if(typeb==2) ans=minaf*maxbf;
else ans=maxaf*maxbz;
}
else
{
if(typeb==1) ans=maxaz*minbz;
else if(typeb==2) ans=minaf*maxbf;
else ans=max(minaz*minbf,maxaf*maxbz);
}
if(typea0) ans=max(ans,0ll);
if(typeb0) ans=min(ans,0ll);
return ans;
}
int main()
{
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
pa[i]=pa[i–1]+(a[i]==0);
if(a[i]>0)
{
stazmax[0][i]=stazmin[0][i]=a[i];
stafmax[0][i]=–INF;
stafmin[0][i]=0;
}
else if(a[i]<0)
{
stafmax[0][i]=stafmin[0][i]=a[i];
stazmax[0][i]=0;
stazmin[0][i]=INF;
}
else
{
stafmax[0][i]=–INF;
stazmin[0][i]=0;
stafmax[0][i]=–INF;
stafmin[0][i]=0;
}
}
for(int i=1;i<=m;i++)
{
cin>>b[i];
pb[i]=pb[i–1]+(b[i]==0);
if(b[i]>0)
{
stbzmax[0][i]=stbzmin[0][i]=b[i];
stbfmax[0][i]=–INF;
stbfmin[0][i]=0;
}
else if(b[i]<0)
{
stbfmax[0][i]=stbfmin[0][i]=b[i];
stbzmax[0][i]=0;
stbzmin[0][i]=INF;
}
else
{
stbfmax[0][i]=–INF;
stbzmin[0][i]=0;
stbfmax[0][i]=0;
stbfmin[0][i]=INF;
}
}
initlog(max(n,m));
buildst(stazmax,stazmin,n);
buildst(stafmax,stafmin,n);
buildst(stbzmax,stbzmin,m);
buildst(stbfmax,stbfmin,m);
while(q—)
{
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
cout<<check(l1,r1,l2,r2)<<endl;
}
return 0;
}

因为是求最短时间，所以明显是用广度优先搜索。
因为流星掉下来会损毁周围四个格子，所以输入时就得把它周围四个格子赋值做标记。
然后就是广搜，每次贝茜走时下一个格子得满足的条件是：第一，没越界；第二，走到时不会有流星掉下来或这块地没被烧焦，即贝茜走到时的时间小于流行落到这块地的时间。
由于这里只说了牧场在直角坐标系第一象限，所以贝茜走的位置只需要x和y都大于等于0就行。

#include<bits/stdc++.h>
using namespace std;
int m,d[350][350];
int dx[5]={0,1,–1,0,0};
int dy[5]={0,0,0,1,–1};
struct node{
int x,y,t;
};
bool vis[350][350];
int bfs()
{
if(!d[0][0]) return –1;
queue<node> q;
q.push({0,0,0});
vis[0][0]=true;
while(!q.empty())
{
node cur=q.front();
q.pop();
if(d[cur.x][cur.y]==0x3f3f3f3f) return cur.t;//没被标记的格子即为安全的
for(int k=1;k<5;k++)
{
int nx=cur.x+dx[k];
int ny=cur.y+dy[k];
if(nx>=0&&ny>=0&&!vis[nx][ny]){
int nt=cur.t+1;
if(d[nx][ny]>nt){
vis[nx][ny]=true;
q.push({nx,ny,nt});
}
}
}
}
return –1;
}
int main()
{
cin>>m;
memset(d,0x3f,sizeof(d));
for(int i=0;i<m;i++)
{
int x_1,y_1,t_1;
cin>>x_1>>y_1>>t_1;
for(int k=0;k<5;k++)
{
int nx=x_1+dx[k];
int ny=y_1+dy[k];
if(nx>=0&&ny>=0){
if(t_1<d[nx][ny])
d[nx][ny]=t_1;//标记流星掉下来的位置和周围四个会被摧毁的格子
}
}
}
cout<<bfs();
return 0;
}