MT2135调整队伍
马蹄集：链表
小码哥迎来了他大学的第一次军训，军训的第一个项目就是列队，每个同学在队伍中都有属于自己的编号。但在练习过程中，教官怎么看这支队伍怎么不顺眼，于是决定调整一下队伍的顺序。
为了顺便考验同学们的反应力，教官与学生们约定了一个口令，每当他说x y 0，x号同学就要移动到y号同学的前面，每当他说x y 1，x号同学就要移动到y*号同学的后面，但学生们不想一次次慢慢移动这么麻烦，想要知道队伍最后是怎么排的然后直接排好。为了解决同学们的烦恼，小码哥立刻动手原地写了一个程序算出了最终排序。
现在告诉你队伍从前到后的初始排序编号以及教官的口令，要你得出队伍从前往后的最终排序。已知有n个学生，编号不重复且1≤编号≤n1≤编号≤n。
格式
输入格式：
第一行两个正整数n，m，表示学生的数量和教官口令的数量；
第二行n个正整数，表示学生们的初始排序；
接下来m行，每行3个整数，表示教官的口令。
输出格式：
nn个数字，每个数字之间用空格隔开，表示队伍从前往后的最终排序。
样例 1
输入：
10 5
8 4 6 7 9 3 5 10 1 2
4 9 0
10 5 1
3 9 0
1 9 1
3 6 0
输出：
8 3 6 7 4 9 1 5 10 2
AC代码：
#include<iostream>
using namespace std;
//这是一个实现循环链表，操作数字前插尾插的操作代码；
const int ma=3e5+7;
struct add{
int l; //左节点；
int r; //右节点；
}insert[ma];
int n,m,ne,head;
int main(){
cin >> n >> m;
//初始化，实现把输入的各各节点已链表的形式连接起来；
while(n--){
int tt;
cin >> tt;
insert[tt].l=ne;
insert[ne].r=tt;
ne=tt;
}
while(m--){
int x,y,op;
cin >> x >> y >> op;
//记录要操作的左右节点；
int i=insert[x].l,j=insert[x].r;
//不管怎样都是要实现删除；
//在外头就实现删除，让操作的左节点的右指针指向右节点的左指针；
//在里头就只要实现插入操作；
insert[i].r=j,insert[j].l=i;
i=insert[y].l,j=insert[y].r;
if(op){
//循环链表基操；
//操作数后插操作；
insert[x].l=y;
insert[x].r=j;
insert[y].r=x;
insert[j].l=x;
}else{
//操作数前插操作；
insert[x].l=i;
insert[x].r=y;
insert[y].l=x;
insert[i].r=x;
}
}
//这里刚开始会有点迷；
//这里主要实现从头(0节点)的右节点开始；
ne=insert[head].r;
//直到遇到一个非正数的数值(/n)等等停止；
while(ne){
cout << ne << " ";
ne=insert[ne].r;
//一直指向下一个右节点；
}
return 0;
}
MT2114括号家族
马蹄集：栈
小码哥在研究只有左括号和右括号组成的序列。给出一个括号序列，求出最长合法子串和它的数量（合法的定义：这个序列中左右括号匹配）。
例如:(()不合法，)()(也不合法，但()()和(())合法。
格式
输入格式：
输入一行只有左括号和右括号组成的序列（只包含小括号）。
输出格式：
输出两个数字：最长子字符串的长度，以及此类子字符串的数量，如果没有这样的子字符串，则输出0 1。
样例 1
输入：
()()))()()(()
输出：
4 2
备注
其中：字符串长度小于等于 10^6;
AC代码：
#include<iostream>
#include<stack>
#include<map>
using namespace std;
//这算个是栈的最最基础代码(主要是用到的两常用容器，下次在见就是复习了)
const int N=10000010;
//pair<char,int>定义映射两种类型；
stack<pair<char,int>> st;
int arr[N]={0};
int main(){
string s;
cin >> s;
int len=s.size();
for(int i=0;i<len;i++){
//左括号操作；
if(s[i]=='('){
//映射左括号，以及它的下标；
pair<char,int> tmp(s[i],i);
//压入栈中；
st.push(tmp);
}else{
//如果栈中是左括号遇到右括号，标记对应的左右括号为 1；
//first这里代表char类型的操作；
if(!st.empty() && st.top().first=='('){
//st.top(),second:栈头元素的int类型进行操作；
//这里就让int类型的操作赋值为 1；
//arr[i]右括号赋值为 1；
arr[i]=arr[st.top().second]=1;
//栈顶出栈(左括号)；
st.pop();
}else{
//俩都不是就继续压入栈中；
pair<char,int> tmp(s[i],i);
st.push(tmp);
}
}
}
//map老朋友了，这里ans记录长度，mp[ans]计入个数；
map<int,int> mp;
int ans=0,ct=0;
for(int i=0;i<len;i++){
if(arr[i]==1){
ct++;
}else{
if(ct>=ans){
ans=ct;
mp[ans]++;
}
ct=0;
}
}
// 在代码中，ct 用于计算当前有效括号的数量，而 ans 用于记录最大有效括号的长度。
// 当遇到无效括号时，代码会检查当前有效的长度 ct 是否大于等于 ans，如果是，就更新 ans 并重置 ct 为0。
// 但是，在循环结束后，如果最后有一段有效的括号（例如字符串以有效括号结尾），就要再次检查 ct。
// 这就是后面的 if(ct >= ans) 这一段的目的，以确保我们不会遗漏最后的有效长度。
if(ct>=ans){
ans=ct;
mp[ans]++;
}
if(ans==0) cout << "0 1" << endl;
else cout << ans << " " << mp[ans] << endl;
return 0;
}