Q779’s Blog

UOJ156 【清华集训2015】恐怖的奴隶主 题解 题目链接：#156. 【清华集训2015】恐怖的奴隶主 题意： “A fight? Count me in!” 要打架了，算我一个。 “Everyone, get in here!” 所有人，都过来！ 冷酷的酒客（Grim Patron）对战歌指挥官（Warsong Commander）的削弱感到很伤心，他打算用一道数学题来纪念战歌指挥官。 设 \(\left \{ u_i \right \}\) 为一数列 \[ \begin{equation} u_i = a + \frac{b}{u_{i-1}} + \frac{c}{u_{i-1}u_{i-2}} \quad (i \geq 2) \end{equation} \] 已知 \(u_0, u_1, a, b, c, n\)。保证 \(x^3 = a x^2 + b x + c\) 有 \(3\) 个不同的正整数解。 求 \(u_n\)。 输入格式： 输入仅一行，包含 \(6\) 个整数 \(u_0, u_1, a, b, c, n\)。 输出格式： 输出仅一行，包含 \...

洛谷P2512 [HAOI2008]糖果传递 题解 题目链接：P2512 [HAOI2008]糖果传递 题意： 有 \(n\) 个小朋友坐成一圈，每人有 \(a_i\) 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 \(1\)。 输入格式： 小朋友个数 \(n\)，下面 \(n\) 行 \(a_i\)。 输出格式： 求使所有人获得均等糖果的最小代价。 数据范围： 对于 \(100\%\) 的数据 \(n\le 10^6\)。 设最后每个人的糖果为 \(\bar{a} = \frac{1}{n} \sum_{1 \le i \le n} a_i\) ，记 \(b_i = a_i -\bar{a}\) 则题目变为如何将 \(b_i\) 全部转化为 \(0\) 。 设 \(x_i\) 表示最终方案中 \(i\) 给 \(i+1\) 了多少糖果（如果 \(x_i\) 为负，则代表 \(i+1\) 给了 \(i\) 多少） 由 \(b_i=0\) 得 \[ a_i+x_{i-1}+x_i = 0 \] 则答案为 \(\sum_{i=1}^{n} |x_i|\) ，考虑...

洛谷P2215 [HAOI2007]上升序列 题解 题目链接：P2215 [HAOI2007]上升序列 题意： 对于一个给定的 \(S=\{a_1,a_2,a_3,…,a_n\}\) , 若有 \(P=\{a_{x_1},a_{x_2},a_{x_3},…,a_{x_m}\}\) , 满足 \((x_1<x_2<…<x_m)\) 且 \((a_{x_1}<a_{x_2}<…<a_{x_m})\) 。那么就称 \(P\) 为 \(S\) 的一个上升序列。如果有多个 \(P\) 满足条件，那么我们想求字典序最小的那个。 任务： 给出 \(S\) 序列，给出若干询问。对于第 \(i\) 个询问，求出长度为 \(L_i\) 的上升序列，如有多个，求出字典序最小的那个（即首先 \(x_1\) 最小，如果不唯一，再看 \(x_2\) 最小……），如果不存在长度为 \(L_i\) 的上升序列，则打印 Impossible。 输入格式： 第一行一个 \(N\)，表示序列一共有 \(N\) 个元素。 第二行 \(N\) 个数，为 \(a_1, a_2 , \c...

SP2885 WORDRING - Word Rings 题解 题目链接：SP2885 WORDRING - Word Rings 题意： 如果字符串 \(A\) 的结尾两个字符与字符串 \(B\) 的开头两个字符相匹配，我们称 \(A\) 与 \(B\) 能 “ 相连 ” ( 注意： \(A\) 与 \(B\) 能相连，不代表 \(B\) 与 \(A\) 能相连 ) 当若干个串首尾 “ 相连 ” 成一个环时，我们称之为一个环串（一个串首尾相连也算） 我们希望从给定的全小写字符串中找出一个环串，使这个环串的平均长度最长 intercommunicational alkylbenzenesulfonate tetraiodophenolphthalein 如上例：第一个串能与第二个串相连，第二个串能与第三个串相连，第三个串又能与第一个串相连。按此顺序连接，便形成了一个环串。 长度为 \(20+21+24=65\) ( 首尾重复部分需计算两次 ) ，总共使用了 \(3\) 个串，所以平均长度是 \(65/3\approx 21.6667\) 输入格式： 多组数据 每组数据第一行一个...

洛谷P2592 [ZJOI2008]生日聚会 题解 题目链接：P2592 [ZJOI2008]生日聚会 题意： 今天是 cxy 小朋友的生日，她邀请了许多朋友来参加她的生日party。 cxy 带着朋友们来到花园中，打算坐成一排玩游戏。为了游戏不至于无聊，就座的方案应满足如下条件： 对于任意连续的一段，男孩与女孩的数目之差不超过 \(D\) 。 很快，小朋友便找到了一种方案坐了下来开始游戏。 cxy 的好朋友 q779 发现，这样的就座方案其实是很多的，所以大家很快就找到了一种，那么到底有多少种呢？热爱数学的 cxy 和她的朋友们开始思考这个问题…… 假设参加party的人中共有 \(n\) 个男孩与 \(m\) 个女孩，你是否能解答 q779 和 cxy 的疑问呢？由于这个数目可能很多，他们只想知道这个数目除以 \(12345678\) 的余数。 输入格式： 一行共 \(3\) 个整数，分别为男孩数目 \(n\) ，女孩数目 \(m\) ， 常数 \(D\) 。 输出格式： 一行答案。 数据范围： 对于 \(100\%\) 的数据， \(n , m \le 150,~D \l...

洛谷P2502 [HAOI2006]旅行 题解 题目链接：P2502 [HAOI2006]旅行 题意： Z 小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。Z 小镇附近共有 \(n\) 个景点（编号为 \(1,2,3,\ldots,n\)），这些景点被 \(m\) 条道路连接着，所有道路都是双向的，两个景点之间可能有多条道路。 也许是为了保护该地的旅游资源，Z 小镇有个奇怪的规定，就是对于一条给定的公路 \(r_i\)，任何在该公路上行驶的车辆速度必须为 \(v_i\)。 速度变化太快使得游客们很不舒服，因此从一个景点前往另一个景点的时候，大家都希望选择行使过程中最大速度和最小速度的比尽可能小的路线，也就是所谓最舒适的路线。 输入格式： 第一行包含两个正整数 \(n,m\)。 接下来的 \(m\) 行每行包含三个正整数 \(x,y,v\)。表示景点 \(x\) 到景点 \(y\) 之间有一条双向公路，车辆必须以速度 \(v\) 在该公路上行驶。 最后一行包含两个正整数 \(s,t\)，表示想知道从景点 \(s\) 到景点 \(t\) 最大最小速度比最小的路径。\(s...

洛谷P2047 [NOI2007] 社交网络 题解 题目链接：P2047 [NOI2007] 社交网络 题意： 在社交网络 ( Social Network ) 的研究中，我们常常使用图论概念去解释一些社会现象。不妨看这样的一个问题: 在一个社交圈子里有 \(n\) 个人，人与人之间有不同程度的关系。我们将这个关系网络对应到一个 \(n\) 个结点的无向图上，两个不同的人若互相认识，则在他们对应的结点之间连接一条无向边，并附上一个正数权值 \(c\) ，\(c\) 越小，表示两个人之间的关系越密切。我们可以用对应结点之间的最短路长度来衡量两个人 \(s\) 和 \(t\) 之间的关系密切程度，注意到最短路径上的其他结点为 \(s\) 和 \(t\) 的联系提供了某种便利，即这些结点对于 \(s\) 和 \(t\) 之间的联系有一定的重要程度。我们可以通过统计经过一个结点 \(v\) 的最短路径的数目来衡量该结点在社交网络中的重要程度。考虑到两个结点 \(A\) 和 \(B\) 之间可能会有多条最短路径。我们修改重要程度的定义如下：令 \(C_{s,t}\) 表示从s到t的不同的...

洛谷P2474 [SCOI2008]天平 题解 题目链接：P2474 [SCOI2008]天平 题意： 你有 \(n\) 个砝码，均为 \(\mathtt{1g}\)，\(\mathtt{2g}\) 或者 \(\mathtt{3g}\)。你并不清楚每个砝码的重量，但你知道其中一些砝码重量的大小关系。 你把其中两个砝码 \(A\) 和 \(B\) 放在天平的左边，需要另外选出两个砝码放在天平的右边。 问：有多少种选法使得天平的左边重 (\(c_1\))、一样重 (\(c_2\))、右边重 (\(c_3\))？(只有结果保证唯一的选法才统计在内) 输入格式： 第一行包含三个正整数 \(n,A,B(4\le n\le 50,~1\le A\ne B\le n)\)，砝码编号为 \(1\sim n\)。 以下 \(n\) 行包含重量关系矩阵，其中第 \(i\) 行第 \(j\) 个字符表示砝码 \(i\) 与砝码 \(j\) 之间的关系，其中加号 \(\mathtt{+}\) 表示砝码 \(i\) 比砝码 \(j\) 重，减号 \(\mathtt{-}\) 表示砝码 \(i\) 比砝码...

LOJ538 「LibreOJ NOIP Round #1」数列递推 题解 题目链接：#538. 「LibreOJ NOIP Round #1」数列递推 题意：cxy 虐爆 OI 之后成为了一名文化课选手。一天，她做作业碰到了一堆数列问题，每道题给出的数列都是以下形式： 给定一个下标从 \(0\) 开始，无限长的整数列 \(\{a_i\},\ i\in \mathbb{N}\)，已知 \(a_0,a_1\) 的值，以及递推式 \(a_{i+2}=k a_{i+1}+a_i,\ i\in\mathbb{N},k\in {\mathbb{N}_+}\)。 cxy 研究了这些数列，发现它们十分优美充满人类智慧，于是决定出一道 OI 题。 cxy 给了你一个集合 \(S\subset \mathbb{N}\)，他想问你对于 \(S\) 中的每个数 \(s_i\)，使得 \(a_{s_i}\) 最大的 \(s_i\) 和使得 \(a_{s_i}\) 最小的 \(s_i\) 分别是多少。如果这样的 \(s_i\) 有多个，请你回答最小的一个。 另外，cxy 准备对她作业中碰到的每个数列...

洛谷P4053 [JSOI2007] 建筑抢修 题解 题目链接：P4053 [JSOI2007] 建筑抢修 题意： cxy 在玩 JSOI 提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T 部落消灭了所有 Z 部落的入侵者。但是 T 部落的基地里已经有 \(N\) 个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。现在的情况是：T 部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮 cxy 合理的制订一个修理顺序，以抢修尽可能多的建筑。 输入格式： 第一行，一个整数 \(N\)。 接下来 \(N\) 行，每行两个整数 \(T_1,T_2\) 描述一个建筑：修理这个建筑需要 \(T_1\) 秒，如果在 \(T_2\) 秒之内还没有修理完成，这个建筑就报废了。 输出格式： 输出一个整数 \(S\)，表示最多可以抢修 \(S\) 个建筑。 对于 \(100 \%...

CF354D Transferring Pyramid 题解 题目链接：CF354D Transferring Pyramid 题意： cxy 正在使用一个有趣的数据结构——金字塔。 金字塔由 \(n\) 行组成，其中第 \(i\) 行有 \(i\) 个格子组成。每一行的最左端相对于上一行左移了半个格子的宽度，金字塔上的格子由 \(1\) 到 \(\binom {n+1}{2}\)，从上至下，从左至右的编号。 下图是一个 \(n = 5\) 的例子： 这个神奇的数据结构能接受下列两种操作： 改变一个特定位置上的值。它需要用 \(3\) 个数作为指令：1 i v。其中 \(i\) 为格子的编号，\(v\) 为改变后的值。 改变一个子金字塔的值。上图蓝色部分显示的是以 \(5\) 号格子为顶的子金字塔，它需要用 \(s + 2\) 个数作为指令：2 i v1 v2 ... vs，其中 \(i\) 为子金字塔顶的格子的编号，\(s\) 为子金字塔的大小 (如上图中是 \(6\))，\(v_i\) 为对应修改后的值。(可以不改变，即 \(v_i\) 为之前的值) 正式地，一个以 ...

洛谷P2606 [ZJOI2010]排列计数 题解 题目链接：P2606 [ZJOI2010]排列计数 题意： 称一个 \(1 \sim n\) 的排列 \(p_1,p_2, \dots ,p_n\) 是 Magic 的，当且仅当 \[ \forall i \in [2,n], p_{\lfloor i/2 \rfloor} < p_i \] 计算 \(1 \sim n\) 的排列中有多少是 Magic 的，答案可能很大，只能输出模 \(m\) 以后的值。 对于 \(100\%\) 的数据，\(1\le n \le 10^6,~1\le m \le 10^9\)，\(m\) 是一个质数。 给张图。 题目就是问 \(n\) 个结点的完全二叉树有多少种满足小根堆性质 设 \(f_i\) 表示以 \(i\) 为根的子树的答案， \(s_i\) 表示原树中以 \(i\) 为根的子树有多少个结点 考虑转移。根一定要放这个子树中最小的，其他的就挑 \(s_{2i}\) 个放左子树就好了，则 \[ f_i = f_{2i} \times f_{2i + 1} \times \db...