Q779’s Blog

洛谷U148215 Q数 题解 题目链接：U148215 Q数 （改编自 CF96B） 本题为私题，作者 q779 （没错，就是本人！） 题意： q779最近迷上了一种数，叫做Q数 Q数是数码仅由1或6构成的素数，例如 \(11\) 是一个Q数，\(61\) 也是一个Q数 q779想知道第一个比 \(N\) 大的Q数是多少，多组询问。 输入格式： 第一行 给出数据组数 \(T\) 接下来 \(T\) 行 分别给出每一个 \(N\) 输出格式： 对于每组数据输出第一个比 \(N\) 大的Q数 数据范围： \(1 \le T \le 10,1 \le N \le 1\times 10^{13}\) 这道题纯属是做了 CF96B 以后搞得同类型题，看得出来我一点都不会出题，最多普及-吧。 这题非常简单，既然只有 \(1\) 和 \(6\) ，那就枚举所有的数就可以了，总共不超过 \(O(n2^n)\) 个 代码： // 2021年01月07日 23:47:57 #include<bits/stdc++.h> using namespace std; #define int l...

LOJ10180 「一本通 5.5 练习 1」烽火传递 题解 题目链接：「一本通 5.5 练习 1」烽火传递 题意： 原题来自：NOIP 2010 提高组初赛 · 完善程序 烽火台是重要的军事防御设施，一般建在交通要道或险要处。一旦有军情发生，则白天用浓烟，晚上有火光传递军情。 在某两个城市之间有 \(n\) 座烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确传递，在连续 \(m\) 个烽火台中至少要有一个发出信号。现在输入 \(n,m\) 和每个烽火台的代价，请计算总共最少的代价在两城市之间来准确传递情报。 输入格式： 第一行是 \(n,m\)，表示 \(n\) 个烽火台和连续烽火台数 \(m\)； 第二行 \(n\) 个整数表示每个烽火台的代价 \(a_i\)。 输出格式： 输出仅一个整数，表示最小代价。 记得哪次模拟赛考过一题，在区间中选不相连的若干段且每段长度都不超过 \(m-1\) ，求最大的和。 这题实际上就是反过来的，而且还有两个城市需要连起来。 首先我们在序列左右各放一个花费为 \(0\) 的烽火台，然后设 \(f_i\) 为 \(i\) 必选时的最小...

洛谷U187024 Cell Membrane 题解 题目链接：U187024 Cell Membrane 本题为私题，作者 q779 （没错，就是本人！） 题目背景： 细胞就像一座化工厂，各个车间（细胞器）有条不紊，忙忙碌碌地生产着各种各样的化学物质，在领导细胞核同志的调控下，共同为化工厂的未来奋斗 工厂人员（化学物质）流动十分频繁，为了保证“工厂“的安全运作，工厂请了一位保安，叫细胞膜 他的日常工作就是检查每一位进出工厂的人 今天他生病了，所以想请你帮帮忙 题目描述： 保安给了你一张工厂人员名单表，（用于检查每个要进工厂上班的人是否为员工，不是员工则不能进入），每个人有唯一的编号 \(a_i\) （正整数） 由于员工的流动性，有一些员工会提前下班，一些下班或休息的员工也会回来继续加班 尊敬的领导细胞核同志要来视察，他会询问编号小于 \(x\) 且在上班的人有多少个 为了方便起见，我们可以把这些条件看作 \(m\) 个操作 输入数据将由以下格式给出 1 x 表示编号为x的人想要进入工厂 2 x 表示编号为x的人离开了工厂 3 x 表示询问编号小于x且在上班的人的个数 输入...

洛谷U148838 数学黑洞 题解 题目链接：U148838 数学黑洞 本题为私题，作者 q779 （没错，就是本人！） 题意： 给定 \(N \le 10^{114514}\) ，求 \(F(N)=f(f(f(\cdots f(N))))\)​ 。 其中 \(f(N)=N\) 中偶数的个数 \(\times 100+ N\) 中奇数的个数 \(\times 10 + N\) 的位数。 例如 \[ f(345)=1\times100+2\times10+3=123 \] 题目保证一定有解。 输入：一行，\(N\)​ 。 输出：一行，答案。 这道题是我初中的时候出的，当时从学校的数学报纸上看到的，难度评级入门到普及-吧。 实际上就是“西西弗斯串”（也叫 \(123\) 数字黑洞），有兴趣可以百度（百度写的还可以）。 注意到 \(f(123)=123\) ，即 \(123\)​ 是原题的一个不动点。有趣的是，实际上任何 \(N \in \mathbb{Z}\) 有 \(F(N)=123\)​ 。 以下记 \(f\) 中的三个数分别为 \(a,b,c\) ，即 \(f(N) = 1...

拉格朗日中值定理 拉格朗日中值定理，也简称均值定理，是以法国数学家约瑟夫·拉格朗日命名，为罗尔中值定理的推广，同时也是柯西中值定理的特殊情形。拉格朗日中值定理也叫做有限增量定理。 拉格朗日中值定理是三大微分中值定理之一。 1. 内容 如果函数 \(f(x)\) 满足 在闭区间 \([a,b]\) 上连续 在开区间 \((a,b)\) 内可微分 则至少有一点 \(\xi(a < \xi < b)\) ，使得 \[ f^{\prime}(\xi) = \frac{f(b)-f(a)}{b-a} \] 2. 证明 令 \(g(x)=\frac{f(b)-f(a)}{b-a} \cdot(x-a)+f(a)-f(x)\) ，那么 \(g\) 在 \([a,b]\) 上连续 \(g\) 在 \((a,b)\) 上可微分 \(g(a)=g(b)=0\) 。 由罗尔定理，存在至少一点 \(\xi \in(a,b)\) 使得 \(g^{\prime}(\xi) = 0\) ，即 \(f^{\prime}(\xi)=\frac{f(b)-f(a)}{b-a}\) 。 3...

网易云音乐播放器 HTML 嵌入 单曲播放： <iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width="300" height=86 src="//music.163.com/outchain/player?type=2&id=2149243877&auto=0&height=66"></iframe> 效果： 参数： width=100% 播放器宽度（自适应） height=86 播放器高度 id=2149243877 为歌曲的ID auto=0 0为不自动播放，1为自动播放 列表循环： <iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width="100%" height=110 src="//music.163.com/outchain/player?type=0&id=7553671185&auto=0&height=9...

洛谷P3704 [SDOI2017] 数字表格 题解 题目链接：P3704 [SDOI2017] 数字表格 题意： \(q\) 组询问，给定 \(n,m\) ，求 \[ \mathrm{Ans} = \prod_{i=1}^n\prod_{j=1}^{m}F_{\gcd(i,j)} \] 其中 \(F\) 的幂次可以快速计算（在本题中是斐波那契数列，\(F_0=0,F_1=1\) ） \(1\le q \le 10^3,1 \le n,m \le 10^6\)​ 莫比乌斯反演 + 数论分块。 既然 \(F\) 可以快速计算，那就是叫我们统计 \(F(k)\) 是怎么贡献的了。 \[ \prod_{i=1}^n\prod_{j=1}^{m}F_{\gcd(i,j)} = \prod_{k=1}^nF_k^{\sum_{i=1}^n \sum_{j=1}^m[\operatorname{gcd}(i, j)=k]} \] 把上面那一堆提出来 \[ \begin{aligned} \sum_{i=1}^n \sum_{j=1}^m[\operatorname{gcd}(i, j)=...

note[16] 本题主要考察了欧拉函数 \(\varphi\) 和莫比乌斯函数 \(\mu\) 的互相转换。 题： \[ \lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{i=1}^n \varphi(i) \] 解： \[ \begin{aligned} \lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{i=1}^n \varphi(i) & = \lim _{n \rightarrow+\infty}\frac{1}{n^2} \sum_{i=1}^n\sum_{d=1}^i [\gcd(d,i)=1] \\[6pt]& =\lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{i=1}^n\sum_{d=1}^i\sum_{k \mid \gcd(d,i)}\mu(k) \\[6pt]& =\lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{i=1}^...

SP4195 MSE08H - GCD Determinant 题解 题目链接：MSE08H - GCD Determinant 题意： 给定 \(n\) 个数 \(x_1,x_2,\cdots,x_n\) ，求 \[ \det A = \left|\begin{array}{ccccc} \operatorname{gcd}\left(x_1, x_1\right) & \operatorname{gcd}\left(x_1, x_2\right) & \operatorname{gcd}\left(x_1, x_3\right) & \ldots & \operatorname{gcd}\left(x_1, x_n\right) \\ \operatorname{gcd}\left(x_2, x_1\right) & \operatorname{gcd}\left(x_2, x_2\right) & \operatorname{gcd}\left(x_2, x_3\right) & \ldots & \oper...

UVA11270 Tiling Dominoes 题解 题目链接：Tiling Dominoes 题意： 给定一个 \(n\times m(\le 100)\) 的矩形网格，在里面放 \(1\times 2\)​ 的多米诺骨牌，求方案数 以下是一种方案。 注意，旋转后本质相同的方案也算作不同方案。 这道题是比较简单的插头dp，所以本文会以简单的方式来介绍插头dp。 插头dp作为模板题是黑题的高级算法，本身的思想其实没有那么复杂，它实际上就是状压dp。 观察本题的图片可以发现，我们没法从某个子矩形的答案直接转移到整个矩形 于是我们就考虑最朴素的，一格一格的逐行递推，也就是下图这种形式（图是题解区偷的） 然后我们发现转移需要上面格子和左边格子的填充信息，而只记录这两个信息就无法转移 又因为这个 \(n\) 比较小，考虑状压dp。 设 \(f(i,S)\) 表示处理到第 \(i\) 行，上图中白色格子的填充状态为 \(S\) 时的方案数。 然后分类讨论上面格子和左面格子的填充情况： 上面没有，左边没有。这种情况必须向上放。 上面没有，左边有。这种情况必须向上放。（转移可以和上...

Smith’s determinant（GCD矩阵的行列式） 翻译&修改自英文原文 Smith’s determinant Smith’s determinant： \[ \left|\begin{array}{cccc} \operatorname{gcd}(1,1) & \operatorname{gcd}(1,2) & \ldots & \operatorname{gcd}(1, n) \\ \operatorname{gcd}(2,1) & \operatorname{gcd}(2,2) & \ldots & \operatorname{gcd}(2, n) \\ \vdots & \vdots & & \vdots \\ \operatorname{gcd}(n, 1) & \operatorname{gcd}(n, 2) & \ldots & \operatorname{gcd}(n, n) \end{array}\right|=\varphi(1) \varph...

UVA10934 Dropping water balloons 题解 题目链接：Dropping water balloons 题意： 这是新生周，今年你的朋友们决定通过向新的计算机科学学生扔水球来进行入门仪式。他们已经装满了一大箱相同的水球，准备好参加活动。但命运会有意想不到的安排，水球竟然非常坚固，可以从几层楼高的地方掉下来而不破裂！ 因此，你的朋友们找到了你求助。他们计划从校园里的一座高楼上扔水球，但希望尽可能少地花费力气将水球拿上楼梯，因此他们想知道从哪一层楼最低的楼层可以扔水球以确保它们会破裂。 你知道这栋建筑有 \(n\) 层楼，你的朋友们给了你 \(k\)​​ 个相同的水球，你可以在试验中使用（和破坏）。 由于你也很懒，你想确定你必须进行的最少试验次数，以确切地确定可以从哪一层楼扔水球以确保它会破裂（或者在最坏的情况下，即使从顶层扔下，水球也不会破裂）。 一个试验包括从某一层楼扔下一个水球。如果一个水球在试验中没有破裂，你可以取回它，并再次用于另一个试验。 输入：多组数据，每次给定 \(k,n\) 。 输出：答案，超过 \(63\) 次则输出 More than...