Q779’s Blog

UOJ278 【UTR #2】题目排列顺序 题解 题目链接：#278. 【UTR #2】题目排列顺序 题意： “又要出题了。” 宇宙出题中心主任 —— cxy ，坐在办公桌前策划即将到来的 UOI。 这场比赛有 \(n\) 道题， cxy 需要决定这些题目的难度，然后再在汪洋大海中寻找符合该难度的题目。 题目的难度可以用一个 \(1\) 到 \(n\) 的排列 \(a_1, \dots, a_n\) 表示，其中 \(a_i\) 表示第 \(i\) 道题目在这 \(n\) 道题目中是第 \(a_i\) 简单的题目，即恰有 \(a_i - 1\) 道题目比第 \(i\) 道题目简单。 经验丰富的 cxy 早就悟出了一种科学地决定难度顺序的方法。首先， cxy 定义了难度递增子序列为序列 \(a_{p_1}, a_{p_2}, \dots, a_{p_k}\) （\(1 \le p_1 < p_2 < \dots < p_k \le n\)） 满足 \(a_{p_1} < a_{p_2} < \dots < a_{p_k}\) 。然后， cxy 决...

CF398B Painting The Wall 题解 题目链接：CF398B Painting The Wall 题意： cxy 打算漆一堵墙。这个墙由 \(n^2\) 块瓷砖构成，它们构成 \(n \times n\) 的表。有些瓷砖是被涂上颜色的，还有些则没有。她想要将这堵墙漆得漂亮，她会按照以下四个步骤进行： 首先，cxy 会检查这堵墙，如果每行、每列均有涂上颜色的瓷砖，则停止刷墙，否则跳转到步骤 2。 cxy 从这 \(n^2\) 块瓷砖中均匀随机地选择一块瓷砖。 如果该瓷砖没有被涂色，则她将那块瓷砖涂色，否则，她什么都不用干。 然后，她休息 \(1\) 分钟，然后回到步骤 1。 cxy 觉得，她会花费太多时间在砌墙上。所以，她想知道，她按照上面的方法砌墙所需的时间的期望。你可以假设涂一块瓷砖不用花费任何时间。 输入格式： 第一行包含两个正整数 \(n, m~(1 \leq n \leq 2000,~0 \leq m \leq \min \{n^2, 20000\})\)，表示墙的大小和已经涂色的瓷砖的个数。 接下来的 \(m\) 行，每行包含两个正整数 \(r,...

CF464D World of Darkraft - 2 题解 题目链接：CF464D World of Darkraft - 2 题意： cxy 在玩 “World of Dardraft - 2” 游戏，有 \(k\) 种不同的装备，初始状态下所有的装备都是 \(1\) 级的。 每当打败一个怪物，她就能获得一个新的装备，新的装备由如下规则生成： 先从 \(k\) 种装备中等概率随机选择一种装备，记作 \(i\)。 设当前类型为 \(i\) 的装备的等级为 \(t_i\)，则会从 \([1, t_i + 1]\) 中等概率随机一个作为新的装备的等级。 cxy 会从新的装备和原来 (对应类型) 的装备中选择一个级别更高的，将它装备上，并出售剩下的一个装备，等级为 \(x\) 的装备的售价为 \(x\) (个硬币)。 请帮助 cxy 决定打败 \(n\) 个怪物后获得的硬币数的期望。 输入格式： 共一行，包含两个正整数 \(n, k\) 。 输出格式： 输出一行一个实数，表示打败 \(n\) 个怪物后获得硬币数的期望。答案被认为正确当且仅当相对或绝对误差不超过 \(10^{-...

洛谷P1399 [NOI2013] 快餐店 题解 题目链接：P1399 [NOI2013] 快餐店 题意： cxy 打算在城市 C 开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的，cxy 希望快餐店的地址选在离最远的顾客距离最近的地方。 快餐店的顾客分布在城市 C 的 \(N\) 个建筑中，这 \(N\) 个建筑通过恰好 \(N\) 条双向道路连接起来，不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。cxy 的快餐店可以开设在任一建筑中，也可以开设在任意一条道路的某个位置上（该位置与道路两端的建筑的距离不一定是整数）。 现给定城市 C 的地图（道路分布及其长度），请找出最佳的快餐店选址，输出其与最远的顾客之间的距离。 输入格式： 第一行包含一个整数 \(N\)，表示城市 C 中的建筑和道路数目。 接下来 \(N\) 行，每行 \(3\) 个整数，\(A_i,B_i,L_i\)（\(1\leq i\leq N\)，\(L_i>0\)），表示一条道路连接了建筑 \(A_i\) 与 \(B_i\...

洛谷P3770 [CTSC2017]密钥 题解 题目链接：P3770 [CTSC2017]密钥 题意： 一个密钥是一个长度为 \(n = 2k + 1\) 的字符串，它包含 \(1\) 个字母 \(\tt{X}\)、k 个字母 \(\tt{A}\) 和k 个字母 \(\tt{B}\)。例如 \(k = 3\) 时，\(\tt{BAXABAB}\) 就是一个密钥。 如下图所示，可以按顺时针顺序把这 \(2k+1\) 个字母排成一个圈： 在 \(k\) 个字母 \(\tt{A}\) 中，有一部分可以定义为 “强的”。具体来说，从 \(\tt{X}\) 出发顺时针走到某个 \(\tt{A}\) 时，如果途中 \(\tt{A}\) 的数目严格多于\(\tt{B}\)的数目，则称此字母 \(\tt{A}\) 为强的。 对于上面的例子来说，顺时针方向从字母 \(\tt{X}\) 数起第 \(1\) 个和第 \(2\) 个字母 \(\tt{A}\) 是强的，而第 \(3\) 个字母 \(\tt{A}\) 不是强的。 一个密钥的特征值就是其中包含的强的字母 \(\tt{A}\) 的个数。 天...

BZOJ4242 水壶 题解 题目链接：#4242. 水壶 题意： cxy 所居住的 IOI 市以一年四季都十分炎热著称。 IOI 市是一个被分成纵 \(H\) \(\times\) 横 \(W\) 块区域的长方形，每个区域都是建筑物、原野、墙壁之一。建筑物的区域有 \(P\) 个，编号为 \(1,2,\cdots ,P\)。 cxy 只能进入建筑物与原野，而且每次只能走到相邻的区域中，且不能移动到市外。 cxy 因为各种各样的事情，必须在各个建筑物之间往返。虽然建筑物中的冷气设备非常好，但原野上的日光十分强烈，因此在原野上每走过一个区域都需要 \(1\) 单位的水。此外，原野上没有诸如自动售货机、饮水处之类的东西，因此 IOI 市的市民一般都携带水壶出行。大小为 \(x\) 的水壶最多可以装 \(x\) 单位的水，建筑物里有自来水可以将水壶装满。 由于携带大水壶是一件很困难的事情，因此 cxy 决定携带尽量小的水壶移动。因此，为了随时能在建筑物之间移动，请你帮他写一个程序来计算最少需要多大的水壶。 现在给出 IOI 市的地图和 \(Q\) 个询问，第 \(i\) 个询问 \(...

导数&不定积分 学习笔记 这是一篇整合&小总结文章。 众所周知，微分和积分是对应可逆的。所以就有了这篇文章 相关文章：导数的基本公式推导 | 不定积分基本公式 基本定义 导数是微积分学中的一个概念。函数在某一点的导数是指这个函数在这一点附近的变化率。 \[ f^{\prime}(x) = \lim_{\Delta x \to 0}\frac{f(x+\Delta x)-f(x)}{\Delta x} \] \(f\) 在 \(x_0\) 处的导数，记作 \(f^{\prime}(x_0)\) 或 \(\frac{df}{dx}(x_0)\) 或 \(\left.\frac{df}{dx}\right|_{x=x_0}\) 。 不定积分是所有原函数的集合。也就是说，如果 \(F^{\prime}(x) = f(x)\) ，则 \[ \int f(x)\,dx = F(x) + C \tag{1} \] 其中 \(C\) 为常数，原因在于 \((C)^{\prime} = 0\)。 线性运算 导数： \[ {[f(x) \pm g(x)]}^{\prime} = ...

小蓝书 16.3 本文写于较早时候，所以可能存在一些问题。 小蓝书上讲的母函数就是普通生成函数。传送门：生成函数 学习笔记 对于一个数列 \(\{f_n\}\) ，定义它的普通生成函数 \(F(x)\) 为以 \(x\) 为未定元的一个形式幂级数，则 \[ F(x) = \sum_{n \ge 0} f_nx^n \\f_n = [x^n]F(x) \] 另一种易于理解的写法是这样的（数列为 \(\{a_n\}\) ） \[ F(x) = \sum_{i=0}^{\infty}a_ix^i = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n + \cdots \] 一些常用的公式&技巧： 更多详见 泰勒级数&麦克劳林级数 公式I \(\forall x : |x| < 1\) \[ \dfrac{1}{1-x} = \sum_{n=0}^{\infty} x^n = 1+x+x^2 + \cdots + x^n + \cdots \] 公式II \(\forall x : |x| < 1,~ k \in \mathbb{Z...

本文统计截止于 2022年09月28日 ，有空再来统计这个。 其实还有很多模板或者 Trick 在洛谷没有被标出来。 难度 通过数/总数 完成度 普及- 7/7 100% 并查集 ok 堆 ok 快速幂 ok 最小生成树 ok 线性筛 ok 快速排序 ok 字符串哈希 ok 普及/提高- 16/16 100% 树状数组 1 ok 乘法逆元 ok LCA ok 线段树1 ok 树状数组 2 ok KMP ok 负环 ok ST 表 ok 矩阵加速（数列） ok 单调栈 ok 单源最短路 1 ok 单源最短路 2 ok 裴蜀定理 ok 字典树 ok 普及+/提高 13/16 81.25% 有理数取余 ok 边双连 欧拉路径 ok 威佐夫博弈 nim 游戏 缩点 ok 线段树 2 ok 全源最短路 ok 割点 ok 二分图最大匹配 ok exgcd ok 最长公共子序列 ok 边双连 提高+/省选- 24/34 70.58% 普通平衡树 1 ok 左偏树 ok 最小费用最大流 ok ...

洛谷P6134 [JSOI2015]最小表示 题解 题目链接：P6134 [JSOI2015]最小表示 题意： 对于一个 \(N\) 个点（每个点从 \(1\) 到 \(N\) 编号），\(M\) 条边的有向图，cxy 发现，如果从图中删去一些边，那么原图的连通性会发生改变；而也有一些边，删去之后图的连通性并不会发生改变。 cxy 想知道，如果想要使得原图任意两点的连通性保持不变，我们最多能删掉多少条边呢？ 为了简化一下大家的工作量，这次 cxy 保证他给定的有向图一定是一个有向无环图（cxy：大家都知道对于给任意有向图的问题，最后都能转化为有向无环图上的问题，所以就干脆简化一下大家的工作）。 输入格式： 第一行包含两个正整数 \(N\) 和 \(M\)。 接下来 \(M\) 行，每行包含两个 \(1\) 到 \(N\) 之间的正整数 \(x_i\) 和 \(y_i\)，表示图中存在一条从 \(x_i\) 到 \(y_i\) 的有向边。 输入数据保证，任意两点间只会有至多一条边存在。 输出格式： 输出一行包含一个整数，表示cxy最多可以删掉的边数。 数据范围： 对于 \(100...

UOJ176 新年的繁荣 题解 题目链接：#176. 新年的繁荣 题意： 在这新年的第一天，神族首领 cxy 打算重新规划一下神族领地的交通。 神族领地中有 \(n\) 个城市，其中第 \(i\) 座城市的繁荣度为 \(a_i\)。神族领地中任意两个城市之间都可以修建双向道路，在第 \(i\) 座城市和第 \(j\) 座城市之间修建道路可以给新的一年带来 \(a_i \mathbin{\mathrm{and}} a_j\) 的繁荣度。其中 \(\mathbin{\mathrm{and}}\) 表示按位与运算，例如 \(2 \mathbin{\mathrm{and}} 3=2\)，\(1 \mathbin{\mathrm{and}} 0=0\)，\(1 \mathbin{\mathrm{and}} 1=1\)。 为了彰显自己的功绩，神族首领 cxy 决定修建若干条道路，使得任意两个城市之间都可以只通过他新修建的道路直接或者间接到达，为了发扬节约精神，他决定修建恰好 \(n-1\) 条道路。一个修建方案的繁荣度是所有要修建的道路带来的繁荣程度之和。 作为一个英明的首领， cxy 决...

泰勒级数&麦克劳林级数 在数学上，对于一个在实数或复数 \(a\) 邻域上，以实数或复数作为变量的函数， 并且是无穷可微的函数 \(f(x)\) ，它的泰勒级数是以下这种形式的幂级数： \[ \sum_{n=0}^{\infty}\dfrac{f^{(n)}(a)}{n!}(x-a)^n \] 当 \(a=0\) 时，可以称这个级数为麦克劳林级数。即 \[ \sum_{n=0}^{\infty}\dfrac{f^{(n)}(0)}{n!}x^n \] 对于 \(e^x,\sin x\) 这种函数，如果我们想求它的较精确近似值，可以考虑麦克劳林级数。 常用麦克劳林级数 当变量 \(x\) 是复数时，这些等式依然成立。 几何级数： \(\forall x : |x| < 1\) \[ \dfrac{1}{1-x} = \sum_{n=0}^{\infty} x^n = 1+x+x^2 + \cdots + x^n + \cdots \] 拓展： \(\forall x : |x| < 1,~ k \in \mathbb{Z}^{+}\) \[ \dfrac{1}{...