2022天梯赛解析要点有哪些？
- 内容介绍
- 文章标签
- 相关推荐
本文共计2736个文字，预计阅读时间需要11分钟。
L1-1+今日我要完成（5+分）项目描述+代码
L1-1 今天我要赢 (5 分) 题目描述 代码#include <iostream>
using namespace std;
int main()
{
cout << "I'm gonna win! Today!" << endl;
cout << "2022-04-23" << endl;
return 0;
}
L1-2 种钻石 (5 分) 题目描述
#include <iostream>
using namespace std;
int main()
{
int n , v;
cin >> n >> v;
cout << n / v;
return 0;
}
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;
}
总结:
- 做这种分类讨论的题,需要人们把所有的情况都考虑清楚,一般分类的情况较多,可以在纸上做一个简单的思维导图,这样思路就清晰,就不会出现考虑不全出现细节的错误(考试出现这种错误,找bug叶难找~~)
- 思维导图:
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;
}
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;
}
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;
}
L1-7 机工士姆斯塔迪奥(20 分) 题目描述 代码 考试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;
}
总结:
- 二维数组空间不宜过大,容易爆栈(比如这道题\(N = 10^5\))
#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;
}
总结
- 这道题只需记录已经释放技能的方格,无需遍历整个方格
- 所以可以利用容器(set等)存储已经释放技能的方格,这样就避免了二维数组开销过大的问题
- 利用pair将行号和列号作为一个整体,便于处理(
经常使用)
L1-8 静静的推荐(20 分) 题目描述
#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;
}
总结:
- 没有考虑两个分数都相同的情况,利用二维数组进行标记无法处理这种情况
- 考试时思维较乱,花了很长时间都没做出来~~
- 对map存储不太熟悉(
不能直接存储结构体(pair)作为键值),调试了很长时间~
#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;
}
总结:
- 这种做法是大众的做法,直接枚举所有批次(k)、所有
>175分的面试者,即需要两重循环来操作 - 利用erase()函数删掉选过的面试者
注意:
(1) erase(迭代器) , vector中删除单个元素的用法是:v.erase(v.begin() + i)
(2)其中i是从0开始到第i个,并且删除元素后容器里元素的下标改变所以每次删除都要将i置为0
(3)由于需调用erase() , 所以增加了运行时间,并且\(max(k*n) = p * 5 * 10 ^ 8(p由erase()函数决定)\),而给定的时间是200ms,所以TLE
#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.按照之前的思路两重循环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;
}
总结:
- 思路就是看有没有重复的时间,如果没有,就输出(除了
00:00:00和23:59:59) - 可以将时间看成字符串,输出字符串
s1,字符'-', 和字符串s2 - 利用set存储要输出的答案:
(1)先将时间全部存储进去
(2)再利用hash判断其时间是否重复
(3)如果重复,就删除,否则就不删除
(4)特判00:00:00和23:59:59, 这两个只要出现就删除
(5)如果不出现00:00:00和23:59:59, 就添加 - emmmm,如果按照以上思路做,直接
TLE(21)分,因为每个区间间隔至少 1 秒,max(n) = 86400 / 2 - 这道题卡输入输出,发现有时能过,有时不能过,可以利用:
//解除缓存的模板
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
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 秒
本文共计2736个文字，预计阅读时间需要11分钟。
L1-1+今日我要完成（5+分）项目描述+代码
L1-1 今天我要赢 (5 分) 题目描述 代码#include <iostream>
using namespace std;
int main()
{
cout << "I'm gonna win! Today!" << endl;
cout << "2022-04-23" << endl;
return 0;
}
L1-2 种钻石 (5 分) 题目描述
#include <iostream>
using namespace std;
int main()
{
int n , v;
cin >> n >> v;
cout << n / v;
return 0;
}
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;
}
总结:
- 做这种分类讨论的题,需要人们把所有的情况都考虑清楚,一般分类的情况较多,可以在纸上做一个简单的思维导图,这样思路就清晰,就不会出现考虑不全出现细节的错误(考试出现这种错误,找bug叶难找~~)
- 思维导图:
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;
}
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;
}
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;
}
L1-7 机工士姆斯塔迪奥(20 分) 题目描述 代码 考试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;
}
总结:
- 二维数组空间不宜过大,容易爆栈(比如这道题\(N = 10^5\))
#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;
}
总结
- 这道题只需记录已经释放技能的方格,无需遍历整个方格
- 所以可以利用容器(set等)存储已经释放技能的方格,这样就避免了二维数组开销过大的问题
- 利用pair将行号和列号作为一个整体,便于处理(
经常使用)
L1-8 静静的推荐(20 分) 题目描述
#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;
}
总结:
- 没有考虑两个分数都相同的情况,利用二维数组进行标记无法处理这种情况
- 考试时思维较乱,花了很长时间都没做出来~~
- 对map存储不太熟悉(
不能直接存储结构体(pair)作为键值),调试了很长时间~
#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;
}
总结:
- 这种做法是大众的做法,直接枚举所有批次(k)、所有
>175分的面试者,即需要两重循环来操作 - 利用erase()函数删掉选过的面试者
注意:
(1) erase(迭代器) , vector中删除单个元素的用法是:v.erase(v.begin() + i)
(2)其中i是从0开始到第i个,并且删除元素后容器里元素的下标改变所以每次删除都要将i置为0
(3)由于需调用erase() , 所以增加了运行时间,并且\(max(k*n) = p * 5 * 10 ^ 8(p由erase()函数决定)\),而给定的时间是200ms,所以TLE
#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.按照之前的思路两重循环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;
}
总结:
- 思路就是看有没有重复的时间,如果没有,就输出(除了
00:00:00和23:59:59) - 可以将时间看成字符串,输出字符串
s1,字符'-', 和字符串s2 - 利用set存储要输出的答案:
(1)先将时间全部存储进去
(2)再利用hash判断其时间是否重复
(3)如果重复,就删除,否则就不删除
(4)特判00:00:00和23:59:59, 这两个只要出现就删除
(5)如果不出现00:00:00和23:59:59, 就添加 - emmmm,如果按照以上思路做,直接
TLE(21)分,因为每个区间间隔至少 1 秒,max(n) = 86400 / 2 - 这道题卡输入输出,发现有时能过,有时不能过,可以利用:
//解除缓存的模板
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
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 秒