2021第十二屆4月藍橋杯大賽軟體類B組C/C++省賽題解

好多題目事后發現錯了，真的血虧TAT，沒找到測評網站，暫時先更新填空題，

試題 A：空間（結果填空）

題意：

做法：1ll * 256 * 1024 * 1024 * 8 / 32

答案：67108864

試題 B：卡片（結果填空）

題意：

做法：這題一定要注意是最多能從1拼到多少，

代碼：

#include<bits/stdc++.h>
using namespace std;
int a[10];
int solve(int x) {
  while(x) {
    if(!a[x%10]) return 0;
    --a[x%10];
    x /= 10;
  }
  return 1;
}
int main() {
  for(int i = 0; i < 10; ++i) a[i] = 2021;
  int cnt = 1;
  while(1) {
    if(!solve(cnt)) break;
    ++cnt;
  }
  cout << cnt - 1;
  return 0;
} 

答案：3181

試題 C：直線（結果填空）

題意：

做法：列舉每兩個點，最后check函式判重，暴力寫法，

代碼：

#include<bits/stdc++.h>
#define eps 1e-9
using namespace std;
const int N = 1e7;
struct xx {
  double k, b;
}p[N];
int tot;
void check(double x1, double y1, double x2, double y2) {
  double k, b;
  k = (y2-y1)/(x2-x1); b = y1 - k*x1;
  int f = 1;
  for(int i = 1; i <= tot; ++i) {
    if(fabs(k - p[i].k) < eps && fabs(b - p[i].b) < eps) {
      f = 0; break;
    }
  }
  if(f) p[++tot] = xx {k, b};
}
int main() {
  int n = 20, m = 21;
  for(double x1 = 0; x1 < n; ++x1) {
    for(double y1 = 0; y1 < m; ++y1) {
      for(double x2 = 0; x2 < n; ++x2) {
        for(double y2 = 0; y2 < m; ++y2) {
          if(x1 == x2 || y1 == y2) continue;
          check(x1, y1, x2, y2);
        }
      }
    }
  }
  cout << tot+n+m;
  return 0;
}

答案：40257

試題 D：貨物擺放（結果填空）

題意：

做法：正確做法是質因子分解把，因為是填空題于是用暴力寫了，

代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
vector<LL> ve;
int main() {
	LL n = 2021041820210418;
	LL sq = sqrt(n);
	for(LL i = 1; i <= sq; ++i) {
	  if(n%i == 0) {
	    ve.push_back(i);
	    if(i != n/i) ve.push_back(n/i);
    } 
  }
  sort(ve.begin(), ve.end());
  int nn = ve.size(), res = 0;
	for(int i = 0; i < nn; ++i) {
	  for(int j = 0; j < nn; ++j) {
	    if(ve[j] > n/ve[i]) break;
      for(int k = 0; k < nn; ++k) {
	      if(ve[i] > n/(ve[j]*ve[k])) break;
	      if(ve[i]*ve[j]*ve[k] == n) ++res;
      }
    }
  }
  cout << res;
  return 0;
}

答案：2430

試題 E：路徑（結果填空）

題意：

做法：建邊+dijsktra跑最短路，

代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> pli;
const int N = 1e4;
const int M = 1e7;
struct xx {
  int to, nxt;
  LL w;
}e[M];
int head[N], tot;
void Add(int u, int v, LL w) {
  e[++tot] = xx{v, head[u], w};
  head[u] = tot;
}
LL dis[N];
int vis[N];
priority_queue< pli, vector<pli>, greater<pli> > pq;
void dij() {
  for(int i = 0; i <= 2021; ++i) dis[i] = 1e18, vis[i] = 0;
  dis[1] = 0;
  pq.push(make_pair(dis[1], 1));
  int u, v;
  while(!pq.empty()) {
    u = pq.top().second; pq.pop();
    if(vis[u]) continue;
    vis[u] = 1;
    for(int i = head[u]; i; i = e[i].nxt) {
      v = e[i].to;
      if(dis[v] > dis[u] + e[i].w) {
        dis[v] = dis[u] + e[i].w;
        pq.push(make_pair(dis[v], v)); 
      }
    }
  }
}
int main() {
  for(int i = 1; i <= 2021; ++i) {
    for(int j = i+1; j <= 2021; ++j) {
      if(j-i <= 21) {
        LL w = i*j/__gcd(i, j);
        Add(i, j, w); Add(j, i, w);
      }
    }
  }
  dij();
  cout << dis[2021];
  return 0;
}

答案：10266837

-----------------------后續更新------------------------

試題 F：時間顯示（程式設計）

題意：

做法：

代碼：

試題 G：砝碼稱重（結果填空）

題意：

做法：

代碼：

答案：

試題 H：楊輝三角形（程式設計）

題意：

做法：

代碼：

試題 I：雙向排序（程式設計）

題意：

做法：

代碼：

試題 J：括號序列（程式設計）

題意：

做法：

代碼：