题目描述 给定 $n$ 和 $k$ 棵有 $n$ 个点的树。对于每个点对 $(i,j)$ ，求出其在每棵树上的路径经过的点（含端点）的交集大小。 数据范围: $1 \leq n, k \leq 500$ 时间限制: $2.000s$ 题解 首先明白一个性质：对于某一棵树，考虑 $x$ 在 $(u, v)$ 路径上的充要条件：$dis(u,x) + …

兰道函数 对于所有非负整数，兰道函数$g(n)$定义为对称群$S_{n}$的所有元素的秩之中，最大的一个。或者说，$g(n)$是$n$的所有整数分拆之中的最小公倍数。 例如${displaystyle 5=2+3}, {displaystyle lcm(2,3)=6}$没有其他5的分割方式能得出一个更大的最小公倍数，故此${displaystyle…

这个是原题链接 关键在于发现题目是逆序对，实际上你在赛场上直接猜结论（确实需要一定的勇气，毕竟数据不够多，罚时等等）也是可以的，那么我们来推导一下这个性质。 $$\sum{(a_i-b_i)^2} = \sum{[a_i^2 + b_i^2 - 2a_ib_i]} = \sum{(a_i^2 + b_i^2)} - 2\sum {a_ib_i}$$…

问题描述 给定一个 $n$ 行 $m$ 列的网格图，每个格子的颜色是蓝色、白色中的一种。白色的格子是障碍点。对于 $2$ 个有公共边的蓝色格子，它们之间是连通的。保证任意 $2$ 个蓝色格子间最多只有 $1$ 条不经过白色格子的路径。现给出 $Q$ 个矩形区域，对每个矩形区域求出对蓝色格子来说的连通块个数（不能经过白色格子和矩形区域外的格子）。 数…

题目大意 在一条数轴上有 $n$ 人 $k$ 把钥匙，每个人能拿且仅能拿一把钥匙，办公室坐标为 $p$ ，所有人同时开始去拿钥匙，然后去办公室。求所有人消耗的最大时长。 每人的坐标在 $a_i$ ，每个钥匙的坐标在 $b_i$ 。 题解 我们先将每个人的坐标和钥匙先排序，然后可以证明： $$\forall a_i\leq a_j\ …

[题目链接] 题目描述 Bessie喜欢在手机上下游戏玩（……），然而她蹄子太大，很难在小小的手机屏幕上面操作。 她被她最近玩的一款游戏迷住了，游戏一开始有$n$个正整数，$(2\leq n\leq262144)$，范围在$1-40$。在一步中，贝西可以选相邻的两个相同的数，然后合并成一个比原来的大一的数（例如两个$7$合并成一个$8$)，目标是使…

网易云歌单~ 今年看过的： 我推的孩子（包括漫画） Another 石纪元 莉可丽丝 东京喰种 中二病也要谈恋爱！Take On Me（剧场版） 刀剑神域 无星之夜的咏叹调（剧场版） 刀剑神域 黯淡黄昏的谐谑曲（剧场版） 橡果兄弟（剧场版） 天国大魔镜（包括漫画，期待第二季） 地狱乐（包括漫画） 寄生兽 无神世界中的神明活动（包括漫画） 未来日记 …

最长上升子序列(LIS) 1. $\mathcal{O}(n^2)$ 做法 设 $dp_{i}$ 表示以i 结尾的答案。所以先枚举一个 $i$ ，再从$1$ 开始枚举 $j$ ，每次看到小于 $a_{j}$ 的数，取一个最大的更新 $dp_{i}$ 。 2. $\mathcal{O}(nlog_n)$ 做法 状态设计： $dp_i$ 表示长度为 $…

一. 01背包 01背包问题关键在于某个物品取还是不取，状态可以从上一个占用空间转移而来。 for(int i = 1; i <= n; i++) { for(int j = m; j >= c[i]; j--) { dp[j] = max(dp[j], dp[j - c[i]] + w[i]); } } 二. 完全背包 完全背包问题就…

[题目链接] Lomsat gelral [原题链接] E. Lomsat gelral Lomsat gelral 题面翻译 有一棵 $n$ 个结点的以 $1$ 号结点为根的有根树。 每个结点都有一个颜色，颜色是以编号表示的， $i$ 号结点的颜色编号为 $c_i$。 如果一种颜色在以 $x$ 为根的子树内出现次数最多，称其在以 $x$ 为根的子…