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\))
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分的面試者,即需要兩重回圈來操作 - 利用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.按照之前的思路兩重回圈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 秒
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/465047.html
標籤：其他