寒假程序设计训练2:基础算法与程序设计(2021-01-02训练单)
2021/6/8 20:21:51
本文主要是介绍寒假程序设计训练2:基础算法与程序设计(2021-01-02训练单),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
寒假程序设计训练2:基础算法与程序设计T1:最大公约数
备注事项
本题来源于今天洛谷上的一次比赛,还请先报名,否则不能提交。给大家造成不便实属不好意思,但是这题真的不错,以后训练会增加这种风格的题,比如codeforces上,这种题挺多,很有趣。
T1:我的参考程序
#include <cstdio> const int maxn = 2e3 + 5; int n, m, x, y, ans, flag; typedef long long ll; ll a[maxn][maxn], cur; ll gcd(const ll& s, const ll& t) { return 0 == t ? s : gcd(t, s % t); } ll getValue(const ll& r, const ll& c) { if(r >= 1 && r <= n && c >= 1 && c <= m) return a[r][c]; else return 0; } int main() { scanf("%d %d", &n, &m); for(int i = 1;i <= n;++i) for(int j = 1;j <= m;++j) scanf("%lld", &a[i][j]); scanf("%d %d", &x, &y); for(ans = 0;ans <= n + m;++ans) { for(int dx = 0, dy = ans;dx <= ans && dy >= 0;++dx, --dy) { cur = gcd(cur, getValue(x - dx, y - dy)); cur = gcd(cur, getValue(x - dx, y + dy)); cur = gcd(cur, getValue(x + dx, y - dy)); cur = gcd(cur, getValue(x + dx, y + dy)); if(cur == 1) { flag = 1; break; } } if(flag) break; } if(flag) printf("%d\n", ans); else printf("-1\n"); return 0; }
T1:算法分析与设计
这题要求计算需要多少次,通过与上下左右求最大公约数的方法,让元素 a[x][y] 的值变为 1。 如果无法让其变为1,则输出 -1,否则输出需要计算的次数。每次计算是让矩阵的每一个元素都变成与上下左右的最大公约数。首先思考,最多需要多少次计算,能让 a[x][y] 变为1 ??
a[x][y] 第一次变换会等于 (x, y - 1)、(x - 1, y)、(x + 1, y)、(x, y + 1) 分别于它本身的最大公约数。我们知道,如果一个数是 0,则任何数与它的最大公约数都是它本身;如果一个数是 1,则任何数与它的最大公约数都是 1。所以四个方向的计算顺序是无所谓的,这一点也很关键。
在行数为n,列数为m的矩阵里,如果最少计算的次数是 k,则需要对从 (x, y)出发的,曼哈顿距离为 k 的所有点进行计算,如果当前最大曼哈顿距离为 k 的时候,能够让 a[x][y] 变为 1,则这个 k 就是最优解。然后k的所有可能值,就是从起点(1, 1)到最远点(n, m),dis = n + m,所以详情见程序,我先去吃海底捞了!
T2:妖梦拼木棒
T2:我的参考程序
#include <cstdio> const int maxn = 1e5 + 5; const int maxv = 1e4 + 5; typedef long long ll; const ll mod = 1e9 + 7; ll ans; int n, a, appear[maxv]; inline int C(int x) { return x * (x - 1) / 2; } int main() { scanf("%d", &n); for(int i = 0;i < n;++i) { scanf("%d", &a); appear[a]++; } for(int i = 1;i < maxv;++i) { for(int j = i;j < maxv;++j) { if(i != j && appear[i] && appear[j] && appear[i + j] >= 2) { ans = (ans + ((ll)appear[i] * appear[j] % mod) * (ll)C(appear[i + j]) % mod) % mod; } else if(i == j && appear[i] && appear[i + j] >= 2) { ans = (ans + (ll)C(appear[i]) * C(appear[i + j]) % mod) % mod; } } } printf("%lld\n", ans); return 0; }
T3:算法设计与分析
吃完海底捞回来了!
这题也比较有意思其实,首先很重要的破题点:四根木棍拼出一个正三角形!如何才能四个木棍?由于组合原理,可以知道,必然有一条边是两根木棍,并且这两根木棍的长度之和要等于另外两条木棍。然后再看数据范围,木棍的长度范围是5 * 10^3,这说明我们可以枚举木棍的长度,然后判断:
1、当前木棍 i 和木棍 j 是否在n个木棍中出现
2、两个木棍的长度和 i + j 是否在 n 个木棍中有两个或两个以上
然后进行计算,这里需要分类讨论:
1、如果 i != j ,则计算 i 的数量(用标记数组)乘以 j 的数量,再乘以 i + j 中选两个的数量(组合数、乘法原理)
2、如果 i = j ,则计算 i 的数量中选两个的个数乘以 i + j 中选两个的个数(同理)
最后详情见程序。
T3:攀爬者
T3:我的参考程序
#include <iostream> #include <algorithm> #include <cmath> #include <cstdio> using namespace std; const int maxn = 50007; struct Point { int x, y, z; }p[maxn]; bool cmp(const Point& p1, const Point& p2) { return p1.z < p2.z; } double dis(const Point& p1, const Point& p2) { return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y) + (p1.z - p2.z) * (p1.z - p2.z)); } int main() { int n; double ans = 0.0; cin >> n; for(int i = 0;i < n;++i) cin >> p[i].x >> p[i].y >> p[i].z; sort(p, p + n, cmp); for(int i = 1;i < n;++i) { ans += dis(p[i], p[i - 1]); } printf("%.3lf\n", ans); return 0; }
T3:算法分析与设计
这题的难度标号就离谱,选的难度是《普及/提高-》,但是真实难度也太普及了……所以就不解释了!
T4:加密通信
T4:我的参考程序
#include <cstdio> #include <cstring> const int maxn = 1e5 + 5; int T, n; typedef long long ll; ll M, a[maxn], res[maxn]; ll gcd(const ll& x, const ll& y) { return 0 == y ? x : gcd(y, x % y); } int main() { scanf("%d", &T); while(T--) { scanf("%d %lld", &n, &M); bool flag = true; ll pos = -1; for(int i = 0;i < n - 1;++i) { scanf("%lld", &a[i]); if(i >= 1 && a[i] != a[i - 1]) { res[i] = gcd(a[i], a[i - 1]); pos = i; } } if(-1 == pos) flag = false; if(flag) { for(int j = pos - 1;j >= 0;--j) res[j] = a[j] / res[j + 1]; for(int j = pos + 1;j < n;++j) res[j] = a[j - 1] / res[j - 1]; for(int i = 0;i < n;++i) { if(res[i] > M) { flag = false; break; } } } if(flag) { for(int i = 0;i < n;++i) printf("%lld ", res[i]); printf("\n"); } else printf("-1\n"); memset(res, 0, sizeof(res)); } return 0; }
T4:算法分析与设计
本题要求输出任意符合条件的密文,然后要求密钥与明文的关系是:B(i) * B(i + 1) = A(i)
由此可以推出:
B(i) = A(i) / B(i + 1)
B(i) = A(i - 1) / B(i - 1)
上述两个式子,然后很明显,如若知道任意一个B(i),就可以递推计算出所有的B(i),通过上面两个式子。并且题目说明了,必然有两个A(i) 和 A(j) 是不相等的,既然有上面的式子的约束,又有此条件,说明存在A(i) 和 A(i + 1)不相等,否则所有的A(i) 都将是相同的。所以一次遍历即可找到这么一对不相等的数对,然后他们的最大公约数,必然是B(i + 1),因为:
A(i) = B(i) * B(i + 1)
A(i + 1) = B(i + 1) * B(i + 2)
所以最大公约数是B(i + 1),然后记录此位置,前后递推即可得到答案!
总结与展望
今天吃了顿海底捞,撑得慌,做题时间有点少,先四道题作为今天的题单,明天继续!希望有志于此的同学一起努力,完成题单的训练,欢迎交流!
感谢阅读~
这篇关于寒假程序设计训练2:基础算法与程序设计(2021-01-02训练单)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)