线性数据结构

T1 P3613 【深基15.例2】寄包柜

用二位数组肯定挂，所以采用map或者vector

#include<bits/stdc++.h>
using namespace std;
map<int , int>a[100020];
int n , m ; 
int main () {
	cin >> n >> m;
	for(int i = 1; i <= m ;i ++) {
		int x;
		cin >> x;
		if(x == 1){
			int o , y , z;
			cin >> o >> y >> z;
			a[o][y] = z;
		}else{
			int o , y ;
			cin >> o >> y ;
			cout << a[o][y] << endl;
		}
	}
}

T2 P1241 括号序列

左括号入栈，然后碰到右括号就判断一下栈顶，如果恰好是左括号就标记，然后出栈，否则就不做处理

#include<bits/stdc++.h>
using namespace std;
stack <pair <char,int> > q;
string s;
int v[100020];
int main () {
	cin >> s;
	int len = s.size();
	for(int i = 0 ; i < len ; i ++){
		if(s[i] == '(' || s[i] == '['){
			q.push(make_pair(s[i] , i));
		}    
		if(q.size() && s[i] == ')' && q.top().first == '('){
			v[i] = 1;
			v[q.top().second] = 1;
			q.pop();
		}
		if(q.size() && s[i] == ']' && q.top().first == '['){
			v[i] = 1;
			v[q.top().second] = 1;
			q.pop();
		}
	}
	for(int i = 0 ;i < len ; i ++){
		if(v[i]){
			cout << s[i];
		}else{
			if(s[i] == '(' || s[i] == ')'){
				cout << "()";
			}
			if(s[i] == '[' || s[i] == ']'){
				cout<< "[]"; 
			}
		}
	} 
}

T3 P1449 后缀表达式

注意读入就好，不需要考虑符号优先级

#include<bits/stdc++.h>
using namespace std;
stack <pair <char,int> > q;
string s;
int v[100020];
int main () {
	cin >> s;
	int len = s.size();
	for(int i = 0 ; i < len ; i ++){
		if(s[i] == '(' || s[i] == '['){
			q.push(make_pair(s[i] , i));
		}    
		if(q.size() && s[i] == ')' && q.top().first == '('){
			v[i] = 1;
			v[q.top().second] = 1;
			q.pop();
		}
		if(q.size() && s[i] == ']' && q.top().first == '['){
			v[i] = 1;
			v[q.top().second] = 1;
			q.pop();
		}
	}
	for(int i = 0 ;i < len ; i ++){
		if(v[i]){
			cout << s[i];
		}else{
			if(s[i] == '(' || s[i] == ')'){
				cout << "()";
			}
			if(s[i] == '[' || s[i] == ']'){
				cout<< "[]"; 
			}
		}
	} 
}

T4P1160 队列安排

简单链表题，不能把A在B右边直接做成B在A左边

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 20;
int n , m;
struct node{
	int l , r;
}a[N];
int v[N];
void insert(int x , int y , int f){
		if(f == 0){
		a[y].r = x;
		a[y].l = a[x].l;
		a[x].l = y;
		a[a[y].l].r = y;
	}else{
		a[y].r = a[x].r;
        a[y].l = x; 
        a[x].r = y;
        a[a[y].r].l = y;
	}
}
int main (){
	cin >> n ;
	insert(1 , 0 , 1);
   for(int i = 2; i <= n ;  i++){
		int x , o;
		cin >> x  >> o;
        insert(x , i  , o);
}
	cin >> m;
	while(m --){
		int x;
		cin >> x;
		v[x] = 1;
	} 
	for(int i = a[0].r ; i ; i = a[i].r){
		if(!v[i]){
			cout << i << " ";
		}
	}
	return 0;
}