首页 > 其他分享 >多校A层冲刺NOIP2024模拟赛20

多校A层冲刺NOIP2024模拟赛20

时间：2024-11-09 20:18:46浏览次数：4  
标签：rt 20 int ll 多校 ans query id NOIP2024

多校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;
}

\(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\) 后多出去的部分直接就看不见了。

标签：rt,20,int,ll,多校,ans,query,id,NOIP2024
From： https://www.cnblogs.com/The-Shadow-Dragon/p/18537242

相关文章

  • 笔趣阁纯净版V2024.10.13
    今天给大家推荐一款非常棒的免费小说阅读软件--笔趣阁纯净版版。不管你是想重温经典文学作品，还是想追读时下最火的小说，这款应用都能满足你的需求。对于小说和漫画爱好者来说，它是一个极佳的阅读工具，带你畅游在书籍的海洋中，享受阅读的乐趣。软件特色：1、界面设计非常简洁，没有......
  • 「NOIP2022」比赛
    洛谷。题目简述给定两个数列\(a,b\)，有\(q\)次询问，每次询问\([L,R]\)的所有子区间\([l,r]\)的\(\max_{i=l}^ra_i\times\max_{i=l}^rb_i\)之和。其中，\(n,q\le2.5e5\)。分析这很像历史版本和，但是我们写过的只有一个数组\(a\)的。那么先从部分分开始。对于\(n,......
  • 2024最新网络安全专业高薪岗位，网络安全入门到精通，收藏这篇就够了
    2024年，随着人工智能、云安全、供应链威胁、SecOps和产品安全威胁日益凸显，五类“顶流”安全职位（人才）有望加入CISO的“50万年薪俱乐部”。在传统网络安全职位薪酬体系中，处于金字塔顶端的是CISO、网络安全总监、信息安全经理、高级软件安全工程师、IT安全架构师等。根据企业规模......
  • 2024-2025-1-《计算机基础与程序设计》20241313刘鸣宇
    作业信息这个作业属于哪个课程 <班级的链接>（如2024-2025-1-计算机基础与程序设计）这个作业要求在哪里 <作业要求的链接>(如2024-2025-1计算机基础与程序设计第一周作业)这个作业的目标 <写上具体方面>作业正文 ...本博客链接教材学习内容总结《计算机基础与科学概论》第八章......
  • 51c大模型~合集20
    我自己的原文哦~ https://blog.51cto.com/whaosoft/11634780#Transformer大模型尺寸变化大模型尺寸正在重走CNN的老路；马斯克：在特斯拉也是这样, Transformer大模型尺寸变化，正在重走CNN的老路！ Transformer大模型尺寸变化，正在重走CNN的老路！看到大家都被LLaMA3.1吸引了注......
  • 2024.11.9组队训练题解记录
    Teleportation鲍勃最近访问了一个奇怪的传送系统。该系统包含\(n\)个房间，编号为\(0\)到\(n-1\)。每个房间都安装了一个传送设备。每个传送设备都有一个看起来像钟表表面的仪表板，上面有一个指针，显示数字\(0\)到\(n-1\)，按顺时针顺序排列。最初，第\(i\)个房间的传送设备上......
  • 大二上计组往年卷刷题之简单题部分 202411109
    2020年计组期末卷（非陈家骏班）1.请简述C++程序设计语言的设计理念、演化历程（包括主要的贡献者），并讨论Simula67在其中的作用。C++程序设计语言的设计理念C++的设计理念主要基于以下几个核心原则：高效地使用硬件：C++旨在保持与C语言的兼容性，使得C++代码与C代码运行时具有相似或更......
  • 多校A层冲刺NOIP2024模拟赛20
    简评：新拉的......
  • [GWCTF 2019]babyRSA
    fromCrypto.Util.numberimport*fromgmpy2import*fromsympyimport*p=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952......
  • 2024-2025-1 20241318 《计算机基础与程序设计》第七周学习总结
    这个作业属于哪个课程https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP这个作业要求在哪里https://www.cnblogs.com/rocedu/p/9577842.html#WEEK07这个作业的目标①数组与链表②基于数组和基于链表实现数据结构③无序表与有序表④树⑤图⑥子程序与参数作......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99