Q779’s Blog

UOJ142 【UER #5】万圣节的南瓜灯 题解 题目链接：#142. 【UER #5】万圣节的南瓜灯 题意： cxy 是一个心灵手巧的女孩纸。今天是万圣节， cxy 正在家里制作南瓜灯。 这时候一群熊孩子们敲开了 cxy 家的门，他们高呼着 “不用给糖，只要捣蛋” 的口号把 cxy 的南瓜灯弄坏了。这让 cxy 很难过，于是她打算把这些被弄坏的南瓜灯做成其他的工艺品。 cxy 把她的南瓜灯划分成了 \(n \times m\) 的网格，并用 \((x,y)\) 表示第 \(x\) 行，第 \(y\) 列的格子。两个格子是相邻的当且仅当它们有一条公共边，特殊地， \((x,1)\) 和 \((x,m)\) cxy 也视为是相邻的，但是他不把 \((1,x)\) 和 \((n,x)\) 当做是相邻的。 对于一个有 \(k\) 个格子被弄坏的南瓜灯，如果它能被制作成工艺品，当且仅当对于任意两个没有被弄坏的格子，都存在且仅存在一条连接它们的简单路径。一条简单路径定义为一个只包含没有被弄坏的格子的序列 \(A_1\) 至 \(A_n\) ，其中对于任意的 \(1 \leq i <...

洛谷P4547 [THUWC2017]随机二分图 题解 题目链接：P4547 [THUWC2017]随机二分图 题意： 某人在玩一个非常神奇的游戏。这个游戏中有一个左右各 \(n\) 个点的二分图，图中的边会按照一定的规律随机出现。 为了描述这些规律，某人将这些边分到若干个组中。每条边或者不属于任何组 （这样的边一定不会出现），或者只属于一个组。 有且仅有以下三类边的分组： 这类组每组只有一条边，该条边恰好有 \(50\%\) 的概率出现。 这类组每组恰好有两条边，这两条边有 \(50\%\) 的概率同时出现，有 \(50\%\) 的概率同时不出现。 这类组每组恰好有两条边，这两条边恰好出现一条，各有 \(50\%\) 的概率出现。 组和组之间边的出现都是完全独立的。 某人现在知道了边的分组和组的种类，想要知道完美匹配数量的期望是多少。你能帮助她解决这个问题吗？ 定义解释： 如果你对完美匹配和期望的定义很熟悉，那么你可以跳过本段。 对于一个左右各 \(n\) 个点的二分图，它的一个完美匹配是指 \(n\) 条没有公共点的边构成的匹配。 两个完美匹配不同，当且仅当它们至少含有...

不定积分基本公式 别问我为什么有导数的基本公式推导 却没有这个不定积分基本公式的推导和证明 因为我现在（20220902）不会证明（逃 等系统地学习以后再修补错误吧 不定积分的定义与性质 不定积分是所有原函数的集合。也就是说，如果 \(F^{\prime}(x) = f(x)\) ，则 \[ \int f(x)\,dx = F(x) + C \tag{1} \] 其中 \(C\) 为常数。 不定积分的性质如下： \[ \int C f(x)\,dx = C\int f(x)\,dx\tag{1} \] \[ \left(\int f(x)\,dx\right)^{\prime} = f(x)\tag{2} \] \[ \int f^{\prime}(x)\,dx = f(x) + C \tag{3} \] \[ \int \left[f(x) \pm g(x)\right] = \int f(x)\,dx \pm \int g(x)\,dx\tag{4} \] 不定积分基本公式 对应着导数的基本公式，可以得到不定积分的基本公式 \[ \int 0 \,dx = C\tag{1}...

UOJ60 【UR #5】怎样提高智商 题解 题目链接：#60. 【UR #5】怎样提高智商 题意： 共有 \(n\) 道选择题，编号为 \(1\) 到 \(n\)。第 \(i\) 道题形如：（\(h_i\) 为 “A” 或 “B” 或 “C” 或 “D”，\(a_i, b_i, c_i, d_i\)都是整数） \(i\). 编号小于 \(i\) 的题目中你一共选了几个 \(h_i\)？ A. \(a_i\) 个 B. \(b_i\) 个 C. \(c_i\) 个 D. \(d_i\) 个 求出所有 \(n\) 道选择题的试卷中，正确答案最多的试卷。 例子： 编号小于 \(1\) 的题目中你一共选了几个 B？ A. \(0\) 个 ，B. \(7\) 个 ，C. \(1\) 个 ，D. \(4\) 个 编号小于 \(2\) 的题目中你一共选了几个 A？ A. \(3\) 个 ，B. \(2\) 个 ，C. \(1\) 个 ，D. \(4\) 个 编号小于 \(3\) 的题目中你一共选了几个 D？ A. \(0\) 个 ，B. \(2\) 个 ，C. \(1\) 个 ，D....

UOJ48 【UR #3】核聚变反应强度 题解 题目链接：#48. 【UR #3】核聚变反应强度 题意： 著名核物理专家 Picks 提出了核聚变特征值这一重要概念。 核聚变特征值分别为 \(x\) 和 \(y\) 的两个原子进行核聚变，能产生数值为 \(\text{sgcd}(x, y)\) 的核聚变反应强度。 其中， \(\text{sgcd}(x, y)\) 表示 \(x\) 和 \(y\) 的次大公约数，即能同时整除 \(x, y\) 的正整数中第二大的数。如果次大公约数不存在则说明无法核聚变， 此时 \(\text{sgcd}(x, y) = -1\)。 现在有 \(n\) 个原子，核聚变特征值分别为 \(a_1, a_2, \dots, a_n\)。然后 Picks 又从兜里掏出一个核聚变特征值为 \(a_1\) 的原子，你需要计算出这个原子与其它 \(n\) 个原子分别进行核聚变反应时的核聚变反应强度，即 \[ \text{sgcd}(a_1, a_1), \text{sgcd}(a_1, a_2), \dots, \text{sgcd}(a_1, a_n) \]...

洛谷P3983 赛斯石（赛后强化版） 题解 题目链接：P3983 赛斯石（赛后强化版） 题意： 现需上市 \(\mathtt{Need}\) 赛斯重量的赛斯石，卖家想算出这些赛斯石经过某种合并方式来获得的最大收益。然而目前有一个问题，市场在真程大殿附近（真程海洋中心位置），卖家需要租船送赛斯石过去（即不考虑卖家自己租船过去的费用），目前有十种船可以租，载重量从 \(1\mathtt{si}\) 到 \(10\mathtt{si}\) ，每艘船的租价也是有所不同的，如下表所示： 由于真程大殿附近有强烈的赛斯力，导致无法对赛斯石进行任何操作，商家将赛斯石运过来之后就只能按照之前合并好的卖。假设卖家不返回，且这些赛斯石全部能卖出去。现在卖家他要计算总盈利（设总盈利=赛斯石的总收益-租船所需总费用），请你设计一个程序，算出一种最佳方案，以获得最大总盈利。 输入格式： 输入一共有两行 第一行有一个数据 \(\mathtt{Need}\)（赛斯石的总量，单位：\(\mathtt{si}\) ） 第二行有十个数据 \(a_1,a_2,\dots, a_{10}\)（分别为 \(1\math...

UOJ14 【UER #1】DZY Loves Graph 题解 题目链接：#14. 【UER #1】DZY Loves Graph 题意： cxy 开始有 \(n\) 个点，现在她对这 \(n\) 个点进行了 \(m\) 次操作，对于第 \(i\) 个操作 (从 \(1\) 开始编号) 有可能的三种情况： Add a b：表示在 \(a\) 与 \(b\) 之间连了一条长度为 \(i\) 的边 (注意，\(i\) 是操作编号)。保证 \(1\le a,b \le n\) 。 Delete k：表示删除了当前图中边权最大的 \(k\) 条边。保证 \(k\) 一定不会比当前图中边的条数多。 Return：表示撤销第 \(i−1\) 次操作。保证第 \(1\) 次操作不是 Return 且第 \(i−1\) 次不是 Return 操作。 请你在每次操作后告诉 cxy 当前图的最小生成树边权和。如果最小生成树不存在则输出 \(0\)。 输入格式： 第一行包含两个正整数 \(n,m (n\le 3\times 10^5,m\le 5\times 10^5)\) 。表示有 \(n\...

UOJ21 【UR #1】缩进优化 题解 题目链接：#21. 【UR #1】缩进优化 题意： 小 O 是一个热爱短代码的选手。在缩代码方面，他是一位身经百战的老手。世界各地的 OJ 上，很多题的最短解答排行榜都有他的身影。这令他感到十分愉悦。 最近，他突然发现，很多时候自己的程序明明看起来比别人的更短，实际代码量却更长。这令他感到很费解。经过一番研究，原来是因为他每一行的缩进都全是由空格组成的，大量的空格让代码量随之增大。 现在设小 O 有一份 \(n\) 行的代码，第 \(i\) 行有 \(a_i\) 个空格作为缩进。 为解决这一问题，小 O 要给自己文本编辑器设定一个正整数的默认 Tab 宽度 \(x\)，然后对于每一行，编辑器从头至尾不断把连续 \(x\) 个空格替换成一个 Tab，直到剩余空格数不足 \(x\) 个。 最终缩进所占代码量为空格数与 Tab 数的和。请你帮小 O 选择一个合适的 \(x\) ，使得缩进所占代码量最小。 输入格式： 第一行包含一个正整数 \(n(n \leq 10^6)\)，表示代码行数。 接下来 \(n\) 行，第 \(i\) 行包含一个正...

CF822E Liar 题解 题目链接：CF822E Liar 题意： 给定两个字符串 \(s, t\)，长度分别为 \(n, m\)。你需要选择 \(s\) 的若干个两两不相交的子串，然后将它们按照原先在 \(s\) 中出现的顺序合并起来，希望得到 \(t\)。 令 \(f(s, t)\) 表示要选择的 \(s\) 的子串数目的最小值，以便它们的并是串 \(t\)。如果无法合理选择这样的子串，则 \(f(s, t) = +\infty\)。现在 cxy 想知道，对于给定的 \(s, t\)，是否有 \(f(s, t) \leq x\)。 输入格式： 第一行包含一个正整数 \(n,~(n \leq 10^5)\)，表示字符串 \(s\) 的长度。 第二行为一个长度为 \(n\) 的，只包含小写字母 \(\mathtt{a} \sim \mathtt{z}\) 的字符串 \(s\)。 第三行包含一个正整数 \(m,~(m \leq n)\)，表示字符串 \(t\) 的长度。 第四行类似地包含一个长度为 \(m\) 的字符串 \(t\)。 第五行包含一个正整数 \(x,~(x \l...

CF712E Memory and Casinos 题解 题目链接：CF712E Memory and Casinos 题意： 现有一排 \(n\) 个赌场。 cxy 在第 \(i\) 个赌场时有 \(p_i\) 的几率获胜并移动到第 \(i+1\) 个赌场，如果 \(i=n\) 则 cxy 会离开赌场； 同时有 \(1-p_i\)的概率失败并移动到第 \(i-1\) 个赌场，如果\(i=1\) 则 cxy 会离开赌场。 定义 cxy “掌控”一段区间 \([i,j]\) 当且仅当 cxy 完成以下过程： cxy 从 \(i\) 号赌场出发； cxy 从未在 \(i\) 号赌场失败； cxy 某一次在 \(j\) 号赌场获胜并离开。 现在有 \(q\) 次操作，操作有以下两种： \(1\ i\ a\ b\)：令 \(p_i = \frac{a}{b}\)； \(2\ l\ r\)：询问 cxy “掌控”区间 \([l,r]\) 的概率。 保证在任意时刻 \(p_i\) 构成的序列是单调不降的。 关键词：线段树、等比数列求和、概率、DP（思想） 设 \(f(l,r)\)...

DP总结-状压dp 状压dp（状态压缩动态规划）是一种dp。（废话） 状压dp的核心就是把若干状态压缩为一个整数 通常要压缩的元素个数不超过 \(15\) ，此时状态数共有 \(2^{15}=32768\) 。 状压dp更多的是一种思想，常见于数位dp等需要记录大量信息的dp中。 集合的整数表示 注意，当集合元素个数较多的时候，可能需要使用 1ll<<n 或者 1ull<<n 。 基本表示： 空集：0 大小为 \(n\) 的全集： (1 << n) - 1 第 \(i\) 个元素 \(x_i\) ：1 << i 交集： \(S\cap \{x_i\}\) ：(S >> i) & 1 \(S\cap T\)：S & T 并集： \(S \cup \{x_i\}\) ：S | (1 << i) \(S \cup T\) ：S | T 绝对补集： \(\sim\!S\) ：U^S 或 U-S 或 (~S) & U ，U为全集 相对补集： \(S\setminus\{x_i\}\...

AT2657 [ARC078D] Mole and Abandoned Mine 题解 题目链接：AT2657 [ARC078D] Mole and Abandoned Mine 题意： cxy 准备住在一个废弃的矿洞里，矿洞的结构可以用一个包含 \(n\) 个点，\(m\) 条边的连通无向简单图来表示，其中点以 \(1,2,\cdots,n\) 编号。第 \(i\) 条边连接点 \(a_i\) 和 \(b_i\)，并且移除它需要花费 \(c_i\) 元。 cxy 想要移除一些边，使得点 \(1\) 和点 \(n\) 之间有且仅有唯一的路径，请你帮她寻找满足要求所需的最小花费。 注：一条路径 (path) 指的是不能经过重复点的途径 (walk)，一条迹 (trail) 指的是不能经过重复边的途径。 输入格式： n m a1 b1 c1 ⋮ ⋮ ⋮ am bm cm 输出格式： 一行，即答案。 数据范围： 保证是连通简单图。 \(2 \leq n \leq 15,~n - 1 \leq m \leq \dbinom n2,~1 \leq a_i, b_i \leq n ,~...