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

csp模拟2

时间：2024-09-08 18:02:42浏览次数：12  
标签：ch int read while 区间 csp 模拟 getchar

T1

原题

根据倒数第二，三个部分分的提示，我们可以发现一个性质，如果两个连续的序列中间被间隔开，如 \(1,2,3,4,6,7,8,9\) 那这两个序列中选数操作互不影响，那这就比较好办了，一个长度为 \(n\) 连续序列最多可以选出 $ \lceil \frac{n}{2}\rceil$ 个数 , 那我们只需要维护连续的区间的个数以及长度，这道题就做完了。

那我们就可以考虑带权并查集 ， 用并查集来维护连续的区间，每个新加入的数，要么单开一个区间，要么接在一个区间的一侧，要么连接两个区间，每当加入这个数之后，判断一下区间的能选的数的个数是否增加。

点击查看代码 




#include<bits/stdc++.h>
using namespace std;

const int N=6e5+107;
int n,a[N];
int num[N];
int vis[N],flag[N];

int fa[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int read()
{
	int f=1,s=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
	return f*s;
}

int main()
{
	n=read();
	for(int i=1;i<N;i++) fa[i]=i;
	
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		if(!vis[a[i]])
		{
			vis[a[i]]=1;
			
			if(vis[a[i]-1]&&vis[a[i]+1])
			{
				int fx=find(a[i]);
				int fy=find(a[i]-1);
				int fz=find(a[i]+1);
				if(fx!=fy)
				{
					fa[fx]=fy;
					num[fy]=num[fx]+num[fy];
				}
				if(fy!=fz)
				{
					fa[fy]=fz;
					if(num[fz]%2==0&&num[fy]%2==0) ans++;
					num[fz]=num[fy]+num[fz]+1;
				}
			}
			else if(vis[a[i]-1])
			{
				int fx=find(a[i]);
				int fy=find(a[i]-1);
				if(fx!=fy)
				{
					fa[fx]=fy;
					num[fy]=num[fx]+num[fy]+1;
					if(num[fy]%2==1) ans++;
				}
			}
			else if(vis[a[i]+1])
			{
				int fx=find(a[i]);
				int fy=find(a[i]+1);
				if(fx!=fy)
				{
					fa[fx]=fy;
					num[fy]=num[fx]+num[fy]+1;
					if(num[fy]%2==1) ans++;
				}
			}
			else 
			{
				num[a[i]]++;
				if(num[a[i]]%2==1) ans++;
			}
		}
		printf("%d ",ans);
	}
	
}

T2

原

容易发现一个性质：设目前有 \(n\) 个叶子节点，目前节点编号为 \(x\) ，那我们可以写出一个关于 \(x\) 的一次函数: $ f(x)=k_{n}x+b_{n}= (k_{\lceil\frac{n}{2}\rceil}(2x) + b_{\lceil\frac{n}{2}\rceil})+(k_{\lfloor\frac{n}{2}\rfloor}(2x+1)+b_{\lfloor\frac{n}{2}\rfloor})+x$

知道这个性质了，我们就可以递推并记忆化求解 \(n\) 个叶子节点时的 \(k\) 值和 \(b\) 值。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int mod=1e9+7;
int n,x,y;

int read()
{
	int f=1,s=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
	return f*s;
}

map<int,int> k,b;
void dp(int n)
{
	if(k[n]) return ;
	int lc=ceil(1.0*n/2),rc=floor(1.0*n/2);
	dp(lc),dp(rc);
	k[n]=(k[lc]+k[rc])*2%mod+1;
	b[n]=(b[lc]+b[rc]+k[rc])%mod;
}

#define lson (rt<<1)
#define rson (rt<<1|1)
int query(int rt,int l,int r)
{
	if(x<=l&&r<=y)
	{
		dp(r-l+1);
		return (k[r-l+1]*rt%mod+b[r-l+1])%mod;
	}
	int ans=0;
	int mid=(l+r)>>1;
	if(x<=mid) (ans+=query(lson%mod,l,mid))%=mod;
	if(y>mid) (ans+=query(rson%mod,mid+1,r))%=mod;
	return ans;
}

signed main()
{
	k[1]=1;
	int T=read();
	while(T--)
	{
		n=read(),x=read(),y=read();
		printf("%lld\n",query(1,1,n));
	}
}

T3

题

题目大意是要求解 \(min(max(a_{p}+a_{q},b_{p}+b_{q}))\) ,其中 \(p\) 代表法杖，\(q\) 代表咒语，比较套路的一种变换，假设 \(a_{p}+a_{q}> b_{p}+b_{q}\) ,那我们就可以将其变为 \(a_{p}-b_{p}>b_{q}-a_{q}\) ,这样就比较方便我们进行操作，我们令 \(u_{p}=a_{p}-b_{p} , v_{q}=b_{q}-a_{q}\)，我们就以 \(u\) 和 \(v\) 为下标建一颗线段树。

这样我们就有一个比较好的性质，所有左区间的 \(u\) 都小于所有右区间的 \(v\) ,所有左区间的 \(v\) 都小于所有右区间的 \(u\) （这不废话嘛），我们在结合上面的判断可以得到整个区间的最小值可以由左区间的最小的 \(b_{p}\) 加上右区间最小的 \(b_{q}\) 得到，或者由左区间最小的 \(a_{q}\) 加上右区间最小的 \(a_{p}\) 得到，这样我们就可以用线段树来维护所有的信息了，好，这题完了。（记得 \(u\) 和 \(v\) 要加一个很大的正值，可能为负数）

点击查看代码 
#include<bits/stdc++.h>
using namespace std;


const int N=2.5e5+107;
const int inf=1e9; 
int q,t;


int read()
{
	int f=1,s=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
	return f*s;
}

multiset<int> s[N<<1][4];
#define lson (rt<<1)
#define rson (rt<<1|1)
struct lmy
{
	int v[4],sum;
}tr[N<<4],tmp;

void pushup(int rt)
{
	for(int i=0;i<4;i++) tr[rt].v[i]=min(tr[lson].v[i],tr[rson].v[i]);
	tr[rt].sum=min(tr[lson].v[1]+tr[rson].v[0],tr[lson].v[2]+tr[rson].v[3]);
	tr[rt].sum=min(tr[rt].sum,tr[lson].sum);
	tr[rt].sum=min(tr[rt].sum,tr[rson].sum);
}

void update(int rt,int l,int r,int pos)
{
	if(l==r)
	{
		tr[rt]=tmp;
		if(tr[rt].v[0]+tr[rt].v[1]<=inf||tr[rt].v[2]+tr[rt].v[3]<=inf)
		tr[rt].sum=min(tr[rt].v[0]+tr[rt].v[1],tr[rt].v[2]+tr[rt].v[3]);
		return ;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) update(lson,l,mid,pos);
	else update(rson,mid+1,r,pos);
	pushup(rt);
}

int ans=0;
int main()
{
	q=read(),t=read();
	for(int i=1;i<=N*4-1;i++)
	{
		for(int j=0;j<4;j++)
		{
			tr[i].v[j]=tmp.v[j]=inf;
		}
		tr[i].sum=tmp.sum=inf;
		
	}
	while(q--)
	{
		int op=read(),type=read(),a=read(),b=read();
		if(t==1) a=ans^a,b=ans^b;
		if(op==1)
		{
			if(type==0)
			{
				int x=a-b+N;
				s[x][0].insert(a),s[x][2].insert(b);
				for(int i=0;i<4;i++)
				{
					if(!s[x][i].empty()) tmp.v[i]=*(s[x][i].begin());
					else tmp.v[i]=inf;
				}
				update(1,1,N<<1,x);
			}
			else
			{
				int x=b-a+N;
				s[x][1].insert(a),s[x][3].insert(b);
				for(int i=0;i<4;i++)
				{
					if(!s[x][i].empty()) tmp.v[i]=*(s[x][i].begin());
					else tmp.v[i]=inf;
				}
				update(1,1,N<<1,x);
			}
		}
		else
		{
			if(type==0)
			{
				int x=a-b+N;
				if(!s[x][0].empty()&&!s[x][2].empty()&&s[x][0].find(a)!=s[x][0].end()&&s[x][2].find(b)!=s[x][0].end())
				{
					s[x][0].erase(a),s[x][2].erase(b);
					for(int i=0;i<4;i++)
					{
						if(!s[x][i].empty()) tmp.v[i]=*(s[x][i].begin());
						else tmp.v[i]=inf;
					}	
					update(1,1,N<<1,x);
				}
			}
			else
			{
				int x=b-a+N;
				if(!s[x][1].empty()&&!s[x][3].empty()&&s[x][1].find(a)!=s[x][1].end()&&s[x][3].find(b)!=s[x][3].end())
				{
					s[x][1].erase(a),s[x][3].erase(b);
					for(int i=0;i<4;i++)
					{
						if(!s[x][i].empty()) tmp.v[i]=*(s[x][i].begin());
						else tmp.v[i]=inf;
					}	
					update(1,1,N<<1,x);
				}
			}
		}
		ans=tr[1].sum;
		if(ans>=N<<1) ans=0;
		printf("%d\n",ans);
	}
	return 0;
}

标签：ch,int,read,while,区间,csp,模拟,getchar
From： https://www.cnblogs.com/zhengchenxi/p/18403140

相关文章

  • 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】约瑟夫问题 题解（队列+模拟+循环）
    约瑟夫问题题目描述个人围成一圈，从第一个人开始报数,数到的人出列，再由下一个人重新从开始报数，数到的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰名小朋友，而该题是全部出圈。输入......
  • 大连市第二十四中学模拟飞行社团章程（草案）
    亲爱的飞行员：你好！欢迎来到大连市第二十四中学模拟飞行社团！我们致力于为每一位喜爱蓝天的同志提供不一样的模拟飞行体验。同时，为了是您更好的了解本社团并在加入后有更好的体验，我们特在此制作本社团章程，旨在维护社团有序、和谐的运行。一.社团简介本社团全名大连市第二十四中学......
  • CSP2024-16
    A题意：交互题。\(n\)个人，每人有一个颜色。你每次可以询问一个集合中不同颜色数量。最后输出每个人的颜色，只需保证相同的相同，不同的不同。\(n\le150\)，交互次数不超过\(3500\)。考虑在区间\([l,r]\)找到与\(x\)颜色相同的编号最小的元素。怎么判断\(x\)有没有在一个集......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99