序

比賽時長： 四個小時
比賽規(guī)則：
藍橋杯比賽跟天梯賽、ACM還不太一樣，比賽中提交的答案并沒有反饋機制，也就是說你提交了答案以后，自己并不知道是對是錯，就像考試一樣，只有交了卷，成績下來以后才能知道自己的獎項。

滿分150
T1-T5答案提交共45分，分值分別是5，5，10，10，15
T6-T10為程序提交共105分，分值分別是15，20，20，25，25

T6-T10開放補題
提交鏈接：https://lx.lanqiao.cn/problemset.page
搜索【第十二屆】【省賽】【B組】

一般來說，藍橋杯=暴力杯
前六題都做對共60分，后面四題嫖一半45分，105以上感覺一般能合格。
T1，T2很裸的暴力
T3，T4需要set優(yōu)化或者思考一下枚舉方案的暴力
T5，T6很裸的暴力，但是要能寫一點點基本的代碼，題目細節(jié)看仔細
T7，T8背包dp與找規(guī)律遞推。很裸的暴力可以打一半。
T9，T10一般是思維題或dp。稍微思考一下的很裸的暴力可以打一半。

T1-T5

T1 空間

• 小藍準備用256MB 的內(nèi)存空間開一個數(shù)組，數(shù)組的每個元素都是32 位
  二進制整數(shù)，如果不考慮程序占用的空間和維護內(nèi)存需要的輔助空間，請問
  256MB 的空間可以存儲多少個32 位二進制整數(shù)？
• 已知1MB=1024KB，1KB=1024B，1B=8b
• 所以答案 67108864

T2 卡片

• 小藍有很多數(shù)字卡片，每張卡片上都是數(shù)字 0 到 9。 小藍準備用這些卡片來拼一些數(shù)，他想從 1 開始拼出正整數(shù)，每拼一個，就保存起來，卡片就不能用來拼其它數(shù)了。 小藍想知道自己能從 1 拼到多少。
  例如，當小藍有 30 張卡片，其中 0 到 9 各 3張，則小藍可以拼出 1 到 10， 但是拼 11 時卡片 1 已經(jīng)只有一張了，不夠拼出 11。
  現(xiàn)在小藍手里有 0 到 9 的卡片各2021 張，共 20210 張，請問小藍可以從 1 拼到多少？ 提示：建議使用計算機編程解決問題。
• 創(chuàng)個數(shù)組表示卡片張數(shù)，枚舉一下就行
• 3181

T3 直線

• 在平面直角坐標系中，兩點可以確定一條直線。如果有多點在一條直線上，那么這些點中任意兩點確定的直線是同一條。
  給定平面上 2 × 3 個整點> {(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z}，即橫坐標是 0 到 1 (包含 0 和 1) 之間的整數(shù)、縱坐標是 0 到 2 (包含 0 和 2) 之間的整數(shù)的點。這些點一共確定了 11 條不同的直線。
  給定平面上 20 × 21個整點 {(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z}，即橫坐標是 0 到 19 (包含 0 和> 19) 之間的整數(shù)、縱坐標是 0 到 20 (包含 0 和 20) 之間的整數(shù)的點。請問這些點一共確定了多少條不同的直線。
• 四層for循環(huán)枚舉(x1,y1)(x2,y2)，根據(jù)y=kx+b和k=(y1-y2)/(x1-x2)分別得出k和b的值，注意斜率不存在的情況。依次遍歷每個點，用set儲存k、b的值用于查重，如果k、b不在map中，則結果加一。注意所有變量都要設為double值，不然計算就會出錯。
• 47753

T4 貨物擺放

• 小藍有一個超大的倉庫，可以擺放很多貨物。 現(xiàn)在，小藍有 n 箱貨物要擺放在倉庫，每箱貨物都是規(guī)則的正方體。小藍規(guī)定了長、寬、高三個互相垂直的方向，每箱貨物的邊都必須嚴格平行于長、寬、高。
  小藍希望所有的貨物最終擺成一個大的立方體。即在長、寬、高的方向上 分別堆 L、W、H 的貨物，滿足 n = L × W × H。給定n，請問有多少種堆放貨物的方案滿足要求。 例如，當 n = 4 時，有以下 6 種方案：1×1×4、1×2×2、1×4×1、2×1×2、 2× 2 × 1、4 × 1 × 1。
  請問，當 n = 2021041820210418 （注意有 16 位數(shù)字）時，總共有多少種方案？

• 求n=三個數(shù)相乘有多少種方案，16位不超過ll，可以暴力。
  考慮優(yōu)化，長寬高和面積顯然是n的因數(shù)。對于該性質，那么枚舉長寬高的時候只需要枚舉n的因數(shù)即可（雖然枚舉n的所有因數(shù)也會超時），但是可以set一下，n/a也是n的因數(shù)，那么復雜度就降低了。
  再遍歷這個集合**（作為一條邊a），可以用n/a計算出另外兩條邊相乘的面積S，另外兩條邊顯然也在初始集合之內(nèi)，且是S的因數(shù)，所以再枚舉S的因數(shù)（即第二條邊）**，就可以計算出第三條邊，統(tǒng)計答案，就不會超時了。

• 2430

  #include<bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  int main(){
      LL n = 2021041820210418;
      set<LL>se;
      for(LL a = 1; a <= n; a++){//枚舉n的因數(shù)
          if(n%a==0){
              if(se.find(a)!=se.end())break; //存在重復值就結束
              se.insert(a);  se.insert(n/a); //n/a優(yōu)化
          }
      }
      LL res = 0;
      for(LL a : se){//枚舉所有可行的第一條邊
          LL s = n/a;
          set<LL>se2;
          for(LL b = 1; b <= s; b++){//枚舉S的因數(shù)(枚舉第二條邊)
              if(s%b==0){
                  //可以計算出第三條邊h=s/b
                  if(se2.find(b)!=se2.end())break;
                  se2.insert(b);  se2.insert(s/b);
                  if(b==s/b)res++;    //b和h相同
                  else res+=2;        //212,221是不同方案
              }
          }
      }
      cout<<res<<"\n";
      return 0;
  }
  

T5 路徑

• 小藍學習了最短路徑之后特別高興，他定義了一個特別的圖，希望找到圖 中的最短路徑。
  小藍的圖由 2021 個結點組成，依次編號 1 至2021。 對于兩個不同的結點 a, b，如果 a 和 b 的差的絕對值大于 21，則兩個結點 之間沒有邊相連；如果 a 和 b的差的絕對值小于等于 21，則兩個點之間有一條長度為 a 和 b 的最小公倍數(shù)的無向邊相連。
  例如：結點 1 和結點 23之間沒有邊相連；結點 3 和結點 24 之間有一條無 向邊，長度為 24；結點 15 和結點 25 之間有一條無向邊，長度為 75。
  請計算，結點 1 和結點 2021 之間的最短路徑長度是多少。 提示：建議使用計算機編程解決問題。

• 暴力建圖跑Dijkstra即可，板子題毫無思維含量，仔細點別寫錯了就行

• 10266837

  #include<bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  int gcd(int a, int b){
      return !b ? a: gcd(b,a%b);
  }
  const int maxn = 2050;
  int e[maxn][maxn];
  int dist[maxn], vis[maxn];
  int main(){
      //建圖
      memset(e,0x3f,sizeof(e));
      for(int i = 1; i <= 2021; i++)e[i][i]= 0;
      int n = 2021;
      for(int i = 1; i <= 2021; i++){
          for(int j = 1; j <= 2021; j++){
              if(abs(i-j)<=21){
                  e[i][j] = e[j][i] = i/gcd(i,j)*j;
              }
          }
      }
      //Dijkstra
      memset(dist,0x3f,sizeof(dist));
      dist[1] = 0;
      for(int i = 1; i <= n; i++){
          int v=-1, t = e[0][0];
          for(int j = 1; j <= n; j++){
              if(!vis[j] && dist[j]<t){
                  t = dist[j];
                  v = j;
              }
          }
          if(v==-1)break;
          vis[v] = 1;
          //dist[v] = t;
          for(int j = 1; j <= n; j++){
              if(dist[j]>dist[v]+e[v][j]){
                  dist[j] = dist[v]+e[v][j];
              }
          }
      }
      //cout<<e[0][0]<<"\n";
      cout<<dist[2021];
      return 0;
  }
  
  
  

T6-T10

T6 時間顯示

• 小藍要和朋友合作開發(fā)一個時間顯示的網(wǎng)站。在服務器上，朋友已經(jīng)獲取了當前的時間，用一個整數(shù)表示，值為從 1970 年 1 月 1 日00:00:00 到當前時刻經(jīng)過的毫秒數(shù)。
  現(xiàn)在，小藍要在客戶端顯示出這個時間。小藍不用顯示出年月日，只需要顯示出時分秒即可，毫秒也不用顯示，直接舍去即可。
  給定一個用整數(shù)表示的時間，請將這個時間對應的時分秒輸出。

• 不用顯示年月日，只要時分秒，所以不難想到很傻比的做法是對獲得的時間戳每次減去60累加即可，注意開longlong，非常簡單。（暴力也能過哦）
  然后優(yōu)化一下很顯然的做法是，直接取模。
  需要注意題目給的是毫秒，不是秒！??！。

  #include<bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  int main(){
      LL ms;  cin>>ms;
      LL h= 0, m=0, s=ms/1000;
      while(s >= 60){
          s -= 60;
          m++;
          if(m==60){
              m = 0;
              h++;
              if(h==24)h = 0;
          }
      }
      printf("%02d:%02d:%02d",h,m,s);
      return 0;
  }
  
  
  #include<bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  int main(){
      LL ms;  cin>>ms;
      LL s = ms/1000;
      LL h = (s/3600)%24;
      LL m = (s/60)%60;
      s %= 60;
      printf("%02d:%02d:%02d",h,m,s);
      return 0;
  }
  
  
  
  

T7 砝碼稱重

• 你有一架天平和 N 個砝碼，這 N 個砝碼重量依次是 W1, W2, · · · , WN。 請你計算一共可以稱出多少種不同的重量？注意砝碼可以放在天平兩邊。
• 放左邊為正數(shù)，放右邊為負數(shù)，不放為0，每種砝碼三種選擇。本質為有限制選擇的背包問題。
  記f[i][j]表示，只從前i個物品中選，總重量為j的所有方案的是否存在。
  轉移的時候，對于第i個物品，可以放左邊+w[i]，放右邊-w[i]，以及不放。
  最后答案就是遍歷總重量m，累加f[n][i]即可。

  #include<bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  const int maxn = 2e5+10,maxx=1e5;
  int w[maxn];
  int f[110][maxn];
  int main(){
      int n, m=0;  cin>>n;
      for(int i = 1; i <= n; i++){
          cin>>w[i];  m+=w[i];
      }
      f[0][0+maxx] = 1; //前0個物品中選，重量為0的方案數(shù)
      for(int i = 1; i <= n; i++){
          for(int j = -m; j <= m; j++){
              f[i][j+maxx] = f[i-1][j+maxx];//不放
              if(j-w[i]>=-m)f[i][j+maxx] |= f[i-1][j-w[i]+maxx];//放左邊
              if(j+w[i]<=m)f[i][j+maxx] |= f[i-1][j+w[i]+maxx];//放右邊
          }
      }
      int res = 0;
      for(int i = 1; i <= m; i++){
          if(f[n][i+maxx])res++;
      }
      cout<<res<<"\n";
      return 0;
  }
  
  
  

T8 楊輝三角形

• 如果我們按從上到下、從左到右的順序把所有數(shù)排成一列，可以得到如下數(shù)列： 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, …
  給定一個正整數(shù) N，請你輸出數(shù)列中第一次出現(xiàn) N 是在第幾個數(shù)？
• 滾動數(shù)組暴力出楊輝三角，特判第幾個數(shù)出現(xiàn)，對于前面的部分可以打表.

  //TLE-30分
  #include<bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  const int maxn = 1010;
  LL f[maxn][maxn];
  int main(){
      LL n;  cin>>n;
      f[1][1] = 1;
      f[2][1] = f[2][2] = 1;
      LL cnt = 3;
      for(int i = 3; ; i++){
          for(int j = 1; j <= i; j++){
              f[i][j] = f[i-1][j-1]+f[i-1][j];
              cnt++;
              if(f[i][j]==n){
                  cout<<cnt<<"\n";
                  return 0;
              }
          }
      }
      return 0;
  }
  
  //TLE-40分
  #include<bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  const int maxn = 1e7+10;
  LL f[2][maxn];
  int main(){
      LL n;  cin>>n;
      f[1][1] = 1;
      f[0][1] = f[0][2] = 1;//2%2==0
      LL cnt = 3;
      for(int i = 3; ; i++){
          for(int j = 1; j <= i; j++){
              f[(i+2)%2][j] = f[(i-1+2)%2][j-1]+f[(i-1+2)%2][j];
              cnt++;
              if(f[i%2][j]==n){
                  cout<<cnt<<"\n";
                  return 0;
              }
          }
      }
      return 0;
  }
  
  
  
  
  

T9 雙向排序

• 給定序列 (a1, a2, · · · , an) = (1, 2, · · · , n)，即 ai = i。
  小藍將對這個序列進行 m次操作，每次可能是將 a1, a2, · · · , aqi 降序排列，或者將 aqi, aqi+1, · · · , an升序排列。
  請求出操作完成后的序列

• 來個簡單粗暴的寫法，就是對于每個輸入均以sort處理，垃圾數(shù)據(jù)表示可以給你60分hhh。

  //TLE-60分
  #include<bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  const int maxn = 1e5+10;
  int a[maxn];
  bool cmp(int x, int y){
      return x>y;
  }
  int main(){
      int n, m;  cin>>n>>m;
      for(int i = 1; i <= n; i++)a[i] = i;
      for(int i = 1; i <= m; i++){
          int p, q;  cin>>p>>q;
          if(p==0)sort(a+1,a+q+1,cmp);
          else sort(a+q,a+n+1);
      }
      for(int i = 1; i <= n; i++){
          cout<<a[i]<<" ";
      }
      return 0;
  }
  
  
  

• 一共兩個操作（1-n）的排列，將某前綴降序排列，將某后綴升序。共m個操作。
  （1）我們本來輸入的序列就是升序的，第一個有效操作必然是降序操作
  （2）對于連續(xù)的降序或升序操作，我們保留最長的一個操作即可。有效操作必然是左右交替的
  （3）當左側區(qū)間長度大于上一個對左端操作時，含重復操作的區(qū)間了，我們只需要操作后一個（長度范圍更大的）左區(qū)間操作即可。

  //RE-60分
  #include<bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  const int maxn = 1e5+10;
  int a[maxn];
  int main(){
      int n, m;  cin>>n>>m;
      //化簡操作
      stack<pair<int,int> >st;
      for(int i = 1; i <= m; i++){
          int p, q;  cin>>p>>q;
          if(p==0){//左邊前綴降序
              //刪除前面比當前操作小的左操作
              while(!st.empty() && st.top().first==0){
                  q = max(q, st.top().second); st.pop();
              }
              //刪掉前邊比當前操作小的左端操作及其對應的右端操作
              if(st.size()>=2){
                  pair<int,int> t = st.top();  st.pop();
                  if(st.top().second>q)st.push(t);
                  else{
                      while(st.size()>=1 && st.top().second<=q){
                          st.pop();  t=st.top();
                          if(st.size()>=1)st.pop();
                      }
                      st.push(t);
                  }
                  
                  
              }
              st.push(make_pair(0,q));
          }
          else if(!st.empty()){   //右邊后綴升序(不需要操作第一個右操作)
              while(!st.empty() && st.top().first==1){
                  q = min(q,st.top().second); st.pop();
              }
              if(st.size()>=2){
                  pair<int,int> t = st.top();  st.pop();
                  if(st.top().second<q)st.push(t);
                  else{
                      while(st.size()>=1 && st.top().second>=q){
                          st.pop();  t=st.top();
                          if(st.size()>=1)st.pop();
                      }
                      st.push(t);
                  }
              }
              st.push(make_pair(1,q));
          }
      }
      //處理操作
      vector<pair<int,int> >vc;
      while(st.size()){vc.push_back(st.top()); st.pop(); }
      reverse(vc.begin(),vc.end());
      int k = n, l = 1, r = n;
      for(int i = 0; i < vc.size(); i++){
          if(vc[i].first==0){
              while(r>vc[i].second && l<=r)a[r--]=k--;
          }else{
              while(l<vc[i].second && l<=r)a[l++]=k--;
          }
          if(l>r)break;
      }
      if(vc.size()%2==1){
          while(l<=r)a[l++]=k--;
      }else{
          while(l<=r)a[r--]=k--;
      }
      for(int i = 1; i <= n; i++){
          cout<<a[i]<<" ";
      }
      return 0;
  }
  
  
  

T10 括號序列

• 給定一個括號序列，要求盡可能少地添加若干括號使得括號序列變得合法，當添加完成后，會產(chǎn)生不同的添加結果，請問有多少種本質不同的添加結果。
  兩個結果是本質不同的是指存在某個位置一個結果是左括號，而另一個是右括號。
  例如，對于括號序列((()，只需要添加兩個括號就能讓其合法，有以下幾 種不同的添加結果：()()()、()(())、(())()、(()()) 和((()))。

• 暴力dfs大約可以打40分，正解是類似于完全背包的dp
  一個合法括號序列滿足2個條件：左右括號數(shù)量相同。任何一個前綴中，左括號數(shù)量不小于右括號數(shù)。
  記f[i][j] 表示只考慮前i個括號，左括號比右括號多j個的方案數(shù)。
  對于轉移，遇到左括號時顯然有f[i][j] = f[i - 1][j - 1]。遇到有括號時，可以考慮往這個右括號前面加左括號，可以是0-j+1個（因為左括號比右括號多j個，且當前位置是右括號所以需要+1），所以f[i][j] = f[i][j-1] + f[i - 1][j+1]。文章來源地址http://www.zghlxwxcb.cn/news/detail-407948.html

  //100分
  #include<bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  const int maxn = 5050, mod = 1e9+7;
  
  string s;
  int f[maxn][maxn], n;
  LL dp(){
      memset(f,0,sizeof(f));
      f[0][0] = 1;
      for(int i = 1; i <= n; i++){
          if(s[i]=='('){
              for(int j = 1; j <= n; j++){
                  f[i][j] = f[i-1][j-1];
              }
          }else{
              f[i][0] = (f[i-1][0]+f[i-1][1])%mod;
              for(int j = 1; j <= n; j++){
                  f[i][j] = (f[i-1][j+1]+f[i][j-1])%mod;
              }
          }
      }
      for(int i = 0; i <= n; i++){
          if(f[n][i])return f[n][i];
      }
      return -1;
  }
  
  int main(){
      cin>>s;  s="0"+s;
      n = s.size()-1;
      LL l = dp();//左括號的做法
      reverse(s.begin()+1,s.end());//右括號的做法，將整個序列反轉,調(diào)用函數(shù)即可
      for(int i = 1; i <= n; i++){
          if(s[i]=='(')s[i]=')';
          else s[i]='(';
      }
      LL r = dp();
      //cout<<l<<" "<<r<<"\n";
      cout<<(l*r%mod)<<"\n";
      return 0;
  }
  
  
  

到了這里，關于2021 第十二屆藍橋杯大賽軟件賽省賽，C/C++ 大學B組題解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！