2023 天梯賽 L1 & L2 補(bǔ)題
L1
L1-089 最好的文檔
輸入輸出題
#include<bits/stdc++.h>
using namespace std;
int main()
{
cout<<"Good code is its own best documentation.";
return 0;
}
L1-090 什么是機(jī)器學(xué)習(xí)
輸入輸出題
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b;
cin>>a>>b;
int c = a + b;
cout<<c-16<<endl;
cout<<c-3<<endl;
cout<<c-1<<endl;
cout<<c;
return 0;
}
L1-091 程序員買包子
k == n 和 k == m 分別輸出，題目怎么說就怎么做
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,k;
string s;
cin>>n>>s>>m>>k;
if(k == n)
cout<<"mei you mai "<<s<<" de";
else if(k == m)
cout<<"kan dao le mai "<<s<<" de";
else
cout<<"wang le zhao mai "<<s<<" de";
return 0;
}
L1-092 進(jìn)化論
判斷一下c 等于a + b還是a*b或者都不是，分別按要求輸出
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
for(int i = 1;i <= n;i++)
{
int a,b,c;
cin>>a>>b>>c;
if(c == a + b) cout<<"Tu Dou";
else if(c == a*b)cout<<"Lv Yan";
else cout<<"zhe du shi sha ya!";
if(i != n) cout<<endl;
}
return 0;
}
L1-093 猜帽子游戲
針對(duì)每一群玩游戲的寶寶，枚舉判斷一下就好了
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int f[N];
int n;
int main()
{
cin>>n;
for(int i = 1;i <= n;i++)
cin>>f[i];
int t;
cin>>t;
for(int j = 1;j <= t;j++)
{
int cnt = 0;
bool flag = true;
for(int i = 1;i <= n;i++)
{
int x;cin>>x;
if(x == 0) continue;
if(x == f[i]) cnt++;
else flag = false;
}
if(flag&&cnt) cout<<"Da Jiang!!!";
else cout<<"Ai Ya";
if(t != j) cout<<endl;
}
return 0;
}
L1-094 剪切粘貼
寫的有點(diǎn)煩，基本就是一步一步模擬，思路在注釋里寫了
#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
string s;
cin>>s>>n;
for(int i = 1;i <= n;i++)
{
int a,b;
string s1,s2;
cin>>a>>b>>s1>>s2;
a -= 1; //保證下標(biāo)從0開始
b -= 1;
//剪切
string t = s.substr(a,b-a+1); //剪切出的字符串
string sbe = s.substr(0,a); //t前面的字符串
string saf = s.substr(b+1,s.size() - b - 1);//t后面的字符串
s = sbe+saf; //剪切后的串
//粘貼
int len1 = s1.size();
int len2 = s2.size();
int st = -1;
for(int j = 0;j + len1 - 1 < s.size();j++)
{
//查找開頭與s1相同的串
string temp = s.substr(j,len1);
if(temp == s1)
{
st = j;//存下標(biāo)
//查看是否以s2結(jié)尾
string af = s.substr(st+len1,len2);
if(af == s2)
{
//粘貼操作
string ss1 = s.substr(0,st+len1);
string ss2 = s.substr(st+len1,s.size());
s = ss1 + t + ss2;
break;
}
else{
st = -1;
}
}
}
//沒有滿足條件的粘貼位置，粘貼在最后
if(st == -1)
s = s + t;
}
cout<<s;
return 0;
}
L1-095 分寢室
枚舉分配方案，代碼中a代表女生寢室的數(shù)量，b為男生寢室的數(shù)量，如果存在寢室人數(shù)差值小于之前的最小值，則更新a，b，最后輸出a和b即可
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int a,b;
int main()
{
int n0,n1,n;
cin>>n0>>n1>>n;
int st = 1e9;
for(int i = 1;i <= n-1;i++)
{
if((n0 % i == 0) && (n1 %(n-i) == 0))
{
int x = n0/i,y = n1/(n-i);
if(x == 1 || y == 1) continue;
if(abs(x-y) < st)
{
st = abs(x-y);
a = i,b = n-i;
}
}
}
if(st != 1e9)
cout<<a<<" "<<b;
else
cout<<"No Solution";
return 0;
}
L1-096 誰管誰叫爹
模擬，要注意
如果 NA正好是 SB的整數(shù)倍，則 A 是爹；如果 NB正好是 SA的整數(shù)倍，則 B 是爹；這里是NA是SB的整數(shù)倍，寫的時(shí)候要小心，容易看錯(cuò)。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll get(ll n)
{
ll res = 0;
while(n)
{
res += n % 10;
n /= 10;
}
return res;
}
int main()
{
int n;
cin>>n;
for(int i = 1;i <= n;i++)
{
ll a,b;
cin>>a>>b;
ll sa = get(a);
ll sb = get(b);
if(!(a % sb) && (b % sa))
cout<<"A";
else if(!(b % sa) && (a % sb))
cout<<"B";
else{
if(a > b) cout<<"A";
else cout<<"B";
}
if(i != n) cout<<"\n";
}
return 0;
}
L2
L2-045 堆寶塔
題目怎么說就怎么做，這里用數(shù)組模擬棧，用起來更舒服一些，個(gè)人覺得比STL好用
#include<bits/stdc++.h>
using namespace std;
const int N = 10100;
int cnt,high;
int va[N],pa;
int vb[N],pb;
int main()
{
int n;
cin>>n;
for(int i = 1;i <= n;i++)
{
int x;
cin>>x;
if(pa == 0) va[pa++] = x;
else
{
if(va[pa-1] > x) va[pa++] = x;
else
{
if(pb == 0 || x > vb[pb-1])
vb[pb++] = x;
else
{
cnt ++;
high = max(high,pa);
pa = 0;
while(pb)
{
if(vb[pb-1] > x)
{
va[pa++] = vb[--pb];
}
else break;
}
va[pa++] = x;
}
}
}
}
if(pa)
{
cnt++;
high = max(high,pa);
}
if(pb)
{
cnt++;
high = max(high,pb);
}
cout<<cnt<<" "<<high;
return 0;
}
L2-046 天梯賽的賽場安排
純暴力寫法用結(jié)構(gòu)體排序 ，然后會(huì)收獲兩個(gè)TLE，只能得18分
這題要用優(yōu)先隊(duì)列去優(yōu)化這個(gè)排序過程，優(yōu)先隊(duì)列底層用堆實(shí)現(xiàn)的，大根堆就是從大到小排序，小根堆是從小到大排序，默認(rèn)是大根堆，所有本題直接用默認(rèn)就好了。
sort排序最快也要O(nlogn)，使用優(yōu)先隊(duì)列將一個(gè)無序序列調(diào)整成有序序列只需要O(n),并且向堆中加入元素，只需要O(logn)，這大大降低這道題的時(shí)間復(fù)雜度。
其次這題可以直接先將各個(gè)大學(xué)可以分配的考場先計(jì)算出來，如果某個(gè)大學(xué)參賽人數(shù)剛好是c的整數(shù)倍，那么他已經(jīng)分配好了不用加入優(yōu)先隊(duì)列中。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
const int INF = 0x3f3f3f3f,mod = 1000000007;
using ll = long long;
int T;
const int N = 5010;
struct Node{
string name;
int num;//未安排人數(shù)
//運(yùn)算符重載
bool operator < (const Node &s) const
{
return num < s.num;
}
}f[N];
int n,c;
int cnt;
map<string,int>mp;
string order[N];
inline void run()
{
cin>>n>>c;
priority_queue<Node>q;//默認(rèn)大根堆
for(int i = 1;i <= n;i++)
{
string name;int num;
cin>>name>>num;
order[i] = name;
int cls = num / c;
cnt += cls;
num = num - cls * c;
if(num != 0)
q.push({name,num});
mp[name] = cls;
}
vector<int>cls;
while (q.size())
{
auto t = q.top();
q.pop();
string name = t.name;
int num = t.num;
bool flag = false;
for(int j = 0;j < cls.size();j++)
{
if((c - cls[j]) >= num)
{
cls[j] += num;
mp[name] += 1;
flag = true;
break;
}
}
if(!flag)
{
cnt++;
cls.push_back(num);
mp[name] += 1;
}
}
for(int i = 1;i <= n;i++)
cout<<order[i]<<" "<<mp[order[i]]<<endl;
cout<<cnt;
}
int main()
{
IOS;
// cin>>T;
// while (T--)
// run();
run();
return 0;
}
L2-047 錦標(biāo)賽
先了解一下敗者樹，這是一個(gè)數(shù)據(jù)結(jié)構(gòu)中比較冷門的考點(diǎn)，詳情可以看王道的講解
下圖是龍珠里武林大賽比武的敗者樹
敗者樹—可以視為一棵完全二叉樹（多一個(gè)頭頭）。k個(gè)葉結(jié)點(diǎn)分別是當(dāng)前參加比較的元素，非葉子結(jié)點(diǎn)用來記憶左右子樹中的“失敗者”，而讓勝利者往上繼續(xù)進(jìn)行比較，一直到根結(jié)點(diǎn)。
這題就是給出敗者樹，然后需要還原原序列，雖然我知道要這么做，但是還是沒寫出來/(ㄒoㄒ)/~~，下面的代碼是另一位博主的，原代碼鏈接點(diǎn)這。
大體思路如下：
每次我們都可以完善數(shù)組的一半，然后剩下一半
完善的過程：
對(duì)于第一層，是第一次比賽的結(jié)果，相鄰兩個(gè)進(jìn)行比較的結(jié)果，因此，我們可以把第一層第i個(gè)數(shù)的位置放在原始數(shù)組i*2-1中
對(duì)于接下來的幾層，它能加入原始數(shù)組的條件就是 它的數(shù)值不小于前一層兩個(gè)對(duì)應(yīng)位置分別的所組成子樹的最大值 否則它將無法加入到原始數(shù)組中去
為了實(shí)現(xiàn)構(gòu)造還要建立一個(gè)數(shù)組，來記錄該位置的一下位置在哪里
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
const int INF = 0x3f3f3f3f,mod = 1000000007;
using ll = long long;
const int N = 20,M = (1 << 19);
int T;
int k;
int ans[M];//結(jié)果數(shù)組
int a[N][M],id[N][M];//a數(shù)組存儲(chǔ)輸入的數(shù)據(jù)，id存儲(chǔ)還能放數(shù)的空余位置
inline void run()
{
cin>>k;
int flag = 1,max1;
for(int i = 1;i <= k;i++){
for(int j = 1;j <= (1<<(k-i));j++){
cin>>a[i][j];
if(i == 1) ans[j*2-1]=a[i][j],id[i][j]=j*2; //loser放在左兒子，winner放在右兒子
else{
max1 = max(a[i][j],max(a[i-1][j*2],a[i-1][j*2-1]));//記錄所構(gòu)成子樹的最大數(shù)值
if(a[i][j] < a[i-1][j*2] && a[i][j] < a[i-1][j*2-1]){
flag = 0;
break;
}else if(a[i][j] >= a[i-1][j*2]){
ans[id[i-1][j*2]] = a[i][j];
id[i][j] = id[i-1][j*2-1];
}else{
ans[id[i-1][j*2-1]] = a[i][j];
id[i][j] = id[i-1][j*2];
}
a[i][j] = max1;
}
}
}
cin >> max1;
if(a[k][1] <= max1) ans[id[k][1]] = max1;
else flag = 0;
if(flag == 0) cout<<"No Solution\n";
else{
for(int i = 1;i <= (1<<k);i++)
cout<<ans[i]<<" \n"[i==(1<<k)];
}
}
int main()
{
IOS;
// cin>>T;
// while (T--)
// run();
run();
return 0;
}
L2-048 尋寶圖
這里需要用vector來存，n*m <= 1e5，二維數(shù)組只能開到1e4。
本來想著數(shù)據(jù)可能很弱，打算直接用二維數(shù)組卡過去(/≧▽≦)/，結(jié)果被卡了一個(gè)點(diǎn)（24分）/(ㄒoㄒ)/~~。
回到這道題，就是一個(gè)連通塊問題，寫個(gè)dfs或者bfs就行了，所以這題關(guān)鍵是要想到用vector。文章來源：http://www.zghlxwxcb.cn/news/detail-436268.html
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int>f[N],st[N];
int cnt,sum;
bool flag;
int n,m;
int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
void dfs(int x,int y)
{
st[x][y] = true;
if(f[x][y] > 1) flag = true;
for(int i = 0;i < 4;i++)
{
int xx = x + dx[i],yy = y + dy[i];
if(xx >= 1 && xx <= n&&yy >= 1&&yy <= m&&f[xx][yy]&&!st[xx][yy])
{
if(f[xx][yy] > 1) flag = true;
dfs(xx,yy);
}
}
}
int main()
{
cin>>n>>m;
for(int i = 1;i <= n;i++)
{
f[i].push_back(0);
st[i].push_back(0);
for(int j = 1;j <= m;j++)
{
char c;
cin>>c;
f[i].push_back(c-'0');
st[i].push_back(0);
}
}
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
{
if(f[i][j] && !st[i][j])
{
flag = false;
sum++;
dfs(i,j);
if(flag) cnt++;
}
}
cout<<sum<<" "<<cnt;
return 0;
}
END?文章來源地址http://www.zghlxwxcb.cn/news/detail-436268.html
到了這里，關(guān)于2023 PTA天梯賽補(bǔ)題（L1 & L2）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
