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：括号序列（程序设计）

题意：

做法：

代码：