洛谷解题日记||基础篇4

#include <iostream>
using namespace std;

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

    // 计算所有矩形的数量
    long long totalRectangles = (long long)(n * (n + 1) / 2) * (long long)(m * (m + 1) / 2);
    
    // 计算正方形的数量
    long long totalSquares = 0;
    int maxSize = min(n, m);
    for (int size = 1; size <= maxSize; ++size) {
        totalSquares += (long long)(n - size + 1) * (long long)(m - size + 1);
    }

    // 计算长方形的数量
    long long totalRectanglesOnly = totalRectangles - totalSquares;

    // 输出正方形和长方形的数量
    cout << totalSquares << " " << totalRectanglesOnly << endl;

    return 0;
}

思路

1. 问题抽象： 这是一个典型的“背包问题”的变种，其中我们有10个配料，每个配料的质量只能是 1、2 或 3，总和要等于给定的美味程度 nnn。我们需要找出所有可能的组合，并且按字典序输出这些组合。

2. 如何生成所有组合：

   • 每个配料的质量范围是 1 到 3，我们可以使用递归（或回溯算法）来生成所有的组合。
   • 递归的每一步，试图给第 iii 种配料分配 1、2 或 3 克，递归处理下一个配料，直到所有配料的质量总和为 nnn。

3. 字典序要求：

   • 由于递归是从第1种配料开始逐步分配，因此可以保证在递归过程中，输出的组合已经是按字典序排列的。

4. 结束条件：

   • 当配料的总质量等于 nnn 时，记录这个组合。
   • 如果总质量超过 nnn，则返回并尝试其他可能的分配。

5. 剪枝：

   • 如果当前的总质量已经超过 nnn，就可以直接停止递归。

解决方案

使用回溯算法来生成所有合法的组合。具体步骤如下：

1. 递归函数：从第 1 种配料开始分配质量，尝试 1、2 或 3 克，并递归计算后续配料的组合。
2. 终止条件：如果所有配料的总质量等于 nnn，则记录该组合。
3. 输出：最终输出所有的组合的数量，并逐一输出这些组合。

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

int n;  // 美味程度
vector<int> current(10, 0);  // 当前的配料组合
vector<vector<int>> results;  // 保存所有符合条件的组合

// 递归回溯函数
void backtrack(int index, int sum) {
    if (index == 10) {  // 如果已经分配了所有10种配料
        if (sum == n) {  // 如果总和等于n，记录当前组合
            results.push_back(current);
        }
        return;
    }
    
    // 试图给第index种配料分配1、2、3克
    for (int i = 1; i <= 3; ++i) {
        if (sum + i <= n) {  // 如果当前总和不超过n
            current[index] = i;  // 设置当前配料的质量
            backtrack(index + 1, sum + i);  // 递归处理下一个配料
        }
    }
}

int main() {
    cin >> n;  // 输入美味程度n
    
    backtrack(0, 0);  // 从第1种配料开始，初始总和为0
    
    // 输出结果
    cout << results.size() << endl;  // 输出组合数量
    for (const auto& combo : results) {
        for (int i = 0; i < 10; ++i) {
            cout << combo[i] << " ";  // 输出每种配料的质量
        }
        cout << endl;
    }

    return 0;
}

求解步骤

1. 二分法求解月利率：

   • 我们的目标是找到一个月利率 r，使得在给定 w0 和 w 的条件下，贷款在 m 个月后刚好还清。
   • 用二分法搜索 r 的范围 [0, 3]（假设最大利率不超过 300% / 12 = 25% 每月）。

2. 模拟贷款偿还过程：

   • 对于给定的 r，我们需要模拟从第 1 个月到第 m 个月的贷款余额，检查总余额是否与初始贷款金额相符。

3. 精度要求：

   • 利率要四舍五入到小数点后一位。

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

// 输入的贷款金额 m、每月还款金额 y、总还款月数 t
double m, y, s;
int t;

// 输出结果的函数，k 是计算得到的月利率
int out(double k)
{
    printf("%.1f", k * 100); // 输出月利率 k，按百分比输出（乘以100）
    exit(0);  // 输出结果后退出程序
}

// 递归函数，二分法寻找合适的月利率
void solve(double l, double r)
{
    double k = (l + r) / 2;  // 计算区间中点
    double u = r - l;  // 当前区间长度
    double a = m;  // 初始贷款余额
    
    // 如果区间已经足够小，精度达到了要求，输出当前的中点利率
    if (u < 0.0001) out(k);
    
    // 计算偿还过程：每月都按利率更新贷款余额
    for (int i = 1; i <= t; i++) {
        a = a * (1 + k) - y;  // 贷款余额更新：利率按复利方式计算，每月减去还款金额
    }
    
    // 如果贷款余额仍大于0，说明当前利率过低，需要增大利率，递归继续在左半区间查找
    if (a > 0) solve(l, k);
    // 如果贷款余额小于0，说明当前利率过高，需要减小利率，递归继续在右半区间查找
    if (a < 0) solve(k, r);
    // 如果贷款余额刚好为0，表示找到合适的利率，直接输出
    if (a == 0) out(k);
}

int main()
{
    // 输入贷款金额 m、每月还款金额 y、还款月数 t
    cin >> m >> y >> t;
    
    // 调用 solve 函数，设置初始的二分法区间为 [0, 5]（月利率范围从 0 到 500%）
    solve(0, 5);
}

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

// 判断是否可以将数列分成 M 段，每段的和不超过 maxSum
bool canSplit(const vector<int>& A, int M, long long maxSum) {
    int count = 1;          // 当前段数，初始为 1 段
    long long currentSum = 0;  // 当前段的和
    for (int num : A) {
        // 如果加入当前数会使得当前段的和超过 maxSum，则需要开始一个新段
        if (currentSum + num > maxSum) {
            count++;         // 增加段数
            currentSum = num; // 新段的和从当前数开始
            // 如果段数超过 M，则不能在 maxSum 下分成 M 段，返回 false
            if (count > M) {
                return false;
            }
        } else {
            // 否则将当前数加入当前段的和中
            currentSum += num;
        }
    }
    // 如果段数不超过 M，说明在 maxSum 下可以分成 M 段，返回 true
    return true;
}

int main() {
    int N, M;
    cin >> N >> M;           // 读取数列长度 N 和分段数 M
    vector<int> A(N);        // 存储数列 A
    long long sum = 0, maxElem = 0; // sum 用于存储数列总和，maxElem 用于存储数列中的最大值

    // 读取数列，同时计算数列的总和 sum 和数列的最大值 maxElem
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        sum += A[i];
        maxElem = max(maxElem, (long long)A[i]);
    }
    
    // 二分搜索范围为 [maxElem, sum]
    long long left = maxElem, right = sum;
    while (left < right) {
        long long mid = left + (right - left) / 2; // 计算中间值 mid，作为候选的每段和的最大值
        if (canSplit(A, M, mid)) {
            // 如果可以在 maxSum = mid 下分成 M 段，那么尝试更小的最大和，右边界左移
            right = mid;
        } else {
            // 如果不可以，则 mid 太小，左边界右移
            left = mid + 1;
        }
    }
    
    // 当 left == right 时即为我们要求的最小的每段和的最大值
    cout << left << endl;
    return 0;
}

解释

• 二分搜索范围确定：left 从数列的最大值开始，因为单段的和不能小于任何一个单独元素。right 从数列的总和开始，因为将所有元素放在一段内，其和就是总和。

• 二分核心逻辑：

  • 在二分的过程中，通过中间值 mid 检查是否可以分成 M 段且每段和不超过 mid。
  • 如果可以，则尝试更小的 mid，以找到更小的每段和的最大值；如果不行，增大 mid 值。

• 贪心的 canSplit 函数：从左到右遍历数列，将元素累加到当前段，直到段和超出 maxSum 时重新开始一段，计数段数。最终判断段数是否符合要求。

这样每次迭代都可以将可能的最大和范围缩小，最终找到符合要求的最小可能值。