L3-1 门诊预约排队系统

本题题面比较难读懂,但捋清楚患者之间的优先级后就比较好做了。 先理解题解中给出数据的含义, 就诊时间:即到该时间时该患者已经加入就诊等待的队列 预约时间:患者在该时间时有最高的优先级(即优先接待他) ID和年龄即字面含义. 我们考虑去枚举时间 所有就诊时间的患者加入等待队列. 处理的优先级是: 这里要考虑用或去维护80岁和非80岁的两个等待患者,因为我们需要查询某个患者的预约时间大小同时还涉及到的比较，还需要将处理过的患者删除,显然用这两个维护更加合适

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 大语言模型的推理

一个小模拟,建图完成后我们考虑以的大小进行访问每个点,当然保证每个点仅访问一次,将条边按照排序后访问即可

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 森林藏宝图

本题做法多样,首先很容易注意到本题给出的图是一个树结构 做都可以,赛时我很自然的想到二分最小值,函数在不访问边权小于的边下若能访问到叶节点即为,最后再约束为求出的最小值下跑一遍统计答案即可

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 超参数搜索

求 后输出答案,然后用查询即可

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;