题意： 给定一个 的二维矩阵，每个位置为 0 或者 1。询问所有 的子矩阵中存在 的矩阵个数。 解法： 二维前缀和。 先从一维说起， 个元素的一维数组为 ，下标从 到 。那么对应的前缀和数组 的定义为： 求前缀和的递推式为： 代码实现： s[0] = 0; for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i]; 利用前缀和，我们可以 求一段区间 的和。 再到二维前缀和： 求二维前缀和的递推式为： 。 求一个子矩阵 的和为： 。 会二维前缀和，那么这道题就结束了。先求出二维前缀和，然后遍历所有 的子矩阵，判断...

题意： 给定一维数轴上 个点之间的距离 ，每个点储存一些货物 。每次询问将一段区间 的货物全部移动到点 的代价和。储物点 有 个货物，全部移动到点 的代价为 。 解法： 前缀和。 先根据 和 ， 之间的关系分情况讨论。 先写下第一种情况的计算式： 令 ，则 令 ，则：。 故只需要做三个前缀和数组 。就可以 计算出答案。 对于第二种情况： 计算式正好是情况一的计算式的相反数。 对于第三种情况，可以将区间拆分为 和 ，分别为情况二和情况一，分开计算然后求和就可以了。 Code： #include <bits/stdc++.h> using namespa...

题意： 个格子组成的迷宫，迷宫中有陷阱 '#'，和可通行的点 '.'，起点为 'S'，终点为 'T'。每次移动代价为 1。另有传送阵若干，可以从传送阵的入口传送至出口，代价为 3。问从起点移动到终点的最小代价。 解法： 不考虑传送阵，最裸的 BFS。考虑传送阵，也算是比较经典的模型。有两种解法，但本质思想是一样。一种是建图，迷宫中的每一个格子视作一个顶点，上下左右相邻的格子间建一条权值为 1 的双向边。传送阵的入口和出口之间建一条权值为 3 的单向边。然后跑个最短路 dijstra 就行了。另一种是堆优化的 BFS，实现也和 dijkstra 很类似。只不过不用重新建图。代码实现的就是这种方式...

题意： 给定一棵含 个节点的二叉树，其节点编号为 到 。二叉树的中序遍历为 。每个节点有一个分数 。 任一棵子树subtree（也包含tree本身）的加分计算方法为：subtree的左子树的加分 subtree的右子树的加分＋subtree 的根的分数。 若左右子树中某一子树为空，规定其分数为 1。若左右子树都为空（即叶节点），则分数为叶节点本身的分数。 求分树最高的 tree。 解法： 对二叉树的概念和二叉树的中序遍历有一定了解的话，就很容易得到这样的性质：二叉树的中序遍历可以不断递归划分成：（左子树）根节点（右子树）。比如样例输出的那棵二叉树： 根节点为 ，则可以划分成 。 根...

题意： 块木板，每块木板有 个格子, 每个格子需要被涂上红色或者蓝色。每次粉刷只能选择一块木板上的一段连续的格子，然后涂上一种颜色。每个格子至多只能被粉刷一次。问粉刷 次，正确粉刷的格子数最多是多少？ 解法： 用 表示第 块木板粉刷 次，正确粉刷的格子总数。 在已经计算出 的前提下，剩下的就是一个分组背包问题：用 表示总共粉刷了 次，正确粉刷的格子总数。 递推式为： 对应代码的第26~30行，注意循环顺序。这部分复杂度为 然后再考虑如何计算 ： 对每块木板，定义 表示粉刷到第 个格子，共粉刷了 次的正确粉刷格子总数。 那么递推式为： 其中 表示前缀红色/蓝色的格...