2022年天梯賽題目解析

• L1-1 今天我要贏 (5 分)[輸出水題]
• • 題目描述
  • • 代碼
• L1-2 種鉆石 (5 分)[四則運算]
• • 題目描述
  • • 代碼
• L1-3 誰能進圖書館 (10 分)[分類討論,判斷題]
• • 題目描述
  • • 代碼
    • 總結:
• L1-4 拯救外星人 (10 分)[數學]
• • 題目描述
  • • 代碼
• L1-5 試試手氣 (15 分)[數組]
• • 題目描述
  • • 代碼
• L1-6 斯德哥爾摩火車上的題 (15 分)[字符串]
• • 題目描述
  • • 代碼
• L1-7 機工士姆斯塔迪奧(20 分)[set用法]
• • 題目描述
  • • 代碼
    • • 考試19分代碼
      • • 總結:
      • AC代碼
      • • 總結
• L1-8 靜靜的推薦(20 分)[模擬,貪心]
• • 題目描述
  • • 代碼
    • • 1.考試1分代碼
      • • 總結:
      • 2. 14分代碼
      • • 總結:
      • 3.AC代碼
      • • 總結:
• L2-2 老板的作息表(25分)[排序]
• • • 代碼
    • • 總結:

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) {//一開始這里沒考慮清楚,最后一分鐘發(fā)現錯誤~printf("1: huan ying ru guan\n");} else if(x2 >= j && x1 < j && x2 < p) {printf("2: huan ying ru guan\n");}return 0; }

總結:

做這種分類討論的題,需要人們把所有的情況都考慮清楚,一般分類的情況較多,可以在紙上做一個簡單的思維導圖,這樣思路就清晰,就不會出現考慮不全出現細節(jié)的錯誤(考試出現這種錯誤,找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 分)[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; }

總結:

二維數組空間不宜過大,容易爆棧(比如這道題$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; }

總結

這道題只需記錄已經釋放技能的方格,無需遍歷整個方格

所以可以利用容器(set等)存儲已經釋放技能的方格,這樣就避免了二維數組開銷過大的問題

利用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; }

總結:

沒有考慮兩個分數都相同的情況,利用二維數組進行標記無法處理這種情況

考試時思維較亂,花了很長時間都沒做出來~~

對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; }

總結:

這種做法是大眾的做法,直接枚舉所有批次(k)、所有>175分的面試者,即需要兩重循環(huán)來操作

利用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

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.按照之前的思路兩重循環(huán)TLE,所以得往一重循環(huán)的方向想
2. 題目的意思是(非常重要):

• 凡是天梯賽分數>=175分都有機會被錄取
• 凡是PTA分數>=s(該企業(yè)的面試分數線) , 直接被錄取(天梯賽分數>=175)
• 同一個批次不能錄取天梯分數一樣的面試者(除了TA分數>=s(該企業(yè)的面試分數線)的面試者) , 即只能錄取一個
• 同一批次的面試者不管PTA考多少分(PTA分數>=s(該企業(yè)的面試分數線) 除外)

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);elsest.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)分,因為每個區(qū)間間隔至少 1 秒,max(n) = 86400 / 2

這道題卡輸入輸出,發(fā)現有時能過,有時不能過,可以利用:

//解除緩存的模板 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 秒

---

總結

以上是生活随笔為你收集整理的2022年天梯赛题目解析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。