Q779’s Blog

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

洛谷P2630 图像变换 题解 题目链接：P2630 图像变换 题意： 给定 \(3\) 行 \(3\) 列的图像各像素点灰度值，给定最终图像，求最短、字典序最小的操作序列。 其中，可能的操作及对应字符有如下四种： A：顺时针旋转 \(90\) 度； B：逆时针旋转 \(90\) 度； C：左右翻转； D：上下翻转。 输入格式： 一个矩阵，表示初始的图像。 一个矩阵，表示最终的图像。 输出格式： 最短、字典序最小的操作序列，保证长度不超过 \(10^8\)，不保证有解。 若长度不超过 \(10^8\) 无解则输出 Poland cannot into space!!! 。 这种题目就是一眼暴搜。但是仔细观察可以发现有些操作其实是重复的 实际上一共只有 \(8\) 种情况，否则无解 A 顺时针转 90° B 逆时针转 90° C 左右翻转 D 上下翻转 = 左右翻转 + 转 180° AA 转 180° AB 不动 AC 左右翻转 + 顺时针转 90° BC 左右翻转 + 逆时针转 180° 显然我一开始没发现这样的性质。 但是至少可以发现两次 C 和两次 D 是浪费...

CF421D Bug in Code 题解 题目链接：CF421D Bug in Code 题意： 最近，在 “低聚果糖” 代码公司发现了一个严重的 bug！“低聚果糖” 公司的负责人 cxy 想找到罪魁祸首并惩罚他。为了这个，她组合了一场会议，主题是：谁写出了 bug？会议上一共有 \(n\) 个程序员，其中每个人都说：“我知道，一定是 \(x\) 或 \(y\) 之一！” cxy 决定选择两名嫌疑人并请到他的办公室。自然地，她需要考虑这 \(n\) 个人的观点。她想要选择这样两个人 \(u, v\)，满足 \(n\) 个人的至少 \(p\) 个人同意。一个人同意指的是，他认为 (是嫌犯) 的两个人中，至少有一个是 \(u\) 或 \(v\)。cxy 想知道，一共有多少种方案选择两名嫌疑人？ 输入格式： 第一行包含两个非负整数 \(n, p~(3 \leq n \leq 3 \times 10^5, 0 \leq p \leq n)\) ，表示 “低聚果糖” 公司中程序员的数量和需要同意的人的最小数目。 接下来的 \(n\) 行，每行包含两个整数 \(x_i, y_i~(1 ...

note[3] 例1：五个本质不同的点在没有重边或者自环的情况下，组成不同的无向图的个数是？ 解： 首先 \(5\) 个点有 \(\mathrm{C}_5^2 = 10\) 条边 每条边显然可以连也可以不连 则总方案数为 \(2^{10} = 1024\) 。 例2： 同时扔出 \(k\) 枚完全相同的六面骰子，每个骰子上有 \(1\) 到 \(6\) 的数字 将得到的点数排序后，有多少种不同的结果？ 解： \(6\) 个元素选 \(k\) 个，可以重复。显然可重组合。 \[ \mathrm{C}_{6+k-1}^{k} \]

CF1728C Digital Logarithm 题解 题目链接：CF1728C Digital Logarithm 题意： 我们定义 \(f(x)\) 表示取出 \(x\) 在十进制下的位数。( 如 \(f(114514) = 6, \; f(998244353) = 9\) )。形式化讲，就是 \(f(x) = \lfloor \log_{10} x \rfloor\) 给定两个数组 \(a\) 和 \(b\)，求执行若干次以下操作后使得 \(a\) 和 \(b\) 排序后相等的最小操作次数。 操作方法如下： 选择一个下标 \(i\)，将 \(a_i\) 赋值为 \(f(a_i)\) 或者将 \(b_i\) 赋值为 \(f(b_i)\)。 输入格式： 第一行一个整数 \(T \; (1 \le T \le 10^4)\) 表示测试样例组数。 对于每组测试样例，第一行为一个整数 \(n \; (1 \le n \le 2 \cdot 10^5)\) 表示数组长度。 接下来的两行分别有 \(n\) 个整数，表示数组 \(a\) 和 \(b \; (1 \le a_i,b_...