2022年天梯赛-全国总决赛（L1~L2）

落日映苍穹つ 2024-03-03 02:50 56阅读 0赞

[题目集入口 - 2022年天梯赛-全国总决赛 (pintia.cn)][- 2022_-_ _pintia.cn]

### L1-3 谁能进图书馆 ###

每一个一一列举

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
    	int minn, maxx, q1, q2;
    	cin >> minn >> maxx >> q1 >> q2;
    	//都可入
    	if(q1 >= minn && q2 >= minn)
    	{
    		cout << q1 << "-Y" << ' ' << q2 << "-Y" << '\n';
    		cout << "huan ying ru guan" << '\n'; 
    	} 
    	//都不可入
    	else if(q1 < minn && q2 < minn)
    	{
    		cout << q1 << "-N" << ' ' << q2 << "-N" << '\n';
    		cout << "zhang da zai lai ba" << '\n';
    	} 
    	//q1必须陪q2进
    	else if(q2 < minn && q1 >= maxx)
    	{
    		cout << q1 << "-Y" << ' ' << q2 << "-Y" << '\n';
    		cout << "qing " << 1 << " zhao gu hao " << 2 << '\n';
    	} 
    	//q2必须陪q1进
    	else if(q1 < minn && q2 >= maxx)
    	{
    		cout << q1 << "-Y" << ' ' << q2 << "-Y" << '\n';
    		cout << "qing " << 2 << " zhao gu hao " << 1 << '\n';
    	} 
    	//q1能进q2不能进
    	else if(q1 >= minn && q1 < maxx && q2 < minn)
    	{
    		cout << q1 << "-Y" << ' ' << q2 << "-N" << '\n';
    		cout << 1 << ": huan ying ru guan" << '\n';
    	} 
    	//q2能进q1不能进
    	else if(q2 >= minn && q2 < maxx && q1 < minn)
    	{
    		cout << q1 << "-N" << ' ' << q2 << "-Y" << '\n';
    		cout << 2 << ": huan ying ru guan" << '\n';
    	}  
    	return 0;
    }

### L1-7 机工士姆斯塔迪奥 ###

注意数组范围，这一列如果被选中就标为1，最后统计0就为安全的数量

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e4;
    int n, m, q, t, c, ans;
    int main()
    {
    	cin >> n >> m >> q;
    	int v[n + 1][m + 1];
    	memset(v, 0, sizeof v);
    	while(q --)
    	{
    		cin >> t >> c;
    		if(t == 0)
    		{
    			for(int i = 1; i <= m; i ++)
    			{
    				v[c][i] = 1;
    			}
    		}
    		else
    		{
    			for(int i = 1; i <= n; i ++)
    			{
    				v[i][c] = 1;
    			}
    		}
    	}
    	for(int i = 1; i <= n; i ++)
    	{
    		for(int j = 1; j <= m; j ++)
    		{
    			if(v[i][j] == 0)ans ++;
    		}
    	}
    	cout << ans;
    	return 0;
    }

### L1-8 静静的推荐 ###

只需要将需要计算的加入计算即可：tts >= 175 && pat < s

同一个分数在一批中只能选择一个人，有k批就可以选择k个人，当然不足k批就选择kk个人（分数相同的人）

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e5 + 10;
    int n, k, s, ans, num;
    struct node
    {
    	int tts, pat;
    }a[N], b[N];
    bool cmp(node x, node y)
    {
    	if(x.tts != y.tts)return x.tts > y.tts;
    	else
    	{
    		return x.pat < y.pat;
    	}
    }
    int main()
    {
    	cin >> n >> k >> s;
    	for(int i = 1;i <= n; i ++)
    	{
    		cin >> a[i].tts >> a[i].pat;
    		if(a[i].tts >= 175 && a[i].pat >= s)ans ++;
    		if(a[i].tts >= 175 && a[i].pat < s)
    		{
    			num ++;
    			b[num] = a[i];
    		}
    	}
    	sort(b + 1, b + 1 + n, cmp);
    	for(int i = 1; i <= num; i ++)
    	{
    		int kk = 1;
    		while(b[i].tts == b[i + 1].tts)
    		{
    			kk ++;
    			i ++;
    		}
    		ans += min(k, kk);
    	}
    	cout << ans;
    	return 0;
    }

### L2-041 插松枝 ###

大模拟，注意第一个空格

#include<bits/stdc++.h>
    using namespace std;
    int n, m, k, x, cnt;
    queue<int> q;
    stack<int> q1;
    queue<int> ans;
    int main()
    {
    	cin >> n >> m >> k;
    	for(int i = 1; i <= n; i ++)
    	{
    		cin >> x;
    		q.push(x);
    	}
    	while(q1.size() || q.size())//如果盒子里或者推送器里有松针片就可以继续操作 
    	{
    		int cnt = 0, last = 1000;
    		bool is_first = true;
    		while(cnt < k)
    		{
    			if(q1.size() && q1.top() <= last)
    			{
    				if(is_first)is_first = false;
    				else cout << ' ';
    				cout << q1.top();
    				last = q1.top();
    				q1.pop();
    				cnt ++;
    			}
    			else if(q.size())
    			{
    				int t = q.front();
    				if(t <= last)
    				{
    					if(is_first)is_first = false;
    					else cout << ' ';
    					last = t;
    					cout << t;
    					q.pop();
    					cnt ++;
    				}
    				else if(q1.size() < m)
    				{	
    					q1.push(t);
    					q.pop();
    				}
    				else break;
    			}
    			else break; 
    		}
    		cout << '\n';
    	}
    	return 0;
    }

### L2-2 老板的作息表 ###

直接用string排序即可

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e5 + 10;
    int n;
    string s3 = " - ";
    struct node
    {
    	string s1, s2;
    }a[N];
    bool cmp(node x, node y)
    {
    	return x.s1 < y.s1;
    }
    int main()
    {
    	cin >> n;
    	for(int i = 1; i <= n; i ++)
    	{
    		cin >> a[i].s1 >> s3 >> a[i].s2;
    	}
    	sort(a + 1, a + 1 + n, cmp);
    	if(a[1].s1 != "00:00:00")
    	{
    		cout << "00:00:00" << ' ' << s3 << ' ' << a[1].s1 << '\n';
    	}
    	for(int i = 1; i < n; i ++)
    	{
    		if(a[i].s2 != a[i + 1].s1)
    		{
    			cout << a[i].s2 << ' ' <<  s3  << ' ' << a[i + 1].s1 << '\n';
    		}
    	}
    	if(a[n].s2 != "23:59:59")cout << a[n].s2 << ' ' << s3  << ' ' << "23:59:59" << '\n';
    	return 0;
    }

### L2-3 龙龙送外卖 ###

如果不回来的话，我们只取决于最后一个点是哪个点，用总走过点数距离的二倍减去最后一个点到根节点的距离，故这里我们可以确定最后的要到的点必须是最深的点

对比如下：

![ae7567409b284cf6aeac0fe1037ee773.jpeg][]

距离只取决于两部分：

1.所有走过边的两倍

2.离根节点最远的距离

故现在只需要动态的求出两个数

dfs(x)表示x这个点到根节点（外卖站）的距离

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e5 + 10;
    int n, m, x, maxx, sum, p[N], d[N];
    int dfs(int u)
    {
    	if(p[u] == -1 || d[u])return d[u];
    	sum ++;
    	d[u] = dfs(p[u]) + 1;
    	return d[u];
    }
    int main()
    {
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	cin >> n >> m;
    	for(int i = 1; i <= n; i ++)cin >> p[i];
    	for(int i = 1; i <= m; i ++)
    	{
    		cin >> x;
    		maxx = max(maxx, dfs(x));
    		cout << sum * 2 - maxx << '\n';
    	}
    	return 0;
    }

### L2-4 大众情人 ###

用floyd,求一下每一个人的最短距离，找到男生对女生（最大距离分之一）就是最小距离，再找一下女生对男生（最大距离分之一），遍历编号，找到异性缘最好的记录

#include<bits/stdc++.h>
    using namespace std;
    const int N = 510, inf = 1e9;
    int n, d[N], g[N][N], sex[N];
    int main()
    {
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	cin >> n;
    	for(int i = 1; i <= n; i ++)
    	{
    		for(int j = 1; j <= n; j ++)
    		{
    			if(i == j)g[i][j] = 0;
    			else g[i][j] = inf;
    		}
    	}
    	for(int i = 1; i <= n; i ++)
    	{
    		char op;
    		int k;
    		cin >> op >> k;
    		if(op == 'F')sex[i] = 1;
    		else sex[i] = 2;
    		for(int j = 1; j <= k; j ++)
    		{
    			int a, b;
    			char s = ':';
    			cin >> a >> s >> b;
    			g[i][a] = b;
    		}
    	}
    	for(int k = 1; k <= n; k ++)
    	{
    		for(int i = 1; i <= n; i ++)
    		{
    			for(int j = 1; j <= n; j ++)
    			{
    				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    			}
    		}
    	}
    	for(int i = 1; i <= n; i ++)
    	{
    		for(int j = 1; j <= n; j ++)
    		{
    			if(sex[i] != sex[j])
    			{
    				d[i] = max(d[i], g[j][i]);
    			}
    		}
    	}
    	int d1 = inf, d2 = inf;//d1为男对女的距离，d2为女对男的距离 
    	for(int i = 1; i <= n; i ++)
    	{
    		if(sex[i] == 2)d1 = min(d1, d[i]);
    		else d2 = min(d2, d[i]); 
    	}
    	vector<int> a, b;
    	for(int i = 1; i <= n; i ++)
    	{
    		if(sex[i] == 2)continue;
    		if(d[i] == d2)a.push_back(i);
    	}
    	for(int i = 1; i <= n; i ++)
    	{
    		if(sex[i] == 1)continue;
    		if(d[i] == d1)b.push_back(i);
    	}
    	cout << a[0];
    	for(int i = 1; i < a.size(); i ++)
    	{
    		cout << ' ' << a[i];
    	}
    	cout << '\n';
    	cout << b[0];
    	for(int i = 1; i < b.size(); i ++)
    	{
    		cout << ' ' << b[i];
    	}
    	return 0;
    }

[- 2022_-_ _pintia.cn]: https://pintia.cn/problem-sets/1518150003758182400
[ae7567409b284cf6aeac0fe1037ee773.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/03/5531be11f2e54da299404578a4ffea43.png