信息学奥赛总结01

栈(stack)

先进后出

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

表达式括号匹配

#include <iostream>
#include <stack>
using namespace std;
int main() {
	stack<int> s ;
	char b = '\0';
	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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

数组模拟栈

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

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

//删除栈顶元素 
tt--

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

//查看栈的大小 
cout << tt; 
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

队列(queue)

先进先出

#include<queue>//头文件
queue<int> q;//定义
q.push(x)//放入队列
q.pop();//删除队头元素
q.front();查看队头元素
q.back();//查看队尾元素
q.size();//查看容量
q.empty()//判空
1
2
3
4
5
6
7
8

数组模拟队列

#include<iostream>
#include<algorithm>
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

公交换乘

#include<iostream>
#include<algorithm>
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

vector(变长数组）

#include<vector>
vector<int> v;
vector<int> 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] <<" ";
1
2
3
4
5
6
7
8
9
10
11

链表(list)

#include<list>
list<int> l;
l.push_front();//放到头部
l.push_back()//放到尾部
l.size()//查看大小
l.begin()//返回一个迭代器
list<int>::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;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

结构体(struct)

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);
1
2
3
4
5
6
7
8
9
10
11
12
13

字符串(string)

#include<string>
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 <<"不是回文字符串";
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

质数（只能被1和他本身整除，最小的质数是2)

判断质数
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);
1
2
3
4
5
6
7
8
9
10
11
12
13
14

map

#include<map>
map<int, string> m;
m[k]  = v;
m[191123456] = "rose";
m.size();
如果是空的值，为0
map<int,int> mp;
cout << mp[123];   //mp[123] = 0
默认自动以key来排序
map<int,int>::iterator it;
for(it = mp.begin(); it != mp.end(); it ++)
	cout << it->first <<" " << it->second;
1
2
3
4
5
6
7
8
9
10
11
12

set

去重

#include<set>
set<int> s;
s.insert(x);
s.size();
set<int>::iterator it;
for(it = s.begin(); it != s.end(); it ++)
	cout << (*it) << " " ;
1
2
3
4
5
6
7

stringstream

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

#include<sstream>
stringstream ss;
string s = "to be or not 123";
ss << s;
string temp;
while(ss >> temp)
{
	cout << temp<<endl;
}
to
be
or
not
123
---------------
#include<sstream>
stringstream ss;
string s = "123 456 789";
ss << s;
int num
while(ss >> num)
{
	cout << temp<<endl;
}
123
456
789
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

math

#incldue<cmath> --->#include<math.h>
//开根号,
int k = sqrt(x);



1
2
3
4
5
6