天梯赛刷题小记 —— L2

最近在重刷 天梯赛，浅浅记录一下，进入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>());， 用容器也可以，自己简单的堆排序也可以