Day -5 ~ 0
被石门中学邀请集训一周，于是放弃一周文化课。
每天上午刷 Codeforces,或 NOIP 真题， 晚上打模拟赛，然后 CS.
感到石门中学简直是度假村一样。
本来通知去东莞提前 3 天，后来石门申请做考场了。
Day 1
上午放松考，调整心态。
T1 写的是直接乘加上特判 1，100.
T2 写的是一元二次方程，100.
直接跳 T4 二维 dp，100.
此时已经过去了 80 分钟，旁边的 dsy 大佬已经 AK了。
然后随便做一下 T3, 只打了 \(O(n^2)\) 50.
玩一会小恐龙，经过漫长的等待，就结束了。
中午回宿舍睡觉。
下午先做的是 T2，先观察一下，分类讨论一下，
发现只要维护最大值，最小值，非正数的最大值和非负数的最小值即可。
一开始我想要只写一个函数节省代码长度，可是这样实在太麻烦了。
然后复制粘贴写了非常多线段树。
由于第 4 个大样例始终不过，于是用 cmd 的 fc 指令发现了哪里出错了。
发现当没有非正数的最大值和非负数的最小值时，返回值出错了。
于是加一个判断即可。
拿到 100 分，然而其他人似乎都挂分了.
此时竟然过去了 1.5 小时。
贴一下代码：
code
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N=1e5+10,inf=2e9;
int n,m,q;
int a[N],b[N],mxa1[4*N],mxa0[4*N],mna1[4*N],mna0[4*N],mnb[4*N],mxb[4*N];
void buildmax0(int t[],int c[],int rt,int l,int r) {
if(l==r) {
if(c[l]<=0) t[rt]=c[l];
else t[rt]=-inf;
return ;
}
int mid=(l+r)/2;
buildmax0(t,c,rt*2,l,mid);
buildmax0(t,c,rt*2+1,mid+1,r);
t[rt]=max(t[rt*2],t[rt*2+1]);
}
void buildmax1(int t[],int c[],int rt,int l,int r) {
if(l==r) {
t[rt]=c[l];
return ;
}
int mid=(l+r)/2;
buildmax1(t,c,rt*2,l,mid);
buildmax1(t,c,rt*2+1,mid+1,r);
t[rt]=max(t[rt*2],t[rt*2+1]);
}
void buildmin0(int t[],int c[],int rt,int l,int r) {
if(l==r) {
t[rt]=c[l];
return ;
}
int mid=(l+r)/2;
buildmin0(t,c,rt*2,l,mid);
buildmin0(t,c,rt*2+1,mid+1,r);
t[rt]=min(t[rt*2],t[rt*2+1]);
}
void buildmin1(int t[],int c[],int rt,int l,int r) {
if(l==r) {
if(c[l]>=0) t[rt]=c[l];
else t[rt]=inf;
return ;
}
int mid=(l+r)/2;
buildmin1(t,c,rt*2,l,mid);
buildmin1(t,c,rt*2+1,mid+1,r);
t[rt]=min(t[rt*2],t[rt*2+1]);
}
int querymax(int t[],int rt,int l,int r,int x,int y) {
if(x<=l&&r<=y) return t[rt];
int mid=(l+r)/2,res=-inf;
if(x<=mid) res=max(res,querymax(t,rt*2,l,mid,x,y));
if(y>mid) res=max(res,querymax(t,rt*2+1,mid+1,r,x,y));
return res;
}
int querymin(int t[],int rt,int l,int r,int x,int y) {
if(x<=l&&r<=y) return t[rt];
int mid=(l+r)/2,res=inf;
if(x<=mid) res=min(res,querymin(t,rt*2,l,mid,x,y));
if(y>mid) res=min(res,querymin(t,rt*2+1,mid+1,r,x,y));
return res;
}
int main() {
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
scanf("%d%d%d",&n,&m,&q);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
for(int i=1; i<=m; i++) scanf("%d",&b[i]);
buildmax1(mxa1,a,1,1,n);
buildmax0(mxa0,a,1,1,n);
buildmin1(mna1,a,1,1,n);
buildmin0(mna0,a,1,1,n);
buildmax1(mxb,b,1,1,m);
buildmin0(mnb,b,1,1,m);
for(int i=1; i<=q; i++) {
int al,ar,bl,br;
scanf("%d%d%d%d",&al,&ar,&bl,&br);
int mina0,mina1,maxa0,maxa1,minb,maxb;
mina0=querymin(mna0,1,1,n,al,ar);
mina1=querymin(mna1,1,1,n,al,ar);
maxa0=querymax(mxa0,1,1,n,al,ar);
maxa1=querymax(mxa1,1,1,n,al,ar);
minb=querymin(mnb,1,1,m,bl,br);
maxb=querymax(mxb,1,1,m,bl,br);
LL ans1=-1ll*inf*inf,ans2=-1ll*inf*inf;
if(minb<0&&mina1!=inf) ans1=1ll*mina1*minb;
else if(minb!=inf&&maxa1>=0) ans1=1ll*maxa1*minb;
if(maxb<0&&mina0!=inf&&mina0<=0) ans2=1ll*mina0*maxb;
else if(maxa0!=-inf) ans2=1ll*maxa0*maxb;
printf("%lld\n",max(ans1,ans2));
}
return 0;
}
做 T1，尝试很多种办法，发现不会做，一开始是贪心选点，发现不行。
于是乎放弃，开始瞎搞，还是不行。
于是只能打 \(O(n^4)\) 暴力，甚至期间 floyd 都不会打了。
拿到 30 分。
T3 太长，没看
做 T4，我以为是直接在路径上求一个dp，但没想到的是竟然可以经过路径外的点中转。
我打了一个 \(O(qn)\) 做法，把每次询问的链拿出来跑一次 dp.
这样的话，甚至可以优化到 \(O(q\log n)\) ，但我没打。
第 4 个大样例死活过不了，我一直在检查，发现不了错误。
在 第 3 个大样例过了之后，我甚至没管第 2 个样例，其实这个样例我已经漏了上述情况。
测了一下，似乎还可以骗 40 分。
这样 30+100+40=170 估分。
标签：rt,大样,int,res,mid,2022,100,游记,CSP From： https://www.cnblogs.com/Simon-Gao/p/16840181.html