1、移动距离
（1）题目描述
小明初始在二维平面的原点 (0,0)，他想前往坐标 (233,666).
在移动过程中，他只能采用以下两种移动方式，并且这两种移动方式可以交替、不限次数地使用：
- 水平向右移动，即沿着 x 轴正方向移动一定的距离。
- 沿着一个圆心在原点 (0,0)、以他当前位置到原点的距离为半径的圆的圆周移动，移动方向不限（即顺时针或逆时针移动不限）。
在这种条件下，他到达目的地最少移动多少单位距离？
只需输出答案四舍五入到整数的结果。
（2）解题思路
（3）代码
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(int argc, char *argv[])
{
// 先求出AC
double Ac_dis = pow(pow(233, 2)+pow(666, 2), 0.5);
double r = Ac_dis;
// 接着求出BC
double Bc_dis = acos(233 / Ac_dis) * r;
// 四舍五入并输出结果
int ans = (int)(Ac_dis + Bc_dis + 0.5);
printf("%d", ans);
return 0;
}（4）难点：无
2、客流量上限
（1）题目描述
一家连锁旅馆在全国拥有 2025 个分店，分别编号为 1 至 2025。随着节日临近，总部决定为每家分店设定每日客流量的上限，分别记作 A1,A2,…,A2025。这些上限并非随意分配，而是需要满足以下约束条件：
- A1,A2,…,A2025 必须是 1 至 2025 的一个排列，即每个 Ai 均是 1 至 2025 之间的整数，且所有 Ai 互不相同。
- 对于任意分店 i 和 j（1≤i,j≤2025，i 可等于 j），它们的客流量上限 Ai 和 Aj 的乘积不得超过 ij+2025。
这些约束旨在平衡各分店客流压力，确保服务质量和运营稳定性。
现在，请你计算这样的分配方案究竟有多少种。由于答案可能很大，你只需输出其对 109+7 取余后的结果即可。
（2）解题思路
（图 A）
（图 B）
列出题目限制的三个条件，从i = j时作为切入点，通过观察最终得到结论在1013<=i<=2025时，Ai = i。
然后讨论i ≠ j的情况，分为图B所示的三种情况，然后根据已经得到的“1013<=i<=2025时，Ai = i”结论，最后得1<= i <=1012时，Ai <= i + 1的结论。
（3）代码
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(int argc, char *argv[])
{
// 或者直接定义：long long mod = 1000000007LL;
long long mod = 1;
for (int i = 0; i < 9; i++) {
mod *= 10;
}
mod += 7;
long long ans = 1;
for (int i = 0; i < 1012; i++) {
ans *= 2;
ans %= mod; // 必须实时取模
}
printf("%lld", ans);
return 0;
}（4）难点：纯数学问题，难。
3、可分解的正整数
（1）题目描述
定义一种特殊的整数序列：这种序列由连续递增的整数组成，并满足以下条件：
- 序列长度至少为 3。
- 序列中的数字是连续递增的整数（即相邻元素之差为 1），可以包括正整数、负整数或 0。
例如，[1,2,3]、[4,5,6,7] 和 [−1,0,1] 是符合条件的序列，而 [1,2]（长度不足）和 [1,2,4]（不连续）不符合要求。
现给定一组包含 N 个正整数的数据 A1,A2,…,AN。如果某个 Ai 能够表示为符合上述条件的连续整数序列中所有元素的和，则称 Ai 是可分解的。
请你统计这组数据中可分解的正整数的数量。
（2）解题思路
（3）代码
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
/*
[−(x−1),−(x−2),...,−1,0,1,...,x−1,x]
因此，在给定的正整数中，只有1不满足条件
*/
int N;
scanf("%d", &N);
int ans = 0;
for (int i = 0; i < N; i++) {
int A;
scanf("%d", &A);
if (A != 1) ans++;
}
printf("%d", ans);
return 0;
}（4）难点：正负抵消的思维。
4、产值调整
（1）题目描述
偏远的小镇上，三兄弟共同经营着一家小型矿业公司“兄弟矿业”。公司旗下有三座矿山：金矿、银矿和铜矿，它们的初始产值分别用非负整数 A、B 和 C 表示。这些矿山的产出是小镇经济的核心，支撑着三兄弟和许多矿工家庭的生计。
然而，各矿山的产值波动剧烈，有时金矿收益高而银矿、铜矿低迷，有时则相反。这种不稳定性让公司收入难以预测，也常引发兄弟间的争执。为了稳定经营，三兄弟设计了一个公平的产值调整策略，每年执行一次，每次调整时，将根据当前的产值 A、B、C，计算新产值：
- 金矿新产值 A′=⌊2B+C⌋；
- 银矿新产值 B′=⌊2A+C⌋；
- 铜矿新产值 C′=⌊2A+B⌋。
其中，⌊⌋ 表示向下取整。例如，⌊3.7⌋=3，⌊5.2⌋=5。
计算出 A′、B′、C′ 后，同时更新：A 变为 A′，B 变为 B′，C 变为 C′，作为下一年调整的基础。
三兄弟认为这个方法能平衡产值波动，于是计划连续执行 K 次调整。现在，请你帮他们计算，经过 K 次调整后，金矿、银矿和铜矿的产值分别是多少。
（2）解题思路
模拟+剪枝
（3）代码
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int T;
scanf("%d", &T);
for (int i = 0; i < T; i++) {
// 输入
int A, B, C, K;
scanf("%d", &A);
scanf("%d", &B);
scanf("%d", &C);
scanf("%d", &K);
// 计算
int A_n, B_n, C_n;
for (int j = 0; j < K; j++) {
A_n = (B + C) / 2;
B_n = (A + C) / 2;
C_n = (A + B) / 2;
// 剪枝，状态未变则退出
if (A_n == A && B_n == B && C_n == C) break;
A = A_n;
B = B_n;
C = C_n;
}
// 输出
printf("%d %d %d\n", A, B, C);
}
return 0;
}（4）难点：剪枝，和A B C变化的趋势。
5、画展布置
（1）题目描述
画展策展人小蓝和助理小桥为即将举办的画展准备了 N 幅画作，其艺术价值分别为 A1,A2,…,AN。他们需要从这 N 幅画中挑选 M 幅，并按照一定顺序布置在展厅的 M 个位置上。如果随意挑选和排列，艺术价值的变化可能会过于突兀，导致观众的观展体验不够流畅。
为了优化布置，他们查阅了《画展布置指南》。指南指出，理想的画展应使观众在欣赏画作时，艺术价值的过渡尽量平缓。指南建议，选择并排列 M 幅画，应使艺术价值的变化程度通过一个数值 L 来衡量，且该值越小越好。数值 L 的定义为：其中 Bi 表示展厅第 i 个位置上画作的艺术价值。
现在，他们希望通过精心挑选和排列这 M 幅画作，使 L 达到最小值，以提升画展的整体协调性。请你帮他们计算出这个最小值是多少。
（2）解题思路
先假设M = 3,然后把L公式展开看下，哦，发现是求相邻元素平方差之和最小。
那么一定要排序且相邻，（其实排序就是为了相邻），但是是哪三个相邻的呢？那么就需要滑动窗口不断更新答案。
（3）代码
#include <stdio.h>
#include <stdlib.h>
#define MIN(a, b) ((a) > (b) ? b : a)
// cmp返回类型一定是int
int cmp(const void* a, const void* b) {
long long n = (*(long long *)a);
long long m = (*(long long *)b);
if (n > m) return 1;
if (n < m) return -1;
return 0;
}
int main(int argc, char *argv[])
{
// 1 输入
int N, M;
scanf("%d %d", &N, &M);
long long arr[N];
for (int i = 0; i < N; i++) {
scanf("%lld", &arr[i]);
arr[i] = arr[i]*arr[i];
}
// 2 排序
qsort(arr, N, sizeof(long long), cmp);
// 3 滑动窗口，更新答案，窗口大小为M
long long ans = arr[N-1] - arr[0] + 1; // 已知该题一定有答案，先初始化一个不可能的答案
for (int i = 0; i + M <= N; i++) {
ans = MIN(ans, arr[i+M-1] - arr[i]);
}
// 4 输出答案
printf("%lld", ans);
return 0;
}（4）难点：滑动窗口，不断更新答案。且”对于所有评测用例，2≤M≤N≤105，1≤Ai≤105。”，所以要用long long。
6、水质检测
（1）题目描述
小明需要在一条 2×n 的河床上铺设水质检测器。在他铺设之前，河床上已经存在一些检测器。如果两个检测器上下或左右相邻，那么这两个检测器就是互相连通的。
连通具有传递性，即如果 A 和 B 连通，B 和 C 连通，那么 A 和 C 也连通。现在他需要在河床上增加铺设一些检测器，使得所有检测器都互相连通。他想知道最少需要增加铺设多少个检测器？
（2）解题思路
Dijkstra
（3）代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 1000005
#define INF 0x3f3f3f3f
// 存储点
typedef struct {
int r, c;
} PII;
// 全局变量，防止栈溢出
char s[2][MAXN];
int dist[2][MAXN]; // dist[i][j]表示到达点(i,j)的最短路径
int st[2][MAXN]; // 标记数组，表示点(i,j)已找到最短路径
int n;
// 手写双端队列
PII deque[MAXN * 4];
int head = MAXN * 2, tail = MAXN * 2;
void push_front(int r, int c) {
deque[--head] = (PII){r, c};
}
void push_back(int r, int c) {
deque[tail++] = (PII){r, c};
}
PII pop_front() {
return deque[head++];
}
int is_empty() {
return head == tail;
}
// 0-1BFS：dijkstra
int main(int argc, char *argv[])
{
// 数据读入
scanf("%s %s", s[0], s[1]);
n = strlen(s[0]);
// 数组初始化
memset(dist, 0x3f, sizeof(dist));
memset(st, 0, sizeof(st));
// 寻找第一个'#'作为源点
int start_r = -1, start_c = -1;
for (int j = 0; j < n; j++) {
if (s[0][j] == '#') {
start_r = 0;
start_c = j;
break;
}
if (s[1][j] == '#') {
start_r = 1;
start_c = j;
break;
}
}
// 剪枝
if (start_r == -1) {
printf("0\n");
return 0;
}
// 0-1 BFS
dist[start_r][start_c] = 0;
push_back(start_r, start_c);
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int max_dis = 0;
while (!is_empty()) {
PII t = pop_front();
int r = t.r, c = t.c;
if (st[r][c]) continue;
st[r][c] = 1; // 标记(r, c)点已获取到最短路径
if (s[r][c] == '#') {
max_dis = dist[r][c]; // 更新答案
}
for (int i = 0; i < 4; i++) {
int nr = r + dx[i];
int nc = c + dy[i];
if (nr >= 0 && nr < 2 && nc >= 0 && nc < n) {
int w = (s[nr][nc] == '#' ? 0 : 1);
if (dist[nr][nc] > dist[r][c] + w) {
dist[nr][nc] = dist[r][c] + w;
if (w == 0) push_front(nr, nc);
else push_back(nr, nc);
}
}
}
}
// 输出
printf("%d\n", max_dis);
return 0;
}（4）难点：完全想不到，想到也不会实现。
7、生成车间
（1）题目描述
小明正在改造一个生产车间的生产流水线。这个车间共有 n 台设备，构成以 1 为根结点的一棵树，结点 i 有权值 wi。
其中，叶结点的权值 wi 表示每单位时间产出 wi 单位材料并送往父结点；根结点的权值 wi 表示每单位时间内能打包 wi 单位成品； 其他结点的权值 wi 表示每单位时间最多能加工 wi 单位材料并送往父结点。
由于生产线中某些结点产能不足，导致无法正常运行，即某些结点每单位时间收到的材料超过其加工能力上限。小明计划删除一些结点使所有结点都能正常运行，想知道删除后根结点每单位时间最多能打包多少单位成品。
（2）解题思路
DFS+DP，树形DP。
（3）代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 1005
#define MAXW 1005
int n;
int w[MAXN]; // w[i]表示节点i单位时间能承受单位材料的最大值
int adj[MAXN][MAXN]; // adj[i][j]表示节点j是否为节点i的子节点（输入的第一个是父节点，所以单向存储即可）
int dp[MAXN][MAXW]; // dp[i][j]表示节点i能否在单位时间向上拿j单位材料
int temp[MAXW];
void dfs(u, fa)
{
int is_leaf = 1;
// 初始化
dp[u][0] = 1;
// 核心
for (int v = 1; v <= n; v++) {
if (adj[u][v]) {
is_leaf = 0;
dfs(v, u);
memset(temp, 0, sizeof(temp));
for (int i = 0; i <= w[u]; i++) {
if (dp[u][i] == 1) {
for (int j = 0; j <= w[v]; j++) {
if (dp[v][j] == 1 && i + j <= w[u]) {
temp[i + j] = 1;
}
}
}
}
// 存储结果
for (int i = 0; i <= w[u]; i++) {
dp[u][i] = temp[i]; // 不断完善dp[u]中
}
}
}
if (is_leaf) {
dp[u][0] = 1;
dp[u][w[u]] = 1;
}
}
int main(int argc, char *argv[])
{
// 1 输入
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &w[i]);
}
for (int i = 0; i < n - 1; i++) {
int u, v;
scanf("%d %d", &u, &v);
adj[u][v] = 1;
}
// 2 DFS构造dp数组
dfs(1, 0);
// 3 输出答案
int ans;
for (int x = w[1]; x >= 0; x--) {
if (dp[1][x] == 1) {
ans = x;
break;
}
}
printf("%d\n", ans);
return 0;
}（4）难点：完全想不到，想到也不会实现。
8、装修报价
（1）题目描述
老王计划装修房子，于是联系了一家装修公司。该公司有一套自动报价系统，只需用户提供 N 项装修相关费用 A1,A2,…,AN，系统便会根据这些费用生成最终的报价。
然而，当老王提交数据后，他发现这套系统的运作方式并不透明：系统只会给出一个最终报价，而不会公开任何运算过程或中间步骤。
公司对此解释称，这套系统会依据某种内部算法，在每对相邻数字之间插入 +（加法）、−（减法）或 ⊕（异或）运算符，并按照特定优先级规则计算总和：异或运算优先级最高，其次是加减。但由于保密性，具体的运算符组合以及中间过程都不会对外公开。
为了验证系统报价是否合理，老王决定模拟其运作方式，尝试每种可能的运算符组合，计算出所有可能出现的总和。如果最终报价明显超出这个范围，他就有理由怀疑系统存在异常或误差。只是老王年事已高，手动计算颇为吃力，便向你求助。
现在，请你帮老王算出所有可能的总和。由于该总和可能很大，你只需提供其对 109+7 取余后的结果即可。
（2）解题思路
由于异或优先级最高，整个表达式被加减号切分成多个“异或块”，而在求所有组合总和时，加减号后的所有后续变化都会因正负对称而相互抵消为 0，因此只需遍历每一个可能成为“第一个加减号前缀”的异或块 s，计算它在所有可能组合中的贡献，最后累加上唯一的“全异或”情况即可。
（3）代码
#include <stdio.h>
#define MOD 1000000007
int main() {
// 1 输入
int n;
scanf("%d", &n);
int a[n + 1];
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
// 预处理数组
long long mi[n + 1];
mi[0] = 1;
for (int i = 1; i <= n; i++) {
mi[i] = (mi[i - 1] * 3) % MOD;
}
// 2 数学逻辑
long long ret = 0;
long long s = 0;
for (int i = 1; i < n; i++) {
s ^= a[i];
long long contribution = (s * 2) % MOD;
contribution = (contribution * mi[n - i - 1]) % MOD;
ret = (ret + contribution) % MOD;
}
s ^= a[n];
ret = (ret + s) % MOD;
printf("%lld\n", ret % MOD);
return 0;
}（4）难点：数学。
