2026天梯全国总决赛L2 L3-1题解

L3-1 门诊预约排队系统本题题面比较难读懂,但捋清楚患者之间的优先级后就比较好做了。先理解题解中给出数据的含义, 就诊时间:即到该时间时该患者已经加入就诊等待的队列预约时间:患者在该时间时有最高的优先级(即优先接待他) ID和年龄即字面含义.我们考虑去枚举时间ttt所有就诊时间≤t\le t≤t的患者加入等待队列.处理的优先级是:①预约了当前时间的患者②80岁以上且id最小的老人③其他① 预约了当前时间的患者 ② 80岁以上且id最小的老人 ③其他①预约了当前时间的患者②80岁以上且id最小的老人③其他这里要考虑用setsetset或multisetmultisetmultiset去维护80岁和非80岁的两个等待患者,因为我们需要查询某个患者的预约时间大小同时还涉及到ididid的比较还需要将处理过的患者删除,显然用这两个维护更加合适int n; struct node{ int l,r; string id; int ag; }e[N]; void solve(){ cin n; string tmp 0; for (int i1; in; i){ cin e[i].l e[i].r e[i].id e[i].ag; } int p 1,sum 0; multisetpairint,stringse1,se2; for (int nx1; sumn;nx){ while(p n and e[p].l nx){ auto [l,r,id,ag] e[p]; if (ag 80){ se1.insert({r,id}); } else { se2.insert({r,id}); } p; } auto it1 se1.lower_bound({nx,tmp}); auto it2 se2.lower_bound({nx,tmp}); if (it1 ! se1.end()){ if (it1-fir nx){ cout nx it1-sec \n; sum; se1.erase(it1); continue; } } if (it2 ! se2.end()){ if (it2-fir nx){ cout nx it2-sec \n; sum; se2.erase(it2); continue; } } if (se1.size()){ cout nx se1.begin()-sec \n; sum; se1.erase(se1.begin()); continue; } if (se2.size()){ cout nx se2.begin()-sec \n; sum; se2.erase(se2.begin()); continue; } } }L2-4 大语言模型的推理一个小模拟,建图完成后我们考虑以ppp的大小进行访问每个点,当然保证每个点仅访问一次,将条边按照ppp排序后访问即可int n,m; vectorvectorpiig(N); bool cmp(pii a, pii b){ if (a.fir b.fir){ return a.sec b.sec; } return a.fir b.fir; } void solve(){ cin n m; for (int i1; im; i){ int u,v,p; cin u v p; g[u].pb({p,v}); } for (int u1; un; u){ sort(all(g[u]),cmp); } int k; cin k; while(k--){ int rt; cin rt; vectorintans; vectorintvis(n1); queueintq; q.push(rt); while(q.size()){ int u q.front(); q.pop(); if (vis[u])continue; vis[u] 1; ans.pb(u); for (auto [w,v]:g[u]){ if (vis[v])continue; q.push(v); break; } } for (auto v:ans){ cout v; if (v ans.back())break; cout -; } cout \n; } }L2-3 森林藏宝图本题做法多样,首先很容易注意到本题给出的图是一个树结构bfsbfsbfsdfsdfsdfs做都可以,赛时我很自然的想到二分最小值,checkcheckcheck函数在不访问边权小于midmidmid的边下若能访问到叶节点即为truetruetrue,最后再约束为求出的最小值下跑一遍dfsdfsdfs统计答案即可int n; vectorvectorpiig(N); vectorintans; bool dfs(int u, int fa, int mid){ if (g[u].size() 1 and u ! 0){ return true; } for (auto [v,w]:g[u]){ if (v fa)continue; if (w mid)continue; if (dfs(v,u,mid)){ return true; } } return false; } void dfs1(int u, int fa, int mid){ if (g[u].size() 1 and u ! 0){ ans.pb(u); return; } for (auto [v,w]:g[u]){ if (v fa or w mid)continue; dfs1(v,u,mid); } } bool check(int mid){ return dfs(0,0,mid); } void solve(){ cin n; for (int i1; in; i){ int fa,w; cin fa w; g[fa].pb({i,w}); g[i].pb({fa,w}); } int l -1, r 101; while(l 1 ! r){ int mid (l r) 1; if (check(mid)){ l mid; } else { r mid; } } cout l \n; dfs1(0,0,l); sort(all(ans)); for (auto v:ans){ cout v; if (v ans.back())break; cout ; } }L2-2 超参数搜索求max⁡i1nai\max_{i1}^{n} a_imaxi1n​ai​后输出答案,然后用multisetmultisetmultiset查询即可int n; int a[N]; void solve(){ cin n; multisetpiise; int mx 0; for (int i1; in; i){ cin a[i]; mx max(mx,a[i]); se.insert({a[i],i}); } vectorintans; for (int i1; in; i){ if (a[i] mx){ ans.pb(i); } } for (auto v:ans){ cout v; if (v ans.back())break; cout ; } cout \n; int m; cin m; while(m--){ int x; cin x; auto it se.upper_bound({x,inf}); if (it se.end()){ cout 0\n; continue; } cout it-sec \n; } }L2-1 姥姥改作业按照题意用栈模拟即可int n,t; int c[N]; void solve(){ cin n t; i64 avg 0; for (int i1; in; i){ cin c[i]; avg c[i]; } avg / n; i64 sum 0; stackintst; vectorintans; for (int i1; in; i){ if (c[i] t){ st.push(i); sum c[i]; } else { ans.pb(i); } } while(1){ stackintb; i64 tol 0; if (st.empty())break; sum / st.size(); while(st.size()){ int id st.top(); st.pop(); if (c[id] sum){ b.push(id); tol c[id]; } else { ans.pb(id); } } st b; sum tol; } for (auto id:ans){ cout id; if (id ans.back())break; cout ; } }头文件#include bits/stdc.h #define lowbit(x) (x - (x)) #define pii pairint,int #define pil pairint,long long #define pli pairlong long,int #define pss pairstring,string #define pll pairlong long,long long #define pdd pairdouble,double #define fir first #define sec second #define Y(s) cout s \n #define all(a) a.begin(),a.end() #define All(a) a.begin()1,a.end() #define MP make_pair #define pb push_back #define pf push_front #define eb emplace_back #define i64 long long #define i128 __int128_t #define ull unsigned long long #define ld long double #define ll long long using namespace std; const int N 3e5100,M 1000,inf 1e9,mod998244353; const long long INF 1e18; const double pi 3.1415926535897932385,eps 1e-9;