Q779’s Blog

洛谷P2508 [HAOI2008]圆上的整点 题解 题目链接：P2508 [HAOI2008]圆上的整点 题意： 求一个给定的圆 \((x^2+y^2=r^2)\) ，在圆周上有多少个点的坐标是整数。 输入格式： 一个正整数 \(r\) 。 输出格式： 整点个数。 数据范围： \(1\le r\leq 2\times 10^9\) 关键词：高斯素数、复平面、费马平方和定理、乘法原理 圆心为原点，半径为 \(r\) 的圆周上有多少个整点？ 实际上我们可以把这个问题转化为以下的形式 存在多少个整数对 \((a,b)\) 满足 \(a^2 + b^2 = N\) ，其中 \(N \in \mathbb{Z}^+\) 。 对于这样的二元问题，我们可以将二维平面看作复平面。 首先我们要知道这么几个前置知识。 1.高斯整数： 高斯整数是实部和虚部都为整数的复数。（只要知道这个就行了） 所有的高斯整数组成了一个整环，写作 \(\mathbb{Z}[i]\) 。 \[ \mathbb{Z}[i] = \{a+bi \mid a,b \in \mathbb{Z}\} \] 高斯整数组成了...

洛谷P4253 [SCOI2015]小凸玩密室 题解 题目链接：P4253 [SCOI2015]小凸玩密室 题意： 小凸和小方相约玩密室逃脱。 这个密室是一棵有 \(n\) 个节点的完全二叉树，每个节点有一个灯泡，点亮所有灯泡即可逃出密室。 每个灯泡有个权值 \(a_i\)，每条边也有个权值 \(b_i\)。 点亮第一个灯泡不需要花费，之后每点亮一个新的灯泡 \(v\) 的花费，等于上一个被点亮的灯泡 \(u\) 到这个点 \(v\) 的距离 \(D_{u,v}\)，乘以这个点的权值 \(a_v\) 。 在点灯的过程中，要保证任意时刻所有被点亮的灯泡必须连通，在点亮一个灯泡后必须先点亮其子树所有灯泡才能点亮其他灯泡。 请告诉他们，逃出密室的最少花费是多少。 输入格式： 第 \(1\) 行包含 \(1\) 个数 \(n\)，代表节点的个数 第 \(2\) 行包含 \(n\) 个数，代表每个节点的权值 \(a_i\)。 \((i = 1, 2,\)……\(, n)\) 第 \(3\) 行包含 \(n - 1\) 个数，代表每条边的权值 \(b_i\)，第 \(i\) 号边是由第 \...

洛谷P3915 树的分解 题解 题目链接：P3915 树的分解 题意： 给出 \(N\) 个点的树和 \(K\)，问能否把树划分成 \(\frac{N}{K}\) 个连通块，且每个连通块的点数都是 \(K\)。 输入格式： 第一行，一个整数 \(T\)，表示数据组数。接下来 \(T\) 组数据，对于每组数据： 第一行，两个整数 \(N, K\)。 接下来 \(N - 1\) 行，每行两个整数 \(A_i, B_i\)，表示边 \((A_i, B_i)\)。点用 \(1, 2, \ldots, N\) 编号。 输出格式： 对于每组数据，输出 YES 或 NO。 数据范围： 对于 \(100 \%\) 的数据，\(1 \le T \le 10\)，\(1 \le N ,K \le 10^5\)。 贪心好题。 首先 \(n \bmod k \ne 0\) 肯定无解。 考虑从下往上依次考虑每个点 如果它的 \(\mathtt{sz}_u = k\) 那就把它的砍掉，并令 \(\mathtt{sz}_u \gets 0\) 在有解的情况下，这么做一定可以分出来。 如果某个 \(\mat...

洛谷P2949 [USACO09OPEN]Work Scheduling G 题解 题目链接：P2949 [USACO09OPEN]Work Scheduling G 题意： 约翰有太多的工作要做。 为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。 他的工作日从 \(0\) 时刻开始，有 \(10^9\) 个单位时间。 在任一时刻，他都可以选择编号 \(1\) 到 \(N\) 的 \(N(1 \leq N \leq 10^5)\) 项工作中的任意一项工作来完成。 因为他在每个单位时间里只能做一个工作，而每项工作又有一个截止日期，所以他很难有时间完成所有 \(N\) 个工作，虽然还是有可能。 对于第 \(i\) 个工作，有一个截止时间 \(D_i(1 \leq D_i \leq 10^9)\)，如果他可以完成这个工作，那么他可以获利 \(P_i( 1\leq P_i\leq 10^9 )\) 。 在给定的工作利润和截止时间下，约翰能够获得的利润最大为多少。 反悔型贪心经典题。 先把所有的工作按时间限制顺序排序。 然后我们从前往后扫一遍，遇到能做的工作就把它吃了...

洛谷P2675 《瞿葩的数字游戏》T3-三角圣地 题解 题目链接：P2675 《瞿葩的数字游戏》T3-三角圣地 题意： 不是说三角形是最稳定的图形嘛，数字王国的中心便是由一个倒三角构成。这个倒三角的顶端有一排数字，分别是 \(1\sim n\)。\(1\sim n\) 可以交换位置。之后的每一行的数字都是上一行相邻两个数字相加得到的。这样下来，最底端就是一个比较大的数字啦！数字王国称这个数字为“基”。cxy 希望“基”越大越好，可是每次都自己去做加法太繁琐了，他希望你能帮他通过编程计算出这个数的最大值。但是这个值可能很大，所以请你输出它 \(\bmod 10007\) 的结果。 任务：给定 \(n\) ，求三角形 \(1\sim n\) 的基的最大值 再去 \(\bmod 10007\)。 输入格式： 一个整数 \(n\) 。 输出格式: 一个整数，表示 \(1 \sim n\) 构成的三角形的最大的“基” 。 数据范围： \(0 \le n \le 10^6\) 首先观察这个贡献是怎么算的 \[ \begin{array}{} a&b&c&d \\a...

note[5] 例：化简该复杂度 \[ \sum_{k=1}^{\pi(n)} \frac{1}{p_k} \] 其中 \(\pi(n)\) 为素数计数函数，\(p_k\) 表示第 \(k\) 大的素数。 来源于 Eratosthenes 筛法 复杂度分析 解： 引理：有以下等式 link \[ \int \frac{\mathrm{d}x}{x \ln x} = \ln(\ln x) \] 证明： 根据换元法公式：令 \(u=g(x)\) ，则 \(du = g^{\prime}(x)dx\) 。 令 \(u = \ln x\) ，则 \(\mathrm{d}u = \frac{1}{x}\mathrm{d}x\) \[ \int \frac{1}{x \ln x} \mathrm{d}x = \int \frac{1}{u} \mathrm{d}u = \ln u \] 故 \[ \int \frac{\mathrm{d}x}{x \ln x} = \ln (\ln x)\qquad \] 证毕。 \(\square\) 根据素数定理有 \(\pi(n) = \The...

洛谷P1269 信号放大器 题解 题目链接：P1269 信号放大器 题意： 树型网络是最节省材料的网络。所谓树型网络，是指一个无环的连通网络，网络中任意两个结点间有且仅有一条通信道路。 网络中有一个结点是服务器，负责将信号直接或间接地发送到各终端机。如图上方，server结点发出一个信号给结点 \(a\) 和 \(c\) ，\(a\) 再转发给 \(b\) 。如此，整个网络都收到这个信号了。 但是，实际操作中，信号从一个结点发到另一个结点，会出现信号强度的衰减。衰减量一般由线路长度决定。 如图下方，边上所标的数字为边的衰减量。假设从server出发一个强度为 \(4\) 个单位的信号，发到结点a后强度衰减为 \(4-3=1\) 个单位。结点 \(a\) 再将其转发给结点 \(b\) 。由于信号强度为 \(1\) ，衰减量为 \(2\) ，因此信号无法发送到 \(b\) 。 一个解决这一问题的方法是，安装信号放大器。信号放大器的作用是将强度大于零的信号还原成初始强度（从服务器出发时的强度）。 上图中，若在结点 \(a\) 处安装一个信号放大器，则强度为 \(4\) 的信号发到 ...

洛谷P2127 序列排序 题解 题目链接：P2127 序列排序 题意： cxy 有一个 \(n\) 个数的整数序列，这个序列的中的数两两不同。cxy 每次可以交换序列中的任意两个数，代价为这两个数之和。cxy 希望将整个序列升序排序，问 cxy 需要的最小代价是多少？ 输入格式： 第一行，一个整数 \(n\) 。 第二行，\(n\) 个整数，表示 cxy 的序列。 输出格式： 一行，一个整数，表示 cxy 需要的最小代价。 数据范围： 对于全部的数据，\(1\le n \le 10^5\) ，输入数据中的其他整数均为正整数且不超过 \(10^9\)。 属于是DP学傻了。还记得这篇么 无序数组交换任意两个元素 最少交换次数 显然这道题就是那个题的带权版。考虑贪心。 对于每个数，我们将它与它最终位置连有向边，最终显然会形成若干个环。 对于每个环，第一种方法是用它的最小值去一个个交换（逆连边方向），显然这样是优的 第二种方法是这题的关键。我们可以用环外的全局最小值去代替这个最小值换一遍。 考虑证明算法的正确性。 首先对于环内的每个点，交换一次一定减少一个错位的数。 环上任意一个点做...

洛谷P1686 挑战 题解 题目链接：P1686 挑战 题意： 桃花岛其实也没什么好玩的，黄蓉经常偷偷跑到江湖上与洪七公等人玩。于是，黄药师就经常想一些游戏与女儿玩，为了是把黄蓉留在身边，江湖险恶啊！ 这次黄药师又想了一种模拟游戏，游戏是这样的：她把整个桃花岛划分成一个坐标系。游戏开始前，黄蓉站在平面坐标系的一个点上，而她的闺房在坐标系的另一个点上，任何时候，她可以从当前所在点跨一步达到她周围的上、下、左、右四个点，黄药师不断地说四个字“东（E）”、“南（S）”、“西（W）”、“北（N）”，则黄蓉就想象着不断地从一个点走到另一个点，直至到自己的闺房为止。 比如，黄蓉开始时站在A点，她的家在B点，黄药师连续说了一串：NNNENNWWWSSW，则走了如下一个线路。然后，黄药师会问黄蓉：中间有没有走“弯路”了？即有没有捷径好走？比如，下图中就有多条捷径，可以从C走NN而到E，或走WW直接到D。 注意：捷径必须是直线。 黄药师听说你是一个程序设计高手，就想请你编个程序帮他测测这个游戏的难度，以便改进游戏规则后再让黄蓉挑战。 你的任务是：找一条最短的捷径。 输入格式： 第一行是一个整数...

洛谷P6155 修改 题解 题目链接：P6155 修改 题意： 给定一个长度为 \(n\) 的整数序列 \(a_i\)，再给定一个长度为 \(n\) 的整数序列 \(b_i\)。 你可以进行一些修改，每次你可以将一个 \(a_i\) 增加 \(1\)，花费为 \(b_i\)，你需要使所有的 \(a_i\) 不相等，且同时满足花费最少。 但 zbw 认为太过简单，于是他规定，你可以在修改前进行无限次如下操作：交换 \(b_i,b_j(1 \leq i,j \leq n)\)。 求最小的花费。 由于答案可能很大，请输出答案对 \(2^{64}\) 取模后的值。 输入格式： 第一行一个整数 \(n\)。 第二行 \(n\) 个整数，第 \(i\) 个数表示 \(a_i\)。 第三行 \(n\) 个整数，第 \(i\) 个数表示 \(b_i\)。 输出格式： 输出一行一个整数，表示答案对 \(2^{64}\) 取模的值。 数据范围： 对于所有数据 \(1 \leq n \leq 10^6\)，\(1\leq a_i,b_i\leq10^9\)。 这里的无限次交换其实就是随便顺序 贪心...

洛谷P2431 正妹吃月饼 题解 题目链接：P2431 正妹吃月饼 题意： 今天是中秋节。uim 带来了一堆大小不同且味道各异的月饼。 这些月饼的质量分别是 1g,2g,4g,8g,16g … 后面一个是前面的2倍。每种只有一个。 uim让正妹随便吃。 正妹希望尝试尽可能多的口味，所以会吃尽可能多数量的月饼（不是重量）。而且她的确有些饿了，至少总共要吃掉 \(A\) g的月饼才能满足。 然而正妹怕长胖，所以吃月饼不能合计超过 \(B\) g。 她希望知道自己最多能吃多少个月饼 输入格式： 两个数，\(A,B\)。 输出格式： 正妹能吃到最多的数量 数据范围： \(1 \le A,B \le 2^{63}-1\) 先吃块月饼再来写题解 显然我们会优先吃质量小的月饼。 但是怎么吃能保证正好在 \([A,B]\) 间呢？ 不难发现，如果要吃满 \(A\) ，能获得的最大价值就是 \(\mathrm{popc}(A)\) 这里 \(\mathrm{popc}(x)\) 表示 \(x\) 在二进制下的 \(1\) 的个数。 证明很简单（其实靠直觉看的出来） 如果想尽可能吃小的，你会发现...

note[4] 例：解方程 \[ x^4 - 2x^3 +x^2 - 15 = 0 \] 解： 令 \(y=x-\dfrac{1}{2}\) ，则 \[ -15 + \left(y + \dfrac{1}{2}\right)^2 - 2\left(y+\dfrac{1}{2}\right)^3 + \left(y + \dfrac{1}{2}\right)^4 = 0 \] 目的在于构造无奇次项的多项式。 构造方式如下： 设 \(y = x + a\) 然后代入原式，找到 \(y^3\) 的系数，这题是 \(-4a-2\) 故令 \(-4a-2=0\) 解得 \(a = -\dfrac{1}{2}\) 全部展开并整理得到 \[ y^4 - \dfrac{y^2}{2} - \dfrac{239}{16} = 0 \] 令 \(z = y^2\) ，则 \[ z^2 - \dfrac{z}{2} - \dfrac{239}{16} = 0 \] 解得 \[ z=\dfrac{1}{4} + \sqrt{15} \quad\mathtt{or}\quad z=\dfrac{1}{...