发表于   |   分类于 洛谷 , 刷题   |   暂无评论

url: https://www.luogu.com.cn/problem/P1827

tag:
递归， 二叉树

代码：

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

string inorder, preorder;

void buildPostorder(int inStart, int inEnd, int preStart, int preEnd) {
    // 若范围无效，则返回
    if (inStart > inEnd || preStart > preEnd) {
        return;
    }

    // 前序遍历的第一个元素即为根节点
    char root = preorder[preStart];

    // 在中序遍历中找到根节点的位置
    int rootIndex = -1;
    for (int i = inStart; i <= inEnd; ++i) {
        if (inorder[i] == root) {
            rootIndex = i;
            break;
        }
    }

    // 根节点左边的节点个数
    int leftTreeSize = rootIndex - inStart;

    // 递归处理左子树
    buildPostorder(inStart, rootIndex - 1,
                   preStart + 1, preStart + leftTreeSize);

    // 递归处理右子树
    buildPostorder(rootIndex + 1, inEnd,
                   preStart + leftTreeSize + 1, preEnd);

    // 最后输出根节点，实现后序遍历顺序：左子树 -> 右子树 -> 根
    cout << root;
}

int main() {
    // 输入中序遍历和前序遍历字符串
    cin >> inorder >> preorder;

    int n = inorder.size();
    buildPostorder(0, n - 1, 0, n - 1);

    return 0;
}

发表于   |   分类于 生活   |   暂无评论

今天是把网盘程序onemanager搬过来了，然后还把两个自己写的网站一个是订阅服务，另外一个是链接网盘都搬过来了。
顺便把之前搭的另外一个博客删掉了，因为主要都是黑历史，然后没有写几篇文章。
突然感觉还是php写的博客程序好，搬家很方便，不用再写反向代理，然后再设置nginx的配置，就很方便。

发表于   |   分类于 洛谷 , 刷题   |   暂无评论

url: https://www.luogu.com.cn/problem/P2004

tag：
前缀和

思路：
先求前缀和，然后遍历右下端点，求出每个对应的子矩阵的总和，判断是否大于res，如果大的话就更新res和坐标x，y。最后输出x和y即可。

ps：这道题很简单，本来不应该传博客的，但是觉得自己写的好优美，忍不住传一下，以后偶尔可以翻出来看看。真的好优美感觉。

代码：

#include <iostream>
using namespace std;
const int N = 1010;
long long p[N][N];
int n, m , c;
int main()
{
    cin >> n >> m >> c;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
        {
            cin >> p[i][j];
            p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
        }
    long long res = 0, x, y;
    for (int i = c; i <= n; i ++)
        for (int j = c; j <= m; j ++)
        {
            long long tmp = p[i][j] - p[i - c][j] - p[i][j - c] + p[i - c][j - c];
            if (tmp > res)
            {
                res = tmp;
                x = i - c + 1;
                y = j - c + 1;
            }
        }
    cout << x << ' ' << y;
    return 0;
}

发表于   |   分类于 刷题   |   暂无评论

问题描述

小U计划进行一场从地点A到地点B的徒步旅行，旅行总共需要 M 天。为了在旅途中确保安全，小U每天都需要消耗一份食物。在路程中，小U会经过一些补给站，这些补给站分布在不同的天数上，且每个补给站的食物价格各不相同。

小U需要在这些补给站中购买食物，以确保每天都有足够的食物。现在她想知道，如何规划在不同补给站的购买策略，以使她能够花费最少的钱顺利完成这次旅行。

  • M：总路程所需的天数。
  • N：路上补给站的数量。
  • p：每个补给站的描述，包含两个数字 A 和 B，表示第 A 天有一个补给站，并且该站每份食物的价格为 B 元。

保证第0天一定有一个补给站，并且补给站是按顺序出现的。

测试样例

样例1：

输入：m = 5 ,n = 4 ,p = [[0, 2], [1, 3], [2, 1], [3, 2]]
输出：7

样例2：

输入：m = 6 ,n = 5 ,p = [[0, 1], [1, 5], [2, 2], [3, 4], [5, 1]]
输出：6

样例3：

输入：m = 4 ,n = 3 ,p = [[0, 3], [2, 2], [3, 1]]
输出：9

代码：

int solution(int m, int n, std::vector<std::vector<int>> p) {
    // 在末尾添加一个虚拟站点表示终点，价格设为0（方便处理，但不会实际购买）
    p.push_back({m, 0});
    int totalCost = 0;
    int currentIndex = 0; // 当前站点索引
    while (currentIndex < p.size() - 1) { // 最后一个虚拟站点不作为实际购买点
        int currentDay = p[currentIndex][0];
        int currentPrice = p[currentIndex][1];
        int nextIndex = currentIndex + 1;
        // 找到下一个比当前站价格低的站点或者终点
        while (nextIndex < p.size() && p[nextIndex][1] >= currentPrice) {
          nextIndex++;
        }
        // 如果未找到更便宜的，nextIndex 会指向虚拟终点站
        if (nextIndex == p.size()) {
          nextIndex = p.size() - 1;
        }
        int nextDay = p[nextIndex][0];
        // 计算从当前站到目标站之间需要的天数差
        int daysNeeded = nextDay - currentDay;
        // 在当前站购买足够的食物以覆盖到下一个更便宜的站或终点
        totalCost += daysNeeded * currentPrice;
        // 将当前站点移动到找到的更便宜的站点
        currentIndex = nextIndex;
    }
    return totalCost;
}

tag：
贪心

思路：
用贪心的策略，每次都找一个花费比当前补给站少的点，然后买刚好到那个补给站的食物。然后将当前的位置更新到那个补给站，直到到达终点。