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

多校A层冲刺NOIP2024模拟赛08

时间：2024-10-17 16:48:00浏览次数：1  
标签：rt return minn 08 tree 多校 ll NOIP2024 rson

多校A层冲刺NOIP2024模拟赛08

\(T1\) A. 传送 (teleport) \(0pts\)

  • 弱化版： [ABC065D] Built? | luogu P8074 [COCI2009-2010#7] SVEMIR | “迎新春，过大年”多校程序设计竞赛 H 二次元世界之寻找珂朵莉

  • 先不管后面加入的 \(m\) 条边。

  • 对于两点间的路径 \(i \to j\) ，经过中转点 \(k\) 更优当且仅当 \(i \to k\) 和 \(k \to j\) 的路径不同向（不同时是 \(x\) 轴路线且不同时是 \(y\) 轴路线）。

  • 为处理同向间的不必要路径，不妨让所有点先后以横纵坐标排序，相邻两点之间连一条边即可。此时所连的边只有 \(2(n-1)\) 条，加上后面加入的 \(m\) 条边后跑 \(Dijsktra\) 即可。

    点击查看代码 
    vector<pair<ll,ll> >e[200010];
ll p[200010],x[200010],y[200010],vis[200010],dis[200010];
void add(ll u,ll v,ll w)
{
	e[u].push_back(make_pair(v,w));
}
bool cmp_x(ll a,ll b)
{
	return x[a]<x[b];
}
bool cmp_y(ll a,ll b)
{
	return y[a]<y[b];
}
void dijsktra(ll s)
{
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	priority_queue<pair<ll,ll> >q;
	dis[s]=0;
	q.push(make_pair(-dis[s],s));
	while(q.empty()==0)
	{
		ll x=q.top().second;
		q.pop();
		if(vis[x]==0)
		{
			vis[x]=1;
			for(ll i=0;i<e[x].size();i++)
			{
				if(dis[e[x][i].first]>dis[x]+e[x][i].second)
				{
					dis[e[x][i].first]=dis[x]+e[x][i].second;
					q.push(make_pair(-dis[e[x][i].first],e[x][i].first));
				}
			}
		}
	}
}
int main()
{
	freopen("teleport.in","r",stdin);
	freopen("teleport.out","w",stdout);
	ll n,m,u,v,w,i;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i];
		p[i]=i;
	}
	for(i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	sort(p+1,p+1+n,cmp_x);
	for(i=2;i<=n;i++)
	{
		add(p[i],p[i-1],x[p[i]]-x[p[i-1]]);
		add(p[i-1],p[i],x[p[i]]-x[p[i-1]]);
	}
	for(i=1;i<=n;i++)
	{
		p[i]=i;
	}
	sort(p+1,p+1+n,cmp_y);
	for(i=2;i<=n;i++)
	{
		add(p[i],p[i-1],y[p[i]]-y[p[i-1]]);
		add(p[i-1],p[i],y[p[i]]-y[p[i-1]]);
	}
	dijsktra(1);
	for(i=2;i<=n;i++)
	{
		cout<<dis[i]<<" ";
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

\(T2\) B. 排列 (permutation) \(20pts\)

  • 部分分
    • 子任务 \(1\) ：爆搜。
    • 子任务 \(3\) ：至多有一个数为 \(k\) 的倍数，故 \(n!\) 即为所求。
  • 正解

    • 将 \(1 \sim n\) 中是 \(k\) 的倍数的数看做断点。

    • 观察到 \(\frac{n}{k} \le 10\) ，枚举全排列后对相邻两数 \(\gcd=1\) 的进行插板法，最后再乘以 \((n-\left\lfloor \frac{n}{k} \right\rfloor)!\) 即可。

      点击查看代码 
      const ll p=998244353;
ll a[3010],inv[3010],jc[3010],jc_inv[3010];
ll qpow(ll a,ll b,ll p)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
		{
			ans=ans*a%p;
		}
		b>>=1;
		a=a*a%p;
	}
	return ans;
}
ll gcd(ll a,ll b)
{
	return b?gcd(b,a%b):a;
}
ll C(ll n,ll m,ll p)
{
	return (n>=m&&n>=0&&m>=0)?(jc[n]*jc_inv[n-m])%p*jc_inv[m]%p:0;
}
ll A(ll n,ll m,ll p)
{
	return (n>=m&&n>=0&&m>=0)?(jc[n]*jc_inv[n-m])%p:0;
}
int main()
{
	freopen("permutation.in","r",stdin);
	freopen("permutation.out","w",stdout);
	ll n,k,m,ans=0,sum=0,i;
	cin>>n>>k;
	m=n/k;
	for(i=1;i<=m;i++)
	{
		a[i]=i;
	}
	jc[0]=jc_inv[0]=1;
	for(i=1;i<=n;i++)
	{
		inv[i]=qpow(i,p-2,p);
		jc[i]=jc[i-1]*i%p;
		jc_inv[i]=jc_inv[i-1]*inv[i]%p;
	}
	do
	{
		sum=0;
		for(i=2;i<=m;i++)
		{
			sum+=(gcd(a[i],a[i-1])==1);
		}
		ans=(ans+C(n-m-sum+m+1-1,m+1-1,p))%p;
	}while(next_permutation(a+1,a+1+m));
	cout<<ans*A(n-m,n-m,p)%p<<endl;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

\(T3\) C. 战场模拟器 (simulator) \(9pts\)

  • 弱化版： 北京建筑大学2024年程序设计竞赛（同步赛） A 寿命修改

  • 部分分

    • 子任务 \(1\) ：模拟。

    • 子任务 \(2\) ：线段树维护。

    • 子任务 \(3\)

  • 正解

    • 因为每个英雄只会死一次，且只有 \(O(q)\) 个护盾，势能线段树即可。
    • 特别地，需要维护最小非负生命值出现次数来计算濒死数量。
    点击查看代码 
    ll a[200010];
struct SMT
{
	struct SegmentTree
	{
		ll sum,minn,cnt,died,lazy;
	}tree[800010];
	ll lson(ll x)
	{
		return x*2;
	}
	ll rson(ll x)
	{
		return x*2+1;
	}
	void pushup(ll rt)
	{
		tree[rt].sum=tree[lson(rt)].sum+tree[rson(rt)].sum;
		tree[rt].minn=min(tree[lson(rt)].minn,tree[rson(rt)].minn);
		tree[rt].cnt=(tree[lson(rt)].minn==tree[rt].minn)*tree[lson(rt)].cnt+(tree[rson(rt)].minn==tree[rt].minn)*tree[rson(rt)].cnt;
		tree[rt].died=tree[lson(rt)].died+tree[rson(rt)].died;
	}
	void build(ll rt,ll l,ll r)
	{
		if(l==r)
		{
			tree[rt].minn=a[l];
			tree[rt].cnt=1;
			return;
		}
		ll mid=(l+r)/2;
		build(lson(rt),l,mid);
		build(rson(rt),mid+1,r);
		pushup(rt);
	}
	void pushdown(ll rt)
	{
		if(tree[rt].lazy!=0)
		{
			tree[lson(rt)].lazy+=tree[rt].lazy;
			tree[lson(rt)].minn+=tree[rt].lazy;
			tree[rson(rt)].lazy+=tree[rt].lazy;
			tree[rson(rt)].minn+=tree[rt].lazy;
			tree[rt].lazy=0;
		}
	}
	void update1(ll rt,ll l,ll r,ll x,ll y,ll val)
	{
		if(tree[rt].died==r-l+1)
		{
			return;
		}
		if(l==r)
		{
			if(tree[rt].sum==0)
			{
				tree[rt].minn-=val;
				if(tree[rt].minn<0)
				{
					tree[rt].minn=0x7f7f7f7f;
					tree[rt].died=1;
				}
			}
			else
			{
				tree[rt].sum--;
			}
			return;
		}
		if(x<=l&&r<=y)
		{
			if(tree[rt].sum==0&&tree[rt].minn-val>=0)
			{
				tree[rt].minn-=val;
				tree[rt].lazy-=val;
				return;
			}
		}
		pushdown(rt);
		ll mid=(l+r)/2;
		if(x<=mid)
		{
			update1(lson(rt),l,mid,x,y,val);
		}
		if(y>mid)
		{
			update1(rson(rt),mid+1,r,x,y,val);
		}
		pushup(rt);
	}
	void update2(ll rt,ll l,ll r,ll x,ll y,ll val)
	{
		if(tree[rt].died==r-l+1)
		{
			return;
		}
		if(x<=l&&r<=y)
		{
			tree[rt].minn+=val;
			tree[rt].lazy+=val;
			return;
		}
		pushdown(rt);
		ll mid=(l+r)/2;
		if(x<=mid)
		{
			update2(lson(rt),l,mid,x,y,val);
		}
		if(y>mid)
		{
			update2(rson(rt),mid+1,r,x,y,val);
		}
		pushup(rt);
	}
	void update3(ll rt,ll l,ll r,ll pos)
	{
		if(tree[rt].died==r-l+1)
		{
			return;
		}
		if(l==r)
		{
			tree[rt].sum++;
			return;
		}
		pushdown(rt);
		ll mid=(l+r)/2;
		if(pos<=mid)
		{
			update3(lson(rt),l,mid,pos);
		}
		else
		{
			update3(rson(rt),mid+1,r,pos);
		}
		pushup(rt);
	}
	ll query1(ll rt,ll l,ll r,ll x,ll y)
	{
		if(x<=l&&r<=y)
		{
			return tree[rt].died;
		}
		pushdown(rt);
		ll mid=(l+r)/2,ans=0;
		if(x<=mid)
		{
			ans+=query1(lson(rt),l,mid,x,y);
		}
		if(y>mid)
		{
			ans+=query1(rson(rt),mid+1,r,x,y);
		}
		return ans;
	}
	ll query2(ll rt,ll l,ll r,ll x,ll y)
	{
		if(x<=l&&r<=y)
		{
			return (tree[rt].minn==0)*tree[rt].cnt;
		}
		pushdown(rt);
		ll mid=(l+r)/2,ans=0;
		if(x<=mid)
		{
			ans+=query2(lson(rt),l,mid,x,y);
		}
		if(y>mid)
		{
			ans+=query2(rson(rt),mid+1,r,x,y);
		}
		return ans;
	}
}T;
int main()
{
	freopen("simulator.in","r",stdin);
	freopen("simulator.out","w",stdout);
	ll n,q,pd,l,r,x,i;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	T.build(1,1,n);
	cin>>q;
	for(i=1;i<=q;i++)
	{
		cin>>pd;
		if(pd==1)
		{
			cin>>l>>r>>x;
			T.update1(1,1,n,l,r,x);
		}
		if(pd==2)
		{
			cin>>l>>r>>x;
			T.update2(1,1,n,l,r,x);
		}
		if(pd==3)
		{
			cin>>x;
			T.update3(1,1,n,x);
		}
		if(pd==4)
		{
			cin>>l>>r;
			cout<<T.query1(1,1,n,l,r)<<endl;
		}
		if(pd==5)
		{
			cin>>l>>r;
			cout<<T.query2(1,1,n,l,r)<<endl;
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

\(T4\) D. 点亮 (light) \(0pts\)

总结

  • \(T1\) 输出成了 \(1\) 到 \(1 \sim n\) 的最短路，而且 \(Dijsktra\) 加入队列时把边权当做点的标号加进去了，挂了 \(40pts\) 。
  • \(T2\) 误认为只要是 \(k\) 的倍数，相邻两数的 \(\gcd\) 就等于 \(k\) ，得到的 \(O(\frac{n^{2}}{k})\) 做法假了。
  • \(T3\) 直接去写势能线段树正解了的，但最后正解没调出来，部分分一点没打。

标签：rt,return,minn,08,tree,多校,ll,NOIP2024,rson
From： https://www.cnblogs.com/The-Shadow-Dragon/p/18472657

相关文章

  • Oracle 19c OCP 认证考试 083 题库(第3题)- 2024年修正版
    【优技教育】Oracle19cOCP083题库(Q3题)-2024年修正版考试科目：1Z0-083考试题量：85道（线下）通过分数：57%以上考试时间：150min（线下）本文为(CUUG原创)整理并解析，转发请注明出处，禁止抄袭及未经注明出处的转载。原文地址：http://www.cuug.com.cn/ocp/083kaoshitiku/38540354314.ht......
  • 「模拟赛」多校 A 层联训 8
    \(22pts\)，本来可以切掉前两个题的？！A.传送(teleport)签到12pts，错的很唐！我把Dij用的dis数组直接赋值成了点到1号点之间的x距离和y距离的最小值，没再赋成极大值，这样会改变Dij过程中点遍历到的顺序，然后就跑不出最短路了。好像不能算挂分？但其实赛时有点感觉是这的问......
  • 2024.10.08星期二
    今天配置了vue环境，学习了基础的vue语法，在这个过程中遇到了如下问题1.安装完node.js和vuecli后，创建项目的时候出现了问题我无法通过yarnserve启动项目，但由于默认下载设置的是yarn，导致也无法使用npmrunserve启动在这里卡了很久，解决办法是在C盘的user目录下有一个文件，其实后面......
  • 洛谷题单指南-字符串-P2922 [USACO08DEC] Secret Message G
    原题链接：https://www.luogu.com.cn/problem/P2922题意解读：已知M个01串，给出N个01串，对于N个串的每一个，求在M个串中有多少与其有公共前缀，且前缀长度是两个串中较小者。解题思路：用Trie树存储M个01串，用cnt1[]记录某个节点结束的01串个数，cnt2[]记录经过某个节点的01串的数量对于N个0......
  • 《安富莱嵌入式周报》第344期：开源手表一年的误差不到1秒，开源32路IMU传感器矩阵，STM32L4
    周报汇总地址：http://www.armbbs.cn/forum.php?mod=forumdisplay&fid=12&filter=typeid&typeid=104 本周更新视频DSP视频教程第13期：汇编浮点库qfplib性能媲美TI的IQmath和硬件FPU，强于C库的math和ARMDSP库，适用于M0和M3(2024-10-12)https://www.armbbs.cn/forum.php?mod=view......
  • 2023杭电多校4
    2023杭电多校4C-SimpleSetProblem题目描述：一共T组输入，每组输入有K个集合，从K个集合中选取K个数，也就是每个集合选取一个数，问这些数字中的最大值减去这些数字中的最小值的最小的值。解题思路：利用双指针，对于每一个右端点，存一段至少包含所有集合的点各一个的区间，然后就......
  • PTA L1系列题解（C语言）（L1_073 -- L1_080）
    L1-073人与神题目内容：L1-073人与神-团体程序设计天梯赛-练习集(pintia.cn)跨界大神L.PeterDeutsch有一句名言：“Toiterateishuman,torecursedivine.”（迭代的是人，递归的是神）。本题就请你直接在屏幕上输出这句话。输入格式：本题没有输入。输出格式：在一行中输......
  • 机器学习篇-day08-聚类Kmeans算法
    一.聚类算法简介概念无监督学习算法根据样本之间的相似性，将样本划分到不同的类别中；不同的相似度计算方法，会得到不同的聚类结果，常用的相似度计算方法有欧式距离法。聚类算法的目的是在没有先验知识的情况下，自动发现数据集中的内在结构和模式。使用不同的聚类准则,产生的......
  • Golang笔记_day08
    Go面试题（一）1、空切片和nil切片区别空切片：   空切片是指长度和容量都为0的切片。它不包含任何元素，但仍然具有切片的容量属性。在Go语言中，可以使用内置的make函数创建一个空切片，例如：emptySlice:=make([]int)   这个语句创建了一个长度为0、容量为0的空切片......
  • [赛记] csp-s模拟11 && 多校A层冲刺NOIP2024模拟赛07
    玩水(water)100pts一道结论题，考场一眼出，结果认为不对，然后被硬控了2h结果打出了个抽象DP然后过了；赛后发现，这DP和那个结论是等价的。。。；首先考虑只有两个人怎么做，那么我们只需找出一个位置$(i,j)$满足$a_{i+1,j}=a_{i,j+1}$即可；那么三个人呢？设现在有两个满......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99