Loading...
题面 https://www.luogu.com.cn/problem/P1363 题解 先说正解。 怎么样才能判断可以无限延伸呢？那就是如果存在一条路径 其中等式右侧的每条路径都不存在中间点。我们不难发现集合 $A$ 是有限的，因为原棋盘是有限的，故 $|A \cup \{S, T\}| \leq nm$。故长度必然为有限，与长度为无限矛盾。证毕。 下面是一些错误结论： 错误结论 1：向...
题面 https://www.luogu.com.cn/problem/P1364 题解 复杂度 $O(n)$ 高赞题解中说带权树的重心。其实关系不是最大，我们直接嗯推方程其实就可以了。 首先定义: $sz[u]$ 是以 $u$ 为根的子树大小 $f[u]$ 是将 $u$ 设置为医院时的总距离 我们不妨以 $1$ 为根。 第一遍 dfs 初始化 $sz$ 与 $f[1]$: 代码 #...
题面 https://leetcode-cn.com/problems/n-queens/ https://leetcode-cn.com/problems/n-queens-ii/ 题解 首先不考虑斜向，根据全排列的性质，1 ~ n 的全排列，以序数为行号，数值为列号就能穷举出不斜向攻击下的 N 皇后摆放情况。所以我们只需要穷举全排列，然后判断每个排列是否可行，复杂度为 $O(n!)$...
题面 https://www.luogu.com.cn/problem/P1236 题解 简单的 next_permutation 即可搞定。这里我手写了 next_permutation。 步骤： 对四个数进行 next_permutation，$O(n!), n = 4$ 穷举所有运算符的可能 $O(4^n), n = 3$ 穷举加括号的位置，两种： ((a ? b) ? c) ? d...
307-07-逐行递推 逐行递推：$dp$在某种情况下按照一行一行的顺序进行递推。 P2704 [NOI2001]炮兵阵地 题目描述 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图...