Q779’s Blog

LOJ6568 「Project Euler 9」特殊勾股数 题解 题目链接：#6568. 「Project Euler 9」特殊勾股数 题意： 一组勾股数由三个自然数组成，\(a < b < c\) ，且 \[ a^2 + b^2 = c^2 \] 例如，\(3^2 + 4^2 = 9 + 16 = 25 = 5^2\)。 给出 \(N\)，请输出所有满足 \(a + b + c = N\) 的勾股数。 输入格式： 只有一行，一个整数 \(N\)。 输出格式： 多行，每行三个整数，\(a, b, c\) ，表示答案。 数据范围： 对于 \(100\%\) 的数据，\(N \leq 10^{12}\)。 想起上次做的圆上的整点，差点开始异想天开了 考虑一组 \(a,b,c\) 是勾股数的充要条件。 不妨设 \(a,b < c\) ，\(a,b\) 大小关系忽略，且 \(\gcd(a,b,c) = 1\) 。 则可以假设 \(a\) 为偶数，\(b,c\) 为奇数。 因为 \(a^2 + b^2 = c^2\) ，若 \(c\) 为偶数，则 \(a,b\) 均...

洛谷P4228 [清华集训2017] 榕树之心 题解 题目链接：P4228 [清华集训2017] 榕树之心 题意： 一棵榕树可以抽象成一棵 \(n\) 个结点的有根树，其中结点编号为 \(1 \sim n\) ，而 \(1\) 号点就是根节点。初始时，树只有一号点，而心也在一号点。之后每一步，树都会长出一个新结点，即某个和当前已经存在的某个结点相邻的结点被加入了树中，之后，心会沿着心到新加结点的简单路径移动一步。这棵 \(n\)个结点的树有很多种生长的顺序，不同的顺序可能会导致最终心的位置不同。现在，Evan和Lyra想知道，哪些结点可能是心在生长过程结束时停留的位置呢？ 例如一棵大小为 \(4\) 的树，连边为 \(\{\langle 1,2 \rangle,\langle 1,3 \rangle,\langle 1,4 \rangle\}\) ，我们有三种不同的生长顺序可以让心分别停留在 \(2,3,4\) 号节点上： 最终停留在 \(2\) 号点： 从1生长出3，心从1移动到3, 从1生长出4，心从3移动回1, 从1生长出2，心从1移动到2. 最终停留在 \(3\) 号点...

CF364D Ghd 题解 题目链接：CF364D Ghd 题意： 定义一组数 \(a_1, a_2, \cdots, a_n\) 的半最大公约数 (Greatest half-common divisor, GHD) 为最大的整数 \(d\)，满足 \(a_1, a_2, \cdots, a_n\) 中至少有 \(\left \lceil \frac{n}{2} \right \rceil\) 个 \(d\) 的倍数。 给定 \(n\) 个正整数 \(a_1, a_2, \cdots, a_n\)，请你求出它们的半最大公约数。 输入格式： 第一行包含一个正整数 \(n~(1\le n \leq 10^6)\)，表示数的个数。 第二行包含 \(n\) 个正整数 \(a_1, a_2, \cdots, a_n(1 \leq a_i \leq 10^{12})\)，表示这 \(n\) 个数的值。 输出格式： 输出一行一个整数，表示这些数的半最大公约数。 前置知识：\(d(10^{12}) \le 6720\) 。 注意到最终的 GHD 的集合 \(S\) 中，一定存在至少一个 \...

洛谷P3275 [SCOI2011]糖果 题解 题目链接：P3275 [SCOI2011]糖果 题意： 幼儿园里有 \(N\) 个小朋友，cxy 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，cxy 需要满足小朋友们的 \(K\) 个要求。幼儿园的糖果总是有限的，cxy 想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。 输入格式: 输入的第一行是两个整数 \(N,K\)。接下来 \(K\) 行，表示这些点需要满足的关系，每行 \(3\) 个数字，\(X,A,B\) 。 如果 \(X=1\)， 表示第 \(A\) 个小朋友分到的糖果必须和第 \(B\) 个小朋友分到的糖果一样多； 如果 \(X=2\)， 表示第 \(A\) 个小朋友分到的糖果必须少于第 \(B\) 个小朋友分到的糖果； 如果 \(X=3\)， 表示第 \(A\) 个小朋友分到的糖果必须不少于第 \(B\) 个小朋友分到的糖果； 如果 \(X=4\...

洛谷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\)，表示情报...