Loading...
题面 https://www.luogu.com.cn/problem/P1717 题解 以五分钟为一个单位，设状态方程：$g[i][j]$ 表示第 $i$ 个时间单位到达 $j$ 农场钓到的鱼。 需要保证大于零。 以及我们还需要保证状态是可达的才行。所以代码中要 memset -1. 代码 #include <iostream> #include <cstring>...
Preface 吐了。写的时候想假了，以为可以用最高位判断，最后发现还不如存个 min 数组。不过问题不大，正好复习了一下 Trie 的写法（翻了翻以前 AC 自动机的写法）。以及，初始化 sz = 1，血的教训。 题面 https://leetcode-cn.com/problems/maximum-xor-with-an-element-from-array/ 题解 观察数据范围，要到 ...
题面 https://www.luogu.com.cn/problem/P1364 题解 复杂度 $O(n)$ 高赞题解中说带权树的重心。其实关系不是最大，我们直接嗯推方程其实就可以了。 首先定义: $sz[u]$ 是以 $u$ 为根的子树大小 $f[u]$ 是将 $u$ 设置为医院时的总距离 我们不妨以 $1$ 为根。 第一遍 dfs 初始化 $sz$ 与 $f[1]$: 代码 #...
Preface 刷 leetcode 好有成就感，毕竟在其他 OJ 直接被虐爆。 题面 https://leetcode-cn.com/problems/delete-columns-to-make-sorted-iii/ 题解 这不就是最长递增子序列吗...只不过现在多了点字符串。很容易可以得到转移方程： 代码 const int maxn = 105; class Solution ...
题面 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...