个人主页：Guiat
归属专栏：算法竞赛真题题解
文章目录
- A. 握手问题（填空题）
- B. 小球反弹（填空题）
- C. 好数
- D. R格式
- E. 宝石组合
- F. 数字接龙
- G. 爬山
- H. 拔河
正文
总共8道题。
A. 握手问题（填空题）
【题目】握手问题
【分析】
纯考察数学中简单排列组合。考虑相互握手的43人：（43 * 42） / 2；考虑剩下7人与43人分别握手：7 * 43；两者相加即最终答案。
【答案】1204
【AC_Code】
#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;void solve() { cout << 1204 << '\n'; }int main() { IOS; solve(); return 0; }
B. 小球反弹（填空题）
【题目】小球反弹
【分析】
考察高中简单物理思维。小球从左上角出发最终回到左上角，说明水平和竖直位移分别是长和宽的偶数倍。又速率之比为位移之比（15：17），可写双重循环控制总过程中长和宽的倍数暴力求解即可。
【答案】1100325199.77
【AC_Code】
#include <iostream>
#include <iomanip>
#include <cmath>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int N = 1e4;
int L = 343720, W = 233333;int solve()
{for (int i = 2; i <= N; i += 2) for (int j = 2; j <= N; j += 2){if (L * i * 17 == W * j * 15){cout << fixed << setprecision(2) << sqrt(pow(L * i, 2) + pow(W * j, 2)) << '\n';return 0;}}
}int main() { IOS; solve(); }
C. 好数
【题目】好数
【分析】
考察模拟。写一个check函数判断是否为好数：逆向思维 ①奇数位为偶数时，返回false；②偶数位为奇数时返回false；①②包含了不满足的所有情况，都不满足最后返回true。其中digit（位数）的使用很关键（在check函数开头设置为1，否则可能会错误累加），还有不要出现悬空else的情况。
【AC_Code】
#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;int n, cnt, digit;bool check(int i)
{digit = 1;while (i){if (digit % 2 == 1) { if ((i % 10) % 2 == 0) return false; }else if ((i % 10) % 2 != 0) return false;digit ++; i /= 10;}return true;
}void solve()
{cin >> n; for (int i = 1; i <= n; i ++) if (check(i)) cnt ++; cout << cnt << '\n';
}int main()
{IOS; solve();return 0;
}
D. R格式
【题目】R 格式
【分析】
一道模拟题。“将浮点数乘以2 ^ n”这句话可以看出数据很大，考虑用数组模拟高精度算法（低精度乘以高精度）。大体思路是将浮点数d处理成字符串，将字符串反转方便处理小数部分，之后依次乘2，进行模拟，最后判断四舍五入，倒序输出答案。
【AC_Code】
#include <iostream>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std;const int N = 1e6 + 10;
int n, pos, len, ans[N]; string d;void solve()
{cin >> n >> d; reverse(d.begin(), d.end());pos = d.find('.'); d.erase(pos, 1); len = d.size();for (int i = 0; i < len; i ++) ans[i + 1] = d[i] - '0';for (int i = 1; i <= n; i ++){for (int j = 1; j <= len; j ++) ans[j] *= 2;for (int j = 1; j <= len; j ++) ans[j + 1] += ans[j] / 10, ans[j] %= 10;if (ans[len + 1]) len ++;}if (ans[pos] >= 5) ans[pos + 1] ++;for (int i = pos + 1; i <= len; i ++) ans[i + 1] += ans[i] / 10, ans[i] %= 10;if (ans[len + 1]) len ++;for (int i = len; i > pos; i --) cout << ans[i]; cout << '\n';
}int main()
{IOS; solve();return 0;
}
E. 宝石组合
【题目】宝石组合
【分析】
有些地方不太明白，先给出代码。
【AC_Code】
#include <iostream>
#include <vector>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int MAXN = 1e5 + 10; int n, h[MAXN]; vector<int> fac[MAXN];void solve()
{cin >> n; for (int i = 1; i <= n; ++ i) cin >> h[i];sort(h + 1, h + 1 + n);for (int i = 1; i <= n; ++ i) for (int j = 1; j * j <= h[i]; ++j){if (h[i] % j == 0){fac[j].push_back(h[i]);if (h[i] / j != j) fac[h[i] / j].push_back(h[i]);}}for (int i = MAXN; i >= 1; -- i){if (fac[i].size() >= 3){int a = fac[i][0], b = fac[i][1], c = fac[i][2];if (__gcd(__gcd(a, b), c) == i) { cout << a << " " << b << " " << c << "\n"; return; }}}
}int main()
{IOS; solve();return 0;
}
F. 数字接龙
【题目】数字接龙
【分析】
不会，先给出代码。
【AC_Code】
#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int N = 15;
int n, k, nums[N][N],
dx[8] = { -1, -1, 0, 1, 1, 1, 0, -1 },
dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
string nber; bool vis[N][N], check[N][N][N][N];bool dfs(int a, int b)
{if (a == n - 1 && b == n - 1) return nber.size() == n * n - 1;vis[a][b] = true;for (int i = 0; i < 8; i ++){int x = a + dx[i], y = b + dy[i];if (x < 0 || x >= n || y < 0 || y >= n) continue;if (vis[x][y]) continue;if (nums[x][y] != (nums[a][b] + 1) % k) continue;if (i % 2 && (check[a][y][x][b] || check[x][b][a][y])) continue;check[a][b][x][y] = true; nber += i + '0';if (dfs(x, y)) return true;nber.pop_back(); check[a][b][x][y] = false;}vis[a][b] = false;return false;
}void solve()
{cin >> n >> k;for (int i = 0; i < n; i ++) for (int j = 0; j < n; j ++) cin >> nums[i][j];if (!dfs(0, 0)) cout << -1 << '\n';else cout << nber << '\n';
}int main()
{IOS; solve();return 0;
}
G. 爬山
【说明】疑似为错题，直接跳过。
H. 拔河
【题目】拔河
【分析】
【AC_Code】
#include <iostream>
#include <set>
#include <cmath>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;
using ll = long long;const int N = 1e3 + 10;
int n; ll a[N], res = 1e9; multiset<long long> s;ll minn(ll a, ll b) { if (a < b) return a; else return b; }void solve()
{cin >> n; for (int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1];for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++) s.insert(a[j] - a[i - 1]);for (int i = 1; i <= n - 1; i++){for (int j = i; j <= n; j++){auto k = a[j] - a[i - 1]; s.erase(s.find(k));}for (int j = 1; j <= i; j++){auto k = a[i] - a[j - 1]; auto p = s.lower_bound(k);if (p != s.end()) res = minn(res, abs(*p - k));if (p != s.begin()) p--, res = minn(res, abs(*p - k));}}cout << res << '\n';
}int main()
{IOS; int _ = 1; // cin >> _; while (_ --) solve();return 0;
}
结语
感谢您的阅读！期待您的一键三连！欢迎指正！
