信息学奥赛总结01

• • 栈(stack)
  • • 数组模拟栈
  • 队列(queue)
  • • 数组模拟队列
  • vector(变长数组）
  • 链表(list)
  • 结构体(struct)
  • 字符串(string)
  • 质数（只能被1和他本身整除，最小的质数是2)
  • map
  • set
  • stringstream
  • math

先进后出

#include//头文件
stack stk;//定义
stk.push(元素)//放元素
stk.pop()//移除栈顶元素
stk.size()//查看容量
stk.top() //查看栈顶元素
stk.empty()//判断是否为空，是空返回true
不可以用迭代器遍历

表达式括号匹配

#include 
#include 
using namespace std;
int main() {
	stack s ;
	char b = '';
	while (b != '@') {
		cin >> b;
		if (b == '(') {
			s.push(1);
		} else if (b == ')' && s.empty() != 1) {
			s.pop();
		} else if (b == ')' && s.empty() == 1) {
			cout << "NO";
			return 0;
		}
	}
	if (s.empty() == 1) {
		cout << "YES";
	} else {
		cout << "NO";
	}
	return 0;
}

#include
#include
using namespace std;
int a[1000],tt = 0; 
int main()
{
//放元素
tt++;
a[tt] = 元素 

//判空
if(tt = 0)就是空

//删除栈顶元素 
tt--

//查看栈顶元素
a[tt] 

//查看栈的大小 
cout << tt; 
return 0;
}

先进先出

#include//头文件
queue q;//定义
q.push(x)//放入队列
q.pop();//删除队头元素
q.front();查看队头元素
q.back();//查看队尾元素
q.size();//查看容量
q.empty()//判空

#include
#include
using namespace std;
int q[1000],hh = 0, tt = -1;
int main()
{
//放入元素
q[++tt] = x;

//删除队头
hh++;
//查看队头
q[hh];

//查看队尾
q[tt];

//查看容量
size = tt - hh + 1

//判空
hh <= tt ->不是空队列 
hh > tt  -> 空队列

//遍历队列
for(int i = hh ; i <= tt; i++)
cout << q[i]<<" "; 

 return 0;
}

公交换乘

#include
#include
using namespace std;
const int N = 1e5+ 10;

//存优惠券 
struct node
{
	int last_time,val;
}q[N];
int hh = 0, tt = -1;
bool st[N];//false是没有用过 
int res = 0;
int main()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++)
	{
		int x,y,z;
		cin >> x >> y >> z;
		if(x == 0)
		{
			res += y;
			q[++tt].val = y;
			q[tt].last_time = z;
		}
		else
		{
			//清除过期优惠券
			while(hh <= tt && z - q[hh].last_time > 45)hh ++;
			for(int j = hh; j <= tt; j ++)
			{
				if(st[j] == false && q[j].val >= y)
				{
					st[j] = true;//代表过期 
					y = 0;
					break;
				}
			}
			res += y;
		}
	}
	cout << res;
	return 0;
}

#include
vector v;
vector arr[100];
v.push_back();//插入
v.pop_back();//删除尾部
v.clear();
v.size();
v.erase(it);
v[i] //取值，类似数组
for(int i = 0; i < v.size(); i ++
	cout << v[i] <<" ";

#include
list l;
l.push_front();//放到头部
l.push_back()//放到尾部
l.size()//查看大小
l.begin()//返回一个迭代器
list::iterator it;//定义迭代器
l.erase(it)//删除
l.remove(x)//删除所有值为x的数，
l.empty()//判空
l.insert(it,x)//插入
//遍历
for(it = l.begin();it != l.end(); it ++)
	cout << (*it)  << endl;

struct node
{
	int id;
	string name;
};
node k;          //普通结构体
node arr[100];//结构体数组
bool cmp(node x, node y)
{
	if(x.name == y.name)return x.id < y.id;
	else return x.name < y.name
}
sort(arr , arr + n,cmp);

#include
string s;
//读取字符串
cin >> s;
//读取一行
getline(cin,s)
s = "hello_world"
//查看大小
s.size()
//查找
for(int i = 0; i < s.size();i ++)
	cout << s[i] <<" ";
//查找字符串，返回第一次出现的下标
int pos = s.find("hello");	
//翻转
reverse(s.begin(),s.end());
//字符串转数字
string to int  
int k = stoi("123");
//数字转字符串
string str = to_string(123);
//判断回文字符串
string str = "123321"d
string temp  = str;
reverse(temp.begin(),temp.end())
if(temp == str ) cout <<"是回文字符串";
else cout <<"不是回文字符串";

判断质数
bool is_prime(int n)
{
	for(int i = 2; i * i <= n; i ++)
	{
		if(n % i == 0)return false;
	}
	return true;
}
n,m最大公约数
int k = __gcd(10,20);//两个下划线
n,m最小公倍数
n * m == 最大公约数 * 最小公倍数
最小公倍数 = n * m / __gcd(n,m);

#include

去重

#include
set s;
s.insert(x);
s.size();
set::iterator it;
for(it = s.begin(); it != s.end(); it ++)
	cout << (*it) << " " ;

把一串字符串以空格分隔开

#include
stringstream ss;
string s = "to be or not 123";
ss << s;
string temp;
while(ss >> temp)
{
	cout << temp<
stringstream ss;
string s = "123 456 789";
ss << s;
int num
while(ss >> num)
{
	cout << temp< 
math 
#incldue --->#include
//开根号,
int k = sqrt(x);
//返回绝对值
abs(x)
//乘方，x的y次方
pow(x,y)
//两个数的最值
max(x1,x2)
min(x1,x2)
//交换两个数的值
x = 10 , y = 20;
z = x;
x = y;
y = z;
----
swap(x,y);//交换两个数的值

// 判断闰年
if(year % 4 == 0 && year % 100 !=0 || year % 400 == 0)
	cout << "是闰年";
//向上取整
x / y ---> (x + y - 1) / y