Q779’s Blog

洛谷P3188 [HNOI2007]梦幻岛宝珠 题解 题目链接：P3188 [HNOI2007]梦幻岛宝珠 题意： 给你 \(n\) 颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过 \(W\)，且总价值最大，并输出最大的总价值。 【数据范围】 对于 \(100\%\) 的数据，\(1\le n \le 100\)，\(1\le W,w_i,v_i \le 2^{30}\)。 保证每个 \(w_i\) 能写成 \(a \times 2^b\space (a,b \in \mathbb N)\) 的形式，\(a \leq 10\) , \(b \leq 30\)，且答案不超过 \(2^{30}\)。 注：下文中将使用 \(m\) 代替 \(W\)。 这么大的背包容量，肯定不是朴素的背包问题 可以发现数据范围里强调了 “保证每个 \(w_i\) 能写成 \(a \times 2^b\space (a,b \in \mathbb N)\) 的形式” 尽管有 \[ \forall\, x \in \mathbb{N},\exist\, a,b \in \...

洛谷P3297 [SDOI2013] 逃考 题解 题目链接：P3297 [SDOI2013] 逃考 题意：髙考又来了，对于不认真读书的小杨来讲，真不是个好消息。为了小杨能在家里认真读书，他的亲戚决定驻扎在他的家里监督他学习，有爷爷奶奶、外公外婆、大舅、大嫂、阿姨…… 小杨实在是忍无可忍了，这种生活跟监狱有什么区别！为了他亲爱的小红，为了他的dota,他决定越狱！ 假设小杨的家是个 \(x_1\times y_1\) 的矩阵，左下角坐标为 \((0,0)\) ，右上角坐标为 \((x_1,y_1)\) 。小杨有 \(n\) 个亲戚，驻扎在矩阵里（位置不同，且不在矩阵的边上）。小杨家里的每个地方都被亲戚监控着，而且只被距离最近的亲戚监控： 也就是说假设小杨所在的位置是 \((3,3)\) ，亲戚A在 \((3,0)\) ， A距离小杨距离是 \(3\)；亲戚B在 \((6,7)\) ，则B距离小杨距离是 \(5\) 。距离A<距离B，所以 \((3,3)\) 位置由A监控。 如果“最近距离”出现同时有几个亲戚，那么那个位置同时被那几个亲戚监控。 给出小杨的坐标 \((x_0,...

洛谷P3327 [SDOI2015]约数个数和 题解 题目链接：P3327 [SDOI2015]约数个数和 题意： 设 \(d(x)\) 为 \(x\) 的约数个数，给定 \(n,m\)，求 \[ \sum_{i=1}^n\sum_{j=1}^md(ij) \] 输入格式： 输入文件包含多组测试数据。 第一行，一个整数 \(T\)，表示测试数据的组数。 接下来的 \(T\) 行，每行两个整数 \(n,m\)。 输出格式： \(T\) 行，每行一个整数，表示你所求的答案。 数据范围： \(1\le T,n,m \le 50000\)。 感觉我前几篇题解的无解释推导有点不可读 所以这篇还是写的清楚一点叭 这题需要一个引理（感觉没必要记住证明的方法） 引理：设 \(d(x)\) 为 \(x\) 的约数个数，则有 \[ d(ij)=\sum_{x \mid i}\sum_{y \mid j}[\gcd(x,y)=1] \] 证明：摘自 https://siyuan.blog.luogu.org/solution-p3327 我们考虑把每个因子一一映射。 如果 \(ij\) 的因子 ...

洛谷P3336 [ZJOI2013]话旧 题解 题目链接：P3336 [ZJOI2013]话旧 题意：小林跟着银河队选手去了一趟宇宙比赛，耳濡目染，变得学术起来。回来后，他发现世界大变样了。比丘兽究级进化，成了凤凰兽；金先生因为发了一篇 paper，一跃成为教授，也成为了银河队选拔委员会成员。 一日，小林与金教授聊天。金教授回忆起过去的岁月，那些年他学过的电路原理。他曾经对一种三角波很感兴趣，并且进行了一些探究。小林感到很好奇，于是金教授就将课题形式化地说了一遍。 有一定义在 \([0,N]\) 的连续函数 \(f(x)\)，其中 \(N\) 是整数，满足 \(f(0)=f(N)=0\)，它的所有极值点在整数处取到，且 \(f(x)\) 的极小值均是 \(0\)。对于任意的 \(0\) 到 \(N-1\) 间的整数 \(I\)，\(f(x)\) 在 \((I, I+1)\) 上是斜率为 \(1\) 或 \(-1\) 的一次函数。 金先生研究的是，若他知道其中 \(K\) 个整点的函数值，那么： 有多少个函数满足条件？ 满足条件的函数中，\(f(x)\) 的最大值，最大能是多少...

洛谷P3747 [六省联考 2017] 相逢是问候 题解 题目链接：洛谷P3747 [六省联考 2017] 相逢是问候 题意：B 君希望以维护一个长度为 \(n\) 的数组，这个数组的下标为从 \(1\) 到 \(n\) 的正整数。 一共有 \(m\) 个操作，可以分为两种： 0 l r 表示将第 \(l\) 个到第 \(r\) 个数（ \(a_l,a_{l+1} ...a_r\)）中的每一个数 \(a_i\) 替换为 \(c^{a_i}\) ，即 \(c\) 的 \(a_i\) 次方，其中 \(c\) 是输入的一个常数，也就是执行赋值 \(a_i = c^{a_i}\)。 1 l r 求第 \(l\) 个到第 \(r\) 个数的和，也就是输出： \(\sum_{i=l}^{r}a_i\) 因为这个结果可能会很大，所以你只需要输出结果 \(\bmod \ p\) 的值即可。 建议先去做一做 P4139 和 P4145 ，这道题就是这俩的综合加强版本 题解在这里 link1 link2 有个结论 \[ O(\varphi^* (p)=1)=O(\log p) \] 注：这里...

洛谷P3935 Calculating 题解 题目链接：P3935 Calculating 题意： 若 \(n\) 的分解质因数结果为 \(\prod_{i=1}^{s}p_i^{k_i}\) 令 \(f(n) = \prod_{i=1}^{s}(k_i+1)\) 求 \[ \sum\limits_{i=l}^{r}f(i) \bmod 998244353 \] 根据容斥原理，可以把答案分为两个部分 \[ \sum_{i=l}^{r}f(i) = \sum_{i=1}^{r}f(i) - \sum_{i=1}^{l-1}f(i) \] 然后推推柿子 \[ \begin{aligned} \sum_{i=1}^{r}f(i) &= \sum_{i=1}^{r}\prod_{j=1}^{s_i}{(k_{ij}+1)} \\&=\sum_{i=1}^{r}\sum_{d\mid i}1 \\&=\sum_{i=1}^{r}\left\lfloor\dfrac{r}{i}\right\rfloor \end{aligned} \] 于是有 \[ \sum_{...

洛谷P3985 不开心的金明 题解 题目链接：P3985 不开心的金明 题意： 金明今天很不开心，家里购置的二手房就要领钥匙了，房里并没有一间他自己专用的很宽敞的房间。更让他不高兴的是，妈妈昨天对他说：“你需要购买哪些物品，怎么布置，你说了不算（有很大的限制），而且不超过 \(W\) 元钱。”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 \(W\) 元。于是，他把每件物品规定了一个重要度整数 \(p_i\) 表示。他还从因特网上查到了每件物品的价格 \(v_i\) （都是整数元）。 妈妈看到购物单后进行了审查，要求购物单上所有的物品价格的极差（最贵的减去最便宜的）不超过\(3\)（当然金明至今不知道为什么会这样）。他希望在不超过 \(W\) 元（可以等于 \(W\) 元）的前提下，使购买的重要度总和 \(\sum p_i\) 的最大。 请你帮助金明设计一个满足要求的购物单，你只需要告诉我们重要度的最大的和。 数据保证：\(\max(v_i)-\min(v_i) \le 3\) 数据范围：\(1 \le N \le 100 ,1\le p_i \le ...

洛谷P4095 [HEOI2013]Eden 的新背包问题 题解 题目链接：P4095 [HEOI2013]Eden 的新背包问题 题意： 失忆的 Eden 总想努力地回忆起过去，然而总是只能清晰地记得那种思念的感觉，却不能回忆起她的音容笑貌。 记忆中，她总是喜欢给 Eden 出谜题：在 valentine’s day 的夜晚，两人在闹市中闲逛时，望着礼品店里精巧玲珑的各式玩偶，她突发奇想，问了 Eden 这样的一个问题：有 \(n\) 个玩偶，每个玩偶有对应的价值、价钱，每个玩偶都可以被买有限次，在携带的价钱 \(m\) 固定的情况下，如何选择买哪些玩偶以及每个玩偶买多少个，才能使得选择的玩偶总价钱不超过 \(m\)，且价值和最大。 众所周知的，这是一个很经典的多重背包问题，Eden 很快解决了，不过她似乎因为自己的问题被飞快解决感到了一丝不高兴，于是她希望把问题加难：多次询问，每次询问都将给出新的总价钱，并且会去掉某个玩偶（即这个玩偶不能被选择），再问此时的多重背包的答案（即前一段所叙述的问题）。 这下 Eden 犯难了，不过 Eden 不希望自己被难住，你能帮帮他么？ 数...

洛谷P4145 上帝造题的七分钟 2 / 花神游历各国 题解 题目链接：P4145 上帝造题的七分钟 2 / 花神游历各国 题意：维护一个数据结构 区间sqrt()（对每个数开平方+下取整） 询问区间和 \(\sqrt{a+b} \ne \sqrt{a}+\sqrt{b}\) 因此无法用线段树维护 那么怎么搞呢？注意到数据范围中，每个数都为正整数，且不超过 \(10^{12}\) \(\sqrt{1}=1\) \(\left(10^{12}\right)^{2^{-6}} \approx 1\) 可以发现，对于一个数，最多进行 \(6\) 次sqrt()操作，它就变成 \(1\) 不变了 于是我们还是用线段树，每次修改直接暴力递归到叶子节点进行修改 诶？不是说不能用线段树吗？怎么又用了？ 因为区间和是可以用线段树维护的呀！qwq 只不过这个开平方没法维护，直接“暴力” 根据势能分析，可知 时间复杂度（ \(n,m\) 同阶 ） \[ O\left(n+n\times \dfrac{6n}n\log n\right) = O(n + 6n \log n) = O(n\l...

洛谷P4141 消失之物 题解 题目链接：P4141 消失之物 题意：ftiasch 有 \(n\) 个物品, 体积分别是 \(w_1,w_2,\dots,w_n\) 。由于她的疏忽，第 \(i\) 个物品丢失了。 “要使用剩下的 \(n-1\) 物品装满容积为 \(x\) 的背包，有几种方法呢？”——这是经典的问题了。 她把答案记为 \(\text{cnt}(i,x)\)，想要得到所有 \(i \in [1,n] ,x \in [1,m]\) 的 \(\text{cnt}(i,x)\) 表格。 只需要输出末位数字。 设 \(f[i][j]\) 为只用前 \(i\) 件物品，不考虑删除任何物品时，恰好装满容量为 \(j\) 的背包的方案数，显然有 \[ f[i][j]=f[i-1][j]+f[i-1][j-w[i]] \] 滚动数组一下就是 f[0]=1; for(int i=1; i<=n; i++) for(int j=m; j>=w[i]; j--) f[j]+=f[j-w[i]]; 那么现在求出来的 \(f[i]\) 也就是原来的 \(f[n][i]\) ...

洛谷P4139 上帝与集合的正确用法 题解 题目链接：P4139 上帝与集合的正确用法 题意： 有无穷数列 \[ a_0=1,a_n=2^{a_{n-1}} \] 当 \(n \to +\infty\) 时，计算 \[ a_n \bmod p \] 即 \[ {2}^{ {2}^{ {2}^{ {.}^{ {.}^{ {.}^{2} } } } } } \bmod p \] 可以证明 \(a_n\bmod p\)在 \(n\) 足够大时为常数 多组数据 \(1\le Q\le 10^3\) ，\(1 \le p\le 10^7\) 其实这个题很简单 根据扩展欧拉定理，有 \[ \begin{aligned} a^b \equiv \begin{cases} a^b,&b< \varphi(m)\\\\ a^{b \ \bmod \ \varphi(m)+\varphi(m)},&b\ge \varphi(m) \end{cases} \pmod{m} \end{aligned} \] 显然当 \(n\) 足够大时，有 \(a_{n-1} > \va...

洛谷P4158 [SCOI2009]粉刷匠 题解 题目链接：P4158 [SCOI2009]粉刷匠 题意：windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。 windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？ 一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。 比较简单的dp 设 \(f[i][j]\) 为前 \(i\) 块木板粉刷 \(j\) 次的情况下能正确粉刷的最大格子数 设 \(g[i][j][k]\) 为第 \(i\) 条木板粉刷 \(j\) 次且只涂了前 \(k\) 个格子的情况下能正确粉刷的最大格子数 设 \(S[i][j]\) 为第 \(i\) 条木板前 \(j\) 个格子的蓝色格子数 不难发现 \[ f[i][j]=\max(f[i][j],f[i-1][j-k]+g[i][k][m]) \\g[i][j][k]=\max(g[i][j][k],g[i][j-1][l]+\max(S[i][k]-S[...