初三奥赛模拟测试4
\(T1\) 最后一课 \(100pts\)
-
简化题意：给定 \(k,x_{1},y_{1},x_{2},y_{2}\) ，求 \(\min \{ (x-x_{1})^2+(k-y_{1})^2+(x-x_{2})^2+(k-y_{2})^2 \}\) 。
-
正解
- 对 \(k,y_{1},y_{2}\) 同侧/异侧进行分讨，冲个 将军饮马问题 即可。
点击查看代码
ll work(ll x1,ll y1,ll x2,ll y2) { return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2); } int main() { ll k,x1,x2,y1,y2; cin>>k>>x1>>y1>>x2>>y2; if(y1>y2) { swap(x1,x2); swap(y1,y2); } if(y1==k&&y2==k) { cout<<work(x1,y1,x2,y2)<<endl; } else { if(k<y1) { cout<<work(x1,y1-2*(y1-k),x2,y2)<<endl; } else { if(y1<k&&k<y2) { cout<<work(x1,y1,x2,y2)<<endl; } else { cout<<work(x1,y1+2*(k-y1),x2,y2)<<endl; } } } return 0; }
\(T2\) 日常 \(60pts\)
-
正解
- 排序后二分模拟即可。
点击查看代码
struct node { ll l,x,y,r; }a[100010]; ll vis[100010]; bool cmp(node a,node b) { return a.r<b.r; } bool check(ll mid,ll w) { return a[mid].l<=w; } int main() { ll n,m,k,minl=0x7f7f7f7f,l,r,mid,ans,w,i; cin>>n>>m>>k; for(i=1;i<=n;i++) { cin>>a[i].l>>a[i].x>>a[i].y>>a[i].r; minl=min(minl,a[i].l); } sort(a+1,a+1+n,cmp); for(i=1;i<=k;i++) { cin>>w; if(w<minl||w>m) { cout<<"Failed"<<endl; } else { l=1; r=n; ans=0; while(l<=r) { mid=(l+r)/2; if(check(mid,w)==true) { l=mid+1; ans=mid; } else { r=mid-1; } } if(w<=a[ans].r) { if(vis[ans]==1) { cout<<"Again"<<endl; } else { vis[ans]=1; if(a[ans].x<=w&&w<=a[ans].y) { cout<<"Perfect"<<endl; } else { cout<<"Normal"<<endl; } } } else { cout<<"Failed"<<endl; } } } return 0; }
\(T3\) 渡尘 \(70pts\)
- 简化题意：给定一个长度为 \(n(n \le 2 \times 10^{5})\) 的序列 \(a\) ， \(m(m \le 3 \times 10^{6})\) 组询问，每次询问给定 \(l,r\) 求 \(\max\limits_{l \le l_{1} \le r_{1} \le r} \{ |\sum\limits_{i=l_{1}}^{r_{1}}a_{i}| \}\) 。
- 部分分
- \(70pts\)
-
考虑把绝对值拆开，有 \(\max\limits_{l \le l_{1} \le r_{1} \le r} \{ |\sum\limits_{i=l_{1}}^{r_{1}}a_{i}| \}=\max\limits_{l \le l_{1} \le r_{1} \le r} \{ \sum\limits_{i=l_{1}}^{r_{1}}a_{i},\sum\limits_{i=l_{1}}^{r_{1}}-a_{i} \}\) 。
-
\(\max\limits_{l \le l_{1} \le r_{1} \le r} \{ \sum\limits_{i=l_{1}}^{r_{1}}a_{i} \}\) 可用线段树维护，记录每个区间的最大前缀和、最大后缀和、最大子段和、区间和，然后合并即可。
-
复杂度为 \(O(m \log_{2}{n})\) ，因线段树的巨大常数巨大所以只能得到 \(70pts\) 。
- 单次查询： luogu P1115 最大子段和
- 不带修，区间查询，不记录路径： SP1043 GSS1 - Can you answer these queries I
- 不带修，区间查询，记录路径： UVA1400 "Ray, Pass me the dishes!"
- 单点修改，区间查询，不记录路径： SP1716 GSS3 - Can you answer these queries III | luogu P4513 小白逛公园
- 区间修改，区间查询，不记录路径： LibreOJ 6265. 最大连续子段和
点击查看代码
ll a[800010]; struct SegmentTree { ll l,r,maxl[2],maxr[2],sum[2],ans[2]; }tree[800010]; ll lson(ll l) { return l*2; } ll rson(ll l) { return l*2+1; } void pushup(ll rt,ll pd) { tree[rt].sum[pd]=tree[lson(rt)].sum[pd]+tree[rson(rt)].sum[pd]; tree[rt].maxl[pd]=max(tree[lson(rt)].sum[pd]+tree[rson(rt)].maxl[pd],tree[lson(rt)].maxl[pd]); tree[rt].maxr[pd]=max(tree[rson(rt)].sum[pd]+tree[lson(rt)].maxr[pd],tree[rson(rt)].maxr[pd]); tree[rt].ans[pd]=max(max(tree[lson(rt)].ans[pd],tree[rson(rt)].ans[pd]),tree[lson(rt)].maxr[pd]+tree[rson(rt)].maxl[pd]); } void build(ll rt,ll l,ll r,ll pd,ll a[]) { tree[rt].l=l; tree[rt].r=r; if(l==r) { tree[rt].sum[pd]=tree[rt].ans[pd]=tree[rt].maxl[pd]=tree[rt].maxr[pd]=a[l]; return; } ll mid=(l+r)/2; build(lson(rt),l,mid,pd,a); build(rson(rt),mid+1,r,pd,a); pushup(rt,pd); } SegmentTree query(ll rt,ll l,ll r,ll pd) { if(l<=tree[rt].l&&tree[rt].r<=r) { return tree[rt]; } ll mid=(tree[rt].l+tree[rt].r)/2; if(r<=mid) { return query(lson(rt),l,r,pd); } else { if(l>mid) { return query(rson(rt),l,r,pd); } else { SegmentTree p=query(lson(rt),l,r,pd),q=query(rson(rt),l,r,pd),num; num.sum[pd]=p.sum[pd]+q.sum[pd]; num.maxl[pd]=max(p.sum[pd]+q.maxl[pd],p.maxl[pd]); num.maxr[pd]=max(q.sum[pd]+p.maxr[pd],q.maxr[pd]); num.ans[pd]=max(max(p.ans[pd],q.ans[pd]),p.maxr[pd]+q.maxl[pd]); return num; } } } int main() { ll n,m,i,l,r; scanf("%lld%lld",&n,&m); for(i=1;i<=n;i++) { scanf("%lld",&a[i]); } build(1,1,n,0,a); for(i=1;i<=n;i++) { a[i]=-a[i]; } build(1,1,n,1,a); for(i=1;i<=m;i++) { scanf("%lld%lld",&l,&r); printf("%lld\n",max(query(1,l,r,0).ans[0],query(1,l,r,1).ans[1])); } return 0; }
-
- \(70pts\)
- 正解
- \(ST\) 表
-
考虑把绝对值拆开，有 \(\max\limits_{l \le l_{1} \le r_{1} \le r} \{ |\sum\limits_{i=l_{1}}^{r_{1}}a_{i}| \}=\max\limits_{l \le l_{1} \le r_{1} \le r} \{ \sum\limits_{i=1}^{r_{1}+1}a_{i}-\sum\limits_{i=1}^{l_{1}}a_{i},\sum\limits_{i=1}^{l_{1}}a_{i}-\sum\limits_{i=1}^{r_{1}+1}a_{i} \}=\max\limits_{r_{1}=l}^{r+1} \{ \sum\limits_{i=1}^{r_{1}}a_{i} \}-\min\limits_{l_{1}=l}^{r+1} \{ \sum\limits_{i=1}^{l_{1}}a_{i} \}\) ，使用 \(ST\) 表维护即可。
点击查看代码
//快读快写已省略 #define cin Fast_IO::fin #define cout Fast_IO::fout ll a[200010],sum[200010],fmaxx[200010][25],fminn[200010][25]; void init(ll n,ll a[]) { memset(fminn,0x3f,sizeof(fminn)); for(ll i=1;i<=n;i++) { fminn[i][0]=fmaxx[i][0]=a[i]; } for(ll j=1;j<=log2(n);j++) { for(ll i=1;i<=n-(1<<j)+1;i++) { fmaxx[i][j]=max(fmaxx[i][j-1],fmaxx[i+(1<<(j-1))][j-1]); fminn[i][j]=min(fminn[i][j-1],fminn[i+(1<<(j-1))][j-1]); } } } ll query_max(ll l,ll r) { ll t=log2(r-l+1); return max(fmaxx[l][t],fmaxx[r-(1<<t)+1][t]); } ll query_min(ll l,ll r) { ll t=log2(r-l+1); return min(fminn[l][t],fminn[r-(1<<t)+1][t]); } int main() { ll n,m,l,r,i; cin(n,m); for(i=1;i<=n;i++) { cin(a[i]); sum[i+1]=sum[i]+a[i]; } init(n+1,sum); for(i=1;i<=m;i++) { cin(l,r); r++; cout(query_max(l,r)-query_min(l,r),'\n'); } return 0; }
-
- 猫树
- “四毛子”算法
- \(ST\) 表
\(T4\) 罪人挽歌 \(0pts\)
- 部分分
- \(0pts\) ：输出
No。
- \(0pts\) ：输出