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 i=1; i<=n; i++){ cin >> e[i].l >> e[i].r >> e[i].id >> e[i].ag; } int p = 1,sum = 0; multiset<pair<int,string>>se1,se2; for (int nx=1; sum<n;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; vector<vector<pii>>g(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 i=1; i<=m; i++){ int u,v,p; cin >> u >> v >> p; g[u].pb({p,v}); } for (int u=1; u<=n; u++){ sort(all(g[u]),cmp); } int k; cin >> k; while(k--){ int rt; cin >> rt; vector<int>ans; vector<int>vis(n+1); queue<int>q; 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; vector<vector<pii>>g(N); vector<int>ans; 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 i=1; i<n; 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 超参数搜索
求maxi=1nai\max_{i=1}^{n} a_imaxi=1nai后输出答案,然后用multisetmultisetmultiset查询即可
int n; int a[N]; void solve(){ cin >> n; multiset<pii>se; int mx = 0; for (int i=1; i<=n; i++){ cin >> a[i]; mx = max(mx,a[i]); se.insert({a[i],i}); } vector<int>ans; for (int i=1; i<=n; 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 i=1; i<=n; i++){ cin >> c[i]; avg += c[i]; } avg /= n; i64 sum = 0; stack<int>st; vector<int>ans; for (int i=1; i<=n; i++){ if (c[i] > t){ st.push(i); sum += c[i]; } else { ans.pb(i); } } while(1){ stack<int>b; 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 pair<int,int> #define pil pair<int,long long> #define pli pair<long long,int> #define pss pair<string,string> #define pll pair<long long,long long> #define pdd pair<double,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 = 3e5+100,M = 1000,inf = 1e9,mod=998244353; const long long INF = 1e18; const double pi = 3.1415926535897932385,eps = 1e-9;
