Fanyi's Blog

给你一棵树，边有边权，定义 \(f_x=\max_{i=1}^n\operatorname{dist}(x,i)\)。\(q\) 次询问，每次给出一个数 \(l\) 求最大的连通块 \(s\) 满足 \(\max_{x\in s}f_x-\min_{x\in s}f_x\le l\)。\(n\le 10^5,q\le 50\)。 首先假设这棵树的直径的两个端点为 \(u,v\)，不难发现 \(f_x=\max(\operatorname{dist}(u,x)\operatorname{v,x})\)。这个用证明直径的方法可以证明。 然后我们需要发现一个性质，那就是将点按照 \(f\) 从大到小排序，那么儿子一定排在父亲的前面。 然后就好办了，我们考虑将点按 \(f\) 从大到小排序，然后我们考虑在上面 two points，一边用并查集维护两个指针所在区间的联通性，插入一个点直接将其儿子…

你需要在平面直角坐标系上进行 \(q\) 次操作。每次操作有两种，要么放置一个两条直角边平行于坐标轴的等腰直角三角形，要么查询某一个点被多少个三角形覆盖。保证所有点的坐标都是整数且 \(\in [1,n]\)。\(n \le 5 \times 10^3, q \le 10^5\)。 考虑到四种方向是对称的，我们只考虑其中一种情况，比如说直角顶点在左下角的情况，令三个顶点为 \((x,y), (x+l,y), (x,y+l)\)。 首先我们发现需要加的所有点 \((x',y')\)，都满足 \(x+y\le x'+y'\le x+y+l\)，这个东西用一棵树状数组就可以维护： 然后我们就是要减去这两块： 我们考虑如何减去，观察这些点的性质，首先均满足 \(x'+y'\in [x+y,x+y+l]\)，然后其还满足 \(x'<x\) 或 \(y'<y\)。于是我们可以考虑开两棵二维树状数组，…

给一个长度为 \(2n\) 的序列，要求将其两两匹配成 \(n\) 组，假设第 \(i\) 组为 \((x_i,y_i)\)，求 \(\max_{i=1}^n(x_i+y_i)\bmod m\) 的最小值，\(1\le n\le 10^5,1\le m\le 10^9,0\le a_i<m\)。 我们首先我们有： 接下来我们看几种情况： 如果我们有 \(x_1\le x_2\le x_3\le x_4\)，那么我们有这样 \(4\) 中情况： 第一种，\(x_3+x_4<m\)，那显然 \((x_1,x_4),(x_2,x_3)\) 更优。 第二种，\(x_1+x_2\ge m\)，和第一种一样。 第三种，\(\begin{cases}x_1+x_3<m\\x_2+x_4\ge m\end{cases}\)，考虑到 \(x_2+x_4-m<x_2\)，故有…

给出 \(n\,(1\le n\le 4000000)\) 天的股票价格，每天可买进或卖出一股，可以同时买进或卖出，也可以不操作，但最终手上只能有一股。问最多 \(k\) 次买进和卖出后的最大收益。 我们先来看一个 \(\mathcal{O}(n\log n)\) 的做法。首先我们考虑如果是一段连续的递增股票，那我们相当于是一开始买进，最后卖出。如果这样连续的段小于等于 \(k\)，那么就直接可以返回答案了。如果比 \(k\) 大，那么我们就需要做出这样两种选择：要么选择一个上升的区间放弃，要么选择一段下降的区间把两段上升的区间给连起来。这个东西我们可以用一个堆或者 set 来维护。 但是我们还有一个 \(\mathcal{O}(n)\) 的做法，需要观察一些性质。我们把读入的股票看成是一个个单调不减的区间。当然有些区间可能只有一个数。 我们考虑一些区间可以合并成一个等价的区间，我们考虑将…

有一个 \((n + 2) \times m\) 的长方形，除了第一行和最后一行，其他每一行每一天最左边和最右边的格子都有 \(p\) 的概率被摧毁，每行之间独立且左边和右边独立，求 \(k\) 天之后最上面一行与最下面一行四联通的概率。 其中 \(1\le n,m\le 1500,\,0\le k\le 10^5\)，答案对 \(10^9+7\) 取模。 一个简单的想法就是我们令 \(h_{i,l,r}\) 表示 \(k\) 天后第 \(i\) 行还剩下 \([l,r]\)，前 \(i\) 行联通的概率。\(P_{l,r}\) 表示单独一行只剩 \([l,r]\) 的概率。 首先我们有： 接下来我们考虑 \(P_{l,r}\)，我们令 \(q_{i}=\binom{k}{i}p^i(1-p)^{k-i}\)，不难发现： 然后我们令 \(f_{i,r}\) 表示右端点为 \(r\) 的所有…

有一张二分图，左边有 \(n_1\) 个点，右边有 \(n_2\) 个点，\(m\) 条边。每个点可能有一种颜色 R 或者 B，也可能没有，也就是 U。现在要给一些边染色，把边染成 R 要花费 \(r\) 的代价，把边染成 B 要花费 \(b\) 的代价，要求对于每个颜色为 R 的点，与之相邻的边中 R 的边严格多于 B 的边；对于每个颜色为 B 的点，与之相邻的边中 B 的边严格多于 R 的边。求花费最小的方案，输出任意一种，无解输出 \(-1\)。其中 \(1 \le n_1, n_2, m, r, b \le 200\)。 考虑网络流建图，对于每条边 \(\left<u,v\right>\)，在网络流图上建立两条边：\(u\to v\)，如果流表示将该边染成红色，\(v\to u\)，表示将改变染成黑色。 建立超源 \(s\) 和超汇 \(t\)，考虑左边红色点，\(s\) 向该点连…

给你一棵 \(k\ (k\le 30)\) 阶的满二叉树，从上到下、从左到右从 \(1\) 开始编号，设 \(\{p_{n}\}\) 是它的 Prüfer 序列。给你三个数 \(a,d,m\)，求 \(\sum_{i=0}^{m-1}p_{a+id}\)。 这题主要是要发现一个性质，就是考虑定义 \(f_{i,k,h}(x)\) 表示以 \(x\) 为根，深度为 \(k\) 的子树，现在要开始删的是 Prüfer 序列中的第 \(i\) 位，对答案的共献，\(h\) 表示 \(x\) 是否有父亲，那么 \(f_{i,k,h}(x)\) 可以表示成 \(a_{i,k,h}x+b_{i,k,h}\lfloor\frac{x}{2}\rfloor+c_{i,k,h}\) 的形式。 令 \(Q\) 表示询问集合，考虑左儿子对答案的贡献为 \(f_{i,k-1,1}(2x)\)，也就是对父亲的贡献是…

给定一个长度为 \(n\) 的字符串，其中只有 '(', ')', '?' 三种字符，其中 '?' 可以为 '(' 或者 ')'。对于一个括号序列，定义其权值为其通过删除字符后可以得到的合法的括号匹配的最深的深度，求出所有可能的括号序列（即问号替换后）的权值和。 在 D1 中，\(n\le 2000\)；在 D2 中，\(n\le 10^6\)。 考虑枚举答案计算方案数，显然对于一个括号序列，存在一个划分点使得划分点左边的左括号个数等于划分点右边的有括号个数。则此时该括号序列的深度就是划分点左边的左括号个数。这样 dp 之后合并一下是 \(\mathcal{O}(n^2)\) 的。这样 D1 就做完了。 考虑把前面 dp 的式子转换成组合数，我们考虑每个分割点，前面有 \(l\) 个左括号，\(r\) 个右括号，前面有 \(x\) 个问号，后面有 \(y\) 个问号。 其实答案就是： 对于…

万年不更了，随便写点什么吧。 首先最小生成树的两种求法 Kruskal 和 Prim，强行丢链接。 其他还有一个 Borůvka 算法，大概思路就是每次将每个集合伸出去的最短的那条边选入，选入后将两个集合合并成一个新的集合，考虑到每次集合个数减半，所以复杂度 \(\mathcal{O}(m\log n)\)。偷了张 Wikipedia 的图： 那这东西有什么用呢？有这么一道题，大概是有一个 \(n\,(n\le 200000)\) 个点的完全图，每个节点的编号为 \(a_i\,(0\le a_i<2^{30})\)，\(i\) 与 \(j\) 的边的权值是 \(a_i\bigotimes a_j\)，\(\bigotimes\) 是按位异或，求该图的最小生成树。 这道题大概用到了 Borůvka 的思想，先用所有点权建一棵 Trie 树，考虑 Trie 树上一棵子树，显然一开始肯定是他们…

万年不更了，决定扔点什么东西上来凑数吧。 查看课件 PDF