多校A层冲刺NOIP2024模拟赛20
\(T1\) A. 星际联邦 \(25pts\)
-
部分分
-
\(25pts\) :暴力建边后跑 \(Kruskal\) 或 \(Prim\) 。
点击查看代码
struct node { int from,to,w; }; int a[300010]; vector<node>e; struct DSU { int fa[300010]; void init(int n) { for(int i=1;i<=n;i++) { fa[i]=i; } } int find(int x) { return (fa[x]==x)?x:fa[x]=find(fa[x]); } }D; bool cmp(node a,node b) { return a.w<b.w; } ll kruskal(int n) { ll ans=0; D.init(n); sort(e.begin(),e.end(),cmp); for(int i=0;i<e.size();i++) { int x=D.find(e[i].from),y=D.find(e[i].to); if(x!=y) { D.fa[x]=y; ans+=e[i].w; } } return ans; } int main() { freopen("star.in","r",stdin); freopen("star.out","w",stdout); int n,i,j; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; } for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { e.push_back((node){i,j,a[j]-a[i]}); } } cout<<kruskal(n)<<endl; fclose(stdin); fclose(stdout); return 0; }
-
\(40pts\) :堆优化 \(Prim\) 。
点击查看代码
ll a[300010],vis[300010],dis[300010]; ll prim(ll n) { memset(dis,0x3f,sizeof(dis)); ll ans=0; priority_queue<pair<ll,ll> >q; q.push(make_pair(-0,1)); while(q.empty()==0) { pair<ll,ll> x=q.top(); q.pop(); if(vis[x.second]==0) { vis[x.second]=1; ans+=-x.first; for(ll i=1;i<=x.second-1;i++) { if(vis[i]==0&&a[x.second]-a[i]<dis[i]) { dis[i]=a[x.second]-a[i]; q.push(make_pair(-dis[i],i)); } } for(ll i=x.second+1;i<=n;i++) { if(vis[i]==0&&a[i]-a[x.second]<dis[i]) { dis[i]=a[i]-a[x.second]; q.push(make_pair(-dis[i],i)); } } } } return ans; } int main() { freopen("star.in","r",stdin); freopen("star.out","w",stdout); ll n,i; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; } cout<<prim(n)<<endl; fclose(stdin); fclose(stdout); return 0; }
-
-
正解
- 贪心地选择 \(a_{j}=\max\limits_{k=1}^{i-1}\{ a_{k} \}\) 的 \(j\) 和 \(a_{j'}=\min\limits_{k=i+1}^{n}\{ a_{k} \}\) 的 \(j'\) 分别与 \(i\) 相连, \(a_{j}=\max\limits_{k=1}^{i-1}\{ a_{k} \}\) 的 \(j\) 和 \(a_{j'}=\min\limits_{k=i+1}^{n}\{ a_{k} \}\) 的 \(j'\) 相连,然后跑最小生成树即可。
- 前者正确性显然,反证法即可证明。对应 \(j \to i \to j'\) 的情况。
- 需要 \(a_{j}=\max\limits_{k=1}^{i-1}\{ a_{k} \}\) 的 \(j\) 和 \(a_{j'}=\min\limits_{k=i+1}^{n}\{ a_{k} \}\) 的 \(j'\) 相连当且仅当 \(a_{i}<a_{j}=\max\limits_{k=1}^{i-1}\{ a_{k} \}\) 或 \(a_{i}>a_{j'}=\min\limits_{k=i+1}^{n}\{ a_{k} \}\) ,此时分别对应 \(i \to j \to j'\) 或 \(j \to j' \to i\) 的情况。
- 正确性分讨最小生成树上 \(i\) 向上、下两条极长下标单调链的链头与其的大小关系即可。
点击查看代码
struct node { ll from,to,w; }; ll a[300010],pre[300010],suf[300010]; vector<node>e; struct DSU { ll fa[300010]; void init(ll n) { for(ll i=1;i<=n;i++) { fa[i]=i; } } ll find(ll x) { return (fa[x]==x)?x:fa[x]=find(fa[x]); } }D; bool cmp(node a,node b) { return a.w<b.w; } ll kruskal(ll n) { ll ans=0; D.init(n); sort(e.begin(),e.end(),cmp); for(ll i=0;i<e.size();i++) { ll x=D.find(e[i].from),y=D.find(e[i].to); if(x!=y) { D.fa[x]=y; ans+=e[i].w; } } return ans; } int main() { freopen("star.in","r",stdin); freopen("star.out","w",stdout); ll n,maxx=-0x3f3f3f3f,minn=0x3f3f3f3f,i; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; maxx=max(maxx,a[i]); pre[i]=(a[i]==maxx)?i:pre[i-1]; } for(i=n;i>=1;i--) { minn=min(minn,a[i]); suf[i]=(a[i]==minn)?i:suf[i+1]; } e.push_back((node){n,pre[n-1],a[n]-a[pre[n-1]]}); e.push_back((node){1,suf[2],a[suf[2]]-a[1]}); for(i=2;i<=n-1;i++) { e.push_back((node){i,pre[i-1],a[i]-a[pre[i-1]]}); e.push_back((node){i,suf[i+1],a[suf[i+1]]-a[i]}); e.push_back((node){pre[i-1],suf[i+1],a[suf[i+1]]-a[pre[i-1]]}); } cout<<kruskal(n)<<endl; fclose(stdin); fclose(stdout); return 0; }
- 贪心地选择 \(a_{j}=\max\limits_{k=1}^{i-1}\{ a_{k} \}\) 的 \(j\) 和 \(a_{j'}=\min\limits_{k=i+1}^{n}\{ a_{k} \}\) 的 \(j'\) 分别与 \(i\) 相连, \(a_{j}=\max\limits_{k=1}^{i-1}\{ a_{k} \}\) 的 \(j\) 和 \(a_{j'}=\min\limits_{k=i+1}^{n}\{ a_{k} \}\) 的 \(j'\) 相连,然后跑最小生成树即可。
\(T2\) B. 和平精英 \(0pts\)
-
部分分
- 子任务 \(1\) :暴搜。
- 子任务 \(3\) :输出
NO
。
点击查看代码
ll a[100010],ans=0; void dfs(ll pos,ll n,ll sum1,ll sum2,ll num1,ll num2) { if(ans==1||sum1<sum2) { return; } if(pos==n+1) { ans|=(sum1==sum2&&num1!=0&&num2!=0); return; } else { dfs(pos+1,n,sum1&a[pos],sum2,num1+1,num2); dfs(pos+1,n,sum1,sum2|a[pos],num1,num2+1); } } int main() { freopen("peace.in","r",stdin); freopen("peace.out","w",stdout); ll n,m,l,r,i; cin>>n>>m; for(i=1;i<=n;i++) { cin>>a[i]; } if(n<=15) { for(i=1;i<=m;i++) { cin>>l>>r; ans=0; dfs(l,r,(1ll<<31)-1,0,0,0); if(ans==0) { cout<<"NO"<<endl; } else { cout<<"YES"<<endl; } } } else { for(i=1;i<=m;i++) { cout<<"NO"<<endl; } } fclose(stdin); fclose(stdout); return 0; }
-
正解
- 先考虑枚举最终答案的值 \(ans\) ,显然应当把所有的 \(a_{i}<ans\) 放到 \(\operatorname{or}\) 集合里,把所有的 \(a_{i}>ans\) 放到 \(\operatorname{and}\) 集合里,而 \(a_{i}=ans\) 放到哪里都行,暴力进行 \(check\) 的时间复杂度不可接受。
- 考虑枚举 \(\operatorname{popcount}(ans)\) ,类似地应当把所有的 \(\operatorname{popcount}(a_{i})<\operatorname{popcount}(ans)\) 放到 \(\operatorname{or}\) 集合里,把所有的 \(\operatorname{popcount}(a_{i})>\operatorname{popcount}(ans)\) 放到 \(\operatorname{and}\) 集合里,而 \(\operatorname{popcount}(a_{i})=\operatorname{popcount}(ans)\) 的 \(a_{i}\) 必须全部相等,在相等的情况下放到哪里都行(至少有一个给 \(\operatorname{or}\) 且有一个给 \(\operatorname{and}\) )。
- 判断相等的一个方法是按位或和等于按位与和。
- 线段树对于每个 \(\operatorname{popcount}\) 扔到线段树里维护即可。
点击查看代码
int a[100010],o[35],an[35],siz[35],sumo[35],suma[35],sums[35]; struct SMT { struct SegmentTree { int sumo[35],suma[35],sums[35]; }tree[400010]; int lson(int x) { return x*2; } int rson(int x) { return x*2+1; } void pushup(int rt) { for(int i=0;i<=30;i++) { tree[rt].sumo[i]=tree[lson(rt)].sumo[i]|tree[rson(rt)].sumo[i]; tree[rt].suma[i]=tree[lson(rt)].suma[i]&tree[rson(rt)].suma[i]; tree[rt].sums[i]=tree[lson(rt)].sums[i]+tree[rson(rt)].sums[i]; } } void build(int rt,int l,int r) { if(l==r) { fill(tree[rt].sumo+0,tree[rt].sumo+31,0); fill(tree[rt].suma+0,tree[rt].suma+31,(1<<30)-1); fill(tree[rt].sums+0,tree[rt].sums+31,0); tree[rt].sumo[__builtin_popcount(a[l])]=a[l]; tree[rt].suma[__builtin_popcount(a[l])]=a[l]; tree[rt].sums[__builtin_popcount(a[l])]=1; return; } int mid=(l+r)/2; build(lson(rt),l,mid); build(rson(rt),mid+1,r); pushup(rt); } int query_o(int rt,int l,int r,int x,int y,int id) { if(x<=l&&r<=y) { return tree[rt].sumo[id]; } int mid=(l+r)/2; if(y<=mid) { return query_o(lson(rt),l,mid,x,y,id); } if(x>mid) { return query_o(rson(rt),mid+1,r,x,y,id); } return query_o(lson(rt),l,mid,x,y,id)|query_o(rson(rt),mid+1,r,x,y,id); } int query_a(int rt,int l,int r,int x,int y,int id) { if(x<=l&&r<=y) { return tree[rt].suma[id]; } int mid=(l+r)/2; if(y<=mid) { return query_a(lson(rt),l,mid,x,y,id); } if(x>mid) { return query_a(rson(rt),mid+1,r,x,y,id); } return query_a(lson(rt),l,mid,x,y,id)&query_a(rson(rt),mid+1,r,x,y,id); } int query_s(int rt,int l,int r,int x,int y,int id) { if(x<=l&&r<=y) { return tree[rt].sums[id]; } int mid=(l+r)/2; if(y<=mid) { return query_s(lson(rt),l,mid,x,y,id); } if(x>mid) { return query_s(rson(rt),mid+1,r,x,y,id); } return query_s(lson(rt),l,mid,x,y,id)+query_s(rson(rt),mid+1,r,x,y,id); } }T; int check(int l,int r,int n) { for(int i=0;i<=30;i++) { sumo[i]=o[i]=T.query_o(1,1,n,l,r,i); suma[i]=an[i]=T.query_a(1,1,n,l,r,i); sums[i]=siz[i]=T.query_s(1,1,n,l,r,i); } for(int i=1;i<=30;i++) { sumo[i]|=sumo[i-1]; sums[i]+=sums[i-1]; } for(int i=29;i>=0;i--) { suma[i]&=suma[i+1]; } for(int i=0;i<=30;i++) { if(sums[i]!=0&&sums[30]-sums[i]!=0&&sumo[i]==suma[i+1]) { return true; } if(o[i]==an[i]&&siz[i]>=2&&sumo[i]==suma[i]) { return true; } } return false; } int main() { freopen("peace.in","r",stdin); freopen("peace.out","w",stdout); int n,q,l,r,i; cin>>n>>q; for(i=1;i<=n;i++) { cin>>a[i]; } T.build(1,1,n); for(i=1;i<=q;i++) { cin>>l>>r; if(check(l,r,n)==true) { cout<<"YES"<<endl; } else { cout<<"NO"<<endl; } } fclose(stdin); fclose(stdout); return 0; }
\(T3\) C. 摆烂合唱 \(0pts\)
\(T4\) D. 对称旅行者 \(0pts\)
-
正解
总结
- \(T1\) 反复读假题加不理解题意导致在 \(T1\) 花的时间太长了,中途的一堆假思路也对正解有阻碍。整场算是死磕 \(T1\) 了。
- \(T2\) 没判断选出的集合非空挂了 \(8pts\) ;同时误认为随机数据下
YES
很多,挂了 \(9pts\) 。 - \(T4\) 不知道怎么处理 \(1,n\) 的旅行情况,导致爆搜的 \(5pts\) 挂了。
后记
- \(T2\) 的样例单行过长导致转成 \(PDF\) 后多出去的部分直接就看不见了。