1、握手问题
（1）题目描述
小蓝组织了一场算法交流会议，总共有 50 人参加了本次会议。在会议上，大家进行了握手交流。按照惯例他们每个人都要与除自己以外的其他所有人进行一次握手 (且仅有一次)。但有 7 个人，这 7 人彼此之间没有进行握手 (但这 7 人与除这 7 人以外的所有人进行了握手)。请问这些人之间一共进行了多少次握手?
注意 A 和 B 握手的同时也意味着 B 和 A 握手了，所以算作是一次握手。
（2）解题思路（数学问题）
数学组合问题
（3）代码
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int total_counts = (50 * 49) / 2;
int no_counts = (7 * 6) / 2;
int ans = total_counts - no_counts;
printf("%d", ans);
return 0;
}（4）难点：无
2、小球反弹
（1）题目描述
有一长方形，长为 343720 单位长度，宽为 233333 单位长度。在其内部左上角顶点有一小球 (无视其体积)，其初速度如图所示且保持运动速率不变，分解到长宽两个方向上的速率之比为 dx:dy=15:17。小球碰到长方形的边框时会发生反弹，每次反弹的入射角与反射角相等，因此小球会改变方向且保持速率不变（如果小球刚好射向角落，则按入射方向原路返回）。从小球出发到其第一次回到左上角顶点这段时间里，小球运动的路程为多少单位长度？答案四舍五入保留两位小数。
（2）解题思路（数学问题）
为什么要求最小的n和m呢？因为题目要求了是第一次回到起点走过的路程。
（3）代码
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
int main(int argc, char *argv[])
{
int x = gcd(3499995, 5843240);
long long n = 3499995 / x;
long long m = 5843240 / x;
double sx = 2.0 * n * 343720;
double sy = 2.0 * m * 233333;
double s = pow(sx * sx + sy * sy, 0.5);
// double s = sqrt(sx * sx + sy * sy);
printf("%.2f", s);
return 0;
}（4）难点：数学思维
3、好数
（1）题目描述
一个整数如果按从低位到高位的顺序，奇数位 (个位、百位、万位 ⋯ ) 上的数字是奇数，偶数位 (十位、千位、十万位 ⋯ ) 上的数字是偶数，我们就称之为 “好数”。
给定一个正整数 N，请计算从 1 到 N 一共有多少个好数。
（2）解题思路（模拟）
先写一个check函数来检查一个数是不是好数。
（3）代码
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 判断一个数是不是好数
bool check(int n) {
int c_pos = 1;
while (n != 0) {
int c_num = n % 10;
if (c_pos % 2 == 1) {
if (c_num % 2 == 0) return false;
} else {
if (c_num % 2 == 1) return false;
}
n = n / 10;
c_pos++;
}
return true;
}
int main(int argc, char *argv[])
{
int N;
scanf("%d", &N);
int ans = 0;
for (int n = 1; n <= N; n++) if (check(n)) ans++;
printf("%d\0", ans);
return 0;
}（4）难点：check函数书写。
4、R 格式
（1）题目描述
小蓝最近在研究一种浮点数的表示方法：R 格式。对于一个大于 0 的浮点数 d，可以用 R 格式的整数来表示。给定一个转换参数 n，将浮点数转换为 R 格式整数的做法是:
- 将浮点数乘以 2n；
- 四舍五入到最接近的整数。
（2）解题思路（模拟+数组）
高精度模板问题
（3）代码
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int main(int argc, char *argv[])
{
// 1 用字符串数组存储输入的浮点数，然后倒序存入b数组，用k记录小数位置
int n;
char m_s[1024];
scanf("%d %s", &n, m_s);
int c = strlen(m_s);
int b[1500];
int k;
int c_s = 0;
for (int i = c - 1; i >= 0; i--) {
if (m_s[i] == '.') {
k = c_s;
} else {
b[c_s++] = m_s[i] - '0';
}
}
// 2 n次循环，每个循环*2，对b数组不断处理
while (n--) {
int t = 0; // t用于记录每一位运算产生的进位
for (int i = 0; i < c_s; i++) {
int cur = b[i] * 2 + t;
b[i] = cur % 10;
t = cur / 10;
}
if (t > 0) {
b[c_s++] = t;
}
}
// 3 对b数组进行四舍五入
if (b[k-1] >= 5) {
int carry = 1;
for (int i = k; i < c_s; i++) {
b[i] += carry;
if (b[i] <= 9) {
carry = 0;
break;
} else {
b[i] = 0;
carry = 1;
}
}
if (carry) {
b[c_s++] = carry;
}
}
// 4 打印输出
for (int i = c_s - 1; i >= k; i--) {
printf("%d", b[i]);
}
printf("\n");
return 0;
}（4）难点：思维+数组运算。
5、宝石组合
（1）问题描述
在一个神秘的森林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状，但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗宝石都有一个与生俱来的特殊能力，可以发出不同强度的闪光。小蓝共找到了 N 枚宝石，第 i 枚宝石的 “闪亮度” 属性值为 Hi，小蓝将会从这 N 枚宝石中选出三枚进行组合，组合之后的精美程度 S 可以用以下公式来衡量：
其中 LCM 表示的是最小公倍数函数。
小蓝想要使得三枚宝石组合后的精美程度 S 尽可能的高，请你帮他找出精美程度最高的方案。如果存在多个方案 S 值相同，优先选择按照 H 值升序排列后字典序最小的方案。
（2）解题思路（数学）
（3）代码
#include <stdio.h>
#define MAXH 100005 // 定义亮度的最大范围
int cnt[MAXH]; // 记录每个亮度值出现的次数
int res[3];
int main() {
// 1 输入
int n;
scanf("%d", &n);
int max_h = 0;
for (int i = 0; i < n; i++) {
int h;
scanf("%d", &h);
cnt[h]++; // 放入桶中
if (h > max_h) max_h = h;
}
// 2 枚举最大公约数
for (int g = max_h; g >= 1; g--) {
int f_c = 0;
// 从小到大（保证了“优先选择按照 H 值升序排列后字典序最小的方案”）
for (int n = g; n <= max_h; n += g) {
for (int k = 0; k < cnt[n] && f_c < 3; k++) {
res[f_c++] = n;
}
if (f_c == 3) break;
}
if (f_c == 3) {
printf("%d %d %d\n", res[0], res[1], res[2]);
return 0;
}
}
return 0;
}（4）难点：数学。
6、数字接龙
（1）题目描述
小蓝最近迷上了一款名为《数字接龙》的迷宫游戏，游戏在一个大小为 N×N 的格子棋盘上展开，其中每一个格子处都有着一个 0…K−1 之间的整数。游戏规则如下：
- 从左上角 (0,0) 处出发，目标是到达右下角 (N−1,N−1) 处的格子，每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。
- 对于路径经过的棋盘格子，按照经过的格子顺序，上面的数字组成的序列要满足：0,1,2,…,K−1,0,1,2,…,K−1,0,1,2… 。
- 途中需要对棋盘上的每个格子恰好都经过一次（仅一次）。
- 路径中不可以出现交叉的线路。例如之前有从 (0,0) 移动到 (1,1) ，那么再从 (1,0) 移动到 (0,1) 线路就会交叉。
为了方便表示，我们对可以行进的所有八个方向进行了数字编号，如下图 2 所示；因此行进路径可以用一个包含 0…7 之间的数字字符串表示，如下图 1 是一个迷宫示例，它所对应的答案就是：41255214。
现在请你帮小蓝规划出一条行进路径并将其输出。如果有多条路径，输出字典序最小的那一个；如果不存在任何一条路径，则输出 −1。
（2）解题思路（DFS）
条件1和条件3共同构成递归出口，条件2、4为判断条件。字典序最小：从小到大枚举方向。
另外由于是一个path数组存储答案 所以找到第一条答案后 立即return所有dfs 否则就会输出所有结果
（3）代码
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 10
int N, K;
// 全局变量定义数组默认初始化为0
int flag = 0; // 判断是否找到答案
int grid[MAX_N][MAX_N]; // 存储棋盘
int visited[MAX_N][MAX_N]; // 标记数组
int path[MAX_N * MAX_N]; // 答案数组
int line[MAX_N][MAX_N][MAX_N][MAX_N]; // 连线判断数组
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; // 反向数组 0:上....
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int is_cross(int x, int y, int dir) {
if (dir == 1) return line[x-1][y][x][y+1];
if (dir == 3) return line[x+1][y][x][y+1];
if (dir == 5) return line[x+1][y][x][y-1];
if (dir == 7) return line[x-1][y][x][y-1];
return 0; // 垂直和水平的情况
}
void dfs(int x, int y, int step) {
// 递归出口
if (step == N*N-1 && x == N-1 && y == N-1) {
flag = 1;
for (int i = 0; i < step; i++) printf("%d", path[i]);
printf("\n");
return;
}
// 遍历方向(从小到大遍历，满足题目字典序最小)
for (int i = 0; i < 8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny] && grid[nx][ny] == (step + 1) % K
&& !is_cross(x, y, i)) {
visited[nx][ny] = 1;
path[step] = i;
line[x][y][nx][ny] = 1;
line[nx][ny][x][y] = 1;
dfs(nx, ny, step + 1);
if (flag == 1) break; // 已经找到答案了 刹车！
// 回溯
visited[nx][ny] = 0;
path[step] = 0;
line[x][y][nx][ny] = 0;
line[nx][ny][x][y] = 0;
}
}
}
int main(int argc, char *argv[])
{
// 1 输入
scanf("%d %d", &N, &K);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
scanf("%d", &grid[i][j]);
}
}
// 2 初始化
visited[0][0] = 1;
// 3 dfs
dfs(0, 0, 0);
if (flag == 0) {
printf("-1\n");
}
return 0;
}（4）难点：DFS
7、拔河
（1）题目描述
小明是学校里的一名老师，他带的班级共有 n 名同学，第 i 名同学力量值为 ai。在闲暇之余，小明决定在班级里组织一场拔河比赛。
为了保证比赛的双方实力尽可能相近，需要在这 n 名同学中挑选出两个队伍，队伍内的同学编号连续：{al1,al1+1,…,ar1−1,ar1} 和 {al2,al2+1,…,ar2−1,ar2}，其中 l1≤r1<l2≤r2。
两个队伍的人数不必相同，但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。
（2）解题思路（前缀和+双指针＋贪心 -> 暴力所有情况）
最好理解的一个思路⛷️，且保证正确：
1、先说思路： 双层循环不断枚举l，r 其中l是左边队列的起点 r是右边队列的终点 其中r从为倒序枚举 即初始化l为0 r为n-1 然后每一次双层循环确定l,r后 再进行while双指针 即不断更新双指针左队列的右起点i 和 右队列的左起点j 如果左边队列的和等于右边队列的和 那么直接输出答案0 如果左边队列的和小于右边队列的和 那么i++ 相反 j– 直到i==j 然后进行下一次双层循环 直到l==r
2、为什么说他一定正确呢？ 第一：保证了左边队列和右边队列的连续性 因为i和j分别都是基于l和r进行++或者–的，一定连续。 第二：保证左边队列在右边队列右边 因为在双指针时 进行了i < j限制。 第三：保证了“左边队列和右边队列有间隔的情况” 因为如果没有剪枝 i和j最终才会相遇 第四：保证了”左边队列不一定从所有同学的起点开始 右边队列也不一定从所有同学的终点结束”的情况。因为l和r是不断枚举的，遍历了所有可能的左队列起点和右队列终点的情况。
第三条和第四条合在一起即枚举了两种队列所有可能的情况。 所以 唯一就是复杂度问题 两层for循环是O(n2) 然后双指针是O(n) 大概是O(n3) 满足题目的数据范围
（3）代码
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main() {
int n;
scanf("%d", &n);
long long a[n + 1];
long long S[n + 1];
S[0] = 0;
for (int k = 1; k <= n; k++) {
scanf("%lld", &a[k]);
S[k] = S[k - 1] + a[k];
}
long long min_diff = -1;
// 枚举左区间的起点
for (int l = 1; l < n; l++) {
// 枚举右区间的终点
for (int r = n; r >= l + 1; r--) {
// 设置左区间的终点和右区间的起点
int i = l;
int j = r;
// 开始进行双指针
while (i < j) {
long long sum_left = S[i] - S[l - 1];
long long sum_right = S[r] - S[j - 1];
long long cur_diff = llabs(sum_left - sum_right);
if (min_diff == -1 || cur_diff < min_diff) {
min_diff = cur_diff;
}
if (min_diff == 0) {
printf("0\n");
return 0;
}
if (sum_left < sum_right) {
i++;
} else {
j--;
}
}
}
}
printf("%lld\n", min_diff);
return 0;
}（4）难点：无
