2022年天梯赛题目解析

L1-1 今天我要赢 (5 分)[输出水题]

题目描述

代码

#include <iostream>
using namespace std;

int main()
{
	cout << "I'm gonna win! Today!" << endl;
    cout << "2022-04-23" << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9

---

L1-2 种钻石 (5 分)[四则运算]

题目描述

代码

#include <iostream>

using namespace std;

int main()
{
    int n , v;
    cin >> n >> v;
    cout << n / v;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11

---

L1-3 谁能进图书馆 (10 分)[分类讨论,判断题]

题目描述

代码

#include <iostream>

using namespace std;

int  main()
{
	int j , p , x1 , x2;
	cin >> j >> p >> x1 >> x2;
	if(x1 >= j || (x1 < j && x2 >= p)) cout << x1 << "-Y ";
	else       cout << x1 << "-N ";
	if(x2 >= j|| (x2 < j && x1 >= p)) cout << x2 << "-Y\n";
	else       cout << x2 << "-N\n";
	if(x1 >= j && x2 >= j) {
		cout << "huan ying ru guan\n";
	} else if(x1 < j && x2 < j) {
		cout << "zhang da zai lai ba\n";
	} else if(x1 < j && x2 >= p) {
		printf("qing 2 zhao gu hao 1\n");
	} else if(x2 < j && x1 >= p) {
		printf("qing 1 zhao gu hao 2\n");
	} else if(x1 >= j && x2 < j && x1 < p) {//一开始这里没考虑清楚,最后一分钟发现错误~
		printf("1: huan ying ru guan\n");
	} else if(x2 >= j && x1 < j && x2 < p) {
		printf("2: huan ying ru guan\n");
	}
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

总结:

1. 做这种分类讨论的题,需要人们把所有的情况都考虑清楚,一般分类的情况较多,可以在纸上做一个简单的思维导图,这样思路就清晰,就不会出现考虑不全出现细节的错误(考试出现这种错误,找bug叶难找~~)
2. 思维导图:
   

---

L1-4 拯救外星人 (10 分)[数学]

题目描述

代码

#include <iostream>
using namespace std;

long long f(int n)//最好写成long long , 防止数据溢出 
{
    long long t = 1;
    for(int i = 1 ; i <= n ; ++i)
        t *= i;
    return t;
}
int main()
{
    int a , b;
    cin >> a >> b;
    cout << f(a + b);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

L1-5 试试手气 (15 分)[数组]

题目描述

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;

int num[10];
bool vis[10][10];
//vis[第i个面][第i个面的点数]:判断是否出现过
int main()
{
    for(int i = 0 ; i < 6 ; ++i) cin >> num[i];
    int n;
    cin >> n;
    while(n--) {
        for(int i = 0 ; i < 6 ; ++i) {
            vis[i][num[i]] = true;
            //从大到小,保证每次点数最大
            for(int j = 6 ; j >= 1 ; --j)
                if(!vis[i][j]) {
                    num[i] = j;
                    break;
                }
        }
    }
    for(int i = 0 ; i < 6 ; ++i) cout << num[i] << " \n"[i == 5];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

---

L1-6 斯德哥尔摩火车上的题 (15 分)[字符串]

题目描述

代码

#include <iostream>

using namespace std;

string f(string s)
{
    string s0;
    for (int i = 1 ; i < s.size(); i++)
        if (s[i] % 2 == s[i-1] % 2)
            s0 += max(s[i], s[i-1]);
    return s0;
}
int main()
{
    string s1 , s2;
    cin >> s1 >> s2;
    if(f(s1) == f(s2)) cout << f(s1);
    else cout << f(s1) << endl << f(s2) << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

L1-7 机工士姆斯塔迪奥(20 分)[set用法]

题目描述

代码

考试19分代码

#include <bits/stdc++.h>

//考试19分
using namespace std;
const int N = 1e4 + 9999;
bool vis[N][N];
int  main()
{
	int n , m , q , ans = 0;
	cin >> n >> m >> q;
	while(q--) {
		int t , c;
		cin >> t >> c;
		if(t == 1) {
			for(int i = 0 ; i < n ; ++i)
				vis[i][c - 1] = true;
		} else {
			for(int i = 0 ; i < m ; ++i)
				vis[c - 1][i] = true;
		}
	}
 	for(int i = 0 ; i < n ; ++i)
		for(int j = 0 ; j < m ; ++j) {
			if(vis[i][j]) continue;
			++ans;
		}
	cout << ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

总结:

1. 二维数组空间不宜过大,容易爆栈(比如这道题$N=10^5$)

AC代码

#include <bits/stdc++.h>

using namespace std;

set<pair<int , int>>st;
int  main()
{
	int n , m , q , ans = 0;
	cin >> n >> m >> q;
	while(q--) {
		int t , c;
		cin >> t >> c;
		if(t == 1) {
			for(int i = 1 ; i <= n ; ++i) {
				if(!st.count({i , c})) ++ans;
				st.insert({i , c});
			}
		} else {
			for(int i = 1 ; i <= m ; ++i) {
				if(!st.count({c , i})) ++ans;
				st.insert({c , i});
			}
		}
	}
	cout << n * m - ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

总结

1. 这道题只需记录已经释放技能的方格,无需遍历整个方格
2. 所以可以利用容器(set等)存储已经释放技能的方格,这样就避免了二维数组开销过大的问题
3. 利用pair将行号和列号作为一个整体,便于处理(经常使用)

---

L1-8 静静的推荐(20 分)[模拟,贪心]

题目描述

代码

1.考试1分代码

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int , int> pii;
multimap<int , int> m;
bool v1[300][105];

int  main()
{

	int n , k , s;
	cin >> n >> k >> s;
	while(n--) {
		int t , p;
		scanf("%d %d" , &t , &p);
		if(t < 175) continue;
  		m.insert(make_pair(t , p));
	}
	int ans = 0 , ans1 = 0 , ans2 = 0;
	for(int l = 0 ; l < k ; ++l) {
		bool v2[300] = {false};
		for(auto i = m.begin() ; i != m.end() ; ++i) {
			if(i->y >= s && !v1[i->x][i->y] && m.count(i->x) > 1 && l != 0) {
				++ans;
				v1[i->x][i->y] = true;
				continue;
			}
			if(!v2[i->x] && !v1[i->x][i->y]) {
				++ans;
				v2[i->x] = true;
				v1[i->x][i->y] = true;
			}
		}
		
	}
	cout << ans<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

总结:

1. 没有考虑两个分数都相同的情况,利用二维数组进行标记无法处理这种情况
2. 考试时思维较乱,花了很长时间都没做出来~~
3. 对map存储不太熟悉(不能直接存储结构体(pair)作为键值),调试了很长时间~

2. 14分代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define x first
#define y second
using namespace std;

typedef pair<int , int> pii;
vector<pii> v;

int main()
{
	int n , k , s;
	cin >> n >> k >> s;
	while(n--) {
		int t , p;
		scanf("%d %d" , &t , &p);
		if(t < 175) continue;
		v.push_back({t , p});
	}
	sort(v.begin() , v.end());
	int ans = 0;
	while(k--) {
		bool vis[300] = {false};
		for(int i = 0 ; i < v.size() ; ++i) {
			if(vis[v[i].x] && v[i].y < s) continue;
			vis[v[i].x] = true;
			++ans;
			v.erase(v.begin() + i);
			i = 0;
		}
	}
	cout << ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

总结:

1. 这种做法是大众的做法,直接枚举所有批次(k)、所有>175分的面试者,即需要两重循环来操作
2. 利用erase()函数删掉选过的面试者
   注意:
   (1) erase(迭代器) , vector中删除单个元素的用法是:v.erase(v.begin() + i)
   (2)其中i是从0开始到第i个,并且删除元素后容器里元素的下标改变所以每次删除都要将i置为0
   (3)由于需调用erase() , 所以增加了运行时间,并且$max(k\ast n)=p\ast 5\ast 10^8(p由erase()函数决定)$,而给定的时间是200ms,所以TLE

3.AC代码

#include <iostream>
#include <cstdio>
#include <unordered_map>
#define x first
#define y second
using namespace std;
unordered_map<int , int> m;
int main()
{
	int n , k , s , ans = 0;
	cin >> n >> k >> s;
	while(n--) {
		int t , p;
		scanf("%d %d" , &t , &p);
		if(t < 175) continue;
		if(p >= s) {
			++ ans;
			continue;
		}
		++m[t];
	}
 	for(auto i : m)
		ans += i.y >= k ? k : i.y;
	cout << ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

总结:

1.按照之前的思路两重循环TLE,所以得往一重循环的方向想
2. 题目的意思是(非常重要):

• 凡是天梯赛分数>=175分都有机会被录取
• 凡是PTA分数>=s(该企业的面试分数线) , 直接被录取(天梯赛分数>=175)
• 同一个批次不能录取天梯分数一样的面试者(除了TA分数>=s(该企业的面试分数线)的面试者) , 即只能录取一个
• 同一批次的面试者不管PTA考多少分(PTA分数>=s(该企业的面试分数线) 除外)

3.所以思路就很明确:

• 先处理掉天梯赛分数>=175的面试者(++ans) 和 天梯赛分数 < 175 (边输入边操作)
• 剩下的就利用hash计数(数组,容器都可以),计算相同分数有多少面试者
• 如果批次k >= 某个分数的面试者的个数, 说明该分数的面试者全部被录取
• 如果批次k < 某个分数的面试者的个数, 说明该分数的面试者部分被录取,录取了k个
• 核心代码: ans += i.y >= k ? k : i.y; , emmmm,有点贪心的思想

L2-2 老板的作息表(25分)[排序]

代码

#include <iostream>
#include <set>
#include <unordered_map>
using namespace std;
set<string>st;
unordered_map<string , int> vis;
void f(string s) {
   	if(vis[s] == 2 || s == "00:00:00" || s == "23:59:59")
		st.erase(s);
	else
		st.insert(s);
}
int main()
{
	//卡输入输出,如果不解除缓存,就TLE(21)分
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n , k , j = 0;
    cin >> n;
    while(n-- ) {
    	char ch;
        string s1 , s2;
        cin >> s1 >> ch >> s2;
        ++vis[s1] , ++vis[s2];
		f(s1) , f(s2);
    }
	if(!(vis["00:00:00"])) st.insert("00:00:00");
	if(!(vis["23:59:59"])) st.insert("23:59:59");
	for(auto i : st) {
		++j;
		cout << i;
		j & 1 ? cout << " - " : cout << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

总结:

1. 思路就是看有没有重复的时间,如果没有,就输出(除了00:00:00 和23:59:59)
2. 可以将时间看成字符串,输出字符串s1,字符'-', 和字符串s2
3. 利用set存储要输出的答案:
   (1)先将时间全部存储进去
   (2)再利用hash判断其时间是否重复
   (3)如果重复,就删除,否则就不删除
   (4)特判00:00:00 和23:59:59 , 这两个只要出现就删除
   (5)如果不出现00:00:00 和23:59:59 , 就添加
4. emmmm,如果按照以上思路做,直接TLE(21)分,因为每个区间间隔至少 1 秒,max(n) = 86400 / 2
5. 这道题卡输入输出,发现有时能过,有时不能过,可以利用:

//解除缓存的模板
ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
1
2
3
4

C/C++如何加速输入输出效率

WINDWOS下[1e5的数据量]：
使用解除绑定的cout ： 30.719000 秒 ， 29.518000 秒 ， 29.446000 秒
不使用解除绑定cout ： 51.749000 秒 , 49.383000 秒 ， 47.605000 秒
C++文件的printf ： 84.962000 秒 ， 76.131000 秒 ， 77.639000 秒
C语言文件的printf ： 29.776000 秒 ， 29.327000 秒 ， 29.862000 秒

---