Q779’s Blog

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

Codechef REBXOR 题解 题目链接：Nikitosh and xor 题意： 给定 \(n\) 个数 ，求 \[ \max_{1 \le l_1 \le r_1 < l_2 \le r_2 \le n}\left\{\left(\bigoplus_{i=l_1}^{r_1} a_i\right) + \left(\bigoplus_{i=l_2}^{r_2} a_i\right)\right\} \] \(2 \le n \le 4\times 10^5,~0\le a_i \le 10^9\) 先考虑只有 \(\bigoplus_{i=l_1}^{r_1} a_i\) 该怎么求 u1s1，我觉得目前能看到我博客的人应该都会求 \(\bigoplus_{i=l_1}^{r_1} a_i\) 的最大值吧 那就直接建一个 \(\mathtt{01trie}\) 把异或前缀和全插入 然后在树上贪心找较大异或值就好啦 那么两个的情况其实是一样的 其实难在选第二个可能会与第一个有交集，以及不好枚举之类的问题 考虑从左往右依次插入每个串，这样枚举第一个是不重不漏的 此时...

CF526G Spiders Evil Plan 题解 题目链接：CF526G Spiders Evil Plan 题意： 二次魔改自 link 最近 q779 迷上了一个叫做割绳子 3 的yúsì（游戏）。 这个游戏的要求是你要扮演蜘蛛去吃掉一个糖果。 那是一个像割绳子游戏一样的界面，共有 \(n\) 个节点，和 \(n-1\) 条有长度的边，组成了一个树状结构。一共有 \(q\) 关，第 \(i\) 关，糖果在第 \(x_i\) 个节点上，共有 \(y_i\) 只蜘蛛。 每只蜘蛛可以用它的网去覆盖任意不同两点 \(a\) 和 \(b\) 之间的路径，因此，\(y\) 只蜘蛛可以覆盖 \(y\) 条树上路径的并。当然，不同的蜘蛛选择的路径可以相交。并且，具有如下的要求： \(y\) 条路径必须包含糖果所在的节点 \(x\)。 \(y\) 条路径的并是连通的。 使 \(y\) 条路径所经过的边的长度总和最大。 可是蜘蛛们好像都非常智障，所以它们需要你帮忙求出最大值。 本题强制在线 ，数据范围： \(1 \le x_i,y_i \le n,~1\le n,q \le 10^5...

LOJ6269 烷基计数 加强版 题解 题目链接：#6269. 烷基计数 加强版 题意：众所周知，大连 24 中是一所神奇的学校，在那里，化竞的同学很多都擅长写代码。 有一天，化学不及格的胡小兔向化竞巨佬晴岚请教化学题： “\(n\) 个碳原子的烷基共有多少种同分异构体？” 刚刚得了化竞全市第一的晴岚听了，认为这道题十分简单，建议胡小兔写个程序解决这个问题。但胡小兔弱得连什么是同分异构体都不知道，于是晴岚给胡小兔画了个图——例如 \(n=4\) 时 (即丁基)，有 \(4\) 种同分异构体： 同理，其他常见烷基同分异构体数目如下表： n 1 2 3 4 5 6 同分异构体数目 1 1 2 4 8 17 现在已知碳原子个数 \(n\)，求对应的烷基有多少种同分异构体。 答案对 \(10^9 + 7\) 取模。 数据范围： \(n \le 5\times 10^3\) 注意：这里的烷基计数不用考虑空间异构，能否稳定存在等各种特殊情况。也就是说，你要求的是 \(n\) 个点的每个点度数不超过 \(4\) 且根的度数不超过 \(3\) 的有根树的数目。 据说这种...

洛谷P3825 [NOI2017] 游戏 题解 题目链接：P3825 [NOI2017] 游戏 题目描述 小 L 计划进行 \(n\) 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。 小 L 的赛车有三辆，分别用大写字母 \(A\)、\(B\)、\(C\) 表示。地图一共有四种，分别用小写字母 \(x\)、\(a\)、\(b\)、\(c\) 表示。 其中，赛车 \(A\) 不适合在地图 \(a\) 上使用，赛车 \(B\) 不适合在地图 \(b\) 上使用，赛车 \(C\) 不适合在地图 \(c\) 上使用，而地图 \(x\) 则适合所有赛车参加。 适合所有赛车参加的地图并不多见，最多只会有 \(d\) 张。 \(n\) 场游戏的地图可以用一个小写字母组成的字符串描述。例如：\(S=\texttt{xaabxcbc}\) 表示小L计划进行 \(8\) 场游戏，其中第 \(1\) 场和第 \(5\) 场的地图类型是 \(x\)，适合所有赛车，第 \(2\) 场和第 \(3\) 场的地图是 \(a\)，不适合赛车 \(A\)，第 \(4\) 场和第 \(7\...