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
————————————————————————————
