NOIP 模拟 七十四
2021/10/12 6:44:09
本文主要是介绍NOIP 模拟 七十四,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
T1 自然数
首先预处理以一为左端点所有的 mex 值,然后插入线段树中。
考虑如何修改,左端点右移一位,相当于把那一位的数删掉了,记录下一个出现这个数的位置为 pos ,那么i 到 pos 之间所有大于 x 的 mex 都要修改为 x。
剩下的就是线段树基本操作了。
#include<bits/stdc++.h> #define N 200010 #define int long long using namespace std; int n,jie,a[N]; long long ans; int tree[N<<2],sum[N<<2],minn[N<<2],tag[N<<2],tong[N],ji,c[N],nxt[N],maxn[N<<2]; struct jj {int ai,id;}p[N]; inline void pushup(int x) { sum[x]=sum[x<<1]+sum[x<<1|1]; minn[x]=min(minn[x<<1],minn[x<<1|1]); maxn[x]=max(maxn[x<<1],maxn[x<<1|1]); }#include<bits/stdc++.h> #define N 200010 #define int long long using namespace std; int n,jie,a[N]; long long ans; int tree[N<<2],sum[N<<2],minn[N<<2],tag[N<<2],tong[N],ji,c[N],nxt[N],maxn[N<<2]; struct jj {int ai,id;}p[N]; inline void pushup(int x) { sum[x]=sum[x<<1]+sum[x<<1|1]; minn[x]=min(minn[x<<1],minn[x<<1|1]); maxn[x]=max(maxn[x<<1],maxn[x<<1|1]); } inline void pushdown(int x,int l,int r) { minn[x<<1]=minn[x<<1|1]=maxn[x<<1]=maxn[x<<1|1]=tag[x<<1]=tag[x<<1|1]=tag[x]; int mid=(l+r)>>1;sum[x<<1]=tag[x]*(mid-l+1);sum[x<<1|1]=tag[x]*(r-mid);tag[x]=-1; } inline void build(int x,int l,int r) { if(l==r){sum[x]=minn[x]=maxn[x]=c[l];return;} int mid=(l+r)>>1; build(x<<1,l,mid);build(x<<1|1,mid+1,r); pushup(x); } inline int query(int x,int l,int r,int L,int R) { if(l>=L and r<=R)return sum[x]; int mid=(l+r)>>1,res=0;if(tag[x]!=-1)pushdown(x,l,r); if(mid<R)res+=query(x<<1|1,mid+1,r,L,R); if(mid>=L)res+=query(x<<1,l,mid,L,R); return res; } inline void update(int x,int l,int r,int L,int R,int val) { if(L>R)return; if(l>=L and r<=R and minn[x]>=val){maxn[x]=minn[x]=val;sum[x]=val*(r-l+1);tag[x]=val;return;} int mid=(l+r)>>1;if(tag[x]!=-1)pushdown(x,l,r); if(mid<R and maxn[x<<1|1]>val)update(x<<1|1,mid+1,r,L,R,val); if(mid>=L and maxn[x<<1]>val)update(x<<1,l,mid,L,R,val); pushup(x); } signed main() { freopen("mex.in","r",stdin); freopen("mex.out","w",stdout); scanf("%lld",&n); for(int i=1;i<=n;++i)scanf("%lld",&a[i]),p[i]=(jj){a[i],i}; int zhi=0; for(int i=1;i<=n;++i) { if(a[i]<=n)tong[a[i]]=1; while(tong[zhi])++zhi; c[i]=zhi; } memset(tong,0,sizeof(tong));memset(tag,-1,sizeof(tag)); for(int i=n;i;--i)if(a[i]<=n){nxt[i]=tong[a[i]];tong[a[i]]=i;} build(1,1,n); for(int i=1;i<=n;++i) { ans+=query(1,1,n,i,n); if(a[i]<=n) { int pos=nxt[i]; if(!pos)pos=n+1; update(1,1,n,i,pos-1,a[i]); } } printf("%lld\n",ans); } build(x<<1,l,mid);build(x<<1|1,mid+1,r); pushup(x); } inline int query(int x,int l,int r,int L,int R) { if(l>=L and r<=R)return sum[x]; int mid=(l+r)>>1,res=0;if(tag[x]!=-1)pushdown(x,l,r); if(mid<R)res+=query(x<<1|1,mid+1,r,L,R); if(mid>=L)res+=query(x<<1,l,mid,L,R); return res; } inline void update(int x,int l,int r,int L,int R,int val) { if(L>R)return; if(l>=L and r<=R and minn[x]>=val){maxn[x]=minn[x]=val;sum[x]=val*(r-l+1);tag[x]=val;return;} int mid=(l+r)>>1;if(tag[x]!=-1)pushdown(x,l,r); if(mid<R and maxn[x<<1|1]>val)update(x<<1|1,mid+1,r,L,R,val); if(mid>=L and maxn[x<<1]>val)update(x<<1,l,mid,L,R,val); pushup(x); } signed main() { freopen("mex.in","r",stdin); freopen("mex.out","w",stdout); scanf("%lld",&n); for(int i=1;i<=n;++i)scanf("%lld",&a[i]),p[i]=(jj){a[i],i}; int zhi=0; for(int i=1;i<=n;++i) { if(a[i]<=n)tong[a[i]]=1; while(tong[zhi])++zhi; c[i]=zhi; } memset(tong,0,sizeof(tong));memset(tag,-1,sizeof(tag)); for(int i=n;i;--i)if(a[i]<=n){nxt[i]=tong[a[i]];tong[a[i]]=i;} build(1,1,n); for(int i=1;i<=n;++i) { ans+=query(1,1,n,i,n); if(a[i]<=n) { int pos=nxt[i]; if(!pos)pos=n+1; update(1,1,n,i,pos-1,a[i]); } } printf("%lld\n",ans); }
T2 钱仓
贪心,一定存在中转点,一定存在一个分界点满足只向一遍运输,这个分界点就是最大子段和的起点。
#include<bits/stdc++.h> #define int long long #define N 200005 using namespace std; int n,c[N],sum[N],nxt[N],maxn,id,tmp,t[N],ans,old[N]; signed main() { freopen("barn.in","r",stdin); freopen("barn.out","w",stdout); scanf("%lld",&n); for(int i=1;i<=n;++i)scanf("%lld",&c[i]); for(int i=1;i<=n;++i) { tmp+=c[i]; if(tmp<i-id)id=i,tmp=0; } ++id; for(int i=id;i<=n;++i)t[i-id+1]=c[i];for(int i=1;i<id;++i)t[i+n-id+1]=c[i]; int zhi1=n; for(int i=n;i;--i) { if(zhi1>i)zhi1=i; while(!t[zhi1])--zhi1; if(!t[i])ans+=(i-zhi1)*(i-zhi1),--t[zhi1]; } printf("%lld\n",ans); }
T3
这篇关于NOIP 模拟 七十四的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2025-01-11cursor试用出现:Too many free trial accounts used on this machine 的解决方法
- 2025-01-11百万架构师第十四课:源码分析:Spring 源码分析:深入分析IOC那些鲜为人知的细节|JavaGuide
- 2025-01-11不得不了解的高效AI办公工具API
- 2025-01-102025 蛇年,J 人直播带货内容审核团队必备的办公软件有哪 6 款?
- 2025-01-10高效运营背后的支柱:文档管理优化指南
- 2025-01-10年末压力山大?试试优化你的文档管理
- 2025-01-10跨部门协作中的进度追踪重要性解析
- 2025-01-10总结 JavaScript 中的变体函数调用方式
- 2025-01-10HR团队如何通过数据驱动提升管理效率?6个策略
- 2025-01-10WBS实战指南:如何一步步构建高效项目管理框架?