【蓝桥备赛冲刺】2021年第十二届省赛B组第一场题解C/C++陆续更新状态ing
目录
A题:空间
B题:卡片
C题:直线
D题:货物摆放
E题:路径
A题:空间
问题描述
题目描述小蓝准备用256MB 的内存空间开一个数组，数组的每个元素都是32 位二进制整数。如果不考虑程序占用的空间和维护内存需要的辅助空间。请问256MB 的空间可以存储多少个32 位二进制整数？思路分析
知道内存单位转换即可 1M = 1024k 1k = 1024B 1B = 8b。需要注意的是不能直接 *8 / 32，而是要 / 4，否则会 int 型数据溢出。
题目代码
#include using namespace std;int main() { /* 1M = 1024k 1k = 1024B 1B = 8b */ cout << 256 * 1024 * 1024 / 4; return 0;}题目答案
67108864B题:卡片
问题描述
小蓝有很多数字卡片，每张卡片上都是数字0 到9。小蓝准备用这些卡片来拼一些数，他想从1 开始拼出正整数，每拼一个，就保存起来。卡片就不能用来拼其它数了。小蓝想知道自己能从1 拼到多少。例如，当小蓝有30 张卡片，其中0 到9 各3 张，则小蓝可以拼出1 到10。但是拼11 时卡片1 已经只有一张了，不够拼出11。现在小蓝手里有0 到9 的卡片各2021 张，共20210 张，请问小蓝可以从1拼到多少？提示：建议使用计算机编程解决问题。思路分析
初始化每张卡片数量为2021，枚举每次用到的卡片并计数，当有任意一张卡片的数量小于0时停止计数。
题目代码
#include using namespace std;int nb[10];bool find(int n) { while (n) { int N = n % 10; n /= 10; if (--nb[N] < 0) return false; // 卡片已经用完 } return true; // 卡片有剩余}int main() { int num = 0; for (int i = 0; i < 10; i++) // 卡片初始化 nb[i] = 2021; for (int i = 1; find(i); i++) num++; cout << num; return 0;}题目答案
3181C题:直线
在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。给定平面上2 × 3 个整点{(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z}，即横坐标是0 到1 (包含0 和1) 之间的整数、纵坐标是0 到2 (包含0 和2) 之间的整数的点。这些点一共确定了11 条不同的直线。给定平面上20 × 21 个整点{(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z}，即横坐标是0 到19 (包含0 和19) 之间的整数、纵坐标是0 到20 (包含0 和20) 之间的整数的点。请问这些点一共确定了多少条不同的直线。问题描述
在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。给定平面上2 × 3 个整点{(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z}，即横坐标是0 到1 (包含0 和1) 之间的整数、纵坐标是0 到2 (包含0 和2) 之间的整数的点。这些点一共确定了11 条不同的直线。给定平面上20 × 21 个整点{(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z}，即横坐标是0 到19 (包含0 和19) 之间的整数、纵坐标是0 到20 (包含0 和20) 之间的整数的点。请问这些点一共确定了多少条不同的直线。思路分析
枚举所有点对并求出直线方程，当斜率k或者截距b有任意一个不同时直线不同，斜率不存在特殊考虑。
题目代码
#include #include #include using namespace std;const int N = 200000;int n;struct Line { double k, b; // 斜率k 截距b} l[N];bool rule(Line A, Line B) { // 制定sort排序规则 if (A.k != B.k) return A.k < B.k; return A.b < B.b;}int main() { /* 枚举所有点对 */ for (int x1 = 0; x1 < 20; x1++) for (int y1 = 0; y1 < 21; y1++) for (int x2 = 0; x2 < 20; x2++) for (int y2 = 0; y2 < 21; y2++) if (x1 != x2) { // 不考虑斜率不存在 double k = (double)(y2 - y1) / (x2 - x1); double b = y1 - k * x1; l[n++] = {k, b}; } sort(l, l + n, rule); // 排序方便选择出不同的直线 int res = 1; for (int i = 1; i 1e-8 || fabs(l[i].b - l[i - 1].b) > 1e-8) // 由于浮点数存在误差，所以用一个极小的数判断两数是否相等 res++; cout << res + 20 << endl; // + 20 为斜率不存在时的直线 return 0;}题目答案
40257D题:货物摆放
问题描述
小蓝有一个超大的仓库，可以摆放很多货物。现在，小蓝有n 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上分别堆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 位数字）时，总共有多少种方案？提示：建议使用计算机编程解决问题。思路分析
由 n = L x W x H 分析出L、W和H均为n的约数，我们只需要把n的所有约数求出存储，最后逐个遍历，当 i * j * k == n 时(i、j、k为n的约数)即为一个可行方案。
题目代码
#include #include using namespace std;typedef long long LL;int main() { LL n = 2021041820210418; LL l, w, h; vector v; /* 存储n的所有约数 */ for (LL i = 1; i * i < n; i++) if (n % i == 0) { v.push_back(i); if (n / i != i) // 判断不是完全平方数，否则会多加一个 v.push_back(n / i); } int cnt = 0; for (int i = 0; i < v.size(); i++) for (int j = 0; j < v.size(); j++) for (int k = 0; k < v.size(); k++) if (v[i] * v[j] * v[k] == n) cnt++; cout << cnt; return 0;}题目答案
2430E题:路径
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。小蓝的图由2021 个结点组成，依次编号1 至2021。对于两个不同的结点a, b，如果a 和b 的差的绝对值大于21，则两个结点之间没有边相连；如果a 和b 的差的绝对值小于等于21，则两个点之间有一条长度为a 和b 的最小公倍数的无向边相连。例如：结点1 和结点23 之间没有边相连；结点3 和结点24 之间有一条无向边，长度为24；结点15 和结点25 之间有一条无向边，长度为75。请计算，结点1 和结点2021 之间的最短路径长度是多少。提示：建议使用计算机编程解决问题问题描述
思路分析
这是一个简单的最短路问题，本题需要解决两个问题：求出可选择路径与编写最短路算法。本题作者选用Dijkstra算法。
其实也可以使用floyd算法，虽然时间复杂度为O(N^3),会算半分钟。但这是填空题。使用臭氧优化加快代码运行速度，最后也就是十多秒就可以算出
题目代码（Dijkstra）
#include #include using namespace std;const int N = 2030;int n = 2021, m;int g[N][N]; // 邻接矩阵，存储图int dist[N]; // 存储每个点到起点的最短距离bool st[N]; // 判断每个点到起点的最短距离是否确定int gcd(int a, int b) { // 欧几里得算法 return b ? gcd(b, a % b) : a;}int dijstra() { memset(dist, 0x3f, sizeof dist); // 初始化距离为正无穷 dist[1] = 0; for (int i = 0; i < n; i++) { int t = 0; // t 表示当前正在确定距离的点 for (int j = 1; j dist[j])) t = j; // 寻找当前结点到所有下一结点中距离最短的点 } st[t] = true; // 1号点到t点的最短距离确定 for (int j = 1; j <= n; j++) dist[j] = min(dist[j], dist[t] + g[t][j]); // 用已经确定最短距离的点更新未确定的点 } return dist[n];}int main() { memset(g, 0x3f, sizeof g); // 初始化距离为正无穷（极大值表示） /* 寻找有效边 */ for (int i = 1; i < n; i++) for (int j = i + 1; j <= n; j++) { if (j - i <= 21) { g[i][j] = i * j / gcd(i, j); // 添加路径距离 } } int t = dijstra(); cout << t; return 0;}题目代码（Floyd）
#include #pragma GCC optimize(3)using namespace std;const int N = 2050,INF = 1e9;int d[N][N]; //邻接矩阵存图int n;void floyd()//floyd{for(int k = 1;k <= n;k++)for(int i =1 ;i<=n;i++)for(int j =1;j<=n;j++)d[i][j] = min(d[i][j],d[i][k]+d[k][j]);}int gcd(int a,int b)//最大公约数{return b?gcd(b,a%b):a;}int main(){n =2021;memset(d,0x3f,sizeof d); for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(abs(j-i)<=21)d[i][j]=min(d[i][j],i*j/gcd(i,j));}floyd();printf("%d\n",d[1][2021]);return 0;}题目答案
10266837