最近在重刷 天梯赛，浅浅记录一下，进入L2阶段了

---

L2-001 紧急救援

解题思路：典型的dijkstra模板题，带路径记录与权重，方案数记录，解析出过     Dijkstra(兼路径)

#include <bits/stdc++.h>
#define inf 0x3f3f3f
using namespace std;
const int N = 510;
int n, m, s, d;
int mp[N][N];
int dis[N], path[N], num[N], cot[N], sum[N];
bool st[N];
//先找到最短路径，再用相等条件下的最优解，记录最优解路径
//输出最短路径数量，输出最优解能召集到的最多数量的救援队，输出最优解路径

void dijkstra(){
    memset(dis, inf, sizeof(dis));
    memset(cot, 0, sizeof(cot));
    memset(st, false, sizeof(st));
    memset(sum, 0, sizeof(sum));
    sum[s] = num[s];
    cot[s] = 1;
    dis[s] = 0;
    for(int i =0; i<n; i++){
        int t = -1;
        for(int j=0; j<n; j++)
            if(!st[j] && ( t == -1 || dis[t] > dis[j])) t = j;
         st[t] = true;
        //cout<<t<<endl;
         for(int j = 0; j<n; j++){
             if(dis[j] > dis[t] + mp[t][j]){
                 path[j] = t;
                 dis[j] = dis[t] + mp[t][j];
                 cot[j] = cot[t];
                 sum[j] = sum[t] + num[j];
             }else if(dis[j] == dis[t] + mp[t][j]){
                 cot[j] += cot[t];
                 if(sum[j] < sum[t]+num[j]){
                     sum[j] = sum[t]+num[j];
                     path[j] = t;
                 }
             }
         }
    }
}
void printPath(int x, int y){
     if(y == x) cout<<x;
     else {
         printPath(x, path[y]);
         cout<<' '<<y;
     }
}
int main()
{
    cin>>n>>m>>s>>d;
    memset(mp, inf, sizeof(mp));
    memset(num, 0, sizeof(num));
    int x, y,z; 
    for(int i = 0; i< n; i++) cin>>num[i];
    while(m--){
        cin>>x>>y>>z;
        mp[y][x] = mp[x][y] = min(mp[x][y], z);
    }
    dijkstra();
    cout<<cot[d]<<' '<<sum[d]<<endl;
    printPath(s, d);
    return 0;
}

L2-002 链表去重

解题思路：指针，先读入，再两个分别用两个指针指向两个序列，记录序列头，重复情况用st记录键值最大也就1e4

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
bool st[N];
int  e[N], ne[N];
int main()
{
    int fpos, anspos1=-1, anspos2 = -1, spos = -1, tpos = -1,n;
    cin>>fpos>>n;
    int a, b, c;
    for(int i = 0; i<n ;i++){
        cin>>a>>b>>c;
        e[a] = b; ne[a] = c;
    }
    memset(st, false, sizeof(st));
    while(fpos != -1){
        if(st[abs(e[fpos])] == false ) {
            if(anspos1 == -1) anspos1 = fpos, anspos2= fpos;
            else ne[anspos2] = fpos, anspos2 = fpos; 
           st[abs(e[fpos])] = true;
        }else{
            if(spos == -1) spos = fpos, tpos = fpos;
            else ne[tpos] = fpos , tpos = fpos;
        }
        fpos = ne[fpos];
    }
    ne[tpos] = -1;
    ne[anspos2] = -1;
    while(anspos1 != -1){
        printf("%05d %d ", anspos1, e[anspos1]);
        if(ne[anspos1] != -1) printf("%05d\n", ne[anspos1]);
        else cout<<-1<<endl;
        anspos1 = ne[anspos1];
    }
    while(spos != -1){
        printf("%05d %d ", spos, e[spos]);
        if(ne[spos] != -1) printf("%05d\n", ne[spos]);
        else cout<<-1<<endl;
        spos = ne[spos];
    }
    return 0;
}

L2-003 月饼

解题思路：自定义排序，测试点2是 库存或者价格可能为小数

L2-004 这是二叉搜索树吗？

解题思路：树的遍历与遍历序列切割，经典，找符合条件的左右孩子，重塑树，同时考虑单调的特殊情况。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3+10;

vector<int > ans, ans2, p(1010);
void build1(int l, int r){
    if(l > r) return ; 
    int x = l+1, y = r;
    while(x <= r && p[x] < p[l]) x++;
    while(y > l && p[y] >= p[l]) y--;
    if(x - y != 1 ) return ;
    build1(l+1, y);
    build1(x, r);
     ans2.push_back(p[l]);
}
void build2(int l, int r){//镜像
    if(l > r) return ;
    int x = l+1, y = r;
    while(x <= r && p[x] >= p[l]) x++;
    while(y > l && p[y] < p[l]) y--;
    
    if(x - y  != 1 ) return ;
    build2(l+1, y);
    build2(x, r);
    ans2.push_back(p[l]);
}
signed main()
{
    int n;
    cin>>n;
    for(int i = 1; i<=n; i++){
         cin>>p[i];
    }
    build1(1, n);
    bool flag = false;
    if(ans2.size() == n){
        cout<<"YES"<<endl;
        for(int i = 0; i< ans2.size(); i++)
            if(i == 0) cout<<ans2[0];
            else cout<<' '<<ans2[i];
    }else{
        ans2.clear();
        build2(1, n);
        if(ans2.size() == n){
            cout<<"YES"<<endl;
            for(int i = 0; i< ans2.size(); i++)
            if(i == 0) cout<<ans2[0];
            else cout<<' '<<ans2[i];
        }
        else {
            cout<<"NO";
        }
    }
    cout<<endl;
	return 0;
}

L2-005 集合相似度

解题思路：STL yyds, 用set， find

L2-006 树的遍历

解题思路：思考过程如下，经典的知道其中两个遍历序列，求另一种，这里是求了层序遍历复杂点，求先序简单。

#include <bits/stdc++.h>
using namespace std;
const int N = 500;
struct node{
    int x, l, r;
}tree[N];
int last[N], mid[N];
int idx = 0;
vector<int > ans ;
int rebuild(int l1, int r1, int l2, int r2){
    int pos;
    if(l1 > r1) return -1;
    for(int i = l1; i<= r1; i++)
        if(mid[i] == last[r2]){
            pos = i; break;
        }
    idx++;
    int ret = idx;
    tree[ret].x = last[r2];
    tree[ret].l = rebuild( l1, pos-1, l2, l2+pos-1-l1);
    tree[ret].r = rebuild( pos+1, r1, l2+pos-l1, r2-1);
    return ret;
}
void bfs(){
    queue<int> q;
    q.push(1);
    ans.clear();
    while(q.size()){
        int tmp = q.front();
        q.pop();
        if(tree[tmp].l != -1) q.push(tree[tmp].l);
        if(tree[tmp].r != -1) q.push(tree[tmp].r);
        ans.push_back(tree[tmp].x);
    }
}
int main()
{
   int n;
    cin>>n;
    for(int i = 1; i<=n; i++)  cin>>last[i];
    for(int i = 1; i<=n; i++)  cin>>mid[i];
    int pos = rebuild( 1, n, 1, n);
    bfs();
    cout<<ans[0];
    for(int i=1; i<ans.size(); i++)
        cout<<' '<<ans[i];
    cout<<endl;
    return 0;
}

L2-007 家庭房产

解题思路：结构体，自定义比较函数，并查集，格式化输出，状态计数

首先读入，对所有存在的人计数，人的编号都4位，同时合并集合，使用临时容器，开始合并同集合的人数与房产，重新标记不重复找出所有的答案，再对答案进行排序输出。

AC代码：

#include <bits/stdc++.h>
#define ll long long 
#define rep(x, a, b) for(int x = a; x <= b; x++)
#define pre(x, a, b) for(int x = b; x >= a; x--)
using namespace std;
const int N = 1e4+10;
//家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。
//并查集！，合并同一家人的信息，先合并，合并人数和房产信息，合并到家庭成员的最小编号的身上，边读边合并吗？
bool st[N], st2[N];
int f[N];
struct node{
    int id, cotm, sumh;
    ll sum;
}nd[N], ans[N], tmp[N];
bool cmp(node a, node b){
    if(a.sum*1.0* b.cotm != b.sum*1.0 * a.cotm) return a.sum*1.0* b.cotm > b.sum*1.0 * a.cotm;
    return a.id<b.id;
}
int find(int x){
    if(x == f[x]) return x;
    else find(f[x]);
}
void merge(int a, int b){
    int x = find(a), y = find(b);
    if(x > y) f[x] = y; 
    else f[y] = x;
}

int main()
{
   int n;
    int a, b ,c, d, tmpcot, tmparea;
    cin>>n;
    memset(st2, false, sizeof(st));
    memset(st, false, sizeof(st));
    for(int i = 0; i< N; i++) f[i] = i; //并查集初始化
    for(int i = 0; i< n; i++){
        cin>>a>>b>>c>>d;
        st[a] = true;
        if(b != -1) merge(a, b), st[b] = true;
        if(c != -1) merge(a, c) , st[c] = true;
        for(int j = 0; j< d; j++){
            cin>>b;
            if(b != -1) merge(b, a),st[b] = true;
        }
        cin>>tmpcot>>tmparea;
        nd[i].id = a;nd[i].cotm = d; nd[i].sumh = tmpcot; nd[i].sum = tmparea;
    }
    for(int i = 0; i<N; i++){
        int t = find(nd[i].id);
        tmp[t].sumh += nd[i].sumh;
        tmp[t].sum += nd[i].sum;
        if(st[i]) tmp[find(i)].cotm++;
    }
    int idx = 0;
    for(int i = 0; i<N; i++){
        int x = find(i);
        if(st[x] && !st2[x]){
            ans[idx].id = x;
            ans[idx].cotm = tmp[x].cotm;
            ans[idx].sumh = tmp[x].sumh;
            ans[idx].sum  = tmp[x].sum;
            idx++;
            st2[x] = true;
        }
    }
    sort(ans, ans+idx, cmp);
    cout<<idx<<endl;
    for(int i = 0; i< idx; i++){
        printf("%04d %d %.3lf %.3lf\n", ans[i].id, ans[i].cotm, (double)(ans[i].sumh*1.0/ans[i].cotm), ans[i].sum*1.0/ans[i].cotm);
    }
    return 0;
}

L2-008 最长对称子串

解题思路：字符串，指针

L2-009 抢红包

解题思路：自定义排序，结构体

L2-010 排座位

解题思路：数量级比较小，关系用二维矩阵记录，朋友的朋友，与敌人之间的共同朋友用并查集解决，再做个判断。

L2-011 玩转二叉树

解题思路：与L2-006 树的遍历差不多，样例树都长得一样6

L2-012 关于堆的判断

解题思路：考察了堆的特质，注意点是读入，读完之后要把整行都吸收了，不然会影响后面的判断。make_heap(a.begin(),a.end(),greater<int>());， 用容器也可以，自己简单的堆排序也可以