1，表达式求值
后缀表达式，非常简单高效的计算方式，用堆栈实现；
从左往右读表达式，
①，读入到实数，将其压入栈中，
②，读入到运算符，从堆栈中弹出适当数量的数，计算这些数的运算结果，并将结果压入栈中；
处理完后，栈顶的值就是表达式求完的值；
#include<bits/stdc++.h>
using namespace std;
//num里面存放着运算结果以及运算的数
//op里面存放着操作符
stack<int> num;
stack<char> op;
//eval()计算目前的表达式的值
void eval()
{
auto c = op.top(); op.pop();
cout << c << ' ';
}
int main()
{
unordered_map<char,int> pr{{'+',1},{'-',1},{'*',2},{'/',2}}; //哈希存储<key,value>
string str;
cin>>str;
for(int i = 0;i < str.size();i ++)
{
auto c = str[i];
//倘若这个字符是数字 且 连续出现数字，那么就需要将数字字符组合起来形成一个数
if(isdigit(c))
{
int x = 0, j = i;
while(isdigit(str[j]) && j < str.size()) //从字符串中从左往右还原整型 1000
x = x * 10 + str[j++] - '0';
i = j - 1;//更新i的值
cout << x << ' ';
}
//倘若是左括号，那么就要入操作符
else if(c == '(') op.push(c);
//若是右操作符，那么直到做操作符里所有的数，都要进行一系列的运算
else if(c == ')')
{
while(op.top() != '(') eval();
op.pop();//且将左括号删除
}
//若操作的是+-/*操作符，则根据栈头与目前操作符比较大小，若栈头操作符大于等于目前操作符则进行计算
//且将当前运算符入栈
else
{
while(op.size() && pr[op.top()] >= pr[c]) eval();
op.push(c);
}
}
//将剩余的运算符进行计算
while(op.size()) eval();
return 0;
}
2，铺设道路
一开始想的是连续上升或者下降的子序列，但是后面发现一个现象，只要ai>ai-1 那么ai-1就可以蹭ai，填大坑的时候顺便把小坑填了，何乐而不为呢；否则的话，ans+=ai – ai-1 ;
#include <bits/stdc++.h>
#define rep1(i,a,n) for(int i=a;i<n;i++)
#define rep2(i,a,n) for(int i=a;i<=n;i++)
#define per1(i,n,a) for(int i=n;i>a;i--)
#define per2(i,n,a) for(int i=n;i>=a;i--)
using namespace std;
const int mod=1e9+7;
using ll=long long;
using PII=pair<int,int>;
const int N=1e5+10;
int a[N];
int n;
int main()
{
cin>>n;
int ans=0;
rep2(i,1,n)
{
scanf("%d",&a[i]);
if(a[i]>a[i-1])ans+=a[i]-a[i-1];
}
cout<<ans;
return 0;
}
3，链表复习
约瑟夫问题；
add(int k,int x)，理解add得含义是在第k-1个插入得数后面插入数，也就是说，它不能直接凭空插入，必须前边有数；
按照模板，如果想要插入1~n，那么首先得add_head(1)，让1作为第0个插入的数，（add（）的含义）,然后
rep(i,2,n)
{
add(i-2,i);从第0个数后面开始插入；
}
这样就完成了1~n的插入操作；
但是，这样不能想删除节点的时候，就非常难受了；
所以改变思路，首先add_head(0),这样1~n都在节点里了就；
add_head(0);
rep(i,1,n)
{
add(i-1,i);从第0个数后面开始插入；
}
这样remove（i-1）就可以完成对i的删除操作
注意！！，每次使用必须初始化！head=-1，idx=0；
#include <bits/stdc++.h>
#define rep1(i,a,n) for(int i=a;i<n;i++)
#define rep2(i,a,n) for(int i=a;i<=n;i++)
#define per1(i,n,a) for(int i=n;i>a;i--)
#define per2(i,n,a) for(int i=n;i>=a;i--)
using namespace std;
const int mod=1e9+7;
using ll=long long;
using PII=pair<int,int>;
const int N=1e5+10;
int head,e[N],ne[N],idx;
void init()
{
head=-1;
idx=0;
}
void add_head(int x)
{
e[idx]=x;
ne[idx]=head;
head=idx;
idx++;
}
void add(int k,int x)
{
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx;
idx++;
}
void remove(int k)
{
ne[k]=ne[ne[k]];
}
int main()
{
int n,m;
int j=0,k=0,n1=n;
int b[500];
cin>>n>>m;
init();
add_head(0);
rep2(i,1,n)
{
add(i-1,i);
}
ne[n]=ne[head];闭合成环
for(int i=ne[head];;i=ne[i])
{
if(e[i]!=0)k++;删除操作不太好弄，吧ei设置一下，判断一下k++即可；
if(k==m)
{
b[j++]=e[i];
e[i]=0;
k=0;
}
if(j==n)break;
}
rep2(i,0,j-1)cout<<b[i]<<" ";
return 0;
}