20241024 模拟赛（长方体，三角形，区间，图）
看题戳这里
总结
1h 看题+骂出题人
1h 把之前没做完的题单补了
1h 闲逛+水群+听歌
1h 疯狂rush暴力！！！
结果看完solution才发现我是fw \(qwq\)
最终分数：30+60+60+10
解析
A. 长方体
难度：绿
暴力：直接三维差分+前缀和搞定。
正解：先算出前缀交与后缀交。被 \(n\) 个长方体覆盖的点就是所有长方体的交。
而只被 \(n-1\) 个长方体覆盖的点怎么算呢，假设其没被第 \(i\) 个长方体覆盖，则答案为前 \(i-1\) 个长方体的交和后 \(n-i\) 个长方体的交再求交，最后减去被 \(n\) 个长方体覆盖的部分，就行了。
时间复杂度 \(O(n)\)。
#include<bits/stdc++.h>
#define mxn 100010
#define ll long long
#define inf 1e12
using namespace std;
struct cube{
ll _x1=-inf,_y1=-inf,_z1=-inf;
ll _x2=inf,_y2=inf,_z2=inf;
}a[mxn],psum[mxn],ssum[mxn];
cube inters(cube &x,cube &y){
cube ret;
ret._x1=max(x._x1,y._x1);
ret._y1=max(x._y1,y._y1);
ret._z1=max(x._z1,y._z1);
ret._x2=min(x._x2,y._x2);
ret._y2=min(x._y2,y._y2);
ret._z2=min(x._z2,y._z2);
return ret;
}
ll get_vol(cube x){
ll ret=1;
ret*=max(0ll,x._x2-x._x1+1);
ret*=max(0ll,x._y2-x._y1+1);
ret*=max(0ll,x._z2-x._z1+1);
return ret;
}
ll n,vall,ans;
int main(){
freopen("cube.in","r",stdin);
freopen("cube.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i]._x1>>a[i]._y1>>a[i]._z1>>a[i]._x2>>a[i]._y2>>a[i]._z2;
for(int i=1;i<=n;i++)
psum[i]=inters(psum[i-1],a[i]);
for(int i=n;i;i--)
ssum[i]=inters(ssum[i+1],a[i]);
vall=get_vol(psum[n]),ans=vall;
for(int i=1;i<=n;i++)
ans+=get_vol(inters(psum[i-1],ssum[i+1]))-vall;
cout<<ans;
return 0;
}
B. 三角形
难度：绿
注意力好题。
我们发现若使某个区间找不出符合条件的三元组，则其边长会呈指数级增长。
但题目中有 \(a_i\leq 10^{18}\)，所以当区间长度 \(\geq100\) 时绝对有符合条件的三元组。
\(\leq100\) 的部分直接暴力就行了。
#include<bits/stdc++.h>
#define mxn 100010
#define ll long long
using namespace std;
ll n,q,a[mxn],l,r,tmp[mxn];
int main(){
freopen("triangle.in","r",stdin);
freopen("triangle.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>a[i];
while(q--){
cin>>l>>r;
if(r-l<=1){
cout<<"No\n";
continue;
}
if(r-l+1>=100){
cout<<"Yes\n";
continue;
}
for(int i=l;i<=r;i++)
tmp[i]=a[i];
sort(tmp+l,tmp+r+1);
bool flg=0;
for(int i=l+1;i<=r-1;i++){
if(tmp[i+1]-tmp[i]<tmp[i-1]){
flg=1;
cout<<"Yes\n";
break;
}
}
if(!flg)cout<<"No\n";
}
return 0;
}
C. 区间
难度：绿-蓝
区间翻转？一开始想到了用链表解决。
但是这里要求出第 \(k\) 位，时间复杂度会炸。
发现两个特殊性质：长度一定，以及 \(l\) 单调不减。
于是可以维护一个双端队列，从左往右更新。
#include<bits/stdc++.h>
#define ll long long
#define mxn 1000010
using namespace std;
int n,m,q,a[mxn],ans,cnt=1,dir;
struct deq{
int num[mxn*2],head=mxn-10;
void init(){
for(int i=1;i<=m;i++)
num[head+i-1]=a[i];
}
void push(int opt,int val,int pos){
if(opt==0)num[head+m]=val,a[pos]=num[head],head++;
else head--,a[pos]=num[head+m],num[head]=val;
}
int get(int opt,int k,int pos){
if(opt==0)return num[head+k-pos];
else return num[head+m+pos-k-1];
}
}dq;
int main(){
freopen("section.in","r",stdin);
freopen("section.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
cin>>a[i];
dq.init();
while(q--){
int opt,x;cin>>opt>>x;
if(opt==1){
while(cnt<x)
dq.push(dir,a[cnt+m],cnt),cnt++;
dir^=1;
}
else{
if(x<cnt||x>=cnt+m)ans^=a[x];
else ans^=dq.get(dir,x,cnt);
}
}
cout<<ans;
return 0;
}
D. 图
难度：绿
发现这玩意就是一个求最大生成树，点权怎么处理呢，我们先搞一个超级点连向所有的点，边权为 \(1\)。
然后对于能连的每一条边，边权设为 \(val_i+val_j\)，然后 \(ans\) 减去每个点的点权就行了。
一种巧妙的建图方式。
#include<bits/stdc++.h>
#define ll long long
#define mxn 1010
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
using namespace std;
ll n,ans,val[mxn],f[mxn],cnt,tot;
struct edge{
ll u,v,w;
}e[mxn*mxn];
int fnd(int x){
if(f[x]==x)return x;
return f[x]=fnd(f[x]);
}
void kruskal(){
sort(e+1,e+cnt+1,[](edge x,edge y){
return x.w>y.w;
});
for(int i=1;i<=n+1;i++)f[i]=i;
for(int i=1;i<=cnt;i++){
int u=e[i].u,v=e[i].v,w=e[i].w;
int fu=fnd(u),fv=fnd(v);
if(fu==fv)continue;
f[fu]=fv;
ans+=w;
tot++;
if(tot>=n)break;
}
return;
}
int main(){
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>val[i];
e[++cnt]=edge{i,n+1,val[i]};
ans-=val[i];
for(int j=1;j<i;j++)
if((val[i]&val[j])==0)
e[++cnt]=edge{i,j,val[i]+val[j]};
}
kruskal();
cout<<ans;
return 0;
}