我模拟了一下, 分享一下我的做题感受和经验, 希望能对你有用
这个比赛的时长是四个小时, 初赛的目标是拿到省一, 才有机会进入国赛
我也不知道, 这个分能不能进国赛, 算了，不管了, 直接开讲, 我本人一般刷面试题比较多, 这种比赛题平常基本不怎么写
1. 握手问题
题目链接: 蓝桥账户中心
题目如下:
问题描述
小蓝组织了一场算法交流会议，总共有 50 人参加了本次会议。在会议上，大家进行了握手交流。按照惯例他们每个人都要与除自己以外的其他所有人进行一次握手 (且仅有一次)。但有 7 个人，这 7 人彼此之间没有进行握手 (但这 7 人与除这 7 人以外的所有人进行了握手)。请问这些人之间一共进行了多少次握手?
注意 A 和 B 握手的同时也意味着 B 和 A 握手了，所以算作是一次握手。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
#include <bits/stdc++.h>
using namespace std;
int main()
{int a=50; int b=7;int res=0;int totalNum=a*(a-1)/2;totalNum-=(b*(b-1)/2);cout<<totalNum<<endl;return 0;
}题意就是说, 有43个人可以和其他人两两握手, 剩下的7个人, 内部不能两两握手, 但是能和其他的43个人握手, 问这些人一共进行握了多少次手
这其实是个数学题, 比赛的时候直接用计算器算一下就行, 不用写代码
思路1：分两类 43个人分一组记作A组, 7个人分一组记作B组, 43个内部随便握手，A组：43*42/2=903(解释一下为啥要/2, 类似于均摊法, 图论中中每条边连接着两个节点, 在计算度数和时, 每条边会被重复计算两次, 结果要除2, 这里握手就相当于两个人(节点)连接了一条边，结果也要/2), B组：7*43=301，最后结果就是301+903=1204次
思路2：整体-特殊(就是我代码中写的)
50个人两两握手减去7个人两两握手
50*49/2-7*6/2=1204
2. 小球反弹
有一长方形，长为 343720343720 单位长度，宽为 233333233333 单位长度。在其内部左上角顶点有一小球 (无视其体积)，其初速度如图所示且保持运动速率不变，分解到长宽两个方向上的速率之比为 dx:dy=15:17。小球碰到长方形的边框时会发生反弹，每次反弹的入射角与反射角相等，因此小球会改变方向且保持速率不变（如果小球刚好射向角落，则按入射方向原路返回）。从小球出发到其第一次回到左上角顶点这段时间里，小球运动的路程为多少单位长度？答案四舍五入保留两位小数。
这是道物理题, 如果你是初中生, 就直接秒了, 但我模拟比赛的时候却被秒了
题意：从做左上角按入射角tan &=dx/dy=15/17射入一条光线, 在矩形中进行反射，求重新返回左上角所经过的路程。
解法：按我下面, 图中的画的进行对称补偿就行
#include <bits/stdc++.h>
using namespace std;
int main(){long long times=1,x=343720,y=233333;while(true){if((15*times)%x==0&&(17*times)%y==0) break;times++;}cout << fixed << setprecision(2) << 2*sqrt(15*15*times*times+17*17*times*times) << endl;return 0;
}3. 好数
题目如下：
问题描述
一个整数如果按从低位到高位的顺序，奇数位 (个位、百位、万位 ⋯⋯ ) 上的数字是奇数，偶数位 (十位、千位、十万位 ⋯⋯ ) 上的数字是偶数，我们就称之为 “好数”。
给定一个正整数 N，请计算从 1 到 N 一共有多少个好数。
输入格式
一个整数 N。
输出格式
一个整数代表答案。
解题思路：按题目进行模拟就行(计数还是不计数，删除还是不删除)
#include <bits/stdc++.h>
using namespace std;
bool isGoodNum(int num) {int pos = 1;while (num > 0) {int digit = num % 10;if (pos % 2 == 1) { if (digit % 2 == 0) {return false;}} else { if (digit % 2 == 1) { return false;}}num /= 10;pos++;}return true;
}int main() {int N;cin >> N;int res = 0;for (int i = 1; i <= N; i++) { if (isGoodNum(i)) {res++;}}cout << res << endl;return 0;
}
------------------------
#include <bits/stdc++.h>
using namespace std;
bool isGoodNum(string num) {int pos = 1; int n=num.size();while (num.size() > 0) {int digit = num[num.size()-1]-'0';if(pos%2==1&&digit%2==1){pos++; num.erase(num.size()-1); continue; }else if(pos%2==0&&digit%2==0){pos++; num.erase(num.size()-1); continue;}else{break;}}if(pos-1==n){return true;}return false;
}int main() {int N;cin >> N;int res = 0;for (int i = 1; i <= N; i++) {string s=to_string(i);if (isGoodNum(s)) {res++;}}cout << res << endl;return 0;
}
------------------------
#include <bits/stdc++.h>
using namespace std;
bool isGoodNum(string num) {int n = num.size();for (int i = n - 1; i >= 0; i--) {int digit = num[i] - '0';int pos = n - i; if ((pos % 2 == 1 && digit % 2 == 0) || (pos % 2 == 0 && digit % 2 == 1)) {return false;}}return true;
}int main() {int N;cin >> N;int res = 0;for (int i = 1; i <= N; i++) {string s = to_string(i);if (isGoodNum(s)) {res++;}}cout << res << endl;return 0;
}
-------------------------
#include <bits/stdc++.h>
using namespace std;bool isGoodNum(string num) {int pos = 1;int n = num.size();while (!num.empty()) {int digit = num.back() - '0';if ((pos % 2 == 1 && digit % 2 == 1) || (pos % 2 == 0 && digit % 2 == 0)) {pos++;num.pop_back();} else {return false;}}return true;
}int main() {int N;cin >> N;int res = 0;for (int i = 1; i <= N; i++) {string s = to_string(i);if (isGoodNum(s)) {res++;}}cout << res << endl;return 0;
}4. R格式
题目如下：
问题描述
小蓝最近在研究一种浮点数的表示方法：RR 格式。对于一个大于 0 的浮点数 d，可以用 RR 格式的整数来表示。给定一个转换参数 n，将浮点数转换为 R 格式整数的做法是:
将浮点数乘以 2^n；
四舍五入到最接近的整数。
输入格式
一行输入一个整数 n 和一个浮点数 d，分别表示转换参数，和待转换的浮点数。
输出格式
输出一行表示答案：d 用 R 格式表示出来的值。
#include <bits/stdc++.h>
using namespace std;
int main() {int n;double d;cin >> n >> d;double p = pow(2.0, n);double res = d * p;int r = round(res);cout << r << endl;return 0;
}
这是模拟比赛时的代码, 提交后发现只过了40%思路：面试题中很少有卡输入输出精度的情况，我又被秒了
正确的解法如下：把数字转换成字符串进行处理，我的建议是你对下面小数进位乘法的板子熟悉的话，就一步一步写。如果你只是想过掉尽量多的用例, 不追求满分的话，就在第一段代码中把数据范围开的尽量大一些，int r->long long r, 能过掉50%，也能拿到10分
#include<bits/stdc++.h>
using namespace std;
string solve(string& num){string res;int c=0;for(int j=num.size()-1;j>=0;j--){int d=num[j]-'0';int p=d*2+c;c=p/10;res.push_back((p%10)+'0');}if(c>0){res.push_back(c+'0');}reverse(res.begin(),res.end());return res;
}
string addOne(string num){int c=1;for(int i=num.size()-1;i>=0;i--){int d=num[i]-'0';int sum=d+c;num[i]=(sum%10)+'0';c=sum/10;}if(c>0){num.insert(num.begin(),'1');}return num;
}
int main(){int n; string d;cin>>n>>d;int point=d.find('.');string frontNum=d.substr(0,point);string backNum=d.substr(point+1);int k=backNum.size();while(k>0&&backNum[k-1]=='0') k--;backNum=backNum.substr(0,k);string Num=frontNum+backNum;for(int i=0;i<n;i++){Num=solve(Num);}int m=Num.size();string q,r;if(m<=k){q="0";r=Num+string(k-m,'0');}else{q=Num.substr(0,m-k);r=Num.substr(m-k);}string h(k,'0');h[0]='5';if(r>=h){q=addOne(q);}cout<<q<<endl;return 0;
}5. 宝石组合
题目链接：
蓝桥账户中心
解题思路：根据题目中给出的公式很容易推导出s=gcd(a,b,c), 所以题目就转换成求gcd(a,b,c) 的最大值
代码如下：
#include<bits/stdc++.h>
using namespace std;
int freq[100001]={0};
int main(){int N;cin>>N;vector<int> a(N);for(int i=0;i<N;i++){cin>>a[i];freq[a[i]]++;}int maxA=*max_element(a.begin(),a.end());vector<int> cnt(maxA+1,0);for(int d=1;d<=maxA;d++){for(int k=d;k<=maxA;k+=d){cnt[d]+=freq[k];}}int bestD=-1;for(int d=maxA;d>=1;d--){if(cnt[d]>=3){bestD=d;break;}}vector<int> c;for(int x: a){if(x%bestD==0){c.push_back(x);}}sort(c.begin(),c.end());cout << c[0] << " " << c[1] << " " << c[2] << endl;return 0;
}6. 数字接龙
题目链接：
https://www.lanqiao.cn/problems/19712/learning/
输出从(0,0)到(N-1,N-1)的最小字典序路径, 思路就是dfs/回溯
#include <bits/stdc++.h>
using namespace std;
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int N, K;
vector<vector<int>> grid;
vector<vector<bool>> visited;
string result = "";
bool isValid(int x, int y) {return x >= 0 && x < N && y >= 0 && y < N;
}
bool solve(pair<int, int> a1, pair<int, int> a2, pair<int, int> b1, pair<int, int> b2) {double x1 = a1.first, y1 = a1.second;double x2 = a2.first, y2 = a2.second;double x3 = b1.first, y3 = b1.second;double x4 = b2.first, y4 = b2.second;double den = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);if (den == 0) return false; double t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)) / den;double u = -((x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3)) / den;if (t >= 0 && t <= 1 && u >= 0 && u <= 1) {double px = x1 + t * (x2 - x1);double py = y1 + t * (y2 - y1);bool isAStart = (px == x1 && py == y1);bool isAEnd = (px == x2 && py == y2);bool isBStart = (px == x3 && py == y3);bool isBEnd = (px == x4 && py == y4);if (!isAStart && !isAEnd && !isBStart && !isBEnd) {return true;}}return false;
}void dfs(int x, int y, int num, int count, string path, vector<pair<pair<int, int>, pair<int, int>>>& segments) {if (x == N-1 && y == N-1) {if (count == N * N) {if (result.empty() || path < result) {result = path;}}return;}for (int i = 0; i < 8; i++) { int nx = x + dx[i];int ny = y + dy[i];if (isValid(nx, ny) && !visited[nx][ny] && grid[nx][ny] == (num + 1) % K) {pair<int, int> current(x, y), next(nx, ny);bool cross = false;for (auto& seg : segments) {if (solve(current, next, seg.first, seg.second)) {cross = true;break;}}if (!cross) {visited[nx][ny] = true;segments.emplace_back(current, next); //记录走过的线段dfs(nx, ny, (num + 1) % K, count + 1, path + to_string(i), segments);segments.pop_back();visited[nx][ny] = false;}}}
}
int main() {cin >> N >> K;grid.resize(N, vector<int>(N));visited.resize(N, vector<bool>(N, false));for (int i = 0; i < N; ++i) {for (int j = 0; j < N; ++j) {cin >> grid[i][j];}}if (grid[0][0] != 0) { cout << -1 << endl;return 0;}visited[0][0] = true;vector<pair<pair<int, int>, pair<int, int>>> segments;dfs(0, 0, 0, 1, "", segments);if (result.empty()) {cout << -1 << endl;} else {cout << result << endl;}return 0;
}7. 拔河
问题描述
小明是学校里的一名老师，他带的班级共有 n 名同学，第 i 名同学力量值为 ai。在闲暇之余，小明决定在班级里组织一场拔河比赛。
为了保证比赛的双方实力尽可能相近，需要在这 nn 名同学中挑选出两个队伍，队伍内的同学编号连续：{al1,al1+1,…,ar1−1,ar1} 和 {al2,al2+1,…,ar2−1,ar2，其中l1≤r1<l2≤r2。
两个队伍的人数不必相同，但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。
解题思路： 我模拟赛时, 用前缀和按顺序模拟题意, 四层循环, 含泪只过了三个样例...
代码如下
#include<bits/stdc++.h>
using namespace std;
int main() {int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; ++i) {cin >> a[i];}vector<int> prefix(n + 1, 0); for (int i = 0; i < n; ++i) {prefix[i + 1] = prefix[i] + a[i];}int minDiff = INT_MAX;for (int l1 = 0; l1 < n; l1++) {for (int r1 = l1 + 1; r1 <= n; r1++) {int sum1 = prefix[r1] - prefix[l1];for (int l2 = r1; l2 < n; l2++) {for (int r2 = l2 + 1; r2 <= n; r2++) {int sum2 = prefix[r2] - prefix[l2];minDiff = min(minDiff, abs(sum1 - sum2));}}}}cout << minDiff << endl;return 0;
}正确解法的时间复杂度为O(n^2*logn), 只要你写的代码时间复杂度<O(n^3)就能过
要不枚举左子数组的结束位置, 要不枚举右子数组的开始位置, 分割点划分给左/右子数组都可以
#include<bits/stdc++.h>
using namespace std;
int main() {int n;cin >> n;vector<long long> a(n + 1);vector<long long> prefix(n + 1, 0);for (int i = 1; i <= n; ++i) {cin >> a[i];prefix[i] = prefix[i - 1] + a[i];}long long ans = LLONG_MAX;set<long long> sumBSet;for (int rA = n; rA >= 1; rA--) {int lB = rA + 1;if (lB <= n) {for (int rB = lB; rB <= n; rB++) {long long sumB = prefix[rB] - prefix[rA];sumBSet.insert(sumB);}}for (int l1 = 1; l1 <= rA; l1++) {long long sumA = prefix[rA] - prefix[l1 - 1];auto it = sumBSet.lower_bound(sumA);if (it != sumBSet.end()) {ans = min(ans, abs(sumA - *it));}if (it != sumBSet.begin()) {ans = min(ans, abs(sumA - *prev(it))); //前后对比}if (ans == 0) {cout << 0 << endl;return 0;}}}cout << ans << endl;return 0;
}总结：题目有点偏数学, 没考dp, 常见的题像搜索, 滑窗, 前缀和, 差分, 双指针, 左右维护, 还有简单一点的贪心, 你都要搞懂, 最后再写几道数学题, 基本上就差不多了, 比赛的时候, 如果没有双机位, 可以和旁边的同学适当讨论一下, 感觉有一些数学技巧确实有点难想。如果你很强，就当我没说。有什么疑问可以发到评论区，感谢！！！
