首页 > 其他分享 >csp-s模拟2

csp-s模拟2

时间:2024-09-08 18:03:20浏览次数:13  
标签:1.0 int return ans frac csp 模拟 mod

A. 不相邻集合

可以发现,一个数只有在第一次出现才会做贡献,对于一个连续数段 \(1,2,3...n\) ,它最多提供 \(\lceil \frac{n}{2} \rceil\)的贡献,所以只需要维护

极长连续段即可

点击查看代码
#include<bits/stdc++.h>
const int maxn=3e5+10; 
using namespace std;
int n,a[maxn],fa[500005],size[500005],ans;
bool vis[500005]; 
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int mo(int x){return (size[x]+1)>>1;}
void merge(int x,int y)
{
	int a=find(x),b=find(y); 
	if(a==b) return ;
	fa[b]=a;
	ans-=mo(a)+mo(b);
	size[a]+=size[b];
	ans+=mo(a);
}

int main()
{
//	freopen("set1.in","r",stdin);
//	freopen("T.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	cin>>n;
	for(int i=1;i<=500001;i++) fa[i]=i,size[i]=1;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(!vis[a[i]])ans++; 
		vis[a[i]]=1;
		if(vis[a[i]-1])
		{
//			cout<<find(a[i]-1)<<" "<<find(a[i])<<endl; 
			merge(a[i]-1,a[i]);
		}
		if(vis[a[i]+1])
		{
			merge(a[i],a[i]+1);
		}
		cout<<ans<<" ";
	}
	

	return 0;
}
/*

*/

B. 线段树

设 \(f(n,x)\) 为有 \(n\) 个节点,根标号为 \(x\) 的线段树的节点标号和,可以发现其是一个确定的一次函数

因为 \(f(n,x)=f(\lceil \frac{n}{2} \rceil,2x)+f(\lfloor \frac{n}{2} \rfloor,2x+1)+x\),可以推出 \(k_n=2(k_{\lceil \frac{n}{2} \rceil}+k_{\lfloor \frac{n}{2} \rfloor})+1\),\(b_n=(b_{\lceil \frac{n}{2} \rceil}+b_{\lfloor \frac{n}{2} \rfloor}+k_{\lfloor \frac{n}{2} \rfloor})\)

每次查到一个区间属于 \(x\)~\(y\) ,没查过则处理一下 \(k_n\) 和 \(b_n\) ,查过则直接返回,单次复杂度 \(O(log_n)\)

点击查看代码
#include<bits/stdc++.h>
#define int long long 
const int mod=1e9+7;
const int maxn=2e5+10;
using namespace std;
int t,n,x,y;
map<int ,int >k,b;
void lsx(int x)
{
	if(x==1) return ;
	if(k[x]&&b[x]) return ; 
	lsx(floor(1.0*x/2));
	k[x]+=2*k[floor(1.0*x/2)];
	b[x]+=b[floor(1.0*x/2)]+k[floor(1.0*x/2)]; 
	k[x]%=mod;
	b[x]%=mod;
	lsx(ceil(1.0*x/2)); 
	k[x]+=2*k[ceil(1.0*x/2)]+1;
	b[x]+=b[ceil(1.0*x/2)];
	k[x]%=mod;
	b[x]%=mod;
}

int solve(int id,int l,int r,int x,int y)
{
	if(l>=x&&r<=y)
	{
		lsx(r-l+1);
		return (k[r-l+1]*id%mod+b[r-l+1])%mod;
	}
	int mid=l+r>>1,tem=0;
	if(mid>=x) tem=(tem+solve((id<<1)%mod,l,mid,x,y))%mod;
	if(mid<y) tem=(tem+solve((id<<1|1)%mod,mid+1,r,x,y))%mod;
	return tem;
}

signed main()
{
//	freopen("T.in","r",stdin);
//	freopen("T.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	k[1]=1,b[1]=0;
	cin>>t;
	while(t--)
	{
		cin>>n>>x>>y;
		cout<<solve(1,1,n,x,y)<<'\n';
	}

	return 0;
}
/*

*/

C. 魔法师

对于魔杖 \(p\) 和魔法 \(q\) ,它们的魔法是 \(\max(a_p+a_q,b_p+b_q)\),先分讨简化,假设 \(a_p+a_q<b_p+b_q\),则有 \(a_p-b_p<b_q-a_q\)

记 \(u_p=a_p-b_q,v_q=b_q-a_q\),则魔力的大小则取决于 \(u_p\) 和 \(v_q\) 的大小,把所有魔杖和魔法以其 \(u_p/v_q\) 为下标存到一棵权值

线段树上,找右区间最小的 \(b_p\) 和左区间最小的 \(b_q\),和找右区间最小的 \(a_p\) 和左区间最小的 \(a_q\)即可

点击查看代码
#include<bits/stdc++.h>
#define lid id<<1
#define rid id<<1|1
const int maxn=25e4+10;
const int mm=25e4;
const int inf=0x7f7f7f;
using namespace std;
int Q,T,ans,last,cnt1,cnt2;
struct lsx
{
	int l,r,a[4],ans;
}m[maxn<<3],s; 
multiset<int >q[maxn<<1][4];

void build(int id,int l,int r)
{
	m[id].l=l,m[id].r=r;
	m[id].ans=m[id].a[0]=m[id].a[1]=m[id].a[2]=m[id].a[3]=inf;
	if(l==r) return ;
	int mid=l+r>>1;
	build(lid,l,mid);
	build(rid,mid+1,r); 
}

void up(int id)
{
	for(int i=0;i<4;i++) m[id].a[i]=min(m[lid].a[i],m[rid].a[i]);
	m[id].ans=min(m[lid].a[3]+m[rid].a[1],m[lid].a[0]+m[rid].a[2]);
	m[id].ans=min(m[id].ans,min(m[lid].ans,m[rid].ans));
}

void update(int id,int x)
{
	int l=m[id].l,r=m[id].r;
	if(l==r)
	{
		m[id]=s;
		if(m[id].a[0]+m[id].a[2]<=inf||m[id].a[1]+m[id].a[3]<=inf) 
			m[id].ans=min(m[id].a[0]+m[id].a[2],m[id].a[1]+m[id].a[3]);
		return ;
	}
	int mid=l+r>>1;
	if(x<=mid) update(lid,x);
	else update(rid,x);
	up(id);
}

int main()
{
//	freopen("T.in","r",stdin);
//	freopen("T.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>Q>>T;
	build(1,1,mm*2);
	s.a[0]=s.a[1]=s.a[2]=s.a[3]=s.ans=inf;
	while(Q--)
	{
		int op,t,x,y;
		cin>>op>>t>>x>>y;
		if(T) x^=last,y^=last;
		int pos=t?y-x+mm:x-y+mm;
		if(op==1)
		{
			if(t)
			{
				q[pos][0].insert(x),q[pos][1].insert(y);
				for(int i=0;i<4;i++)
				{
					if(q[pos][i].size()) s.a[i]=*q[pos][i].begin();
					else s.a[i]=inf;
				}
//				cout<<s.a[0]<<" "<<s.a[1]<<" "<<s.a[2]<<" "<<s.a[3]<<endl;
				update(1,pos);
			}
			else
			{
				q[pos][2].insert(x),q[pos][3].insert(y);
				for(int i=0;i<4;i++)
				{
					if(q[pos][i].size()) s.a[i]=*q[pos][i].begin();
					else s.a[i]=inf;
				}
//				cout<<s.a[0]<<" "<<s.a[1]<<" "<<s.a[2]<<" "<<s.a[3]<<endl;
				update(1,pos);
			}
		}
		else
		{
			if(t)
			{
				if(q[pos][0].size()&&q[pos][1].size()&&q[pos][0].find(x)!=q[pos][0].end()&&q[pos][1].find(y)!=q[pos][1].end())
				{
					q[pos][0].erase(q[pos][0].find(x));
					q[pos][1].erase(q[pos][1].find(y));
					for(int i=0;i<4;i++)
					{
						if(q[pos][i].size()) s.a[i]=*q[pos][i].begin();
						else s.a[i]=inf;
					}
					update(1,pos);
				}
				
			}
			else
			{
				if(q[pos][2].size()&&q[pos][3].size()&&q[pos][2].find(x)!=q[pos][2].end()&&q[pos][3].find(y)!=q[pos][3].end())
				{
					q[pos][2].erase(q[pos][2].find(x));
					q[pos][3].erase(q[pos][3].find(y));
					for(int i=0;i<4;i++)
					{
						if(q[pos][i].size()) s.a[i]=*q[pos][i].begin();
						else s.a[i]=inf;
					}
					update(1,pos);
				}
				
			}
		}
		cout<<(m[1].ans>=inf?0:m[1].ans)<<'\n'; 
		last=(m[1].ans>=inf?0:m[1].ans);
	}

	return 0;
}
/*

*/

标签:1.0,int,return,ans,frac,csp,模拟,mod
From: https://www.cnblogs.com/oceansofstars/p/18403192

相关文章

  • 9.8 模拟赛(炼石计划 11 月 11日 CSP-S 十连测 #9)
    炼石计划11月11日CSP-S十连测#9【补题】-比赛-梦熊联盟(mna.wang)\(100+60+20+15=195\)。复盘顺序开题。T1是二分板子。写之前思考好了所有代码细节直接写代码。一遍过了所有大样例。T2。题意好麻烦。\(35\)分是极易的。跳过\(25\)分部分分,直接想正解。有......
  • csp模拟2
    T1原题根据倒数第二,三个部分分的提示,我们可以发现一个性质,如果两个连续的序列中间被间隔开,如\(1,2,3,4,6,7,8,9\)那这两个序列中选数操作互不影响,那这就比较好办了,一个长度为\(n\)连续序列最多可以选出$\lceil\frac{n}{2}\rceil$个数,那我们只需要维护连续的区间的个......
  • NOIP 模拟赛 Round5
    T1:赛时一眼秒了,然后爆单了。没有什么思路就要想到一些套路比如把模拆成减除,然后发现有个\(k\),自然思路就出来了,\(k\)必然是一个数的因数。复杂度是根号的。注意特判\(s=0,s<0\)!!!T2:一眼二分贪心……显然不能优化建图按照a排序也是显然的。T3:最唐的地方是所有人都在考虑......
  • csp-s模拟1
    A.喜剧的迷人之处在于切入点在\(a\),考虑\(a\)是不是完全平方数,是的话直接找最小能匹配的完全平方数即可,不是的话\(a\)一定可以表示成\(kx^2\)的形式,倒着找到最大的平方因子除去,只需要在\(L\)~\(R\)间找到一个最小的数也等于\(kx^2\)即可点击查看代码#include<bits......
  • ZR 2024 NOIP 十连 & CSP 七连
    NOIPday1T1简单建图跑bfs,vector会被卡空间,用前向星才能过。T2注意到原串是否确定不重要,因为无非是把每种可能的转移都多做一遍。把所有可能出现的回文串的一半插进AC自动机中,就可以转移了。CSPday1T3设\(nxt_i\)表示下一个与\(a_i\)值相同的位置到\(i\)的距......
  • C++STL之stack和queue容器适配器:基本使用及模拟实现
    目录stack的介绍和使用stack的介绍stack的使用queue的介绍和使用queue的介绍queue的使用priority_queue的介绍和使用priority_queue的介绍priority_queue的使用deque双端队列(容器)deque的介绍及使用deque的缺点deque的原理(了解)容器适配器概念stack和queue的......
  • NOIP2024模拟赛5 总结
    NOIP2024模拟赛5总结T1天才俱乐部特判了\(sum-s<0\),但没有考虑\(sum-s=0\)。挂为0pts。T2实战教学由于写的不够优,贪心+二分的思路TLE了。由于不明原因,输出\(\max(a_i+b_i)\)能过。非常神奇。T3穿越银匙之门T4绳网委托一句话总结:挂分挂成sb了。......
  • 【题解】CPS-S模拟2
    目录PreT1.不相邻集合题目描述部分分40pts10pts正解思路代码T2.线段树题目描述部分分20pts正解思路代码T3.部分分40pts正解思路代码T4.部分分10pts正解思路代码AndPre赛时没有第一时间找到签到题,遂四处游走,后来决定先打T1,约1h时切了,然后1h打后3题暴力,后面推了推T4一个特殊性质,......
  • 【C++】vector的模拟实现
    文章目录一、前言二、构造函数模拟实现构造函数调用不明确1.问题描述2、解决调用不明确的方法三、基础接口1.empty和clear2.size和capacity3.[]和iterator四、resize和reservereserve中的深浅拷贝问题1、reserve中浅拷贝发生原因2、浅拷贝发生的图解3、解决方法五、尾......
  • 【洛谷 P1996】约瑟夫问题 题解(队列+模拟+循环)
    约瑟夫问题题目描述个人围成一圈,从第一个人开始报数,数到的人出列,再由下一个人重新从开始报数,数到的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。注意:本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰名小朋友,而该题是全部出圈。输入......