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

多校A层冲刺NOIP2024模拟赛09

时间：2024-10-19 21:44:12浏览次数：7  
标签：记得 线段 09 多校 down push ll NOIP2024 define

GG

多校A层冲刺NOIP2024模拟赛09

T1 排列最小生成树 (pmst)

需要思考一会。

你得发现一个性质：所有要的边的权值都得小于 n ，因为每个点都可以找到至少一条边权小于 n 的边，所以最后生成树里的边的边权一定小于 n 。

那么 $ \vert p_i - p_j \vert \times \vert i - j \vert $ 中较小的那个一定小于等于 $ \sqrt{n} $ ，所以直接 $ O (n \sqrt{n} ) $ 枚举建边即可，然后你就会因为把优先队列炸了而获得不如暴力的 $ 30 $ 分高分。

直接拿数组记就行了，然后 $ O(n) $ 枚举也可，直接 sort 也能过。

挂 70。。。。。。。。。。。。。。。。。。。。。。。

码 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mk make_pair
#define ps push_back
const int N=1e6+10,inf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
inline ll read(){
	char c=getchar();ll x=0,f=1;
	while(!isdigit(c))f=c=='-'?0:-1,c=getchar();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return f?x:-x;
}
int n,a[N],len,fa[N];
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
struct jj{
	int i,j,v;
	inline bool operator <(const jj&x)const{return v>x.v;}
}q[N<<4];
int pos[N];
unordered_map<int,bool> ma;
signed main(){

	// #ifndef ONLINE_JUDGE
	freopen("pmst.in","r",stdin);
	freopen("pmst.out","w",stdout);
	// #endif

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	n=read();
	for(int i=1;i<=n;++i)
		a[i]=read(),fa[i]=i;
	int len=sqrt(n),cnt=0;
	
	for(int i=1;i<=n;++i){
		ma.clear();
		for(int j=i-1;j&&i-j<=len;--j){
			if((i-j)*abs(a[i]-a[j])<=n&&!ma[j])q[++cnt]={i,j,(i-j)*abs(a[i]-a[j])},ma[j]=1;
		}
		for(int j=a[i];j<=n&&j<=a[i]+len;++j)
			if(pos[j]&&(i-pos[j])*(j-a[i])<=n&&!ma[pos[j]])q[++cnt]={i,pos[j],(i-pos[j])*(j-a[i])},ma[pos[j]]=1;
		for(int j=a[i];j&&j>=a[i]-len;--j)
			if(pos[j]&&(i-pos[j])*(a[i]-j)<=n&&!ma[pos[j]])q[++cnt]={i,pos[j],(i-pos[j])*(a[i]-j)},ma[pos[j]]=1;
		pos[a[i]]=i;
	}
	int num=0;
	ll ans=0;
	sort(q+1,q+1+cnt,[](const jj&x,const jj&y){return x.v<y.v;});
	for(int i=1;i<=cnt&&num<n-1;++i){
		int fx=find(q[i].i),fy=find(q[i].j);
		if(fx!=fy){
			++num;fa[fx]=fy;ans+=q[i].v;
		}
	}
	cout<<ans;


	return 0;
}

T2 卡牌游戏 (cardgame)

签到题。

首先为了方便讨论，我们假设 $ n \le m $ ，那么对于每一个 $ a_i $ ，他会对应一些 $ b_j (j=(i+kn) \mod m | k < n)$ 。这些 $ b_j $ 是一个循环，那么我们只要记下所有循环节，并对于所有的 $ b_j $ ，把他属于的的循环节的编号记下来，对于每个 $ a_i $ 他肯定对应着 $ b_i $ （因为 n < m），所以就能找到与 $ a_i $ 相对应的循环节，然后直接 lower_bound 即可。

别忘了一开始 swap 保证 $ n \le m $ ，最后答案也要 swap 回去。

码 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mk make_pair
#define ps push_back
const int N=1e6+10,inf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
inline ll read(){
	char c=getchar();ll x=0,f=1;
	while(!isdigit(c))f=c=='-'?0:-1,c=getchar();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return f?x:-x;
}
int n,m,a[N],b[N],cnt;
int id[N];
#define ne(x) (x+n>m?x+n-m:x+n)
vector<int> v[N/10];
signed main(){

	// #ifndef ONLINE_JUDGE
	freopen("cardgame.in","r",stdin);
	freopen("cardgame.out","w",stdout);
	// #endif

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	n=read(),m=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	for(int i=1;i<=m;++i)
		b[i]=read();
	bool f=0;
	if(n>m)swap(n,m),swap(a,b),f=1;
	int gc=__gcd(n,m);
	for(int i=1;i<=m;++i){
		if(!id[i]){
			id[i]=++cnt;v[cnt].ps(b[i]);
			for(int j=ne(i);j!=i;j=ne(j))
				id[j]=cnt,v[cnt].ps(b[j]);
			sort(v[cnt].begin(), v[cnt].end());
		}
	}
	ll ans1=0,ans2=0,ans3=0;
	for(int i=1;i<=n;++i){
		int pos=lower_bound(v[id[i]].begin(),v[id[i]].end(),a[i])-v[id[i]].begin(),pos2=upper_bound(v[id[i]].begin(), v[id[i]].end(),a[i])-v[id[i]].begin();
		ans1+=pos,ans2+=pos2-pos,ans3+=v[id[i]].size()-pos2;
	}
	ans1*=gc;ans2*=gc,ans3*=gc;
	if(f)swap(ans1,ans3);
	cout<<ans1<<'\n'<<ans3<<'\n'<<ans2;

	return 0;
}

T3 比特跳跃 (jump)

竟然是一道分讨题。

对于 & 操作

数越 & 越小，然后你就可以发现一个性质：只要最大点不是 $ 1111111_{(2)} $ 这类数，或者说他只要在小于等于 n 的范围内有一个 0 ，那么他一定可以通过某个数耗费 0 的代价转移过来。如果他全是 1 的话，那么就只能选一个跟他有关的最小边或者直接通过 1 转移过来。

所以直接特判 n 即可。

对于 ^ 操作

^ 其实就是看两个数二进制之间有多少位不一样，然后你又可以发现：先不一样一个 1 ，再不一样一个 2 ，和直接不一样一个 3 是等价的，所以我们只建有一位不一样的边即可，边数是 $ O (m+ nlog(n)) $ 的。

然后跑 dij 就行了。

对于 | 操作

数越 | 越大，所以通过|操作最多只转移 1 次，而且因为起点是 1 ，那么从 1 去转移 $ i $ ，耗费最大是 $ K \times (i+1) $ ，而且无论从哪些点转移到 $ i $ ，最小耗费也得是 $ K \times i $ ，那么哪些可以只消耗 $ K \times i $ 转过来呢，只有 $ i $ 的子集可以做到，那么我们不能枚举所有子集吧，那就只枚举少一个 1 的子集，此时用 $ tag_i $ 表示 $ i 和 i 的子集 $ 的 $ dis $ 的最小值，这样就可以 $ O (nlog(n)) $ 转移了。

所以只需要加上 1 到所有点 | 的边，跑一边 $ dij $ ，然后枚举 | 转移，然后再跑一边 $ dij $ 即可。

为什么只需要跑两遍 $ dij $ ？因为之前说过通过 | 只会转移一次。所以只 | 转移一次就行。

码 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mk make_pair
#define ps push_back
const int N=1e6+10,inf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
inline ll read(){
	char c=getchar();ll x=0,f=1;
	while(!isdigit(c))f=c=='-'?0:-1,c=getchar();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return f?x:-x;
}
#define int ll
int n,m,cnt,hd[N],S,K;
struct jj{
	int to,next;ll w;
}bi[N<<3];
inline void add(int x,int y,ll z){bi[++cnt]={y,hd[x],z},hd[x]=cnt,bi[++cnt]={x,hd[y],z},hd[y]=cnt;}
ll dis[N],adis[N];
bool vis[N];
inline void dij(){
	fill(vis+1,vis+1+n,0);
	dis[1]=0;
	priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > >q;
	for(int i=1;i<=n;++i)
		q.push({dis[i],i});
	// q.push({dis[1],1});
	while(!q.empty()){
		int k=q.top().se;q.pop();
		if(vis[k])continue;
		// cout<<k<<' '<<dis[k]<<"DIJ\n";
		vis[k]=1;
		for(int i=hd[k];i;i=bi[i].next){
			int j=bi[i].to;
			if(dis[j]>dis[k]+bi[i].w)
				dis[j]=dis[k]+bi[i].w,q.push({dis[j],j});
		}
	}
}
signed main(){

	// #ifndef ONLINE_JUDGE
	freopen("jump.in","r",stdin);
	freopen("jump.out","w",stdout);
	// #endif

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	n=read(),m=read();S=read(),K=read();
	// cout<<S<<','<<K<<',';
	for(int i=1,x,y,z;i<=m;++i){
		x=read(),y=read(),z=read();
		add(x,y,z);
		// cout<<x<<','<<y<<','<<z<<',';
	}
	if(S==1){
		for(int i=2;i<n;++i)
			cout<<0<<' ';
		if((int)log2(n+1)!=(int)log2(n)){
			int ans=inf;
			for(int i=1;i<=cnt;++i){
				if(bi[i].to==n)ans=min(ans,bi[i].w);
			}
			cout<<min(ans,K);
		}
		else{
			cout<<0;
		}
		return 0;
	}
	if(S==2){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;j<<=1)
				if((i^j)<=n)add(i,i^j,j*K);
		}
		for(int i=2;i<=n;++i)
			add(1,i,K*(i^1));
		fill(dis+1,dis+1+n,linf);
		dij();
		for(int i=2;i<=n;++i)
			cout<<dis[i]<<' ';
		return 0;
	}
	else{
		// cout<<n<<','<<m<<',';
		// return 0;
		for(int i=2;i<=n;++i)
			add(1,i,K*(i|1));
		fill(dis+1,dis+1+n,linf);
		dij();
		adis[1]=0;
		for(int i=2;i<=n;++i){
			adis[i]=linf;
			for(int j=1;j<i;j<<=1){
				if((i&j)){
					adis[i]=min(adis[i],adis[i^j]);
					// cout<<i<<' '<<j<<' '<<dis[j]<<' '<<dis[i]<<endl;
				}
			}
			adis[i]=min(adis[i],dis[i]);
			dis[i]=min(dis[i],adis[i]+i*K);
			// cout<<i<<' '<<dis[i]<<endl;
		}
		dij();
		for(int i=2;i<=n;++i)
			cout<<dis[i]<<' ';
		return 0;
	}
	// for(int i=1;i<=n;++i){
	// 	for(int j=i+1;j<=n;++j){
	// 		add(i,j,K*(S==1?(i&j):S==2?(i^j):(i|j)));
	// 		// cout<<i<<' '<<j<<' '<<(i|j)<<endl;
	// 	}
	// }
	// fill(dis+1,dis+1+n,linf);
	// dij();
	// for(int i=2;i<=n;++i)
	// 	cout<<dis[i]<<' ';
	// return 0;
	


	return 0;
}

T4 区间 (interval)

<marquee>线段树记得push_down！！！ 线段树记得push_down！！！ 线段树记得push_down！！！</marquee>

<marquee>线段树记得push_down！！！ 线段树记得push_down！！！ 线段树记得push_down！！！</marquee>

<marquee>线段树记得push_down！！！ 线段树记得push_down！！！ 线段树记得push_down！！！</marquee>

<marquee>线段树记得push_down！！！ 线段树记得push_down！！！ 线段树记得push_down！！！</marquee>

<marquee>线段树记得push_down！！！ 线段树记得push_down！！！ 线段树记得push_down！！！</marquee>

<marquee>线段树记得push_down！！！ 线段树记得push_down！！！ 线段树记得push_down！！！</marquee>

<marquee>线段树记得push_down！！！ 线段树记得push_down！！！ 线段树记得push_down！！！</marquee>

<marquee>线段树记得push_down！！！ 线段树记得push_down！！！ 线段树记得push_down！！！</marquee>

<marquee>线段树记得push_down！！！ 线段树记得push_down！！！ 线段树记得push_down！！！</marquee>

<marquee>线段树记得push_down！！！ 线段树记得push_down！！！ 线段树记得push_down！！！</marquee>

好的，这就是我爆 0 的原因。

这题其实就是个求区间历史和的板子。

我们可以用离线下来按照 $ r $ 排序，然后单调栈维护可以贡献的区间有哪些，但是发现这些区间并不是连续的，也就有可能被卡成 $ O(n^2) $ 的，但是因为这是一段后缀抛去了一些被单调栈弹出去的数，那么我们给这些被弹出去的数打上tag，然后直接区间加就行了。

挂 100。

码 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int ll
typedef pair<int,int> pii;
#define fi first
#define se second
#define mk make_pair
#define ps push_back
const int N=1e6+10,inf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
inline ll read(){
	char c=getchar();ll x=0,f=1;
	while(!isdigit(c))f=c=='-'?0:-1,c=getchar();
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return f?x:-x;
}
int n,Q,a[N],b[N];
struct jj{
	int l,r,id;
}q[N];
ll sum[N<<2],tag[N<<2],c[N<<2],ta[N<<2];
inline void down(int k,int len1,int len2){
	if(ta[k])sum[k<<1]+=ta[k]*(len1-tag[k<<1]),sum[k<<1|1]+=ta[k]*(len2-tag[k<<1|1]),ta[k<<1]+=ta[k],ta[k<<1|1]+=ta[k],ta[k]=0;
}
inline void add(int k,int l,int r,int pos){
	if(l==r)return (void)(++tag[k]);
	int mid=l+r>>1;
	down(k,mid-l+1,r-mid);
	pos<=mid?add(k<<1,l,mid,pos):add(k<<1|1,mid+1,r,pos);
	tag[k]=tag[k<<1]+tag[k<<1|1];
}
inline void add(int k,int l,int r,int L,int R){
	if(L<=l&&r<=R)return (void)(sum[k]+=r-l+1-tag[k],ta[k]++);
	int mid=l+r>>1;
	down(k,mid-l+1,r-mid);
	if(L<=mid)add(k<<1,l,mid,L,R);
	if(R>mid)add(k<<1|1,mid+1,r,L,R);
	sum[k]=sum[k<<1]+sum[k<<1|1];
}
inline int ask(int k,int l,int r,int L,int R){
	if(L<=l&&r<=R)return sum[k];
	int mid=l+r>>1,ans=0;
	down(k,mid-l+1,r-mid);
	if(L<=mid)ans=ask(k<<1,l,mid,L,R);
	if(R>mid)ans+=ask(k<<1|1,mid+1,r,L,R);
	return ans;
}
int top;
pii st[N];
ll ans[N];
signed main(){

	// #ifndef ONLINE_JUDGE
	freopen("interval.in","r",stdin);
	freopen("interval.out","w",stdout);
	// #endif

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	n=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	for(int i=2;i<=n;++i)
		b[i]=read();
	Q=read();
	for(int i=1;i<=Q;++i){
		q[i].l=read(),q[i].r=read();q[i].id=i;
	}
	sort(q+1,q+1+Q,[](const jj&x,const jj&y){return x.r<y.r;});
	for(int i=1,j=1;i<=n;++i){
		int l=1,r=top,pos=0;
		while(l<=r){
			int mid=l+r>>1;
			if(st[mid].se<b[i])pos=mid,r=mid-1;
			else l=mid+1;
		}
		// cout<<i<<' '<<pos<<' '<<st[pos].fi<<endl;
		if(pos&&st[pos].fi<i)add(1,1,n,st[pos].fi,i-1);
		while(j<=Q&&q[j].r==i){
			ans[q[j].id]=ask(1,1,n,q[j].l,i),++j;
		}
		while(top&&st[top].se<=a[i])add(1,1,n,st[top].fi),--top;
		st[++top]={i,a[i]};
	}

	for(int i=1;i<=Q;++i)
		cout<<ans[i]<<'\n';
	return 0;
}

标签：记得,线段,09,多校,down,push,ll,NOIP2024,define
From： https://www.cnblogs.com/GGrun-sum/p/18486623

相关文章

  • 09视图
    视图......
  • [51] (多校联训) A层冲刺NOIP2024模拟赛09
    关于生成式AI怎么才能让这个b学会断句我目前的方案是，把逗号和句号单独作为一个特殊词汇看待，也统计到词频里，该断句的时候就断表扬这次的题解，写的很清楚A.排列最小生成树总存在一颗生成树使得树上最大边权值小于\(n\)考虑直接连接序列里的所有\((i,i+1)\)，因为\(|a_......
  • P1091 [NOIP2004 提高组] 合唱队形
    分析题目知道求一个最长上升子序列和一个最长下降子序列的长度均为同一个起点的最长的长度。于是求点击查看代码#include<iostream>#include<stack>#include<cmath>#include<algorithm>#include<set>#include<vector>#include<climits>#include<string.h>#incl......
  • Golang笔记_day09
    Go面试题（二）1、怎么做代码优化减少内存分配        内存分配是任何程序的基本操作之一，也是一个明显的性能瓶颈。在Golang中，减少内存分配是一种有效的代码优化方式。为了减少内存分配，我们可以使用以下技巧：复用变量：在循环或迭代过程中，尽量避免重新分配变量。通过在循......
  • 2024.10.18 2309版
    起于《海奥华预言》的思考◆地球管理结构和参考持续更新中...... 英文地址：https://github.com/zhuyongzhe/Earth/tags中文地址：https://www.cnblogs.com/zhuyongzhe85作者：朱永哲 ---------------------------------------------------------------------------------......
  • P10992 Solution
    DescriptionLinkSolution好题。本题主要有两个问题：哈希函数的设计和子串的枚举。作为哈希题的套路，首先可以想到二分答案长度，再做check。考虑如何设计哈希函数来check。令二分出的长度为\(len\)。设计出的哈希函数需要满足两个条件：两个串对应的字符集相同，对应字符集的下......
  • [49 & 50] (多校联训) A层冲刺NOIP2024模拟赛08 | CSP-S 模拟 12
    一小孩在奶茶店玩封盖机被绞断四根手指记者：你现在感觉怎么样小孩：......
  • P5690 [CSP-S2019 江西] 日期 &&P7909 [CSP-J 2021] 分糖果 &&P5657 [CSP-S2019] 格雷
    今天继续懒惰，继续三合一！！！[CSP-S2019江西]日期题目背景CSP-SJX2019T1题目描述Alice在纸上写下了一个日期，形式为\(\text{MM-DD}\)，其中\(\text{MM}\)与\(\text{DD}\)都是两位数字，分别表示月和天，然而这个日期并不一定存在。Alice找来了Bob要他更改若干位上的数字，使得这个......
  • 10093-基于STM32的无线串口小型直流电机调速器设计（仿真+原理图+源代码工程+详细介绍说
    10093-基于STM32的无线串口小型直流电机调速器设计（仿真+原理图+源代码工程+详细介绍说明书+proteus）功能描述：直流电机的调速器设计设计，需要设计一个调速与控制系统，是设备可以直接控制和读取信息，并且显示。①设计直流电机转速控制系统；②通过按键调节直流电机转速；③可以在......
  • 10093-基于STM32的无线串口小型直流电机调速器设计（仿真+原理图+源代码工程+详细介绍说
    10093-基于STM32的无线串口小型直流电机调速器设计（仿真+原理图+源代码工程+详细介绍说明书+proteus）功能描述：直流电机的调速器设计设计，需要设计一个调速与控制系统，是设备可以直接控制和读取信息，并且显示。①设计直流电机转速控制系统；②通过按键调节直流电机转速；③可以在......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99