Q779’s Blog

洛谷P4588 [TJOI2018]数学计算 题解 题目链接：P4588 [TJOI2018]数学计算 题意： cxy 现在有一个数 \(x\)，初始值为 \(1\)。cxy 有 \(Q\) 次操作，操作有两种类型： 1 m：将 \(x\) 变为 \(x \times m\)，并输出 \(x \bmod M\) 。 2 pos：将 \(x\) 变为 \(x\) 除以第 \(\mathtt{pos}\) 次操作所乘的数（保证第 \(\mathtt{pos}\) 次操作一定为类型 \(1\)，对于每一个类型 \(1\) 的操作至多会被除一次），并输出 \(x \bmod M\)。 输入格式： 一共有 \(t\) 组输入。 对于每一组输入，第一行是两个数字 \(Q,M\)。 接下来 \(Q\) 行，每一行为操作类型 \(\mathtt{op}\)，操作编号或所乘的数字 \(m\)（保证所有的输入都是合法的）。 输出格式： 对于每一个操作，输出一行，包含操作执行后的 \(x \bmod M\) 的值。 数据范围： 对于 \(100\%\) 的数据，\(1 \le Q \le 10^5\...

洛谷P3687 [ZJOI2017]仙人掌 题解 题目链接：P3687 [ZJOI2017]仙人掌 题意： 如果一个无自环无重边无向连通图的任意一条边最多属于一个简单环，我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。 现在九条可怜手上有一张无自环无重边的无向连通图，但是她觉得这张图中的边数太少了，所以她想要在图上连上一些新的边。同时为了方便的存储这张无向图，图中的边数又不能太多。经过权衡，她想要加边后得到的图为一棵仙人掌。 不难发现合法的加边方案有很多，可怜想要知道总共有多少不同的加边方案。 两个加边方案是不同的当且仅当一个方案中存在一条另一个方案中没有的边。 输入格式： 多组数据，第一行输入一个整数 \(Q\) 表示数据组数。 每组数据第一行输入两个整数 \(n,m\) ，表示图中的点数与边数。 接下来 \(m\) 行，每行两个整数 \(u,v(1\le u,v \le n, u\ne v)\) 表示图中的一条边。保证输入的图联通且没有自环与重边。 输出格式： 对于每组数据，输出一个整数表示方案数，当然方案数可能很大，请对 \(998244353\) 取模后输出。 ...

洛谷P7961 [NOIP2021] 数列 题解 题目链接：P7961 [NOIP2021] 数列 题意： 给定整数 \(n, m,d\)，和一个长度为 \(m + 1\) 的正整数数组 \(v_0, v_1, \ldots, v_m\)。 对于一个长度为 \(n\)，下标从 \(1\) 开始且每个元素均不超过 \(m\) 的非负整数序列 \(\{a_i\}\)，我们定义它的权值为 \(v_{a_1} \times v_{a_2} \times \cdots \times v_{a_n}\)。 当这样的序列 \(\{a_i\}\) 满足整数 \(S = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_n}\) 的二进制表示中 \(1\) 的个数不超过 \(d\) 时，我们认为 \(\{a_i\}\) 是一个合法序列。 计算所有合法序列 \(\{a_i\}\) 的权值和对 \(998244353\) 取模的结果。 输入格式： 输入第一行是三个整数 \(n, m, d\)。 第二行 \(m + 1\) 个整数，分别是 \(v_0, v_1, \ldots, v_...

MacOS 重装Homebrew 莫名其妙的，我的Homebrew挂了。 然后又到了欢乐的重装时刻。（恼 根据官方的文档，卸载指令如下：或者戳这里 /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/uninstall.sh)" 然后我这里就报错了，原因是被墙了，报错如下 curl: (7) Failed to connect to raw.githubusercontent.com port 443 after 4 ms: Connection refused 报错解决方案：（这个指令就是临时改一下这个终端的环境，具体我也不是很懂） # 把下面的端口号改成自己的（前提是需要有VPN） export https_proxy=http://localhost:58591/ http_proxy=http://localhost:58591/ all_proxy=socks5://localhost:51837/ 如果不知道这几个端口号是啥，可以参考一下我这里的端口号 ...

CF1142E Pink Floyd 题解 题目链接：CF1142E Pink Floyd 题意： 有一张 \(n\) 个点的竞赛图 \(G\)，其中有 \(m\) 条边是粉色的，剩下 \(\binom {n}{2} - m\) 条边都是绿色的。你现在已经知道所有 \(m\) 条粉色边及其定向，但你不知道绿色边的方向。 你可以向交互库发出不超过 \(2 n\) 次询问，每次询问的内容为 ” 询问一条绿色边的方向 “。在询问完毕后，你需要找到一个点 \(u\)，使得：对于 \(G\) 中的任何一个点 \(v\)，均存在一条从 \(u\) 到 \(v\) 的 (有向) 路径，满足路径上的所有边同色。 可以证明，对于任何一张竞赛图和任意的边染色方案，这样的点 \(v\) 是一定存在的。 输入格式： 第一行包含两个正整数 \(n, m (1 \leq n \leq 10^5,~0 \leq m \leq \min \left\{ \binom n2, 10^5 \right\})\)，表示竞赛图的点数和粉色边的条数。 接下来的 \(m\) 行，每行两个正整数 \(u, v~(1 \le...

UOJ67 新年的毒瘤 题解 题目链接：#67. 新年的毒瘤 题意： 辞旧迎新之际，喜羊羊正在打理羊村的绿化带，然后他发现了一棵长着毒瘤的树。 这个长着毒瘤的树可以用 \(n\) 个结点 \(m\) 条无向边的无向图表示。这个图中有一些结点被称作是毒瘤结点，即删掉这个结点和与之相邻的边之后，这个图会变为一棵树。树也即无简单环的无向连通图。 现在给你这个无向图，喜羊羊请你帮他求出所有毒瘤结点。 输入格式： 第一行两个正整数 \(n, m\)，表示有 \(n\) 个点 \(m\) 条边。保证 \(n \geq 2\)。 接下来 \(m\) 行，每行两个整数 \(v, u\)，表示 \(v\) 和 \(u\) 之间有一条无向边。\(1 \leq v, u \leq n\)。保证没有重边和自环。 输出格式： 第一行一个正整数 \(n_s\)，表示这个图中有 \(n_s\) 个结点是毒瘤。 接下来一行，共 \(n_s\) 个整数，每个整数表示一个毒瘤结点的编号。请按编号从小到大的顺序输出。 数据保证图中至少存在一个毒瘤结点。 数据范围： \(2 \le n ,m \le 10^5\) 。...

note[8] 例：\(n\) 个涂色的小球，颜色在 \(1 \sim n\) 中等概率随机，求 \(n\) 个球颜色种数的期望。 解： 感谢 Roundgod 老师的耐心指导 Orz 根据期望的线性性，可以考虑每种颜色的期望，再乘上 \(n\) \[ n\times\left(1-\left(1-\frac{1}{n}\right)^n\right) \] 其中 \(\left(1-\frac{1}{n}\right)^n\) 指所有球均不是这种颜色的概率 然后用 \(1\) 去减它就是「有球染成这个颜色」的概率。 把它乘上一个 \(1\) ，就是每种颜色的期望。最后把 \(n\) 种颜色的期望加起来就好啦。

洛谷P3264 [JLOI2015]管道连接 题解 题目链接：P3264 [JLOI2015]管道连接 题意： cxy 最近进入了某情报部门，该部门正在被如何建立安全的通道连接困扰。 该部门有 \(n\) 个情报站，用 \(1\) 到 \(n\) 的整数编号。给出 \(m\) 对情报站 \((u_i,v_i)\) 和费用 \(w_i\)，表示情报站 \(u_i\) 和 \(v_i\) 之间可以花费 \(w_i\) 单位资源建立通道。 如果一个情报站经过若干个建立好的通道可以到达另外一个情报站，那么这两个情报站就建立了通道连接。形式化地，若 \(u_i\) 和 \(v_i\) 建立了通道，那么它们建立了通道连接；若 \(u_i\) 和 \(v_i\) 均与 \(t_i\) 建立了通道连接，那么 \(u_i\) 和 \(v_i\) 也建立了通道连接。 现在在所有的情报站中，有 \(p\) 个重要情报站，其中每个情报站有一个特定的频道。 cxy 面临的问题是，需要花费最少的资源，使得任意相同频道的情报站之间都建立通道连接。 输入格式： 第一行包含三个整数 \(n,m,p\)，表示情报...

洛谷P4294 [WC2008]游览计划 题解 题目链接：P4294 [WC2008]游览计划 题意： 从未来过绍兴的 cxy 有幸参加了 Winter Camp 2008 ，他被这座历史名城的秀丽风景所吸引，强烈要求游览绍兴及其周边的所有景点。 主办者将绍兴划分为 \(n\) 行 \(m\) 列共 \(n \times m\) 个方块，如下图 \((8\times 8)\)： 景点含于方块内（图中的灰色部分），且一个方块至多有一个景点。无景点的方块视为路。 为了保证安全与便利，主办方依据路况和治安状况，在非景点的一些方块内安排不同数量的志愿者；在景点内聘请导游（导游不是志愿者）。在选择旅游方案时，保证任意两个景点之间，存在一条路径，在这条路径所经过的每一个方块都有志愿者或者该方块为景点。既能满足选手们游览的需要，又能够让志愿者的总数最少。 例如，在上面的例子中，在每个没有景点的方块中填入一个数字，表示控制该方块最少需要的志愿者数目： 图中用红色标出的方块区域就是一种可行的志愿者安排方案，一共需要 \(20\) 名志愿者。 由图可见，两个相邻的景点是直接（有景点内的路）连通...

斯坦纳树 学习笔记 斯坦纳树问题是组合优化问题1 ，其中最常见的是最小斯坦纳树问题。 我们一般使用状压dp来求解最小斯坦纳树的问题，当然也有不用状压dp的题啦（ 最小斯坦纳树 题目链接：P6192 【模板】最小斯坦纳树 题意： 给定一个包含 \(n\) 个结点和 \(m\) 条带权边的无向连通图 \(G=(V,E)\)。 再给定包含 \(k\) 个结点的点集 \(S\)，选出 \(G\) 的子图 \(G^{\prime}=(V^{\prime},E^{\prime})\)，使得： \(S\subseteq V^{\prime}\)； \(G^{\prime}\) 为连通图； \(E^{\prime}\) 中所有边的权值和最小。 你只需要求出 \(E^{\prime}\) 中所有边的权值和。 数据范围： \(1\leq n\leq 100,~1\leq m\leq 500,~1\leq k\leq 10,~1\leq u,v\leq n,~1\leq w\leq 10^6\)。 保证给出的无向图连通，但 可能 存在重边和自环。 \(\mathcal{Part\ 1}\) ...

洛谷P5210 [ZJOI2017]线段树 题解 题目链接：P5210 [ZJOI2017]线段树 题意： 线段树是九条可怜很喜欢的一个数据结构，它拥有着简单的结构、优秀的复杂度与强大的功能，因此可怜曾经花了很长时间研究线段树的一些性质。 最近可怜又开始研究起线段树来了，有所不同的是，她把目光放在了更广义的线段树上：在正常的线段树中，对于区间 \([l, r]\)，我们会取 \(m = \lfloor \frac{l+r}{2} \rfloor\)，然后将这个区间分成 \([l, m]\) 和 \([m + 1, r]\) 两个子区间。在广义的线段树中，\(m\) 不要求恰好等于区间的中点，但是 \(m\) 还是必须满足 \(l \le m < r\) 的。不难发现在广义的线段树中，树的深度可以达到 \(O(n)\) 级别。 例如下面这棵树，就是一棵广义的线段树： 为了方便，我们按照先序遍历给线段树上所有的节点标号，例如在上图中，\([2, 3]\) 的标号是 \(5\)，\([4, 4]\) 的标号是 \(9\)，不难发现在 \([1, n]\) 上建立的广义线段树，...

UOJ49 【UR #3】铀仓库 题解 题目链接：#49. 【UR #3】铀仓库 题意： 顽皮的 cxy 潜入了著名核物理专家 Picks 的研究所，走进了存放浓缩铀的仓库。 浓缩铀存放在一个个箱子里，一共有 \(n\) 叠箱子排成一条直线，不妨想象一根数轴，第 \(i\) 叠箱子坐标为 \(x_i\)，竖直方向叠着 \(a_i\) 个箱子。 cxy 脑洞大开，决定进行一项游戏。她会先选择一个整数坐标 \(s\)（可以不和任意一个 \(x_i\) 相等），然后初始时她两手空空站在坐标 \(s\) 处，进行至多 \(t\) 秒的行动。 这段时间内她的行动方式包括： 向左移动单位 \(1\) 的距离，花费 \(1\) 秒。 向右移动单位 \(1\) 的距离，花费 \(1\) 秒。 如果现在手上是空的，那么可以从当前位置拿起一个装有浓缩铀的箱子，瞬间完成。 如果现在拿着一个装有浓缩铀的箱子，那么可以把这个箱子放在当前位置所有箱子的顶部，瞬间完成。 由于 cxy 很小，任意时刻她只能拿着至多一个箱子。她希望进行至多 \(t\) 秒的行动后，初始位置 \(s\) 叠着的箱子尽量多。 ...