Fanyi's Blog

给一个长度为 \(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

感觉已经濒临 AFO 了。 题解中的翻译大部分来自网上，如果有侵权行为请联系我。 查看题解 PDF

声明：本游记的所有内容均是在 CSP 结束之后写的。 都高二了，第一次正式出去玩，第一次写游记。 上午信心赛，然后 yk 就放了场 Day2，窝打到自闭了。 啥我 T2 打了个奇怪的贪心过了？？？旺仔和 zyy 竟然 T1 同时没开大数组同一个数组海星…… 听说如果这场把 RP 用光会导致 CSP 爆 0，窝怕不是药丸。 高二老年选手第一次参加NOIPCSP，是不是晚了点。 路上好多人都在奶今年原题大战。 先去学车想围观一下考场，然而不让进。 和daifucong住一个房间，感觉酒店环境一般，但也还算过得去。 听说那叫“维也纳三好酒店”，名字不错。 晚上 daifucong 勾引我打 cs1.6，尝试下然鹅被卡巴基佬删了，听说 dfc 那个也被 360 删了。 然后开始无所事事。 dfc 给我讲了 pkuwc2019 的 D1T1，然后我想了好久是不是药丸…… 自闭后开始背板，然鹅还没开始…