2022天梯赛-全国总决赛复盘赛
今天下午进行了为期三个小时的复盘赛,说一下感受
相比于比赛时的紧张这次做起来除了做后几个题紧张,其余题倒是没有那种大脑空白的感觉,但是后面有几个题还是相当棘手,代码量和思维跳跃都比较大,所以l2凭目前能力只做了两个,l1最后一个耗费时间也会多了,也有最后一个小时主攻l2的张总的作息表了,反正l2比l1难度上涨了是肯定的,另外l2没做够l3就没做
当然,在家做和比赛当时做肯定是不一个心态了,这一点还是要承认的
当然在此之外还发现了一些问题,就是关于自己在某些知识上还存在空缺和遗忘,比如处理染色和dfs相结合的问题,还有就是对于最短路径复杂化的一个问题,还有就是关于STL的一些应用
下面是关于一些题目的解析:
前两道题简单水题
第三题:
if-else来回嵌套系列,麻烦且恶心,但思维上不算是难题,难在一步步拆解和嵌套上
1 #include<bits/stdc++.h>//天梯赛3 2 using namespace std; 3 int y1, y2, a, b; 4 int main() 5 { 6 cin >> y1 >> y2 >> a >> b; 7 if (a >b)//分两种情况,分别输出两者的序号 8 { 9 if (b >= y1)//小者年龄大于可进入年龄,两者都可 10 { 11 cout << a << "-Y " << b << "-Y" << endl; 12 cout << "huan ying ru guan" << endl; 13 } 14 else if (b < y1 && a >= y2)//小者年龄小于儿童进入年龄但有大人陪同 15 { 16 cout << a << "-Y " << b << "-Y" << endl; 17 cout << "qing 1 zhao gu hao 2" << endl; 18 } 19 else if (a <y1)//都不行 20 { 21 cout << a << "-N " << b << "-N" << endl; 22 cout << "zhang da zai lai ba" << endl; 23 } 24 else if (b < y1 && a < y2)//只有一个行 25 { 26 cout << a << "-Y " << b << "-N" << endl; 27 cout << "1: huan ying ru guan" << endl; 28 } 29 } 30 else//同上 31 { 32 if (a >= y1) 33 { 34 cout << a << "-Y " << b << "-Y" << endl; 35 cout << "huan ying ru guan" << endl; 36 } 37 else if (a < y1 && b >= y2) 38 { 39 cout << a << "-Y " << b << "-Y" << endl; 40 cout << "qing 2 zhao gu hao 1" << endl; 41 } 42 else if (b < y1) 43 { 44 cout << a << "-N " << b << "-N" << endl; 45 cout << "zhang da zai lai ba" << endl; 46 } 47 else if (a < y1 && b < y2) 48 { 49 cout << a << "-N " << b << "-Y" << endl; 50 cout << "2: huan ying ru guan" << endl; 51 } 52 } 53 return 0; 54 }
4水
5:还是说一下吧
题目最后得出的结果必定是最大的(抛去最大值和与原本元素重复的),那么这个采取的策略可以是先预处理让其变到当前的最大,然后在进行后面轮数的处理
对于后面的处理如果和原本元素相同就递减2,否则为1;
1 #include<bits/stdc++.h>天梯赛5 2 using namespace std; 3 int a[10]; 4 int b[10];//预存变量,保证原来元素不受影响 5 int n; 6 int main() 7 { 8 std::ios::sync_with_stdio(false); 9 cin.tie(0); 10 cout.tie(0); 11 for(register int i=1;i<=6;i++)//预处理 12 { 13 cin>>a[i]; 14 b[i]=a[i]; 15 } 16 cin>>n; 17 for(register int i=1;i<=6;i++) 18 { 19 if(a[i]==6) //重复递减2 20 a[i]--; 21 else //1 22 a[i]=6; 23 } 24 25 for(register int i=1;i<=n-1;i++) 26 { 27 for(register int j=1;j<=6;j++) 28 { 29 a[j]--; 30 if(a[j]==b[j]) 31 a[j]--; 32 } 33 } 34 for(register int i=1;i<6;i++) { 35 cout<<a[i]<<" "; 36 } 37 cout<<a[6]<<endl; 38 return 0; 39 }
7没啥卖点;
6
有一个有意思的地方是字符串,其余照着题面来
#include<bits/stdc++.h>//天梯赛6 using namespace std; int main(){ string a,b,s1="",s2=""; int i,j,k,l,m,n; cin>>a>>b; for(i=1;i<a.length();i++) { if((a[i]-'0')%2==(a[i-1]-'0')%2){ s1 += max(a[i], a[i-1]); } } for(i=1;i<b.length();i++) { if((b[i]-'0')%2==(b[i-1]-'0')%2){ s2 += max(b[i], b[i-1]); } } if(a.length()==1) s1+=a[i]; if(b.length()==1) s2+=b[i]; if(s1==s2) cout<<s1; else cout<<s1<<endl<<s2; }
8.读题费劲,读懂题意处理起来就好做了,其实还是贵在阅读理解,得多做做长题面的题来学习一下了;
1 #include<iostream>//天梯赛8 2 using namespace std; 3 int a[1000];//每个分段的达标人数 4 int n,k,s; 5 int sum; 6 int main() 7 { 8 cin>>n>>k>>s; 9 for(register int i=1;i<=n;i++) 10 { 11 int x,y; 12 cin>>x>>y; 13 if(x>=175) 14 { 15 if(y>=s) sum++; //特殊的不受批次影响 16 else if(a[x]<k) 17 { 18 a[x]++; 19 sum++; //普通的受批次影响的 20 } 21 } 22 } 23 cout<<sum; 24 return 0; 25 }
下面是L2题目:
L2相比L1而言题目难度无疑是上升一个层面的,数据结构的应用很多也很灵活,其中不乏对于树图的处理和栈,队列的应用,当然,也有可能存在链表
难度不低,谨慎食用;
L2-1
暂时不太会,但基本思路是确定用栈与队列双模拟了,明天补题
L2-2张总的作息表
转化时间这一步是必要的,然后进行结束时间排序,因为只有结束了才能开始下一段区间,参考部分背包思想
以上是预处理
下面是正式处理
首先是处理两个情况,即两个临界点
凌晨从开始时间到第一个结束的时间,这是第一个时间段
在处理其余的时间,就是从一段结束的时间到下一段开始的时间
然后是另外一个临界点23点近24点;
处理方式同0点
1 #include<bits/stdc++.h>//天梯赛l2张朝阳的作息表 2 using namespace std; 3 const int num = 1e5; 4 struct times 5 { 6 int begin1; 7 int end1; 8 }t[num]; 9 10 bool cmp1(times x , times y){ 11 return x.end1 < y.end1; 12 } 13 int main(){ 14 std::ios::sync_with_stdio(false); 15 cin.tie(0); 16 cout.tie(0); 17 int n; 18 cin >> n; 19 for(int i = 0 ; i <n ; i ++) 20 { 21 int h1=0,m1=0,s1=0,h2=0,m2=0,s2=0; 22 scanf("%d:%d:%d - %d:%d:%d",&h1,&m1,&s1,&h2,&m2,&s2); 23 t[i].begin1 = h1*3600 + m1 * 60 + s1; 24 t[i].end1 = h2*3600 + m2 * 60 + s2; 25 } 26 27 sort(t,t+n,cmp1); 28 29 if(t[0].begin1 != 0){ 30 int h3=0; 31 int m3=0; 32 int s3=0; 33 int h4=0; 34 int m4=0; 35 int s4=0; 36 h4 = t[0].begin1 / 3600; 37 m4 = t[0].begin1 / 60 % 60; 38 s4 = t[0].begin1 % 60; 39 printf("00:00:00 - %02d:%02d:%02d\n",h4,m4,s4); 40 } 41 42 for(int i = 0 ; i < n - 1 ; i ++){ 43 if(t[i].end1 != t[i+1].begin1){ 44 int h3,m3,s3,h4,m4,s4; 45 h3 = t[i].end1 / 3600; 46 m3 = t[i].end1 / 60 % 60; 47 s3 = t[i].end1 % 60; 48 h4 = t[i+1].begin1 / 3600; 49 m4 = t[i+1].begin1 / 60 % 60; 50 s4 = t[i+1].begin1 % 60; 51 printf("%02d:%02d:%02d - %02d:%02d:%02d\n",h3,m3,s3,h4,m4,s4); 52 } 53 } 54 55 if(t[n-1].end1 != 23*3600 + 59 * 60 + 59){ 56 int h3,m3,s3,h4,m4,s4; 57 h3 = t[n-1].end1 / 3600; 58 m3 = t[n-1].end1 / 60 % 60; 59 s3 = t[n-1].end1 % 60; 60 printf("%02d:%02d:%02d - 23:59:59",h3,m3,s3); 61 } 62 return 0; 63 }
L2-3没做
L2-4是复杂化佛洛依德算法,明天更
L3一个没做
分割线 2022/6/22/21:10
————————————————————————————