Q779’s Blog

UOJ405 【IOI2018】组合动作 题解 题目链接：#405. 【IOI2018】组合动作 题意： 你在玩一个动作游戏。游戏控制器有 \(4\) 个按键，A、B、X 和 Y。在游戏中，你用组合动作来赚金币。你可以依次按这些按键来完成一个组合动作。 这个游戏有一个隐藏的按键序列，可以表示为由这 \(4\) 个字符组成的串 \(S\)。你并不知道这个串 \(S\)，但是你知道它的长度为 \(N(1\le N \le 2000)\)。 你还知道，\(S\) 的首字符不会在串中重复出现。例如，\(S\) 可以是”ABXYY“或者”XYYAA“，但不能是”AAAAA“或”BXYBX“。 你可以依次按最多 \(4N\) 个按键来完成一个组合动作。串 \(p\) 为你所按的按键序列。你用这个组合动作赚到的金币数量，等于同时为 \(p\) 之子串和 \(S\) 之前缀的最长字符串的长度。串 \(t\) 的子串定义为 \(t\) 中的连续字符序列 (可以为空)。\(t\) 的前缀定义为 \(t\) 的子串，其或者为空，或者包含 \(t\) 的首字符。 例如，如果 \(S\) 是 “ABXY...

洛谷P3291 [SCOI2016]妖怪 题解 题目链接：P3291 [SCOI2016]妖怪 题意： 邱老师是妖怪爱好者，他有 \(n\) 只妖怪，每只妖怪有攻击力 \(\mathtt{atk}\) 和防御力 \(\mathtt{dnf}\) 两种属性。邱老师立志成为妖怪大师，于是他从真新镇出发，踏上未知的旅途，见识不同的风景。 环境对妖怪的战斗力有很大影响，在某种环境中，妖怪可以降低自己 \(ka\) 点攻击力，提升 \(kb\) 点防御力或者，提升自己 \(ka\) 点攻击力，降低 \(kb\) 点防御力。 \(a,b \in \mathbb{R}_{+},~k \in \mathbb{R}\) ，但是 \(\mathtt{atk}\) 和 \(\mathtt{dnf}\) 必须始终非负。 妖怪在环境 \((a,b)\) 中的战斗力为妖怪在该种环境中能达到的最大攻击力和最大防御力之和 \[ \mathtt{strength}(a,b)=\max\{\mathtt{atk}(a,b)\}+\max\{\mathtt{dnf}(a,b)\} \] 环境由 \(a,b\) 两个...

洛谷P3648 [APIO2014] 序列分割 题解 题目链接：P3648 [APIO2014] 序列分割 题意： 你正在玩一个关于长度为 \(n\) 的非负整数序列的游戏。这个游戏中你需要把序列分成 \(k + 1\) 个非空的块。为了得到 \(k + 1\) 块，你需要重复下面的操作 \(k\) 次： 选择一个有超过一个元素的块（初始时你只有一块，即整个序列） 选择两个相邻元素把这个块从中间分开，得到两个非空的块。 每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。 输入格式： 第一行包含两个整数 \(n\) 和 \(k\)。保证 \(k + 1 \leq n\)。 第二行包含 \(n\) 个非负整数 \(a_1, a_2, \cdots, a_n\) \((0 \leq a_i \leq 10^4)\)，表示前文所述的序列。 输出格式： 第一行输出你能获得的最大总得分。 第二行输出 \(k\) 个介于 \(1\) 到 \(n - 1\) 之间的整数，表示为了使得总得分最大，你每次操作中分开两个块的位置。第 \(i\) 个整数 \(s_i\)...

洛谷P1397 [NOI2013] 矩阵游戏 题解 题目链接：P1397 [NOI2013] 矩阵游戏 题意： cxy 是个喜欢矩阵的小朋友，有一天她想用电脑生成一个巨大的 \(n\) 行 \(m\) 列的矩阵 (你不用担心她如何存储)。她生成的这个矩阵满足一个神奇的性质： 若用 \(F_{i, j}\) 来表示矩阵中第 \(i\) 行第 \(j\) 列的元素，则 \(F_{i, j}\) 满足下面的递推式： \[ \begin{cases} F_{1, 1} & = & 1 \\ F_{i, j} & = & a \times F_{i, j-1} + b & j \neq 1 \\ F_{i, 1} & = & c \times F_{i-1, m} + d & i \neq 1 \end{cases} \] 递推式中 \(a, b, c, d\) 都是给定的常数。 现在 cxy 想知道 \(F_{n, m}\) 的值是多少，请你帮助她。由于最终结果可能很大，你只需要输出 \(F_{n, m}\) 除以 \(1...

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\}\) 套路地，由于我们只需要知道总答案，而并非每一条路径的答案 于是考虑每个点的贡献...