贪心入门

题意概括

给定一系列特殊重量的月饼，重量分别为 20,21,22,…2^0, 2^1, 2^2, \dots 克，每种重量的月饼只有一个。我们需要选择吃掉一些月饼，要求满足吃掉的总重量 WW 在 [A,B][A, B] 这个闭区间内。目标是最大化吃掉的月饼的数量。

数据范围：1≤A,B≤263−11 \le A, B \le 2^{63}-1。

基础知识

本题的核心思想是贪心算法 (Greedy Algorithm) 与 位运算 (Bitwise Operations)。

  1. 二进制表示：题目中月饼的重量都是2的幂次方，这强烈暗示了问题和数字的二进制表示有关。任何一个正整数都可以被唯一地表示为一些不同的2的幂次方的和。例如，13=8+4+1=23+22+2013 = 8+4+1 = 2^3+2^2+2^0。在二进制中，1313 就是 110121101_2。

  2. 问题转化：选择吃掉总重量为 WW 的月饼，等价于选择 WW 的二进制表示中为 '1' 的那些位所对应的月饼。因此，吃掉的月饼数量就是整数 WW 在二进制表示下 '1' 的个数。这个问题在C++中可以通过 __builtin_popcountll() 函数高效计算。

  3. 贪心策略：问题最终转化为：在区间 [A,B][A, B] 内寻找一个整数 WW，使其二进制表示中 '1' 的个数最多。 为了使 '1' 的数量最大化，我们可以采用贪心策略。一个自然的想法是，从下限 AA 开始，尝试通过最少的重量增加来换取一个额外的月饼。 具体来说，我们应该优先选择吃最轻的、目前还没吃的月饼。在二进制位上，这就对应着将一个为 '0' 的位翻转成 '1'。为了使总重量的增加量最小，我们应该从最低位（第0位）开始尝试。

    算法流程：

    • 令当前的总重量 WW 初始化为 AA。
    • 从低到高遍历 WW 的二进制位（例如，从第 0 位到第 62 位）。
    • 如果当前第 ii 位是 '0'，我们尝试将其变为 '1'。这相当于多吃一个重量为 2i2^i 的月饼。
    • 新的总重量将是 W′=W∣(1LL≪i)W' = W | (1LL \ll i)。
    • 我们检查这个新的总重量是否超过上限 BB。如果 W′≤BW' \le B，说明这个操作是允许的。我们就接受这次改变，令 W=W′W = W'。
    • 遍历完所有位后，最终得到的 WW 就是在 [A,B][A, B] 区间内，由 AA 通过贪心策略能达到的 '1' 最多的数。它的 popcount 值即为答案。

C++ 代码实现

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll a, b;
    cin >> a >> b;

    // 贪心策略：从A开始，从低位到高位尝试将0变为1
    // 只要不超过B，就进行变换
    for (int i = 0; i < 63; ++i) {
        // 检查第i位是否为0
        if (!((a >> i) & 1)) {
            ll tmp = a | (1LL << i); // 尝试将第i位置1
            
            // 如果新的值没有超过B，就采纳这个变化
            if (tmp <= b) {
                a = tmp;
            }
        }
    }

    // GCC内置函数，用于计算long long类型数在二进制表示下1的个数
    cout << __builtin_popcountll(a) << endl;

    return 0;
}

搜索

题意概括

在一个 3×33 \times 3 的棋盘上，有八个标有数字 11 到 88 的棋子和一个空格（用 00 表示）。任何与空格相邻的棋子都可以移动到空格位置。问题要求从一个给定的初始状态，通过最少的移动次数，达到目标状态 123804765。题目保证所有测试数据均有解。

输入：一个包含 0−80-8 九个数字的字符串，表示初始状态。 输出：一个整数，表示最少移动步数。

基础知识

本题是典型的状态空间搜索问题，求解最短路径，最适合的算法是广度优先搜索 (Breadth-First Search, BFS)。

  1. 状态表示： 我们可以将 3×33 \times 3 棋盘的布局“压平”成一个长度为 9 的字符串或一个整数来表示一个状态。例如，目标状态 123804765 对应棋盘：

    1 2 3
8 0 4
7 6 5

  2. 状态转移： 当空格与相邻棋子交换位置时，就完成了一次状态转移。整个问题可以看作一个巨大的状态图，每个状态是一个节点，每次移动是连接两个节点的一条边。我们的目标就是在这个图中寻找从 初始状态 节点到 目标状态 节点的最短路径。

  3. 广度优先搜索 (BFS)： BFS 是一种用于图的遍历算法，它从根节点开始，逐层地探索邻近节点。由于它是一层一层地进行搜索，因此当它第一次找到目标节点时，所经过的路径必然是所有路径中最短的（在边权为1的情况下）。这完美契合了本题“最少移动次数”的要求。

  4. 判重 (Hashing / Visited Set)： 在搜索过程中，可能会反复遇到同一个状态。为了避免陷入死循环和进行不必要的计算，我们需要一个机制来记录已经访问过的状态。这里可以使用 C++ STL 中的 map 或 unordered_map，将字符串表示的状态映射到一个整数（代表到达该状态的步数），这样既能判重，也能记录步数。

算法流程：

  1. 创建一个队列 q，用于存放待访问的状态。
  2. 创建一个 map<string, int> dis，用于记录从初始状态到任一状态的最短距离，同时兼具判重功能。
  3. 将初始状态 src 放入队列 q，并标记距离为 0 (dis[src] = 0)。
  4. 当队列不为空时，取出队头状态 cur： a. 如果 cur 等于目标状态，则 dis[cur] 就是答案，搜索结束。 b. 否则，找到 cur 中 '0'（空格）的位置。 c. 尝试将空格与其上、下、左、右四个方向的棋子交换，生成新的状态 nxt。 d. 对于每个新状态 nxt，如果它从未被访问过（即在 dis 中没有记录），则将其距离记为 dis[cur] + 1，并将其加入队列。
  5. 重复步骤 4 直至找到目标。

C++ 代码实现

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string src;
    cin >> src;

    string tar = "123804765";
    
    queue<string> q;
    map<string, int> dis;

    q.push(src);
    dis[src] = 0;

    // 方向数组，方便进行上下左右移动
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};

    while (!q.empty()) {
        string cur = q.front();
        q.pop();

        int d = dis[cur];
        if (cur == tar) {
            cout << d << endl;
            return 0;
        }
        
        // 找到'0'的位置
        int z = cur.find('0');
        int x = z / 3; // 转换为二维坐标
        int y = z % 3;

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 检查新位置是否越界
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                string nxt = cur;
                swap(nxt[z], nxt[nx * 3 + ny]); // 移动棋子
                
                // 如果是新状态，则记录距离并入队
                if (dis.find(nxt) == dis.end()) {
                    dis[nxt] = d + 1;
                    q.push(nxt);
                }
            }
        }
    }

    return 0;
}

Flood FIll

题意概括

在一个 x×yx \times y 的二维字符网格中，* 代表墙壁，0 代表重要区域。洪水会从网格的边界涌入，所有与边界联通的 0 区域（包括边界上的 0）都会被淹没。水流可以从一个 0 移动到上下左右相邻的另一个 0。求最终没有被洪水淹没的重要区域 (0) 的数量。

数据范围: 1≤x,y≤5001 \le x, y \le 500。

基础知识

本题的核心是判断哪些区域与外界（即网格边界）是连通的。这是一个典型的图论中的连通性问题，可以使用广度优先搜索 (BFS) 或深度优先搜索 (DFS) 来解决。

算法思路:

  1. 将整个网格看作一个图，每个 0 是一个节点，相邻的 0 之间有一条边。
  2. 所有位于网格边界上的 0 都是最初被洪水淹没的源头。
  3. 从所有这些边界上的 0 开始进行图遍历（BFS 或 DFS），将所有能访问到的 0 节点都标记为“被淹没”。
  4. 遍历完成后，统计网格中所有未被标记的 0 的数量，即为所求的答案。这种方法被称为“反向思考”，我们不去寻找被包围的，而是标记所有未被包围的，剩下的就是答案。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int x, y;
char g[505][505];
bool vis[505][505];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void bfs(int r, int c) {
    queue<pair<int, int>> q;
    q.push({r, c});
    vis[r][c] = true;

    while (!q.empty()) {
        auto [cr, cc] = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i) {
            int nr = cr + dx[i];
            int nc = cc + dy[i];

            // 检查新坐标是否越界或者不合法
            if (nr < 0 || nr >= x || nc < 0 || nc >= y) continue;
            if (vis[nr][nc] || g[nr][nc] == '*') continue;

            vis[nr][nc] = true;
            q.push({nr, nc});
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> x >> y;
    for (int i = 0; i < x; ++i) {
        for (int j = 0; j < y; ++j) {
            cin >> g[i][j];
        }
    }

    // 从所有边界上的 '0' 开始进行BFS，标记所有被淹没的区域
    for (int i = 0; i < x; ++i) {
        if (g[i][0] == '0' && !vis[i][0]) bfs(i, 0);
        if (g[i][y - 1] == '0' && !vis[i][y - 1]) bfs(i, y - 1);
    }
    
    for (int j = 0; j < y; ++j) {
        if (g[0][j] == '0' && !vis[0][j]) bfs(0, j);
        if (g[x - 1][j] == '0' && !vis[x - 1][j]) bfs(x - 1, j);
    }

    int ans = 0;
    // 遍历整个网格，统计未被访问过的 '0'
    for (int i = 0; i < x; ++i) {
        for (int j = 0; j < y; ++j) {
            if (g[i][j] == '0' && !vis[i][j]) {
                ans++;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

image-20250821201627037

倍增

题意概括

给定一个长度为 mm 的数列和 nn 次询问。对于每次询问，需要找出给定区间 [a,b][a, b] 内的最小值。这是一个静态的（即数列中的值不会改变）区间查询问题。

数据范围: 1≤m≤1051 \leq m \leq 10^5, 1≤n≤1051 \leq n \leq 10^5。

基础知识

本题是经典的 静态区间最值查询 (Range Minimum/Maximum Query, RMQ) 问题。对于没有修改操作的区间查询，Sparse Table (ST) 算法 是一个非常高效的标准解决方案。

ST 算法核心思想:

  1. 预处理 (Preprocessing):

    • 我们使用一个二维数组，设为 st[i][j]st[i][j]，它存储的是从数组下标 ii 开始、长度为 2j2^j 的区间的最小值。
    • 该数组可以通过动态规划计算得出。
    • 状态定义: st[i][j]st[i][j] 表示区间 [i,i+2j−1][i, i + 2^j - 1] 的最小值。
    • 基础状态: st[i][0]st[i][0] 就是数列的第 ii 个元素本身。
    • 状态转移方程: 一个长度为 2j2^j 的区间可以看作是两个长度为 2j−12^{j-1} 的子区间的并集。因此，状态转移方程为：$$st[i][j] = \min(st[i][j-1], st[i + 2^{j-1}][j-1]) $$
    • 预处理的时间复杂度为 O(mlog⁡m)O(m \log m)。

  2. 查询 (Query):

    • 对于任意查询区间 [a,b][a, b]，我们可以找到一个最大的整数 kk，使得 2k≤b−a+12^k \le b - a + 1。
    • 我们可以用两个长度为 2k2^k 的区间，即 [a,a+2k−1][a, a + 2^k - 1] 和 [b−2k+1,b][b - 2^k + 1, b]，来完全覆盖查询区间 [a,b][a, b]。
    • 因此，区间 [a,b][a, b] 的最小值就是这两个子区间最小值的较小者：$$\text{query}(a, b) = \min(st[a][k], st[b - 2^k + 1][k]) $$
    • 查询的时间复杂度为 O(1)O(1)。

算法总时间复杂度为 O(mlog⁡m+n)O(m \log m + n)，空间复杂度为 O(mlog⁡m)O(m \log m)，能够轻松解决本题。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// m: 账目数, n: 问题数
int m, n; 

// st[i][j] 存储从第 i 个数开始，长度为 2^j 的区间内的最小值
int st[100005][20]; 

// lg[i] 预处理 log2(i) 的整数部分
int lg[100005];

// 查询区间 [l, r] 的最小值
int ask(int l, int r) {
    int k = lg[r - l + 1];
    return min(st[l][k], st[r - (1 << k) + 1][k]);
}

void pre() {
    // 预处理 log 函数值
    lg[1] = 0;
    for (int i = 2; i <= m; ++i) {
        lg[i] = lg[i / 2] + 1;
    }

    // ST 表的动态规划构建过程
    for (int j = 1; j <= lg[m]; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= m; ++i) {
            st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> m >> n;
    
    // 读入数据，初始化 st 表的基础状态 st[i][0]
    for (int i = 1; i <= m; ++i) {
        cin >> st[i][0];
    }
    
    // 预处理
    pre();

    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        cout << ask(a, b) << (i == n - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

素数筛法

题意概括

给定一个正整数 nn 和 qq 次询问。每次询问输入一个正整数 kk，要求我们输出在 11 到 nn 范围内的第 kk 小的素数。

数据范围: n=108n = 10^8, 1≤q≤1061 \le q \le 10^6，保证查询的素数不大于 nn。

基础知识

本题的数据范围 nn 达到了 10810^8，要求我们必须使用一种高效的算法来预处理出所有范围内的素数。在众多数素筛法中，线性筛（也称欧拉筛）是解决此类问题的理想选择。

线性筛 (Euler Sieve):

线性筛法是一种能在 O(n)O(n) 线性时间内找出 11 到 nn 所有素数的算法。其核心思想是：确保每一个合数都只被它的最小质因子筛掉一次。

算法流程:

  1. 维护一个布尔数组 vis，vis[i] = true 表示 i 是合数。同时，维护一个数组 p 用于存储所有已找到的素数。
  2. 从 22 开始遍历到 nn。
  3. 如果当前数字 i 未被标记 (!vis[i])，则说明 i 是一个素数，将其存入素数数组 p 中。
  4. 不论 i 是否为素数，都用已找到的素数 p[j] 去筛掉 i 的倍数，即标记 vis[i * p[j]] = true。
  5. 最关键的一步: 当 i % p[j] == 0 时，必须立即停止当前轮的筛选 (break)。
    • 原因: 如果 i 是 p[j] 的倍数，那么 p[j] 就是 i 的最小质因子。对于任何一个比 p[j] 更大的素数 p[k]，合数 i * p[k] 的最小质因子仍然是 p[j]。为了遵守“每个合数只被其最小质因子筛掉”的原则，我们必须在此处停止，否则 i * p[k] 将会被 p[k] 筛掉，从而导致重复筛选，算法退化。

解题步骤:

  1. 全局定义 vis 数组和 p 数组以避免栈溢出。vis 大小为 n+1n+1，pp 的大小需要估算，10810^8 内大约有 576 万个素数，开到 600 万比较保险。
  2. 编写一个线性筛函数，预处理出 11 到 nn 的所有素数，并存入 p 数组。
  3. 对于 qq 次查询，每次输入 kk，直接输出 p[k-1]（数组下标从0开始，而题目是第k小）。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 100000001;

// p 存储素数, vis 标记合数, cnt 记录素数个数
int p[6000000];
bool vis[MAXN];
int cnt;

// 线性筛法函数
void sve(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) {
            // i 是素数
            p[cnt++] = i;
        }

        // 遍历已找到的素数来筛掉合数
        for (int j = 0; j < cnt && 1LL * i * p[j] <= n; ++j) {
            vis[i * p[j]] = true;

            // 关键：保证每个合数只被其最小质因子筛掉
            if (i % p[j] == 0) {
                break;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin >> n >> q;

    // 预处理所有素数
    sve(n);

    while (q--) {
        int k;
        cin >> k;
        // 查询的 k 是第 k 小, 对应数组下标 k-1
        cout << p[k - 1] << '\n';
    }

    return 0;
}

深搜

题意概括

要制作一个 MM 层的生日蛋糕，总体积为 NπN\pi。每层都是一个圆柱体，从上到下（设为第 i+1i+1 层到第 ii 层）半径和高度都必须严格增大。目标是设计一个方案，使得蛋糕与空气接触的总表面积 QQ 最小。求 S=Q/πS = Q/\pi 的最小值。

其中，总表面积 QQ 包括所有层的侧面积以及最顶层的顶面积。由于蛋糕是堆叠的，这等价于所有层的侧面积之和，再加上最底层（最大层）的底面积。

设从下往上第 ii 层的半径为 RiR_i，高度为 HiH_i，则：

  1. 体积约束: ∑i=1MRi2Hi=N\sum_{i=1}^{M} R_i^2 H_i = N
  2. 形状约束: Ri>Ri+1R_i > R_{i+1} 且 Hi>Hi+1H_i > H_{i+1} (对于 1≤i<M1 \le i < M)
  3. 优化目标: 最小化 S=R12+∑i=1M2RiHiS = R_1^2 + \sum_{i=1}^{M} 2R_iH_i

数据范围: N≤2×104,M≤15N \le 2 \times 10^4, M \le 15。

基础知识

本题是一个典型的组合优化问题。由于 MM 的值很小（≤15\le 15），我们可以使用 深度优先搜索 (DFS) 结合强大的 剪枝 (Pruning) 策略来寻找最优解。

搜索顺序: 为了方便施加约束，我们从上到下（第 MM 层到第 11 层）来确定每一层的尺寸。假设我们正在确定第 dep 层的半径 RR 和高度 HH，那么它必须满足 R<Rdep+1R < R_{dep+1} 和 H<Hdep+1H < H_{dep+1}。

核心剪枝策略: 设全局最优答案为 ans。在搜索到第 dep 层，已用体积为 VusedV_{used}，已产生的侧面积为 SusedS_{used} 时：

  1. 可行性剪枝 (体积): * 剩下的 depdep 层蛋糕，即使以最小的尺寸（半径和高度分别为 1,2,...,dep1, 2, ..., dep）来制作，也需要一个最小体积。如果剩余待分配的体积 N−VusedN - V_{used} 小于这个最小体积，那么当前方案不可行，剪枝。

  2. 最优性剪枝 (面积):

    • 剪枝 A: 如果当前已产生的侧面积 SusedS_{used} 加上剩下 depdep 层蛋糕可能产生的最小侧面积，就已经超过了当前最优解 ans，那么继续搜索不可能得到更优的解，剪枝。
    • 剪枝 B (更强): 对于剩余体积 VremV_{rem} 和当前层往下的最大半径 RmaxR_{max}，我们可以推导出剩余部分面积的一个更紧的下界。剩余侧面积 ∑2RiHi=∑2Ri(Ri2Hi)\sum 2R_iH_i = \sum \frac{2}{R_i}(R_i^2H_i)。因为之后所有层的半径都小于 RmaxR_{max}，所以 1Ri>1Rmax\frac{1}{R_i} > \frac{1}{R_{max}}。因此，∑2RiHi>2⋅VremRmax\sum 2R_iH_i > \frac{2 \cdot V_{rem}}{R_{max}}。如果 Sused+2⋅VremRmax≥ansS_{used} + \frac{2 \cdot V_{rem}}{R_{max}} \ge ans，则可以剪枝。

  3. 搜索顺序优化:

    • 在枚举当前层的半径和高度时，从大到小进行枚举。这是一种启发式策略，倾向于先搜索约束更强、可能更优的分支，从而可以更快地更新 ans，让最优性剪枝更早、更频繁地生效。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n, m;
int ans = 1e9; // 初始化答案为一个极大值

// minv[i] 和 mins[i] 分别表示 i 层蛋糕所需的最小体积和最小侧面积
int minv[20];
int mins[20];

// dep: 当前层数(从 m 向下到 1)
// rv: 剩余体积
// rs: 已累加的侧面积
// mr: 上一层(dep+1)的半径, 作为当前层半径的上限
// mh: 上一层(dep+1)的高度, 作为当前层高度的上限
void dfs(int dep, int rv, int rs, int mr, int mh) {
    // 剪枝：剩余体积不足以构成 dep 层
    if (rv < minv[dep]) return;
    
    // 剪枝：当前面积 + 剩下 dep 层最小面积 > 已知最优解
    if (rs + mins[dep] >= ans) return;

    // 剪枝：更强的最优性剪枝
    // 剩余体积为 rv, 上层半径为 mr, 那么之后所有层的半径都 < mr
    // 剩余侧面积 > 2 * rv / mr
    if (rs + 2 * rv / mr >= ans) return;

    // Base Case: 到达最底层(第1层)
    if (dep == 1) {
        // 枚举最后一层的半径 r
        for (int r = dep; r < mr; ++r) {
            // 体积公式 V = R^2 * H, H = V / R^2
            if (rv % (r * r) == 0) {
                int h = rv / (r * r);
                // 判断高度是否满足约束
                if (h < mh) {
                    ans = min(ans, rs + 2 * r * h + r * r);
                }
            }
        }
        return;
    }
    
    // 递归搜索下一层: 从大到小枚举半径和高度
    // r 的上限是上一层半径-1, 且 r*r*dep(最小高度) 不能超过剩余体积
    for (int r = min(mr - 1, (int)sqrt(rv)); r >= dep; --r) {
        // h 的上限是上一层高度-1, 且 r*r*h 不能超过剩余体积
        for (int h = min(mh - 1, rv / (r * r)); h >= dep; --h) {
            dfs(dep - 1, rv - r * r * h, rs + 2 * r * h, r, h);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m;

    // 预处理最小体积和面积, 用于剪枝
    for (int i = 1; i <= m; ++i) {
        minv[i] = minv[i - 1] + i * i * i;
        mins[i] = mins[i - 1] + 2 * i * i;
    }

    // 初始调用: m层, 体积n, 侧面积0, 半径和高度上限可设为较大值
    dfs(m, n, 0, n + 1, n + 1);

    if (ans == 1e9) {
        cout << 0 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

0 条评论

目前还没有评论...
87
已通过
0
题解被赞
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  3. 京ICP备2024092232号-2
  4. 京公网安备图标 京公网安备11010802045784号
  5. DAMON THRONE