Q779’s Blog

UOJ31 【UR #2】猪猪侠再战括号序列 题解 题目链接：#31. 【UR #2】猪猪侠再战括号序列 题意： 什么魔怔题目（（ 有一个由 \(n\) 个左括号 ( 和 \(n\) 个右括号 ) 组成的序列。每次操作时可以选定两个数 \(l, r\)，然后把第 \(l\) 到第 \(r\) 个括号的顺序翻转（括号的朝向保持不变）。例如将 ()((()( 翻转第 \(3\) 到第 \(7\) 个括号后的结果为 ()()(((。 我希望使用不超过 \(n\) 次操作，将这个序列变为一个合法的括号序列。 众所周知，合法括号序列的定义如下： () 是合法括号序列； 如果 A 是合法括号序列，则 (A) 是合法括号序列； 如果 A,B 是合法括号序列，则 AB 是合法括号序列。 输入格式： 一行一个长度为 \(2n\) 的非空字符串表示初始序列。保证字符串只包含左括号和右括号，且左右括号的个数均为 \(n\)。 输出格式： 对于给出的字符串，输出调整成合法的括号序列的方案。如果不存在这样的方案输出一行一个整数 \(-1\)。 否则，第一行一个整数 \(m\) 表示要进行 \(m\)...

洛谷P3452 [POI2007]BIU-Offices 题解 题目链接：P3452 [POI2007]BIU-Offices 题意： Bytel 是一家移动通信公司。该公司的每位员工都收到了一部公司生产的电话，电话的通讯录中存储着一些同事的电话号码（每部手机中也都有该手机本身的电话号码）。 由于业务扩张，公司总部需要迁移至新的办公区。为了提高工作效率，董事会决定在不同栋楼工作的每一对员工需要相互知道对方的电话号码。即如果 \(u\) 和 \(v\) 在不同的楼工作，则 \(u\) 的通讯录里需要存储 \(v\) 的电话号，\(v\) 的通讯录里也要存储 \(u\) 的电话号码。 同时，董事会决定租用尽可能多的楼，以确保良好的工作条件。现在你需要帮助 Bytel 公司计算出他们需要租用多少栋楼。 输入格式： 输入第一行包含两个整数 \(n,m\)，分别代表公司的员工数和通讯录的信息数，员工从 \(1\) 到 \(n\) 编号。 接下来 \(m\) 行，每行两个整数 \(a_i,b_i\)，表示 \(a_i\) 和 \(b_i\) 相互知道对方的电话号码，保证任意两条信息不重复。...

洛谷P4302 [SCOI2003]字符串折叠 题解 题目链接：P4302 [SCOI2003]字符串折叠 题意： 折叠的定义如下： 一个字符串可以看成它自身的折叠，记作 \(S = S\) 。 \(X(S)\) 是 \(X(X>1)\) 个 \(S\) 连接在一起的串的折叠，记作 \(X(S) = SSSS\dots S(x \,\texttt{个}\,S)\)。 如果 \(A = A^{\prime}, B = B^{\prime}\) ，则 \(AB = A^{\prime}B^{\prime}\) 。例如，因为 \(\mathtt{3(A)} = \mathtt{AAA}, \mathtt{2(B)} = \mathtt{BB}\)，所以 \(\mathtt{3(A)C2(B)} = \mathtt{AAACBB}\) ，而 \(\mathtt{2(3(A)C)2(B)} = \mathtt{AAACAAACBB}\) 。 给一个字符串，求它的最短折叠。例如 \(\mathtt{AAAAAAAAAABABABCCD}\) 的最短折叠为：\(\mathtt{9(...

CF632F Magic Matrix 题解 题目链接：CF632F Magic Matrix 题意： 定义一个大小为 \(n\times n\) 矩阵 \(a\) 为魔法矩阵，当且仅当 \(a\) 满足以下条件： 以下 \(i,j,k\in \mathbb{Z_+}\) \(\forall i\in[1,n],~a_{i,i}=0\) \(\forall i,j\in[1,n],~a_{i,j}=a_{j,i}\) \(\forall i,j,k\in[1,n],~a_{i,j}\le\max\{a_{i,k},a_{j,k}\}\) 给你一个矩阵，问它是不是魔法矩阵。 如果 \(a\) 是魔法矩阵输出 \(\texttt{MAGIC}\)，否则输出 \(\texttt{NOT MAGIC}\) 。 数据范围： \(1\leq n\leq 2500,~\forall i,j\in[1,n],~0\le a_{i,j}\le 10^9\) 前两条限制已经告诉你了，这个东西就是个无向简单图的邻接矩阵，不然肯定不满足条件。 考虑第三条限制怎么处理。注意到后面的 \(a_{i,...

CF875E Delivery Club 题解 题目链接：CF875E Delivery Club 题意： Petya 和 Vasya 是两个快递员。他们每天需要去 \(n\) 个地点送信，其中这 \(n\) 个点在同一条直线上。 由于公司内部的规定，送包裹必须按照某种特定的顺序依次送达。初始时 Petya 在位置 \(s_1\)，Vasya 在位置 \(s_2\)，并且送包裹的顺序为 \(x_1, x_2, \cdots, x_n\)。 他们以如下形式送包裹：当前 \(i\) 个包裹均送达后，他们中的一个去送第 \(i+1\) 个包裹 (可以和送第 \(i\) 个包裹的人是同一个人，也可以是不同的人)，另一个人则在原地等候。 由于他们需要互相交流，他们带了一对通讯设备。这对通讯设备在距离比较远时通讯功能较差。因此 Petya 和 Vasya 想找到一种合适的送包裹方案 (假如顺序是预先知道的)，使得他们之间的最大距离尽可能的小。帮助他们确定在不违反规定的情况下，最大距离的最小可能值。 输入格式： 第一行包含三个非负整数 \(n, s_1, s_2,~(1 \leq n \le...

渐进记号总结 & 《算法导论》 3.1 用来描述算法渐进运行时间的记号根据定义域为自然数集 \(\mathbb{N}\) 的函数来定义。 这样的记号对描述最坏情况运行时间的函数 \(T(n)\) 是方便的。 紧渐进界记号 \(\Theta\) 断句：紧 渐进 界 记号 upd. 还是叫 紧确渐进界记号 \(\Theta\) 比较好.. \[ \Theta(g(n)) = \{f(n) \mid \texttt{存在正常量} \,c_1,c_2\,\texttt{和}\,n_0\,\texttt{使得对所有}\,n\ge n_0\,\texttt{有}\,c_1g(n) \le f(n) \le c_2g(n)\} \] 例子 \(f(n) = 3n^2-n+5 = \Theta(n^2)\) 定理1：对于任意两个函数 \(f(n)\) 和 \(g(n)\) ，我们有 \(f(n)=\Theta(g(n))\) ，当且仅当 \(f(n)=O(g(n)) \land f(n) = \Omega(g(n))\) 或者等价的表示为： \(\Theta(f(n)) = O(n) \...

洛谷P5884 [IOI2014]game 游戏 题解 题目链接：P5884 [IOI2014]game 游戏 题意： q779 是一个喜欢做游戏的小男生。当有人问问题时，他更喜欢通过玩游戏的方式作答，而不是直接回答。 q779 碰到了他的朋友 cxy ，跟她讲了台湾的航空网。在台湾有 \(n\) 个城市（编号为 \(0,\cdots,n−1\)），其中有些城市之间有航线。每个航线连接两个城市，并且是双向的。 cxy 问 q779 ，是否任意两个城市之间都可以坐飞机互达（直接或间接）， q779 不想直接回答，而是要通过做游戏的方式来告诉她。 cxy 可以问”城市 \(u\) 和 \(v\) 之间有直接航线吗？“， q779 会立刻直接回答该问题。 cxy 会询问每对城市恰好一次，因此总计会有 \(r = \frac{n (n−1)}{2}\) 个问题。如果由前 \(i\)（\(i<r\)）个问题的答案可以推断出整个航空网是否连通，也就是说，是否任意一对城市之间都可以坐飞机互达（直接或间接）， cxy 就获胜。否则意味着她需要知道全部 \(r\) 个回答，此时 q779 ...

CF915F Imbalance Value of a Tree 题解 题目链接：CF915F Imbalance Value of a Tree 题意： 给定一棵 \(n\) 个点的树，每个点有点权 \(a_i\) 。 定义 \(I(x,y)\) 为 \(x\) 到 \(y\) 的简单路径上的 \(\max\{a_i\}-\min\{a_i\}\) 求 \[ \sum_{i=1}^{n}\sum_{j=1}^{n} I(i,j) \] 数据范围： \(1 \le n \le 10^6\) 这个 \(I(i,j)\) 是真的难看。考虑化简。 \[ \sum_{i=1}^{n}\sum_{j=1}^{n} f(i,j)-\sum_{i=1}^{n}\sum_{j=1}^{n} g(i,j) \] \(f(i,j)\) 表示 \(i\) 到 \(j\) 的简单路径上的 \(\max\{a_i\}\) \(g(i,j)\) 表示 \(i\) 到 \(j\) 的简单路径上的 \(\min\{a_i\}\) 套路地，由于我们只需要知道总答案，而并非每一条路径的答案 于是考虑每个点的贡献...

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....