2023团体程序设计天梯赛赛后总结

发布于 2023-04-25  4631 次阅读


暂时只总结本人赛场AC的题,L1满分,L2其实只AC了一道,但还有一道DFS的是细节问题,差一分,就当我ac了吧QAQ

Ps:我是菜狗,别喷QAQ

L1 -89最好的文档

题目详情 - L1-089 最好的文档 (pintia.cn)

天梯赛嘛,第一道题都是有手就行的,建议其实建议用php,只不过php在后面不太好翻,python直接print就可以,php直接CV大法即可

L1 -90什么是机器学习

题目详情 - L1-090 什么是机器学习 (pintia.cn)

这种题真心没什么好说的

#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
cout<<a+b-16<<endl;
cout<<a+b-3<<endl;
cout<<a+b-1<<endl;
cout<<a+b;
}

L1 -91程序员买包子

题目详情 - L1-091 程序员买包子 (pintia.cn)

经典程序员笑话,天梯赛L1模拟居多,所以怎么说怎么做呗如果K是m说明看到卖x的了,如果k是n说明没看到,其他输出wang le zhao mai X de

#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
string x;
int m,k;
cin>>n>>x>>m>>k;
if(k==n){
cout<<"mei you mai "<<x<<" de";
}else if(k==m){
cout<<"kan dao le mai "<<x<<" de";
}else{
cout<<"wang le zhao mai "<<x<<" de";
}
}

L1 -92进化论

题目详情 - L1-092 进化论 (pintia.cn)

吕岩和土豆的漫才喜剧还是值得一看的(一年一度喜剧大赛1&2还是有不少不错的作品的)

还是模拟没什么可说的这种题比的就是读题速度和敲代码手速(也和语言有关)

#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
   cin>>n;
   while(n--){
       int a,b,c;
       cin>>a>>b>>c;
       if(a*b==c){
           cout<<"Lv Yan"<<endl;
      }else if(a+b==c){
           cout<<"Tu Dou"<<endl;
      }else{
           cout<<"zhe du shi sha ya!"<<endl;
      }
  }
}

L1 -93猜帽子游戏

题目详情 - L1-093 猜帽子游戏 (pintia.cn)

感觉也没什么说的就是模拟,这种成功与否的问题,因为成功的条件往往特别苛刻,所以先找出不成功的条件,当满足不成功的条件时,无论后面成不成功,结果都是不成功的

#include<bits/stdc++.h>
using namespace std;
int main(){
   int n;
   cin>>n;
   int s[n];
   for(int i=0;i<n;i++){
       cin>>s[i];
  }
   int k;
   cin>>k;
   while(k--){
       int flag=1;//默认都猜对了
       int count=0;//记录没猜的人数
       for(int i=0;i<n;i++){
           int temp;
           cin>>temp;
           if(temp!=s[i]&&temp!=0){
               flag=0;//有人猜错了,后续结果就不重要了,一定输!
          }else if(temp==0){
               count++;
          }  
      }
       if(count==n){
           cout<<"Ai Ya"<<endl;//都没猜
      }else if(flag){
           cout<<"Da Jiang!!!"<<endl;//猜对了
      }else{
           cout<<"Ai Ya"<<endl;//猜错了
      }
  }
}

L1 -94剪切粘贴

题目详情 - L1-094 剪切粘贴 (pintia.cn)

天梯赛每年必有的字符串题,今年的还好,对于小白(比如我)来说可能是在找粘贴的位置时会有点麻烦,最开始想的就是找粘贴位置的前半部分和后半部分,后来发现不对,因为可能有满足前半部分不满足后半部分的,也会有满足后半部分不满足前半部分的,所以分开找就不一定确定找的是对的(可能需要继续向下判断,这部分就容易出错),所以我想的是把前半部分和后半部分作为一个整体去找,如果找到了,能百分百确定就是找到了插入的位置,而不是继续向下判断看另一部分是否满足,找到了就把找到的位置加上前半部分字符串的长度再减一(因为是下标)得到的位置就是插入的位置,如果没找到直接接到后面即可

#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
int t;
cin>>t;
while(t--){
int a,b;
cin>>a>>b;
string c,d;
cin>>c>>d;
string jq=s.substr(a-1,b-a+1);//获取剪切的字符串
s=s.substr(0,a-1)+s.substr(b,s.size()-b);//把被剪切的子串从原字符串中删除(创建个新字符串等于a前面的加上b后面的)
string zhao=c+d;//将粘贴位置的前后字符串拼接
int weizhi=s.find(zhao);
int flag=weizhi;
weizhi=weizhi+c.size()-1;
if(flag==-1){//没找到
s=s+jq;
}
else{//找到了
s=s.substr(0,weizhi+1)+jq+s.substr(weizhi+1,s.size()-weizhi-1);
}
jq="";//剪贴板置空
}
cout<<s;
}

L1 -95分寝室

题目详情 - L1-095 分寝室 (pintia.cn)

我个人感觉,天梯赛L1的难点(当然对于大佬们L1是没有难点的QAQ)从来不在于题目所需要的算法,而是在于需要理解题目在说啥(Ps:好像所有题都得理解...说了但好像又没说。相对,相对来说,咳咳..QAQ)

  • 男女生不能混住:男生分男生的,女生分女生的,互不影响
  • 不允许单人住一间寝室:男/女生人数不能等于房间数
  • 对每种性别的学生,每间寝室入住的人数都必须相同:男/女生除以各自性别房间数必须整除
  • 在有多种分配方案满足前面三项要求的情况下,要求两种性别每间寝室入住的人数差最小:多种满足情况,每间寝室两性别人数差最小
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b,n;
cin>>a>>b>>n;
int cha=1000000;
int ra,rb;
int flag=0;
for(int i=1;i<n;i++){
if(a%i==0&&b%(n-i)==0&&a!=i&&b!=n-i){
if(abs(a/i-b/(n-i))<cha){
cha=abs(a/i-b/(n-i));
ra=i;
rb=n-i;
flag=1;
}
}
}
if(flag){
cout<<ra<<" "<<rb;
}else{
cout<<"No Solution";
}
}

L1 -96谁管谁叫爹

题目详情 - L1-096 谁管谁叫爹 (pintia.cn)

模拟,没什么说的,注意读题别忽略某些条件就行(不是很理解,这题是20分的..感觉和15分的差不多,这题和字符串换一下正好)

#include<bits/stdc++.h>
using namespace std;
int sum(int a){
   int r=0;
   while(a){
       r=r+a%10;
       a=a/10;
  }
   return r;
}
int main(){
   int n;
   cin>>n;
   while(n--){
       int na,nb;
       cin>>na>>nb;
       int sa=sum(na);
       int sb=sum(nb);
       if(na%sb==0&&nb%sa!=0){
           cout<<"A"<<endl;
      }else if(nb%sa==0&&na%sb!=0){
           cout<<"B"<<endl;
      }else{
           if(na>nb){
               cout<<"A"<<endl;
          }else{
               cout<<"B"<<endl;
          }
      }
  }
}

L2 -45堆宝塔

题目详情 - L2-045 堆宝塔 (pintia.cn)

还是模拟,只要你能数据结构入门(比如我)在读题时应该就能想到用什么数据结构去做这道题

堆宝塔,每次需要判断的都是最顶上的"圈圈",也就是最后进来的,所以我就用栈来做的这道题

手写两个栈,sa,sb,topa,topb,然后按照题目写if、else,用三个变量resulta、ra、maxa分别记录,当前塔的高度,塔的数量,目前为止最高塔的高度,经典数据结构大模拟!

#include<bits/stdc++.h>
using namespace std;
int resulta=0;
int maxa=0;
int ra=0;
int sa[1005];
int sb[1006];
int topa=-1;
int topb=-1;
int main(){
int n;
cin>>n;
int s[n];
for(int i=0;i<n;i++){
cin>>s[i];
}
if(n==1){
cout<<"1 1";
return 0;
}
for(int i=0;i<n;i++){
if(topa==-1||s[i]<sa[topa]){//如果a为空,或者c小于a顶,可以放进a
sa[++topa]=s[i];
resulta++;
}else if(s[i]>sb[topb]||topb==-1){//不满足放进a的条件,如果c大于b,或者b为空都可以放b中
sb[++topb]=s[i];
}else{//需要把a中都弹出,把b里大于c的都弹到a里,并继续判断
topa=-1;//清空a栈
maxa=max(resulta,maxa);//记录最大高度
resulta=0;//高度记录清零
ra++;//宝塔数加1
while(sb[topb]>s[i]){//如果b顶大于c,循环把b放到a
sa[++topa]=sb[topb--];
resulta++;//高度++
}
sa[++topa]=s[i];//把c放到a
resulta++; //高度++
}
}
if(topa!=-1) ra++;//如果a不为空,算一个塔
if(topb!=-1) ra++;//如果b不为空,算一个塔
cout<<ra<<" "<<maxa;
}

L2 -46没拿满分不分析了...

题目详情 - L2-046 天梯赛的赛场安排 (pintia.cn)

十八分代码贴出来>﹏<

#include<bits/stdc++.h>
using namespace std;
map<string,int> mp;
struct dw{
string s;
int renshu;
int yushu;
};
bool cmp(dw a,dw b){
return a.yushu<b.yushu;
}
int main(){
int n,c;
cin>>n>>c;
dw s[n];
string z[n];
int sc=0;
for(int i=0;i<n;i++){
cin>>s[i].s>>s[i].renshu;
z[i]=s[i].s;
s[i].yushu=s[i].renshu%c;
if(s[i].yushu){
sc=1;
}
}
sort(s,s+n,cmp);

int jilu=c;
for(int i=0;i<n;i++){
mp[s[i].s]=s[i].renshu/c;
if(s[i].yushu!=0){
mp[s[i].s]++;
}
sc=sc+s[i].renshu/c;
if(s[i].yushu<=jilu){
jilu=jilu-s[i].yushu;
}else{
sc++;
jilu=c-(s[i].yushu-jilu);
}

}
for(int i=0;i<n;i++){
cout<<z[i]<<" "<<mp[z[i]]<<endl;
}
cout<<sc;
}

L2 -48寻宝图

一眼图遍历,DFS比较好写,所以就用dfs写了,找过的点就标记为0,因为以当前点作为起点所经过的所有位置都属于一个岛,所以不需要重复记录,然后用一个变量来记录以当前点作为起点是否找到宝物,如果是,说明该岛屿藏有宝物,就加一(注意,无论你此次路径找到多少个宝物,都只加一),所以加1不能在dfs中进行,要是做过dfs的题就会觉得很简单,天梯赛基本上必有字符串的题和图的题。

这题考场上过了24分,原因在于习惯用二维数组了,直接开爆了,然后考场上不知道为啥就没想到用vector,后来也是时间不太够急着往下看题了,L2我先做的就是这道题╥﹏╥...

vector满分代码:

#include<bits/stdc++.h>
using namespace std;
int baobei=0;
int n,m;
bool flag;
vector<vector<char>> s;
void dfs(int i,int j){
if(i>=n||i<0||j>=m||j<0){
return ;
}
if(s[i][j]=='0'){
return ;
}
if(s[i][j]>='2'&&s[i][j]<='9'){
flag=true;
}
s[i][j]='0';
dfs(i,j+1);
dfs(i,j-1);
dfs(i+1,j);
dfs(i-1,j);
}
int main(){
int dy=0;
cin>>n>>m;
for(int i=0;i<n;i++){
string temp;
cin>>temp;
vector<char> t;
for(int j=0;j<m;j++){
t.push_back(temp[j]);
}
s.push_back(t);
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(s[i][j]!='0') dy++;
dfs(i,j);
if(flag) baobei++;
flag=false;
}
}
cout<<dy<<" "<<baobei;
return 0;
}

第一次打天梯,个人分167,差点能拿到国三,有点可惜QAQ,团队省三对于我们这种菜鸟小白感觉还阔以了。(๑•̀ㅂ•́)و✧


星星温柔泛滥,人间至善