金币

题目大意

按照特定规则，国王每天给骑士发金币：

• 第 1 天发 1 枚金币；
• 第 2～3 天每天发 2 枚金币；
• 第 4～6 天每天发 3 枚金币；
• 第 7～10 天每天发 4 枚金币；
• 以此类推。

规律是：金币数为 $n$ 的这一轮，会持续 $n$ 天。然后进入金币数为 $n+1$ 的下一轮，持续 $n+1$ 天。

给定前 $k$ 天，求骑士一共获得了多少金币。

---

题意分析

本质是将天数分组，第 $n$ 组有 $n$ 天，每天发 $n$ 枚金币。

例如：

• 第 1 组：1 天，每天 1 枚 → 总计 1 枚
• 第 2 组：2 天，每天 2 枚 → 总计 4 枚
• 第 3 组：3 天，每天 3 枚 → 总计 9 枚
• 第 4 组：4 天，每天 4 枚 → 总计 16 枚
• ...

题目要求我们从第 1 天起，一直到第 $k$ 天，计算每天金币数的总和。

---

解题思路

模拟发放金币的过程：

1. 用两个变量：
   • day：记录已经走过的天数；
   • value：当前阶段每天发的金币数量，也是阶段的天数；
2. 每次判断：
   • 如果 day + value <= k，说明当前阶段所有天数都能算入，总金币加 value * value；
   • 否则说明只剩下不足一个阶段的天数了，加上 (k - day) * value，结束；
3. 最后输出金币总数。

---

时间复杂度解析

每轮最多走 $1 + 2 + 3 + \cdots + n$ 天，直到超过 $k$，最多循环 $\sqrt{2k}$ 次，远小于 $10^4$，因此 时间复杂度为 $O(\sqrt{k})$，可以快速处理。

---

代码演示

#include <iostream>
using namespace std;

int main() {
    int k;
    cin >> k;

    int day = 0;       // 已走的天数
    int value = 1;     // 当前阶段的金币数
    int ans = 0;       // 总金币数

    while (day + value <= k) {
        ans += value * value;  // 当前阶段：value 天，每天 value 金币
        day += value;
        value++;
    }

    // 处理剩余不足一个阶段的天数
    if (day < k) {
        ans += (k - day) * value;
    }

    cout << ans << endl;
    return 0;
}

买奶茶

题目大意

有 $n$ 个人排队买奶茶，每人奶茶的制作时间为 $T_i$。奶茶店每次只能为一个人制作奶茶。一个人的等待时间是他开始制作之前所有人制作时间的总和。

例如制作时间顺序为 [1, 2, 3]：

• 第一个人等待时间为 $0$
• 第二个人等待时间为 $1$
• 第三个人等待时间为 $1 + 2 = 3$

总等待时间为 $0 + 1 + 3 = 4$，平均等待时间为 $4 / 3 = 1.33$。

本题要求：找一种排队顺序，使得 所有人平均等待时间最小。

---

题意分析

问题本质：最小化总等待时间。

关键观察：

• 第 $i$ 个人的等待时间是 他前面所有人制作时间之和。
• 所以：先做制作时间小的，可以减少后面所有人的等待时间。

这是经典的贪心策略问题，结论如下：

将所有制作时间 $T_i$ 从小到大排序，按此顺序排队，可以得到最小的平均等待时间。

---

解题思路

1. 输入 $n$ 和 $n$ 个制作时间 $T_i$。
2. 将 $T_i$ 排序。
3. 遍历排序后的数组：
   • 累加当前人的等待时间；
   • 每轮累加前面的总时间，注意第一个人等待时间是 $0$。
4. 求平均等待时间：$\frac{\text{总等待时间}}{n}$，保留两位小数。

---

时间复杂度分析

• 排序：$O(n \log n)$
• 遍历计算等待时间：$O(n)$

总时间复杂度为：$O(n \log n)$，对于 $n \leq 10^5$ 是可以接受的。

---

代码演示

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip> // 用于保留小数

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> t(n);

    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }

    sort(t.begin(), t.end()); // 按制作时间从小到大排序

    long long total_wait = 0; // 总等待时间
    long long sum = 0;        // 前缀和

    for (int i = 0; i < n; i++) {
        total_wait += sum;    // 当前人的等待时间
        sum += t[i];          // 累加制作时间供后人等待
    }

    // 输出平均等待时间，保留两位小数
    cout << fixed << setprecision(2) << (double)total_wait / n << endl;

    return 0;
}

种树

题目大意

一条街分为 $n$ 个区域，每个区域最多可以种一棵树。现在有 $h$ 个居民，每个居民想在区间 $[b_i, e_i]$ 中至少看到 $t_i$ 棵树。

这些居民的要求区间可能会重叠。我们需要决定在哪些位置种树，使得总共种树数最少，并且满足所有居民的要求。

---

题意分析

本题要求我们满足所有区间最小树数的限制，且总种树数量最少。这是一个贪心 + 差分 + 贪心调度的组合问题，具有如下特征：

• 每个区域最多一棵树（0或1）；
• 每个区间的需求是至少 $t_i$ 棵树；
• 要求在满足所有区间的前提下，总种树数量最小。

---

解题思路

我们使用如下策略：

1. 维护每个位置是否已经种树（用数组 vis[] 表示）；
2. 按照区间结束位置升序排序（先处理结束早的区间）；
3. 处理每个居民的区间要求时，计算当前区间内已种了多少棵树；
4. 如果不满足，就从区间右端往左贪心地种树，每种一棵就 t--，直到满足或区间种满。

这个策略的关键是：从右往左种树，因为右边的区域对后面的区间干扰更小，有利于节省树。

---

时间复杂度

• 排序：$O(h \log h)$；
• 每个区间最多访问 $e_i - b_i + 1$ 个位置，总最多为 $O(nh)$，但由于提前剪枝（最多每个点种一次），实际复杂度接近 $O(n + h \log h)$。

---

代码演示

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 3e4 + 10;

struct Request {
    int b, e, t;
};

int n, h;
bool vis[MAXN]; // 记录某个区域是否已经种树

int main() {
    cin >> n >> h;
    vector<Request> req(h);
    
    for (int i = 0; i < h; ++i) {
        cin >> req[i].b >> req[i].e >> req[i].t;
    }

    // 贪心策略：按照区间的右端升序排列
    sort(req.begin(), req.end(), [](Request a, Request b) {
        return a.e < b.e;
    });

    int res = 0; // 最少树木数

    for (auto r : req) {
        int count = 0;
        // 统计当前区间内已经种了几棵树
        for (int i = r.b; i <= r.e; ++i) {
            if (vis[i]) count++;
        }

        int need = r.t - count;
        // 如果不够，从右往左种树，直到满足
        for (int i = r.e; i >= r.b && need > 0; --i) {
            if (!vis[i]) {
                vis[i] = true;
                res++;
                need--;
            }
        }
    }

    cout << res << endl;
    return 0;
}

水壶

题目大意

有 $n$ 个编号为 $1$ 到 $n$ 的水壶，每个水壶初始时有 $A_i$ 单位水。你最多可以进行 $k$ 次操作，每次操作可以将某个水壶 $i$（$1 \le i \le n-1$）的水全部倒入它右边的水壶 $i+1$ 中（然后 $A_i$ 变成 0）。

最终你可以任选一个水壶，将其中的水全部喝掉。请问最多可以喝到多少水。

---

题意分析

这个问题本质上是在问：最多经过 $k$ 次“左往右倒水”操作后，某个水壶中水量最多是多少？

由于每次只能往右倒水，因此水是“右移”趋势。我们目标是集中水量，形成一个“巨无霸”水壶。

---

解题思路

• 想喝最多的水，就要把尽量多的水“搬运”到某个水壶中；
• 由于操作有限 ($k$ 次)，只能将连续的 $k+1$ 个水壶合并成一个，这样能把最多的水集中在一个水壶中；
• 最优策略：选一个长度为 $k+1$ 的连续子数组，求其和，最大值即为答案。

所以问题转化为：在数组 $A$ 中，找到长度为 $k+1$ 的连续子段最大和。

可以使用前缀和快速解决。

利用 前缀和 数组 $s$，定义：

• $s[i] = A[1] + A[2] + \cdots + A[i]$

那么，区间 $[l, r]$ 的和为：

• $s[r] - s[l-1]$

遍历所有长度为 $k+1$ 的区间 $[i, i + k]$，找到其中区间和最大值即可。

---

时间复杂度

• 构造前缀和数组：$O(n)$
• 枚举所有长度为 $k+1$ 的区间：$O(n)$
• 总体复杂度：$O(n)$

---

代码演示

#include <iostream>
#include <vector>
using namespace std;
long long a[1000010], pre[1000010]; // a[1..n], pre[0..n]
int main() {
    int n, k;
    cin >> n >> k;

    // 读入数组
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i]; // 构建前缀和
    }

    long long ans = 0;

    // 枚举所有长度为 k+1 的区间 [i, i+k]
    for (int i = 1; i + k <= n; ++i) {
        long long sum = pre[i + k] - pre[i - 1];
        ans = max(ans, sum);
    }

    cout << ans << endl;

    return 0;
}

---

钞票问题

题目大意

你有三种钞票面值：1元、5元、11元。现在你需要刚好凑出 n 元，问最少需要多少张钞票。

题意分析

这是一个典型的 完全背包问题，每种钞票可以使用任意多次，目标是最小化使用的张数，凑出固定的金额。

解题思路

我们设 dp[i] 表示凑出 i 元 需要的最少钞票数。

状态表示：

• dp[i]：表示凑出金额 i 所需的最少钞票数。

初始条件：

• dp[0] = 0：凑出 0 元不需要任何钞票。
• 其他 dp[i] 初始设为一个很大的值（比如 2e6 或 INT_MAX/2），表示尚未计算过。

状态转移方程推导：

我们有三种钞票：1、5、11 元。

我们考虑金额 i 时，它可能是由以下几种方式得到的：

• 从 i-1 元加上一张 1元 的钞票。
• 从 i-5 元加上一张 5元 的钞票（前提是 i ≥ 5）。
• 从 i-11 元加上一张 11元 的钞票（前提是 i ≥ 11）。

所以我们有状态转移方程：

$dp[i] = \min(dp[i-1] + 1,\ dp[i-5] + 1,\ dp[i-11] + 1)$

当然，i-5 和 i-11 必须 ≥ 0。

这就是完全背包的标准套路：用物品来更新状态，每个状态都由更小的状态转移而来。

最终答案：

$dp[n]$

时间复杂度解析

• 时间复杂度：$O(n)$，每个金额只被遍历一次，常数为 3。
• 空间复杂度：$O(n)$，用了一个一维数组 dp 存状态。

代码演示

#include <bits/stdc++.h>
using namespace std;

const int INF = 2e6 + 10; // 初始大值
int dp[2000010]; // 注意范围要比 n 大一点

int main() {
    int n;
    cin >> n;

    // 初始化
    for (int i = 1; i <= n; ++i) dp[i] = INF;
    dp[0] = 0; // 凑出0元不需要钞票

    for (int i = 1; i <= n; ++i) {
        // 使用1元钞票
        dp[i] = min(dp[i], dp[i - 1] + 1);
        // 使用5元钞票
        if (i >= 5) dp[i] = min(dp[i], dp[i - 5] + 1);
        // 使用11元钞票
        if (i >= 11) dp[i] = min(dp[i], dp[i - 11] + 1);
    }

    cout << dp[n] << endl;
    return 0;
}

---

数字金字塔问题

题目大意

给定一个数字金字塔，共有 n 行，每行包含对应数量的正整数。
从金字塔顶端出发，每一步可以向左下方或右下方移动，求路径上数字和的最大值。

题意分析

这是一个经典的二维动态规划问题。

• 从顶部到底部的路径有很多条，但每一步只能往左下或右下走。
• 需要找到一条路径，使得路径上的数字和最大。

解题思路

状态定义

设 dp[i][j] 表示从顶端到第 i 行第 j 个数字位置的最大路径和。

状态转移

对于第 i 行第 j 个数字，它可以从上一行的两个位置转移而来：

• dp[i-1][j-1] （左上方）
• dp[i-1][j] （右上方）

因此，

$dp[i][j] = \text{value}[i][j] + \max(dp[i-1][j-1], dp[i-1][j])$

其中，dp[i-1][j-1] 和 dp[i-1][j] 需合法存在。

边界条件

• 顶点：dp[1][1] = value[1][1]
• 对于每一行的第一个和最后一个元素，只能从一个位置转移。

最终答案

最后一行 dp[n][j] 的最大值就是所求路径最大和。

---

时间复杂度和空间复杂度

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n^2)$，可以优化成 $O(n)$（只保留上一行数据）

---

代码演示

#include <bits/stdc++.h>
using namespace std;
int value[1010][1010], dp[1010][1010];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> value[i][j];
        }
    }

    dp[1][1] = value[1][1];

    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (j == 1) {
                // 每行第一个只能从上一行第一个转移
                dp[i][j] = dp[i-1][j] + value[i][j];
            } else if (j == i) {
                // 每行最后一个只能从上一行最后一个转移
                dp[i][j] = dp[i-1][j-1] + value[i][j];
            } else {
                // 其他位置可从左上和右上中取最大
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + value[i][j];
            }
        }
    }

    int ans = 0;
    for (int j = 1; j <= n; j++) {
        ans = max(ans, dp[n][j]);
    }
    cout << ans << "\n";

    return 0;
}

传球游戏

题目大意

有 $n$ 个同学围成一个圆圈，编号从 $1$ 到 $n$。球从编号为 $1$ 的同学开始传，传球规则是每次只能传给左右相邻的同学（即球可以传给当前同学的左边或右边）。问传了 $m$ 次球后，球又回到编号为 $1$ 的同学，有多少种不同的传球方法。

两种传球方法被认为不同当且仅当球的传递顺序（即每次接球的同学编号组成的序列）不同。

题意分析

• 圆圈中每个同学都有两个邻居：左邻居和右邻居。
• 起点固定是同学 $1$。
• 传球 $m$ 次后回到同学 $1$，计算所有可能的传球路径数。
• 因为路径顺序不同即为不同方法，所以统计所有符合条件的路径数量。

解题思路

使用动态规划（DP）模拟传球过程：

定义状态：

• $dp[i][j]$：表示传球进行了 $i$ 次，球现在在编号为 $j$ 的同学手中的方法数。

状态转移：

• 因为每次只能传给左右邻居，所以

  $dp[i][j] = dp[i-1][left(j)] + dp[i-1][right(j)]$

  其中，左邻居 $left(j) = j-1$（若 $j=1$，则左邻居是 $n$），右邻居 $right(j) = j+1$（若$j=n$，则右邻居是 $1$）。

初始条件：

• $dp[0][1] = 1$，因为传球开始时球在同学 $1$ 手中，且传球次数为 0。

目标：

• 计算 $dp[m][1]$，即传球了 $m$ 次后球回到同学 $1$ 的方法数。

时间复杂度分析

• 状态数量为 $m \times n$，
• 每次转移花费 $O(1)$ 时间，
• 总时间复杂度为 $O(mn)$，满足题目要求。

代码演示

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    // dp[i][j]: 传球i次，球在j号同学手中时的方法数
    long long dp[31][31] = {0};

    dp[0][1] = 1; // 起点，传0次球时球在1号手中

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int left = j - 1 == 0 ? n : j - 1; // 左邻居
            int right = j + 1 == n + 1 ? 1 : j + 1; // 右邻居
            dp[i][j] = dp[i-1][left] + dp[i-1][right];
        }
    }

    cout << dp[m][1] << "\n";

    return 0;
}

---

奶牛分群

题目大意

有 $N$ 头奶牛组成一个群，群体可能在三岔路口分裂。分裂条件是：如果群体能恰好分成两部分，且这两部分奶牛数目相差为 $K$，则分裂成两个群，否则不分裂。问最终会有多少群奶牛静静吃草。

题意分析

• 传入当前奶牛数 $x$。
• 判断是否满足分裂条件：
  • $x > K$，且 $(x - K)$ 是偶数；
  • 否则不分裂，返回1表示当前群数。
• 满足条件则分裂为两个群，大小分别为 $\frac{x - K}{2}$ 和 $\frac{x + K}{2}$。
• 递归求两个子群的最终群数之和。

解题思路

用递归实现，核心逻辑是：

1. 判断当前奶牛数是否满足分裂条件。
2. 不满足直接返回1。
3. 满足则递归求左右两部分的群数。
4. 返回左右部分群数之和。

代码演示

#include <bits/stdc++.h>
using namespace std;

int n, k;

int dfs(int x) {
    // 不能分裂的条件
    if (x <= k || (x - k) % 2 == 1) {
        return 1;
    }
    // 分裂成两部分递归求解
    return dfs((x - k) / 2) + dfs((x + k) / 2);
}

int main() {
    cin >> n >> k;
    cout << dfs(n) << "\n";

    return 0;
}

---

国王的魔镜

题目大意

国王有一个魔镜，每次将项链的一端接触镜面，会使整条项链复制一份翻转后的副本并接在原项链尾部。

例如，初始为 $AB$：

• 第一次镜像后：$AB \rightarrow ABBA$
• 第二次镜像后：$ABBA \rightarrow ABBAABBA$
• 第三次镜像后：$ABBAABBA \rightarrow ABBAABBAABBAABBA$

给定最终的字符串，求最初可能的最短项链长度。

---

题意分析

观察发现，每次操作是将字符串翻转后接在原串末尾：

• 设初始字符串为 $S_0$，长度为 $l$；
• 镜像一次：$S_1 = S_0 + \text{rev}(S_0)$，长度 $2l$；
• 镜像两次：$S_2 = S_1 + \text{rev}(S_1)$，长度 $4l$；
• 依此类推，最终长度为 $L = l \cdot 2^k$；

题目给定的是一个最终结果 $S$，我们需要从 $S$ 中还原出最初的项链，即找出最短的字符串 $s$，使得不断镜像可以构造出原串。

---

解题思路

从题目定义反向思考：

每次镜像形成的是：$S \rightarrow S + \text{rev}(S)$。

因此原串可以每次都从中间折半检查是否回文对称，如果是，则可能是某一次镜像的结果，可以继续还原。

我们采用如下策略：

1. 当前字符串长度为 $L$；
2. 判断前一半 $S[0, L/2 - 1]$ 是否等于后一半的翻转；
   • 即：$S[0, L/2 - 1] == \text{rev}(S[L/2, L - 1])$；
3. 若成立，说明这个串是由 $L/2$ 长度的字符串镜像而来，继续向下处理；
4. 否则，无法继续折叠，当前字符串即为最短原始项链。

---

时间复杂度分析

• 每次字符串长度减半，共最多 $\log_2 n$ 次；
• 每次比较一半的字符串是否为翻转，代价 $O(n)$；
• 总体时间复杂度为 $\boxed{O(n)}$，因为每个字符最多比较一次。

---

代码演示

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string s;
    cin >> s;
    while (true) {
        int len = s.size();
        if (len % 2 != 0) break; // 奇数长度不能镜像产生
        string left = s.substr(0, len / 2);
        string right = s.substr(len / 2);
        reverse(right.begin(), right.end());
        if (left == right) {
            s = left; // 说明这是镜像产生的结果，继续还原
        } else {
            break;
        }
    }
    cout << s.size() << endl;
    return 0;
}

zzc 种田

---

题目大意

给定一个长为 $x$、宽为 $y$ 的矩形田地，每次可以种一个正方形区域，体力消耗等于这个正方形的周长，不能重叠种地。

求：种满这块矩形田地的最小体力值总和。

---

题意分析

体力消耗 = 所种正方形周长总和，而每次种的正方形不能重复、不能重叠，我们的目标是用若干个不重叠的正方形，完全铺满 $x \times y$ 的矩形，使得总周长最小。

关键思路：递归 + 贪心

从 $x \times y$ 这块田开始，每次都贪心种一个最大的正方形（边长为 $\min(x, y)$）：

• 体力消耗：$4 \times \min(x, y)$（周长）
• 然后剩下一个矩形：$(x - \min(x, y)) \times y$ 或 $x \times (y - \min(x, y))$
• 不断递归处理剩余的区域

---

解题思路

这是一个经典的「矩形划分为若干个不重叠正方形的最优分割问题」，我们用如下策略：

1. 每次从矩形中剪去最大的正方形（边长 $= \min(x, y)$）
2. 记录它的周长：$4 \times \min(x, y)$
3. 然后继续对剩余的矩形递归
4. 终止条件：$x = 0$ 或 $y = 0$

注意：数据范围极大，$x, y \leq 10^{16}$，所以不能暴力模拟，必须使用 long long 类型，且每步必须贪心取最大正方形。

---

时间复杂度分析

每一步减少 $\min(x, y)$ 的倍数次，相当于模拟欧几里得算法，复杂度为 $\mathcal{O}(\log \min(x, y))$。

---

代码实现

#include <iostream>
using namespace std;

typedef long long ll;

ll solve(ll x, ll y) {
    if (x == 0 || y == 0) return 0;
    if (x < y) swap(x, y);
    // 在 x * y 里最多可以放 x / y 个 y * y 的正方形
    return (x / y) * y * 4 + solve(x % y, y);
}

int main() {
    ll x, y;
    cin >> x >> y;
    cout << solve(x, y) << endl;
    return 0;
}

蛋糕

---

题目大意

有 $n$ 个长方形蛋糕，第 $i$ 个蛋糕的尺寸为 $H_i \times W_i$（长和宽为整数）。
现在有 $k$ 个人，每人要分到一块 面积相同的正方形蛋糕，且正方形的边长必须是整数。

要求求出能分到的正方形蛋糕的最大可能边长。

---

题意分析

约束条件：

1. 切出来的所有正方形边长相同；
2. 每个人得到一块（总共至少切出 $k$ 块）；
3. 边长必须是整数。

关键问题：

• 给定一个正方形边长 $len$，如何判断能否切出至少 $k$ 块？
• 如果能切出来，则尝试更大的边长；如果不能，则尝试更小的边长。

这就是典型的二分答案思路。

---

解题思路

1. 判断函数 check(len)
   对于每个蛋糕 $H_i \times W_i$：

   • 能切出的正方形个数是：

     $\left\lfloor \frac{H_i}{len} \right\rfloor \times \left\lfloor \frac{W_i}{len} \right\rfloor$

   • 累加所有蛋糕的个数，如果总和 $\ge k$，则表示边长 $len$ 可行。

2. 二分搜索边长

   • 左边界 $l = 1$（最小可能的边长）；
   • 右边界 $r = \max(H_i, W_i)$（最大可能的边长）；
   • 二分过程中：
     • 如果 check(mid) 为真，说明可以切得更大，$l = mid + 1$；
     • 否则缩小，$r = mid - 1$；
   • 最终答案是最大的可行边长。

---

时间复杂度分析

• 每次 check 需要遍历 $n$ 个蛋糕，复杂度 $O(n)$；
• 二分次数是 $O(\log \max(H_i, W_i)) \approx O(\log 10^5) \approx 17$；
• 总复杂度 $O(n \log M)$，其中 $M = \max(H_i, W_i)$；
• 在 $n \le 10^5$ 范围内可轻松运行。

---

代码实现

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

int n, k;
int H[100005], W[100005];

// 检查是否能切出至少 k 块边长为 x 的正方形
bool check(int x) {
    LL cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt += 1LL * (H[i] / x) * (W[i] / x);
        if (cnt >= k) return true; // 提前终止
    }
    return cnt >= k;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> H[i] >> W[i];

    int l = 1, r = 1e5, ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid; // 尝试更大的边长
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    cout << ans << '\n';
    return 0;
}

小苹果

题目大意

桌上有 $n$ 个编号为 $1$ 到 $n$ 的苹果排成一列。每天，小苞从当前序列的第一个苹果开始，按“拿一个苹果，跳过两个苹果，拿一个苹果，跳过两个苹果……”的规则拿走苹果，被拿走的苹果移除，剩余的苹果重新排列。问：

• 多少天后所有苹果被拿完？
• 编号为 $n$ 的苹果是哪一天被拿走的？

题意分析

• 每天的规则是从序列左侧第一个苹果开始，间隔两苹果拿一个，即序列中位置为 $pos$ 满足 $pos \equiv 1 \pmod{3}$ 的苹果当天被拿走。
• 被拿走的苹果被移除，剩余的苹果重新排列，继续下一天。
• 需要求编号 $n$ 的苹果被拿走的天数，以及所有苹果被拿完所需天数。

解题思路

• 观察到每天被拿走的苹果在当前序列中的位置是 $1, 4, 7, 10, \ldots$，即位置为 $pos \equiv 1 \pmod{3}$。
• 剩余苹果的序号需要转换到下一天的位置。
• 编号为 $n$ 的苹果被拿走的天数即为它经过若干次“剩余序号变换”后，首次出现在位置 $pos \equiv 1 \pmod{3}$ 的天数。
• 总天数是所有苹果被拿完的天数，即编号 $n$ 苹果被拿走的天数。

基于以上，我们用循环模拟这个“位置更新”过程：

• 初始化天数 $sum=0$。

• 每次循环：

  • 天数加一。

  • 判断当前苹果编号是否满足当天被拿的条件 $n$。

  • 计算下一天编号更新：

    $n = n - \frac{n-1}{3} - 1$

  • 直到 $n$ 减至 0（即苹果被拿完）。

复杂度分析

• 每天苹果数量减少大约三分之一，循环次数最多约为 $\log_{1.5}(n)$，效率非常高，适合 $n$ 高达 $10^9$。

代码实现

#include <iostream>
using namespace std;

int main() {
    freopen("apple.in", "r", stdin);
    freopen("apple.out", "w", stdout);

    int n;
    cin >> n;
    int sum = 0;  // 天数计数
    int ans = 0;  // 编号为 n 的苹果被拿走的天数
    bool flag = false;  // 标记是否已找到编号为 n 的苹果被拿走的天数

    int cur = n;  // 当前编号，初始为输入 n

    while (cur > 0) {
        sum++;  // 新的一天
        if (cur % 3 == 1 && !flag) {
            ans = sum;  // 编号 n 的苹果当天被拿走
            flag = true;
        }
        // 更新编号，进入下一天的序列位置
        cur = cur - (cur - 1) / 3 - 1;
    }

    cout << sum << " " << ans << "\n";

    fclose(stdin);
    fclose(stdout);
    return 0;
}

二叉树最近公共祖先（暴力版）

题目大意

给定一个用数组表示的二叉树，根节点下标为 1。
节点下标 $x$ 的左孩子是 $2x$，右孩子是 $2x+1$（若存在）。
需要对 $q$ 次查询，给定两个节点编号 $id_1, id_2$，求它们的最近公共祖先（LCA）节点编号。

题意分析

• 节点编号即数组下标，表示树结构。
• 最近公共祖先定义为两个节点的公共祖先中离根最近的那个节点。
• 这里是完全二叉树（虽然节点可能不满），节点父节点编号为 $\lfloor x/2 \rfloor$。
• 目标是快速求多个节点对的 LCA。

解题思路

• 对于任意两个节点 $u, v$，不断将编号较大的节点上移其父节点（$x \to \lfloor x/2 \rfloor$），直到两者相等为止。
• 该公共节点即为 LCA。
• 这是利用二叉树性质，父节点编号为 $\lfloor x/2 \rfloor$，向上跳到同一深度再相等即可。
• 时间复杂度均摊较高，但对于 $q \leq 10^5$，且编号最大 $n \leq 10^5$，暴力方法可行。

复杂度分析

• 每次查询最坏情况跳转 $\log n$ 次，$q$ 次查询共 $O(q \log n)$，符合题目要求。

代码实现

#include <iostream>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;

    // 读入节点值，但题目只要求输出节点编号，不用用到值
    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
    }

    while (q--) {
        int u, v;
        cin >> u >> v;

        // 将较大节点上移，直到两个节点相同
        while (u != v) {
            if (u > v) u /= 2;
            else v /= 2;
        }
        cout << u << "\n";
    }

    return 0;
}

逃离迷宫

题目大意

给定一个 $M \times N$ 的迷宫地图，其中：

• @ 表示起点位置；
• . 表示可以通行的安全格子；
• # 表示有陷阱，不能通行；
• * 表示宝物位置。

要求从起点出发，经过最少的格子数（包含起点），找到宝物。如果无法到达宝物，输出 -1。

输入包含多组数据，以 0 0 结束。

题意分析

• 迷宫由多个格子组成，起点和宝物各唯一。
• 需要在迷宫中找到从起点到宝物的最短路径长度。
• 路径只能经过安全格子（. 和 @ 起点），不能经过陷阱格子（#）。
• 典型的迷宫最短路径问题，适合用 广度优先搜索（BFS）。

解题思路

• 使用 BFS 从起点开始搜索。
• 队列中保存当前坐标和走过的步数。
• 遍历四个方向（上下左右），只访问没有访问过且安全的格子。
• 如果找到宝物，输出当前步数。
• BFS 结束仍未找到宝物，输出 -1。

时间复杂度

• BFS 最多遍历 $M \times N$ 个格子，每个格子最多访问一次。
• 时间复杂度为 $O(M \times N)$。
• $M, N \leq 20$，效率足够。

代码实现

#include<iostream>
#include<algorithm>
#include<iomanip>
#include<queue>
#define ll long long
using namespace std;

// 定义节点结构体，包含位置坐标和当前步数
struct node
{
    int x, y, step;
};

int n, m;                      // 迷宫行数和列数
int vis[1010][1010];           // 访问标记数组
char a[1010][1010];            // 迷宫地图字符数组

// 4个方向移动向量：下，上，右，左
int dir[4][2] = { {1,0}, {-1,0}, {0,1}, {0,-1} };

// BFS函数，从(x,y)开始，目标坐标为(fx, fy)
int bfs(int x, int y, int fx, int fy)
{
    queue<node> q;
    q.push({x, y, 0});       // 起点步数计为1，包含起点所在格子
    vis[x][y] = 1;

    while(!q.empty())
    {
        node now = q.front();
        q.pop();

        // 到达目标宝物格
        if(now.x == fx && now.y == fy)
        {
            return now.step;   // 返回经过的格子数
        }

        // 遍历4个方向
        for(int i = 0; i < 4; i++)
        {
            int dx = now.x + dir[i][0];
            int dy = now.y + dir[i][1];

            // 判断边界并且未访问且为可通行格（'.'或'*'或'@'）
            if(dx >=1 && dx <= n && dy >= 1 && dy <= m)
                if(!vis[dx][dy] && (a[dx][dy] == '.' || a[dx][dy] == '*' || a[dx][dy] == '@'))
                {
                    q.push({dx, dy, now.step + 1});
                    vis[dx][dy] = 1;
                }
        }
    }
    // 未找到宝物
    return -1;
}

int main()
{
    while(true)
    {
        cin >> n >> m;
        if(n == 0 && m == 0) break;

        int sx = -1, sy = -1, tx = -1, ty = -1;  // 起点和终点坐标

        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                cin >> a[i][j];
                if(a[i][j] == '@')
                {
                    sx = i; sy = j;
                }
                else if(a[i][j] == '*')
                {
                    tx = i; ty = j;
                }
                vis[i][j] = 0; // 初始化访问数组
            }
        }

        int ans = bfs(sx, sy, tx, ty);
        cout << ans << "\n";
    }

    return 0;
}

逃离迷宫2

题目大意

给定一个 $n \times m$ 的迷宫，由空地 . 和障碍物 # 组成。
要求从左上角格子 $(1,1)$ 走到右下角格子 $(n,m)$，输出最短路径步数（每步移动到上下左右相邻格子），如果无法到达输出 -1。

题意分析

• 迷宫格子小（$n,m \leq 10$），可用 DFS 搜索所有路径，找出最短路径。
• 每次 DFS 递归尝试四个方向，剪枝避免重复访问。
• 记录最短步数。
• 起点终点必为通路，保证有效起点和终点。

解题思路

• 使用 DFS 深度优先搜索遍历所有可能路径。
• 维护访问标记数组 vis，防止走回头路导致死循环。
• 当走到终点时，更新当前路径长度最小值。
• 最终输出最短路径长度或 -1。

时间复杂度

• DFS 最坏情况下搜索全部空地格，格子数最多为 $n \times m \leq 100$，复杂度约为 $O(4^{n \times m})$，但实际由于剪枝访问且网格较小，运行可接受。
• 适合小规模迷宫。

代码实现

#include <iostream>
using namespace std;

int n, m;
char a[50][50];         // 迷宫地图
int vis[50][50];        // 访问标记数组
int dir[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0} };  // 四个方向：右，下，左，上
int step = 0xfffffff;   // 最短步数初始为一个很大数
int found = 0;          // 标记是否找到路径

// 判断坐标是否在迷宫范围内
int inmap(int x1, int y1)
{
    return x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= m;
}

// DFS搜索路径，(x,y)为当前位置，st为当前路径步数
void dfs(int x, int y, int st)
{
    // 到达终点
    if(x == n && y == m)
    {
        found = 1;           // 标记找到路径
        if(st < step) step = st;  // 更新最短路径
        return;
    }

    for(int i = 0; i < 4; i++)
    {
        int x1 = x + dir[i][0];
        int y1 = y + dir[i][1];
        // 如果位置合法且未访问且是通路
        if(inmap(x1, y1) && a[x1][y1] == '.' && !vis[x1][y1])
        {
            vis[x1][y1] = 1;      // 标记访问
            dfs(x1, y1, st + 1);  // 递归搜索
            vis[x1][y1] = 0;      // 回溯，撤销访问标记
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
        }
    }

    vis[1][1] = 1;       // 起点标记访问
    dfs(1, 1, 0);        // 从起点开始搜索，步数0

    if(found)
        cout << step << "\n";  // 输出最短步数
    else
        cout << -1 << "\n";    // 无路径输出-1

    return 0;
}

【DFS】八皇后问题

题目大意

给定一个 $n \times n$ 的棋盘，要求放置 $n$ 个棋子，使得：

• 每行恰好一个棋子；
• 每列恰好一个棋子；
• 每条对角线上最多一个棋子（包括主对角线及所有平行对角线）；

输出所有满足条件的放置方案，方案以行号从1到$n$表示，序列中第$i$个数字表示第$i$行棋子所在的列号。

要求按字典序输出前三个解，并输出所有解的总数。

题意分析

• 本题即经典的 $n$ 皇后问题变种。
• 约束条件保证每行列和两条对角线不能有重复棋子。
• 利用 DFS 回溯，逐行放置棋子，遇冲突则回溯。

解题思路

• 使用三个布尔数组分别标记列、主对角线、副对角线是否已被占用：
  • dy[i]：第 $i$ 列是否有棋子。
  • add[i+x]：主对角线标记。这里 $i+x$ 保证从左上到右下的对角线索引唯一。
  • minu[i - x + n]：副对角线标记。这里偏移 $+n$ 避免负数索引。
• 每行从列1到$n$尝试放置，若未冲突则递归放下一行。
• 每找到一个合法解，计数器加一，并在前三个解时输出。
• 最终输出总解数。

复杂度分析

• 该算法最坏情况下时间复杂度约为 $O(n!)$，因需要枚举排列。
• 对于 $n \leq 13$，回溯剪枝可接受。

代码实现

#include <iostream>
using namespace std;

int n;
int a[20];           // 存放每行棋子所在列
int dy[20] = {0};    // 列占用标记
int add[40] = {0};   // 主对角线占用标记
int minu[40] = {0};  // 副对角线占用标记
int ans = 0;         // 记录解的数量

void dfs(int x) {
    if (x == n + 1) {
        ans++;
        if (ans <= 3) {
            for (int i = 1; i <= n; i++) {
                cout << a[i] << (i == n ? '\n' : ' ');
            }
        }
        return;
    }

    for (int i = 1; i <= n; i++) {
        // 判断列和两个对角线是否被占用
        if (dy[i] || add[i + x] || minu[i - x + n]) continue;
        // 标记占用
        dy[i] = add[i + x] = minu[i - x + n] = 1;
        a[x] = i;
        dfs(x + 1);
        // 回溯撤销标记
        dy[i] = add[i + x] = minu[i - x + n] = 0;
    }
}

int main() {
    cin >> n;
    dfs(1);
    cout << ans << "\n";

    return 0;
}

神庙迷宫1

题目大意

给定一个 $n \times m$ 的迷宫，起点在左上角 $(1,1)$，终点在右下角 $(n,m)$。
迷宫中 . 表示可通行格子，# 表示障碍物。
判断是否存在路径可以从起点走到终点，只能上下左右移动。

题意分析

• 典型的网格路径搜索问题。
• 需要判断起点是否能通过合法路径达到终点。
• 适合使用广度优先搜索（BFS）遍历迷宫。
• 维护访问数组避免重复访问。

解题思路

• 使用队列实现 BFS，从起点开始搜索可达的相邻通路格子。
• 搜索过程中标记访问。
• 搜索结束后检查终点是否被访问。
• 若访问过输出 YES，否则输出 NO。

复杂度分析

• BFS 最坏遍历全部格子，时间复杂度 $O(n \times m)$，符合题目限制。

代码实现

#include <iostream>
#include <queue>
using namespace std;

char a[110][110];        // 迷宫地图
int vis[110][110];       // 访问标记
int dir[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};  // 上下左右移动

struct node {
    int x, y;
};

int main() {
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    queue<node> q;
    q.push({1, 1});
    vis[1][1] = 1;

    while(!q.empty()) {
        node now = q.front();
        q.pop();

        for(int i = 0; i < 4; i++) {
            int x = now.x + dir[i][0];
            int y = now.y + dir[i][1];

            // 判断坐标合法，未访问且非障碍物
            if(x >= 1 && x <= n && y >= 1 && y <= m && !vis[x][y] && a[x][y] != '#') {
                vis[x][y] = 1;
                q.push({x, y});
            }
        }
    }

    if(vis[n][m]) cout << "YES";
    else cout << "NO";

    return 0;
}

神庙迷宫2

题目大意

给定一个 $n \times m$ 的迷宫地图，地图中 . 表示空地可以通行，# 表示障碍物不能通行。
起点为左上角格子 $(1,1)$，终点为右下角格子 $(n,m)$。
要求找出从起点到终点的最短路径长度（包含起点和终点所在格子），如果无法到达输出 -1。

题意分析

• 需要计算网格中两点间最短路径长度。
• 经典的网格 BFS 问题，利用队列层层扩展，记录距离。
• 访问数组 vis 除了标记访问外，也存储当前节点到起点的距离。
• 距离即为从起点到当前格子的步数。

解题思路

• 使用 BFS，从起点开始搜索可达的相邻格子。
• 记录访问并标记距离，距离初始为1（表示起点）。
• 当到达终点，直接输出距离-1（因为起点计为1，但题目要求路径长度一般是步数，即格子数减1）。
• 搜索结束后如果终点未访问，输出 -1。

时间复杂度分析

• BFS 最多访问所有格子一次，时间复杂度为 $O(n \times m)$。
• 适合 $n,m \leq 40$ 的限制。

代码实现

#include <iostream>
#include <queue>
using namespace std;

char a[110][110];           // 迷宫地图
int vis[110][110];          // 访问及距离数组
int dir[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};  // 上下左右四个方向

struct node {
    int x, y;
};

int main() {
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
            vis[i][j] = 0;  // 初始化访问距离数组
        }
    }

    queue<node> q;
    q.push({1, 1});
    vis[1][1] = 1;   // 起点距离记为1

    while(!q.empty()) {
        node now = q.front();
        q.pop();

        for(int i = 0; i < 4; i++) {
            int x = now.x + dir[i][0];
            int y = now.y + dir[i][1];

            // 判断合法、未访问且可通行
            if(x >= 1 && x <= n && y >= 1 && y <= m && !vis[x][y] && a[x][y] == '.') {
                vis[x][y] = vis[now.x][now.y] + 1;
                q.push({x, y});
            }
        }
    }

    if(vis[n][m]) cout << vis[n][m] - 1 << "\n";  // 输出最短路径长度
    else cout << -1 << "\n";                       // 无法到达输出-1

    return 0;
}

神庙迷宫3

题目大意

给定一个 $n \times m$ 的迷宫地图，. 表示空地，# 表示障碍。
起点为左上角 $(1,1)$，求每个格子到起点的最短距离（步数）。
若该格子不可达或为障碍，则输出 -1。
输出整个迷宫对应的距离矩阵。

题意分析

• 需要求从起点到每个格子的最短距离，属于多源最短路中的单源多点问题。
• 适用广度优先搜索（BFS）完成。
• BFS从起点扩展，vis[i][j]记录距离（步数+1，方便处理）。
• 访问障碍物不计距离且不可通行。
• BFS结束后，对于未访问的格子（vis[i][j]==0），输出 -1。

解题思路

• 初始化 vis 数组为0，表示未访问。
• 起点 vis[1][1]=1，距离起点为0。
• 使用队列实现 BFS，依次扩展相邻四个方向。
• 如果新位置合法且非障碍且未访问，更新距离并入队。
• BFS结束后，遍历输出距离矩阵，未访问格子输出 -1。

复杂度分析

• BFS遍历所有格子一次，时间复杂度 $O(n \times m)$。
• 适用于 $n, m \leq 1000$ 的规模。

代码实现

#include <iostream>
#include <queue>
using namespace std;

char a[1010][1010];
int vis[1010][1010];    // 记录距离+1，0表示未访问
int dir[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};

struct node {
    int x, y;
};

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
            vis[i][j] = 0;  // 初始化
        }
    }

    queue<node> q;
    if(a[1][1] == '.') {  // 起点必须可通行
        q.push({1, 1});
        vis[1][1] = 1;    // 距离起点为0，但vis标记为1方便区分未访问
    }

    while(!q.empty()) {
        node now = q.front();
        q.pop();

        for(int i = 0; i < 4; i++) {
            int x = now.x + dir[i][0];
            int y = now.y + dir[i][1];

            if(x >= 1 && x <= n && y >= 1 && y <= m && !vis[x][y] && a[x][y] == '.') {
                vis[x][y] = vis[now.x][now.y] + 1;
                q.push({x, y});
            }
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(vis[i][j]) cout << vis[i][j] - 1 << " ";
            else cout << -1 << " ";
        }
        cout << "\n";
    }

    return 0;
}