首页 > 其他分享 >stack和queue的使用介绍和模拟实现

stack和queue的使用介绍和模拟实现

时间：2024-11-02 17:20:56浏览次数：3  
标签：const queue vector push include stack 模拟

一.适配器的介绍

        1.首先，vector和list在STL组件里面被称作容器，而stack和queue则是被称作适配器。

        2.容器适配器在底层实现时，主要是对特定类进行封装来作为其底层的容器，并在底层实现的时候，添加了多种函数接口来实现其具体的功能。

        3.适配器顾名思义就是“适配”，也就是可以在多种容器的基础上构建出具备特定功能的容器，例如stack栈和queue队列，其在构造使用的时候，底层的容器可以选择vector也可以是list，都适配。

二.stack的介绍

        1.stack(栈)是一种容器适配器，主要用于具备后进先出的情景内，其删除和插入的操作永远只能从一段进行(栈顶的位置)，也就是一段数据的尾部。

        2.在stack的底层实现中，提供了一组特定的函数来访问其内部元素，其底层容器可以是任何形式的容器模板或者是一些特定的容器类。

        3.而这些作为底层实现的容器，必须要具备判空，尾插，尾删，返回尾部元素的功能，才能够作为stack的底层容器，正因为这些功能的统一，stack才能够在底层支持各种容器，成为所谓的适配器。

        4.由于栈具有先进后出的功能，所以并不支持随机插入和随机访问，这样会破坏掉栈的封装性。

        (1).stack一些接口的使用说明

        1.stack的构造->stack()构建出一个空栈

        explicit stack (const container_type& ctnr = container_type());

        在实现的时候可以看到stack的构造函数中，有一个缺省参数是一个默认的容器，在使用stack的构造函数的时候，可以传入一个提前定义好的容器，当然也可以不传，使用底层默认的容器。

#include<iostream>
#include<stack>
#include<vector>
#include<list>
using namespace std;
int main()
{
	stack<int> st1;/*同容器一样，适配器也是使用模板实现的，并且有两个模板参数，
					一个参数表征内部数据的类型，另一个参数表征实现时所使用的容器类型，
					所以在定义的时候需要表明类型*/
				   /*在没有给出第二个模板参数的时候，缺省参数使得适配器的默认实现容器为
					 deque,类似于template<class T,class CONT=vector<T>>*/
	vector<int> v1(5, 20);
	list<int> l1(5, 30);
	stack<int, vector<int>> st2(v1);//容器使用vector构建的stack
	stack<int, list<int>> st3(l1);//容器使用list构建的stack
	return 0;
}

        2.bool empty()const

        判断栈是否为空！

#include<iostream>
#include<stack>
#include<vector>
#include<list>
using namespace std;
int main()
{
	stack<int> st1;
	cout << st1.empty();
	return 0;
}

        3. size_t size()const

        返回栈中数据个数！

#include<iostream>
#include<stack>
#include<vector>
#include<list>
using namespace std;
int main()
{
	stack<int> st1;
	vector<int> v1(5, 20);
	stack<int, vector<int>> st2(v1);
	cout << st1.size() << endl;
	cout << st2.size() << endl;

	return 0;
}

        4. value_type& top()

        返回栈顶元素！(当栈为空的时候，再使用该函数会发生报错)

#include<iostream>
#include<stack>
#include<vector>
#include<list>
using namespace std;
int main()
{
	vector<int> v1(5, 20);
	stack<int, vector<int>> st2(v1);
	cout << st2.top() << endl;

	return 0;
}

        5.void push(const value_type& val) 

         插入一个数据项！

#include<iostream>
#include<stack>
#include<vector>
#include<list>
using namespace std;
int main()
{
	stack<int> st1;
	st1.push(1);
	cout << st1.top() << endl;
	return 0;
}

         6.void pop()

        删除栈顶的元素！        

#include<iostream>
#include<stack>
#include<vector>
#include<list>
using namespace std;
int main()
{
	stack<int> st1;
	st1.push(1);
	st1.push(2);
	cout << st1.top() << endl;
	st1.pop();
	cout << st1.top();
	return 0;
}

        7. void swap(stack& x) 

        交换两个栈！

#include<iostream>
#include<stack>
#include<vector>
#include<list>
using namespace std;
int main()
{
	vector<int> v1(5, 20);
	vector<int> v2(5, 30);
	stack<int, vector<int>> st1(v1);
	stack<int, vector<int>> st2(v2);
	st1.swap(st2);
	cout << st1.top() << endl;
	cout << st2.top();
	return 0;
}

        (2).stack栈的模拟实现

        从栈的功能上来看，先进后出很符合vector的功能，所以在实现stack的时候远比list要好的多，所以在stack的模拟实现中，我们使用vector充当底层容器。

#pragma once
#include<iostream>
#include<deque>
#include<vector>
namespace wang
{
	template<class T>
	class stack
	{
	private:
		std::vector<T> st;
	public:
		stack()
		{}
		void push(const T& data)
		{
			st.push_back(data);
		}
		void pop()
		{
			st.pop_back();
		}
		bool empty()const
		{
			return st.empty();
		}
		size_t size()const
		{
			return st.size();
		}
		T& top()
		{
			return st.back();
		}
		const T& top()const
		{
			return st.back();
		}
	};

}

        这里体现出了stack作为适配器的功能，在其内部所容纳的函数接口中，都是直接调用了相应容器的接口。

三.queue的介绍

        同stack差不多，唯一的区别就是queue是一个先进先出的适配器，这种功能如果用vector来进行实现的话，有一个很明显的错误就是数据挪动的问题，会产生很多时间上的浪费。

        在queue的源码中，容器依旧使用的默认容器deque，但在模拟实现的时候，我们更偏向于使用list来实现queue。

        (1)queue的一些接口的使用说明

        1.queue的构造->构造出一个空队列

        explicit queue (const container_type& ctnr = container_type());

#include<iostream>
#include<queue>
#include<vector>
#include<list>
using namespace std;
int main()
{
	queue<int> q1;//构建出一个空队列
	vector<int> v1(5, 20);
	list<int> l1(5, 30);
	queue<int, vector<int>> q2(v1);//用vector构建出一个队列
	queue<int, list<int>> q3(l1);//用list构建出一个队列
	return 0;
}

        2.bool empty() const

         查看队列是否为空！

#include<iostream>
#include<queue>
#include<vector>
#include<list>
using namespace std;
int main()
{
	queue<int> q1;//构建出一个空队列
	vector<int> v1(5, 20);
	list<int> l1(5, 30);
	queue<int, vector<int>> q2(v1);//用vector构建出一个队列
	queue<int, list<int>> q3(l1);//用list构建出一个队列
	cout << q1.empty() << endl;
	cout << q2.empty() << endl;
	return 0;
}

        3.size_t size()const

        返回队列中数据个数！

#include<iostream>
#include<queue>
#include<vector>
#include<list>
using namespace std;
int main()
{
	queue<int> q1;//构建出一个空队列
	vector<int> v1(5, 20);
	list<int> l1(5, 30);
	queue<int, vector<int>> q2(v1);//用vector构建出一个队列
	queue<int, list<int>> q3(l1);//用list构建出一个队列
	cout << q1.size() << endl;
	cout << q2.size() << endl;
	return 0;
}

        4. value_type& front();const value_type& front() const

         返回队首节点的数据！

#include<iostream>
#include<queue>
#include<vector>
#include<list>
using namespace std;
int main()
{
	list<int> ls;
	ls.push_back(1);
	ls.push_back(2);
	ls.push_back(3);
	ls.push_back(4);
	queue<int, list<int>> q1(ls);
	cout << q1.front();
	return 0;
}

        5.value_type& back();const value_type& back() const 

        返回队尾的数据项！

#include<iostream>
#include<queue>
#include<vector>
#include<list>
using namespace std;
int main()
{
	list<int> ls;
	ls.push_back(1);
	ls.push_back(2);
	ls.push_back(3);
	ls.push_back(4);
	queue<int, list<int>> q1(ls);
	cout << q1.back();
	return 0;
}

        6.void push (const value_type& val)

        在队尾插入一个数据项！

#include<iostream>
#include<queue>
#include<vector>
#include<list>
using namespace std;
int main()
{
	list<int> ls;
	ls.push_back(1);
	ls.push_back(2);
	ls.push_back(3);
	ls.push_back(4);
	queue<int, list<int>> q1(ls);
	q1.push(5);
	cout << q1.back();
	return 0;
}

        7.void pop()

        删除队头的数据(节点)！ 

#include<iostream>
#include<queue>
#include<vector>
#include<list>
using namespace std;
int main()
{
	list<int> ls;
	ls.push_back(1);
	ls.push_back(2);
	ls.push_back(3);
	ls.push_back(4);
	queue<int, list<int>> q1(ls);
	q1.pop();
	cout << q1.front();
	return 0;
}

        8.void swap(queue& x) 

        交换两个队列！

#include<iostream>
#include<queue>
#include<vector>
#include<list>
using namespace std;
int main()
{
	queue<int> q1, q2;
	q1.push(1);
	q1.push(1);
	q1.push(1);
	q2.push(2);
	q2.push(2);
	q2.push(2);
	q1.swap(q2);
	cout << q1.front() << endl;
	cout << q2.front() << endl;

	return 0;
}

        (2)queue队列的模拟实现

#pragma once
#include<list>
namespace wang
{
	template<class T>
	class queue
	{
	private:
		std::list<T> ls;
	public:
		queue()
		{}
		void push(const T& data)
		{
			ls.push_back(data);
		}
		void pop()
		{
			ls.pop_back();
		}
		bool empty()const
		{
			return ls.empty();
		}
		size_t size()const
		{
			return ls.size();
		}
		T& back()
		{
			return ls.back();
		}
		const T& back()const
		{
			return ls.back();
		}
		T& front()
		{
			return ls.front();
		}
		const T& front()const
		{
			return ls.front();
		}
	};

}

 队列如果使用vector就会设计到数据挪动的问题，所以用list最为合适。

四.priority_queue的介绍

        priority_queue相较于queue来说，priority_queue叫做优先队列，同样也是一种容器适配器，它可以保证第一个元素总是它所包含的元素中的最大值，也就是说每次弹出队列的元素永远是最大的那一个，默认状态下大的优先级最高。

        (1)priority_queue一些接口的使用和说明

        1.priority_queue的构造

        priority_queue() / priority_queue(InputIterator first,InputIterator last)

        第一个构造函数的作用为构造一个空的优先队列，第二个构造函数的作用为选取一段由两个迭代器指向的空间来构造一个优先队列。

#include<iostream>
#include<queue>
#include<vector>
#include<list>
using namespace std;
int main()
{
	vector<int> v1(5, 20);
	vector<int>::iterator it1 = v1.begin();
	vector<int>::iterator it2 = v1.end();
	priority_queue<int> pq1;//一个空优先队列
	priority_queue<int> pq2(it1, it2);//一个由vector的迭代器构建的优先队列
	return 0;
}

        2.bool empty()const

        判断队列是否为空！

#include<iostream>
#include<queue>
#include<vector>
#include<list>
using namespace std;
int main()
{
	vector<int> v1(5, 20);
	vector<int>::iterator it1 = v1.begin();
	vector<int>::iterator it2 = v1.end();
	priority_queue<int> pq1;//一个空优先队列
	priority_queue<int> pq2(it1, it2);//一个由vector的迭代器构建的优先队列
	cout << pq1.empty() << endl;
	cout << pq2.empty() << endl;

	return 0;
}

        3.size_t size()const

        返回优先队列中数据的个数!

#include<iostream>
#include<queue>
#include<vector>
#include<list>
using namespace std;
int main()
{
	vector<int> v1(5, 20);
	vector<int>::iterator it1 = v1.begin();
	vector<int>::iterator it2 = v1.end();
	priority_queue<int> pq1;//一个空优先队列
	priority_queue<int> pq2(it1, it2);//一个由vector的迭代器构建的优先队列
	cout << pq1.size() << endl;
	cout << pq2.size() << endl;
	return 0;
}

        4.const value_type& top() const

        返回优先队列头部的数据元素，也就是优先级最高的元素！ 

#include<iostream>
#include<queue>
#include<vector>
#include<list>
using namespace std;
int main()
{
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	vector<int>::iterator it1 = v1.begin();
	vector<int>::iterator it2 = v1.end();
	priority_queue<int> pq1;//一个空优先队列
	priority_queue<int> pq2(it1, it2);//一个由vector的迭代器构建的优先队列
	cout << pq2.top() << endl;
	return 0;
}

        5.void push (const value_type& val)

        插入一个数据元素！

#include<iostream>
#include<queue>
#include<vector>
#include<list>
using namespace std;
int main()
{
	priority_queue<int> pq1;//一个空优先队列
	pq1.push(1);
	pq1.push(2);
	pq1.push(3);
	cout << pq1.top() << endl;
	return 0;
}

        6.void pop()

        删除优先级最高的元素！

#include<iostream>
#include<queue>
#include<vector>
#include<list>
using namespace std;
int main()
{
	priority_queue<int> pq1;//一个空优先队列
	pq1.push(1);
	pq1.push(2);
	pq1.push(3);
	pq1.pop();
	cout << pq1.top() << endl;
	return 0;
}

        7.void swap(priority_queue& x)

        交换两个优先级队列！

#include<iostream>
#include<queue>
#include<vector>
#include<list>
using namespace std;
int main()
{
	priority_queue<int> pq1;//一个空优先队列
	pq1.push(1);
	pq1.push(2);
	pq1.push(3);
	priority_queue<int> pq2;
	pq2.push(4);
	pq2.push(5);
	pq2.push(6);
	pq1.swap(pq2);
	cout << pq1.top() << endl;
	cout << pq2.top() << endl;

	return 0;
}

        (2)priority_queue的模拟实现

        优先队列是如何做到优先的？它的底层实现中，采用的是堆的数据结构，使用大堆的数据结构可以保证顶部元素永远是最大的，经历元素弹出后由底层的算法调整，可以让余下的元素中的最大元素到达堆顶，小堆也是如此。

        在构建优先队列的时候，究竟是数值大的元素优先级高还是数值小的元素优先级高，主要通过仿函数来进行的识别和判断。

        仿函数：仿函数是一种类似函数的对象，它可以被用作函数并接受参数，在c++中，通常是重载了函数调用的运算符operator()，通过重载这一符号，仿函数可以像函数一样被调用。 

         1.仿函数的使用

         对于仿函数的调用，主要是两个:greater<T>,less<T>，因为仿函数是模板实现的，所以需要传输优先队列的数据元素类型。

        greater<T>：数据小的优先级高

        less<T>：数据大的优先级高（默认为此）

        在使用仿函数的时候，必须要传入实现优先队列所使用的容器类型。

#include<iostream>
#include<queue>
#include<functional>
using namespace std;
int main()
{
	priority_queue<int> pq1;
	pq1.push(1);
	pq1.push(2);
	pq1.push(3);
	cout << pq1.top() << endl;
	priority_queue<int, vector<int>, greater<int>> pq2;
	pq2.push(1);
	pq2.push(2);
	pq2.push(3);
	cout << pq2.top() << endl;
	return 0;
}

        2.仿函数的模拟实现 

template<class T>
struct less
{
	bool operator()(const T& left, const T& right)
	{
		return left < right;
	}
};
template<class T>
struct greater
{
	bool operator()(const T& left, const T& right)
	{
		return left > right;
	}
};

        3.向下调整算法构建堆

         大堆：父节点的数据大小大于每一个子节点的数据

         小堆：父节点的数据大小小于每一个子节点的数据

        那么该如何调整这些数据来构造出一个堆呢，答案是使用向下调整算法。

        （1）从存在最后一个存在子节点的父节点开始，对这棵小树运用向下调整算法，如果存在父节点和两个子节点，那么把三个节点中最大(最小)的数据项放到父节点的位置，这样就保证了父节点是最大(最小)的数据项。

        （2）通过循环，将这一层的小树全部调整为大堆或者小堆的格式，然后再对父节点的上面一层进行调整，此时父节点上一层父父节点的子节点全部都是大堆或者小堆的格式，这时候再次使用向下调整算法，将父父节点调整为最大的或者最小的，此时父节点拿到了调整下来的节点数据，再对父节点和子节点那一棵树进行调整，调整为大堆或者小堆的格式。

        （3）由此可见，在使用向下调整算法的时候，必须要求父节点的左右子树全部是大堆(小堆)的格式，这样就不用担心在调堆的过程中将堆调乱，所以需要从最底部的一层父节点开始调。

          

                所以向下调整算法，传入一个节点，就需要一直调到这棵树的最后，而且调的时候需要满足从这个节点开始往下的小树全部是大堆(小堆)的格式，所以我们需要从末尾一层父节点开始往上走，这样就可以保证调到上面的时候，下面的小树全部是大堆(小堆)的格式。

void AdjustDown(int parent)
{
    int child=parent*2+1;//先拿到左孩子
    while(child<c.size())//开始循环，从头调到尾，结束条件就是子节点到了数据末尾
    {
        if(child+1<c.size()&&Com()(c[child],c[child+1]))
        /*比较左孩子大还是右孩子大，首先需要保证右孩子得存在，然后直接创造一个对象Com(),让这个对象直接调用重载的()符号，默认状态下是less也就是调大堆,所以如果c[child]比c[child+1]要小，那么准备将右孩子和父节点交换*/
        {
            child+=1;//指向右孩子
        }
        if(Com()(c[parent],c[child]))
        {
            //如果父节点比子节点要小，那么交换，最大的去到父节点的位置
            std::swap(c[parent],c[child]);
            parent=child;//parent迭代到调下来的位置，准备接下来的调堆
            child=parent*2+1;//child再次迭代到parent的左孩子的位置，准备接下来的循环
        }
        else
        {
            //进入else里面说明父节点的数值要大于子节点的数值，那么就不需要进行交换，调堆完毕
            return;
        }
    }
}

        4.向上调整算法

        向上调整主要适用于插入数据后，将堆进行调整，恢复大堆(小堆)的格式。

        调堆的条件为，目标堆在插入数据前是大堆(小堆)的格式。

void AdjustUp(int child)
{
    int parent=(child-1)/2;
    while(child)//将child作为循环结束条件，可以保证完成当parent为0时的最后一次调堆
    {
        if(Com()(c[parent],c[child]))
        {
            //此时说明c[child]比c[parent]要大，那么就需要交换节点
            std::swap(c[parent],c[child]);
            child=parent;
            parent=(child-/1)/2;
        }
        else
            return;
    }
}

        5. priority_queue类及构造函数的模拟实现

template<class T,class Container=std::vector<T>,class Com=less<int>>
class priority_queue
{
private:
    Container c;
public:
    priority_queue(){}
    template<class InputIterator>
    priority_queue(InputIterator first,InputIterator last)
        :c(first,last)
    {
        int count=c.size()-1;
        int root=(count-1)/2;
        for(;root>=0;root--)
        {
            AdjustDown(root);
        }
    }
}

        6. void push(const T& x)的模拟实现

void push(const T& x)
{
	c.push_back(x);
	AdjustUp(c.size()-1);
}

        7. void pop()的模拟实现

void pop()
{
	if (!c.empty())
	{
		std::swap(c.front(), c.back());
		c.pop_back();
		AdjustDown(0);
	}
}

        8.size_t size()的模拟实现

size_t size()
{
	return c.size();
}

        9.bool empty()的模拟实现

bool empty()
{
	return c.empty();
}

        10.const T&top()const的模拟实现 

const T& top()const
{
	return c.front();
}

        模拟实现总代码：

namespace wang
{
	//仿函数的模拟实现
	template<class T>
	struct less
	{
		bool operator()(const T& left, const T& right)
		{
			return left < right;
		}
	};
	template<class T>
	struct greater
	{
		bool operator()(const T& left, const T& right)
		{
			return left > right;
		}
	};
	template<class T, class Container = std::vector<int>, class Com = less<int>>
	class priority_queue
	{
	private:
		Container c;
	public:
		priority_queue()  {}
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			: c(first, last)
		{
			int count = c.size()-1;
			int root = (count - 1) / 2;
			for (; root >= 0; root--)
			{
				AdjustDown(root);
			}
		}
		void push(const T& x)
		{
			c.push_back(x);
			AdjustUp(c.size()-1);
		}
		void pop()
		{
			if (!c.empty())
			{
				std::swap(c.front(), c.back());
				c.pop_back();
				AdjustDown(0);
			}
		}
		size_t size()
		{
			return c.size();
		}
		bool empty()
		{
			return c.empty();
		}
		const T& top()const
		{
			return c.front();
		}
		void AdjustDown(int parent)
		{
			int child = parent * 2 + 1;
			while (child < c.size())
			{
				if (child + 1 < c.size() && Com()(c[child], c[child+1]))
				{
					child += 1;
				}
				if (Com()(c[parent], c[child]))
				{
					std::swap(c[child], c[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					return;
			}
		}
		void AdjustUp(int child)
		{
			int parent = (child - 1) / 2;
			while (child)
			{
				if (Com()(c[parent], c[child]))
				{
					std::swap(c[child], c[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
					return;
			}
		}
	};
}

 五.简单介绍一下deque

        deque时一种双端开口的“连续”空间的数据结构，双端开口的含义就是，可以在两端进行插入和删除的操作，而且时间复杂度都是O(1)，与vector相比较，头插效率比较高，不需要大量挪动数据，与list相比，空间利用率比较高。

        但是deque并不是真正意义上的连续的空间，而是由一段连续的小空间拼接而成的，类似于一个动态的二维数组。

 类似于这种结构，下方数组中每个节点存储了一个指针，每个指针指向一段小空间，一段空间满了接着开辟下一段空间，在头插尾插的时候皆是如此。

        所以与vector相比较，头插效率高，不需要挪动数据，另外增容的时候也不需要去拷贝数据。

        与list相比较的话，就是空间利用率比较高，不需要去大量存储next指针等，节省了空间。

        但是它有一个致命的缺陷，就是不适合遍历，因为在遍历的时候，需要不断控制指针是否到达了一段小空间的结束而进入下一段小空间，这样一来效率就会极其低下。

在构建stack选择容器的时候，容器只需要支持尾插尾删操作就可以，在list的时候容器只需要支持尾插头删操作就可以，显然deque完美符合二者的要求，所以会选择deque作为stack和list的默认容器。

        在使用deque作为stack和list的容器的时候，扬长避短，完美避开了容器遍历的问题，同时解决了vector和list的缺陷。

标签：const,queue,vector,push,include,stack,模拟
From： https://blog.csdn.net/2301_81245562/article/details/143404202

相关文章

  • List类函数使用讲解及模拟实现
    一.List介绍    1.List是一个支持在任意位置进行插入和删除的序列式容器。    2.List底层实现时使用的是双向链表结构，每个节点之间都互不相干，通过指针进行前后结点的指向。    3.List的优点在于进行数据的插入和删除的时候，不需要去大量的挪动数据，效......
  • 多校A层冲刺NOIP2024模拟赛17
    多校A层冲刺NOIP2024模拟赛17T1、网格首先看上去很麻烦，但是最终所有的式子都可以写成几个数的积相加的形式，那么我们只要处理数（拼接起来）、数的积以及积的和。那么我们维护三个变量，第一个是$x$，表示最后一个积前面所有的数和，第二个是$y$，表示目前的积，第三个是z，表......
  • CW 11.02 模拟赛 FSYo T2
    算法看到交换,这里有一个套路:确定最终的形态后,交换次数即为逆序对个数我们直接设\(f_{i,j,k,0/1/2}\)表示\(3\)种颜色填到哪里了，最后一个是什么颜色，逆序对数最少是多少转移分最后一个是什么颜色讨论关于\(O(1)\)求逆序对的方法:if(i==0&&a)f[a][b][......
  • CW 11.02 模拟赛 FSYo T1
    题面自出题挂个pdf题面下载算法暴力可能的答案只有\(O(n^2)\)个,考虑每个答案\(\rm{check}\)是\(O(n\logn)\)的总时间复杂度\(O(n^3\logn)\)/*O(answer*n*logn),即O(n^3logn)的算法,预期60pts*//*对于每一种可能的答案,首先对于每一个点,计算......
  • 2024.11.02模拟赛
    挂了至少30分！！不——开——心——钢哥说，大家要休息好，于是模拟赛晚点，变成了3小时3道题。T1打的正解(但没调出来版)，T2T3打的暴力(但全挂了版)，预计总分120+，但实际总分80。小小总结一下：昨晚多睡了一小时，今天思路确实感觉更清晰了(但也有可能是因为题目不难……)。但今天时间没分配......
  • openstack云平台部署（详细+图文）
    一.准备工作云平台需要两个节点，一个controller（控制节点），一个compute（计算节点）环境要求：VM虚拟机2台，镜像为centos7或7.5。本指南使用的ip控制节点(controller)：一块100G的硬盘。两块网卡，两块网卡第一块网卡IP地址为192.168.100.10，第二块网卡IP地址为192.168.200.10。（编辑时用......
  • 11.2 炼石模拟赛
    T1贪心即可。T2考虑贪心。观察1不能出玩偶的机子应该最后修。所有钦定不出玩偶的机子都是平凡的，就是假在这里了！观察2所有人一起修机是最优的。观察3对于所有钦定出玩偶的机子，应该按照\(b\)数组从小到大排序后修理。有以上的观察，不难发现应该按照\(b\)数组排序。......
  • 多校 A 层冲刺 NOIP2024 模拟赛 17
    多校A层冲刺NOIP2024模拟赛17T1网格签到题注意到\(+\)与\(\times\)由于优先级其实是分开的，所以可以考虑每到达一个\(+\)计算一次贡献（乘上一个组合数），然后将前置贡献重新赋值为方案数，DP只需考虑连续\(\times\)段即可。时间复杂度\(O(nm)\)。T2矩形根号分治发现不......
  • 模拟实现字符串函数
    今天给大家分享几个字符串函数的模拟实现，它们分别是strlen，strcpy，strcat函数。这几个函数我上一期已经介绍过了，那么今天我就不过多介绍它们了，今天着重来看它们是如何实现的1.strlen函数我们先看代码这个函数的逻辑便是记录＼0之前的字符，那么我们便可以通过计数器来实现，用一......
  • 20241101 模拟赛总结
    期望得分：100+47+35+22=204实际得分：100+47+3+22=172订正记录T1订正了之前T3，晚了半个多小时才开T1……开始大胆猜想是从小到大排序计算，后面发现不对？又想了一个邻项交换的点子，发现没什么区别，后面又猜是不是一段后缀，发现几个样例还真是！进一步思考后发现，是一段递增的子序列，并且起......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99