首页 > 其他分享 >数据结构

数据结构

时间：2024-09-14 16:25:03浏览次数：16  
标签：return int lowbit sum long 200010 数据结构

数据结构

栈

  • 栈，一种基本的先进后出的线性数据结构，手写栈一般有一个指针指向栈顶元素。
STL中有个容器叫stack,支持一些功能
  • push,将元素放置在栈顶；
  • top(),输出栈顶元素
  • pop()，弹出栈顶元素
  • size(),访问栈中元素
  • clear，清空

详细操作可以见栈

手写栈
  • 可以用数组模拟栈，代码如下。
int t=0;
struct sta{
	int a[20100];
	void push(int x){	a[++t]=x; }
	void pop(){	--t; }
	int top()	{ return a[t];}
	int empty(int x){	return t==0?1:0;}
	int size(){ return t;}
}st;
单调栈
  • 单调栈即满足单调性的栈结构
  • 可以用来维护左边或右边第一个比自己小或者大的
  • 通过维护一个栈，如果比当前值小就弹出。
for(int i=n;i>=1;i--){
	while(st.size()&&(a[st.top()]<=a[i])){
		st.pop();
	}
	if(st.size()){
		ans[i]=st.top();
	}
	st.push(i);
}

例题：

括号序列

  • 读题得到能匹配的就输出
  • 不能匹配就填上
#include<bits/stdc++.h>
#include<stack>
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')	f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48),ch=getchar();}
	return x*f; 
} 
inline void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
string s;
stack<pair<int,int> >st;
int vis[210];
signed main(){
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]=='('){
			st.push(make_pair(i,0));
		}
		else if(s[i]=='['){
			st.push(make_pair(i,1));
		}
		if(s[i]==')'&&st.size()){
			 if(st.top().second==0){
				vis[st.top().first]=1;
				vis[i]=1;
					st.pop();
			}
		
		}
		else if(s[i]==']'&&st.size()){
			if(st.top().second==1){
				vis[st.top().first]=1;
				vis[i]=1;	st.pop();
			}
		}
	} 
	for(int i=0;i<s.size();i++){
		if(vis[i]){
			cout<<s[i];
		}
		else{
			if((s[i]=='(')||(s[i]==')')){
				cout<<"()";
			}
			else if((s[i]=='[')||(s[i]==']')){
				cout<<"[]";
			}
		}
	}
	return 0;	
}

队列

  • 队列，是一种先进先出的线性数据结构，手写队列一般有两个指针指向队头和队尾元素
  • 其对应 STL: queue
  • 先进先出。
普通队列
  • STL 即可

优先队列

  • 也是二叉堆，可以维护最小/最大值。
  • priority_queue

例题：

舞蹈课

  • 首先将相邻的放入优先队列，然后再从绝对值最小的开始出队，然后再将他们的位置用链表更新
#include<bits/stdc++.h>
#define mp make_pair
#define int long long
using namespace std;
int n;
string s;
int a[200010];
int nxt[200010],pre[200010];
int b[2000010];
struct node{
	int sum,l,r;
};
bool operator<(node a,node b){
	if(a.sum==b.sum)return a.l>b.l;
	return a.sum>b.sum;
}
bool flag[200010];
priority_queue<node>q;
vector<pair<int,int> >st;
signed main(){
	cin>>n;
	cin>>s;s=" "+s;
	for(int i=1;i<=n;i++){
		cin>>a[i];
        pre[i]=i-1;nxt[i]=i+1;
	}
	for(int i=1;i<=n;i++){
		b[i]=(s[i]=='B');
	}
	for(int i=1;i<n;i++){	
		if(b[i]^b[i+1])	q.push((node){abs(a[i+1]-a[i]),i,i+1});
	}
	while(q.size()){
		node t=q.top();
		q.pop();
		if((!flag[t.l])&&(!flag[t.r])){
			flag[t.l]=1,flag[t.r]=1;
			pre[nxt[t.r]]=pre[t.l];
			nxt[pre[t.l]]=nxt[t.r];	
            st.push_back(mp(t.l,t.r));
            if(pre[t.l]<1||nxt[t.r]>n)  continue;
			if(b[pre[t.l]]^b[nxt[t.r]])	q.push((node){abs(a[pre[t.l]]-a[nxt[t.r]]),pre[t.l],nxt[t.r]});

		}
	}
	cout<<st.size()<<'\n';
	for(int i=0;i<st.size();i++){
		cout<<st[i].first<<" "<<st[i].second<<'\n';
	}
	return 0;
}

建筑抢修

  • 读题得到意思是要我们尽量修最多的，而不修的一定是耗时最多的，这样会影响后面所有的
  • 所以考虑先将截止时间排序，然后尝试放，如果放不了，那么就把耗时最大的弹出
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
struct node{
	int t1,t2;
}a[150010];
priority_queue<int>q; 
bool cmp(node x,node y){
	if(x.t2!=y.t2)	return x.t2<y.t2;
	return x.t1<y.t1;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].t1>>a[i].t2;
	}
	sort(a+1,a+1+n,cmp);
	int ans=0,sum=0;
	for(int i=1;i<=n;i++){
		ans+=a[i].t1;
		q.push(a[i].t1);
		if(ans<=a[i].t2){
			sum++;
		}
		else{
			ans-=q.top();
			q.pop();
		}
	}
	cout<<sum;
	return 0;
}

ST表

  • 可以静态维护区间问题，区间RMQ，区间GCD
  • 通过倍增的方法维护。

具体实现如下

  • 首先ST表维护一个数组st[i][j]表示从 \(i\) 的位置到 \(i+2^j\) 的区间问题
  • 当前位置跳 \(2^j\) 等价于 先跳 \(2^{j-1}\) ,再跳 \(2^{j-1}\)
for(int j=1;j<=lg[n];j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
		}
}

查询

当前长度最大从l跳 \(2^j\) 不跳出去有多长，j是lg[len]。

  cout<<max(dp[l][lg[len]],dp[r-(1<<lg[len])+1][lg[len]])<<'\n';

例题：

Max GEQ Sum

  • 读题得到最大值得取值只有n种，考虑枚举最大值，然后用单调栈得到最左端和最右端得端点
  • 因为我们想要区间和最大，即 \(pre[r]-pre[l-1]\) 最大，所以用ST表维护这个区间最大前缀和再处理即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
long long T,n,a[200010],ans[200010],num[200100];
long long sum[200010];
long long dp[200010][30],dp1[200010][30],lg[200010];
stack<long long>q;
int qd(int l,int r){
	int len=lg[r-l+1];
	return max(dp[l][len],dp[r-(1<<len)+1][len]);
}
int qx(int l,int r){
	int len=lg[r-l+1];
	return min(dp1[l][len],dp1[r-(1<<len)+1][len]);
}
void init(){
	for(int i=n;i>=1;i--){
		while(!q.empty()&&a[i]>=a[q.top()]){
			q.pop();
		}
		if(!q.empty()){
			ans[i]=q.top()-1;
		}
		else{
			ans[i]=n;	
		}	
		q.push(i);
	}
	while(q.size()) 
		q.pop();
	for(int i=1;i<=n;i++){
		while(!q.empty()&&a[i]>=a[q.top()]){
			q.pop();
		}
		if(!q.empty()){
			num[i]=q.top()+1;
		}
		else{
			num[i]=1;	
		}	
		q.push(i);
	}
		while(q.size()) 	
			q.pop();
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>T;
	while(T--){
		cin>>n;
		lg[0]=-1;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			sum[i]=sum[i-1]+a[i];		
			lg[i]=lg[i/2]+1;
		}
		for(int j=1;j<=lg[n];j++){
			for(int i=0;i+(1<<(j-1))<=n;i++){
				dp1[i][j]=1e9;
			}
		}
		init();	
		for(int i=1;i<=n;i++){
			dp[i][0]=sum[i];
			dp1[i][0]=sum[i];	
		}
		for(int j=1;j<=lg[n];j++){
			for(int i=0;i+(1<<(j-1))<=n;i++){
				dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
				dp1[i][j]=min(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);
			}
		}
		bool flag=0;
		for(int i=1;i<=n;i++){
			int maxn=qd(i,ans[i]);
			int minn=qx(num[i]-1,i-1);
		//	cout<<maxn<<" "<<minn<<"\n";
			if(maxn-minn>a[i]){
				flag=1;
				cout<<"NO"<<"\n";
				break;
			}
		}
	//	cout<<"\n";
		if(!flag)
			cout<<"YES"<<"\n";
	}
	return 0;
}

Array Stabilization (GCD version)

  • 读题可以得到当前这个位置被修改k次后的值是 \(gcd(a_i,....,a_{k+i})\)
  • 所以可以用ST表维护区间 \(GCD\) ，发现 \(k\) 可以枚举，而且有单调性，考虑二分
#include<bits/stdc++.h>
using namespace std;
int t,n;
int lg[400010];
int st[400010][30];
int a[400010];
int gcd(int x,int y){
	if(y==0)	return x;
	return gcd(y,x%y);
}
int m;
bool check(int x){
	int ans=0;
	for(int i=1;i<=m-x;i++){
		if(!ans)	ans=gcd(st[i][lg[x+1]],st[i+x-(1<<lg[x+1])+1][lg[x+1]]);
		else if(ans!=gcd(st[i][lg[x+1]],st[i+x-(1<<lg[x+1])+1][lg[x+1]]))	return 0;
	}
	return 1;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	lg[0]=-1;
	for(int i=1;i<=400000;i++){
		lg[i]=lg[i>>1]+1;
	}
	cin>>t;
	while(t--){
		cin>>n;
		lg[0]=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];	a[i+n]=a[i];
			st[i][0]=a[i];
		 	st[i+n][0]=a[i];	
		}
		 m=n*2;
		for(int j=1;j<=lg[m];j++){
			for(int i=1;i<=m-(1<<j)+1;i++){
				st[i][j]=gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
			}
		} 
		int l=0,r=n-1;
		int ans=n-1;
		while(l<=r){
			int mid=l+r>>1;
			
			if(check(mid))	r=mid-1,ans=mid;
			else	l=mid+1;
		}
		cout<<ans<<'\n';
	}
	return 0;
}

树状数组

  • 支持区间修改，单点查询。单点修改，区间查询的数据结构
  • 修改与查询都是 \(\operatorname{O(\log n)}\)

这是一棵基本的树状数组；

在学习前先介绍一个 $lowbit(x) $ 这个函数可以求出某个数二进制数的最后一个1所带的0的十进制大小
int lowbit(int x){
	return x&-x;
}
  • 接下来开始正题
  • 接下来第一个单点修改，区间查询。
\(a_k\) 的意义是什么？
即是 \({k-lowbit(k)+1} {\ — \ } {\ }k\) 的这个区间的值
看上图得知当我们修改了 \(a_1\) 的值时，\(t_1,t_2,t_4,t_8\) 的权值都需要修改
在修改了 \(a_3\) 的值时，\(t_3,t_4,t_8\) 的权值修改。
综上，我们发现了 当修改了 \(a_k\) 的值时， \(a_{k+lowbit(k)}\),\({k+lowbit(k)+lowbit(k+lowbit(k)))}...\) 的值都会修改,复杂度为 \(\operatorname{O(\log n)}\)
void merge(int x,int k){
	for(int i=x;i<=n;i+=lowbit(x)){
		tree[x]+=k;
	}
}
修改写完了，接下来改写查询了。
举个例子，假如我们要求前7个的和，那查询的数组应该是 \(tree[7],tree[6],tree[4]\) 的总和
假如要求前4个的和，那查询的数组应该是 \(tree[4]\)
综上，我们发现了 查询前 \(k\) 个值时，应该要查询 \(tree_{k},tree_{k-lowbit(k)},tree_{k-lowbit(k)-lowbit(k-lowbit(k))}\) 的权值
int query(int x){
	int sum=0;
	while(x){
		sum+=tree[x];
		x-=lowbit(x);
	}
	return sum;
}
要求区间和的话，用类似前缀和的方法即可
  • 区间修改，单点查询
接下来开始修改操作
维护一个差分数组，因为差分数组的特性，所以只要将 \(1\) ~ \(r\) 的

标签：return,int,lowbit,sum,long,200010,数据结构
From： https://www.cnblogs.com/lmy333/p/18414261

相关文章

  • 【数据结构】队列
    队列的概念及结构队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstInFirstOut)入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头队列的模拟实现队列也可以数组和链表的结构实现，使用链表的结构......
  • 数据结构与算法-求数的最小深度是多少?
    给定一颗二叉树的头节点head求以head为头的树中,最小深度是多少？publicclassMinHeight{publicstaticclassTreeNode{publicintval;publicTreeNodeleft;publicTreeNoderight;publicTreeNode(intx){val=x;......
  • C++一元多项式解析、计算、输出(数据结构作业)，可直接运行
    //Copyright(c)wyy-personal@outlook.com#include<bits/stdc++.h>classPolynomial{private:std::unordered_map<int,int>data_;voidzero_value_optimization(){for(autoiter=data_.begin();iter!=data_.end();){......
  • 数据结构基础讲解（六）——串的专项练习
    本文数据结构讲解参考书目：通过网盘分享的文件：数据结构 C语言版.pdf链接: https://pan.baidu.com/s/159y_QTbXqpMhNCNP_Fls9g?pwd=ze8e 提取码:ze8e数据结构基础讲解（五）——队列专项练习-CSDN博客个人主页：樱娆π-CSDN博客目录串的定义串的类型定义、存储结......
  • 基础数据结构-二分变形C语言实现
    基础二分下面是一个最基础的二分搜索代码，从一个数组（数据从小到大排）中找出某元素。#include<stdio.h>//函数声明intbinarySearch(intarr[],intleft,intright,intx);intmain(){//测试数据intarr[]={2,3,4,10,40};intn=sizeof(arr)......
  • 【数据结构】字符串与JSON字符串、JSON字符串及相应数据结构（如对象与数组）之间的相互转
    前言：下面打印日志用的是FastJSON依赖库中的 @Log4j2。依赖：<!--AlibabaFastjson--><dependency><groupId>com.alibaba</groupId><artifactId>fastjson</artifactId><version>1.2.80</version></dependency>目录普通字......
  • 数据结构之美-深入理解树形结构
    一认识树形结构树形结构是一种广泛应用的非线性数据结构，它在计算机科学和日常生活中都有广泛的应用。比如文件系统，邮件系统，编译器语法树，决策树，网络通信，甚至机器学习当中，都有树形数据结构的影子。本文旨在梳理日常用到的各类树形结构以及其优点和劣势，让渎者对树形结构有一个深入......
  • 【数据结构】第八节：链式二叉树
    个人主页： NiKo数据结构专栏： 数据结构与算法 源码获取：Gitee——数据结构一、二叉树的链式结构typedefintBTDataType;typedefstructBinaryTreeNode{ BTDataTypedata; structBinaryTreeNode*left;//左子树根节点 structBinaryTreeNode*right;//右子......
  • C# 开源教程带你轻松掌握数据结构与算法
    前言在项目开发过程中，理解数据结构和算法如同掌握盖房子的秘诀。算法不仅能帮助我们编写高效、优质的代码，还能解决项目中遇到的各种难题。给大家推荐一个支持C#的开源免费、新手友好的数据结构与算法入门教程：Hello算法。项目介绍《HelloAlgo》是一本开源免费、新手友好的数......
  • 数据结构和算法之基本概念
    原文出处：数据结构和算法之基本概念  关注码农爱刷题，看更多技术文章！！其他文章：Java基础之数组    在计算机领域中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构（Structure）。数据结构是相互之间存在一种或多种特定关系的数......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99