Fanyi's Blog

设计一个数据结构. 给定一个正整数数列 \(a_0, a_1, ..., a_{n - 1}\)，你需要支持以下两种操作： \(n \le 100000\)，\(q \le 10000\)，\(a_i \le 10^9 (0 \le i < n)\)，QUERY x 中的 \(x \le 10^{18}\)，MODIFY id x 中的 \(0 \le id < n\)，\(1 \le x \le 10^9\)。 前缀 \(\gcd\) 序列有一个有趣的性质，那就是后一个数一定是前一个数的因数，所以至少会除 \(2\)。 于是我们发现前缀 \(\gcd\) 序列之多只会有 \(\log\) 个不同的数。 考虑到 \(\gcd\) 与 \(\bigotimes\) 没有什么太大的联系，我们考虑枚举 \(\gcd\)，然后找出…

给下一届出题，自然是出得水一点比较好咯～ 查看题目 PDF 戳这里下载 查看题解 PDF 由于数据太大，放百度网盘上去了，戳这里下载 提取码：xc6z 戳这里下载，包括一些暴力

给你一块巧克力，横着最多切 \(a\) 刀，竖着最多切 \(b\) 刀，定义每切一刀的收益为切完后所有巧克力的和，每次随机在能切的所有地方等概率随机切一刀，求切 \(k(k\le a + b)\) 到刀得到收益的期望。答案对 \(998244353\) 取模。 \(a, b\le 10^{18}\)。 我们考虑每个正方形左下角（如下图）为贡献，如黄色格子的贡献我们看成是点 \(P\) 的贡献，那我们可以把点分成三类：中间的（红色点），边缘的（蓝色点），左下角的（绿色点）。 如果一个点“暴露在了外面”，即该点对应的方块成为了整个方块的左下角，那么之后每切一次它就会对答案有 \(1\) 的贡献。 首先我们来看中间的点（红点）。 对于每个点，如果第 \(i\) 次切割后它暴露在外面，那么前 \(i\) 次切割必定有一次切了它所在竖列，还有一次且了它所在横行。所以有…

给你讲个鬼故事。 有一只神犇叫 Wzp，模拟赛时出了一道计算几何题，精度开到了 1e-13。 题目大意就是给你一个 \(\Delta ABC\) 和 \(n(n\le 1000)\) 个向量，你可以在其中选至多 \(k\) 个作用在 \(A\) 上，使最终得到的三角形周长最长。特别的，这个三角形可以退化成一条线，其实只要算 \(AB+BC+AC\) 就可以了。 其中所有给出的数据（包括向量的 \(x, y\)）都是整数。 正解在这里就不说了我才不会告诉你是因为我不会做这道题，重点是那个细节，也就是 1e-13 的精度应该怎么整。 重点就是那个 sqrt，这玩意考场上测了一下（用 long double）精度大概只有 \(10^{-8}\sim 10^{-9}\)，直接悲惨爆 0…… 有一个很妙的 trick，我们设需要计算 \(s=\sqrt{x}\)，我们设 \(s\) 的整数部分是…

成功抢到 luogu 最劣解+bzoj 最劣解（至少我提交的时候是这样）…… 题意是给你一张拓扑图，求出一个拓扑序使得第 \(i\) 个点在第 \(k_i\) 个位置之前。先构造一组解，然后输出每个点可以到的最小的位置。 构造一组解很简单，建个反图之后按 \(k_i\) 为关键字排序一下，从小到大一个一个遍历即可。因为如果 \(k_i\) 小的航班都没有开出，开 \(k_i\) 大的显然没有意义。 然后我们发现如果给出的 \(k\) 序列无解，那么输出的序列一定不合法（怎么可能合法？），然后我们发现可以二分。 复杂度？\(\mathcal{O}(nm\log n)\)……显然 T，T 了 4 个点。 然后开始 \(\mathcal{O}(\text{松})\) 卡常。 然后发现它过了。 虽然我卡了一年…… 下面是卡完的代码：

把正整数 \(n\) 分解成几个正整数的和，是它们的乘积最大。 以下纯口胡，如果有问题求在下面留言。 根据均值不等式（证明在最下面）： 先不考虑整数的限制，我们应将一个数均匀地分成 \(k\) 份，每个数为 \(x\)，那么有： 另乘积为 \(y\)，有： 于是问题就变成了求 \(y=x^{\frac{1}{x}}​\) 在 \(x>0​\) 上的极值。 两边同取对数： 两边同时关于 \(x\) 求导： 右边应该没问题，那左边为什么不是 \(\frac{1}{y}​\) 呢？ 因为 \(y\) 是个因变量，其导数不一定就是 \(1\)，即 \(x\) 增加 \(\mathrm{d}x\)，\(y\) 不一定增加 \(\mathrm{d}x\)。 但我们有： 于是： 当 \(y'=0\) 时： 由于 \(x>0\)： 即： 但 \(e\) 不是整数，由于…

并没想打算开篇小小结，只是随便写写（感觉开小小结的成本太高了啊……） 感觉还是挺妙的。以前听zyy 大佬讲课的时候说过，函数的积分用二次函数拟合一下。 加入我们要算 \(\int_l^r F(x)\mathrm{d}x\)，我们用二次函数 \(f(x)=ax^2+bx+c\) 来拟合。 我们发现： 于是我们有： 然后就可以拟合辣！ 然而就是要么 WA（炸精度）要么 T…… 有一种叫自适应辛普森的方法解决这个问题，我们用辛普森计算 \(\int_l^rF(x)\mathrm{d}x\)，\(\int_l^{(l+r)/2}F(x)\mathrm{d}x\)，\(\int_{(l+r)/2}^rF(x)\mathrm{d}x\) 的值，如果 那么直接返回值，否则递归下去算。 upd：忽然发现我学了个假的 simpson。其实 eps 应该是相对误差，所以每次递归下去时…

一道毒瘤的大模拟。 查看题目 PDF 题目大概就是让你写一个叫“Mua 语言”解释器，这是第一步，就是把输入代码中的每个“token”（词法单元）都分开来。 一共有六种 token（Mua 语言严格区分大小写）： RESERVED（保留字）： 下面列出所有保留字（福利：附赠 c++ 代码）： NUMBER（数字常量）： 需要注意的是负数包含两个 token，“-”是单独的一个 token，下面会说。 STRING（字符串）： 由双引号 "" 或单引号 '' 包围的字符串常量，只支持四种转义字符：\"，\'，\\，\n。字符串内部不能有物理换行符。 SYMBOL（符号）： 英文 pdf 假掉了，有几个 SYMBOL 没有完全显示。 直接赠送 c++ 代码： NAME（标识符）： 必须以字母开头，后跟若干个字母、数字或者下划线。注意，保留字不能作为标识符。 EOL（物理换行符）： 不多说，都懂…

原题链接 有一棵树，第 \(i\) 个节点上有 \(k_i\) 只海狸。现在，有一只吃海狸的机器"Beavermuncher-0xFF"从根节点 \(s\) 出发，每吃一只海狸，它就能够且必须走到与该节点两边的下一个节点并吃掉那个节点上的一只海狸。该机器每到一个节点，一次都只能吃一只海狸。要求最终机器回到根节点。问该机器最多能吃多少只海狸。 先输入节点个数 \(n(n\le 10^5)\)，然后是 \(n\) 个整数 \(k_i\)，后面 \(n−1\) 行描述一棵树，最后一个整数表示根节点 \(s\)。 样例一大概是这样一幅图： 不难发现从一个节点出发，没前往它的一棵子树，都要花费 \(1\) 的代价（废话）。 回到父亲又要花费 \(1\) 的代价。 所以一个显然的贪心策略就是先花费 \(k_{i-1}\) 的代价“游历”各个儿子，然后再返回父亲。 令 \(dp[i]\) 表示从…

有两个快递员，分别在 \(s_1, s_2(0\le s_1,s_2\le 10^9)\)，现在有 \(n(1\le n\le 100000)\) 个任务，每个任务 \(x_i\) 表示要将货物送到 \(x_i\)，让任何一个快递员到 \(x_i\) 都可以。由于快递员之间需要有对讲机联系，请你设计一种方案使得两个快递员之间的最长距离最短。 先输入 \(n,s_1,s_2\)，在一行 \(n\) 个整数 \(x_i\)。 CF 如此多的二分+贪心，但我就是想不出来…… 首先二分答案。 难点是在如何判断答案合法。 显然正着做是不行的，所以我们考虑倒着做。 我们考虑现在二分的距离为 \(L\)，枚举到第 \(i\) 步，如果两个快递员中至少有一个的起点出现在 \([l_i,r_i]\) 的范围内，且两个快递员相距不超过 \(L\)，那么是合法的。 现在考虑从…