Q779’s Blog

洛谷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 不希望自己被难住，你能帮帮他么？ 数...

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

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

洛谷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[...

洛谷P4310 绝世好题 题解 题目链接：P4310 绝世好题 题意：给定一个长度为 \(n\) 的数列 \(a_i\) ，求 \(a_i\) 的子序列 \(b_i\) 的最长长度 \(k\)，满足 \(b_i \& b_{i-1} \ne 0\)，其中 \(2\leq i\leq k\)， \(\&\) 表示位运算取与。 设 \(dp[i][j]\) 为前 \(i\) 个数的每个子序列的最后一个数第 \(j\) 位为 \(1\) 的最大长度 然后对于每个数枚举一遍dp，再转移一遍dp即可 注意到这个递推式可以滚动数组，然后搞一搞就好了 答案就是 \(\max(dp[i][j])\) 时间复杂度 \(O(n \log \max(a_i))\) 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)() int n,res,dp[35]; signed main() ...

洛谷P4342 [IOI1998]Polygon 题解 题目链接：P4342 [IOI1998]Polygon 题意：多边形是一个玩家在一个有 \(n\) 个顶点的多边形上的游戏，如图所示，其中 \(n=4\) 。每个顶点用整数标记，每个边用符号+（加）或符号*（乘积）标记。 第一步，删除其中一条边。随后每一步： 选择一条边连接的两个顶点V1和V2，用边上的运算符计算V1和V2得到的结果来替换这两个顶点。 游戏结束时，只有一个顶点，没有多余的边。 如图所示，玩家先移除编号为3的边。之后，玩家选择计算编号为1的边，然后计算编号为4的边，最后，计算编号为2的边。结果是0。 这里每条边的运算符旁边的数字为边的编号，不拿来计算 编写一个程序，给定一个多边形，计算最高可能的分数。 \(3 \le n\le 50\) 对于任何一系列的操作，顶点数字都在 \([-32768,32767]\) 的范围内。 容易发现我们需要断环为链，然后区间dp 注意到存在负数，而负负得正，说明不是简单的区间dp 不难发现两个负的极小值之乘积对答案有更大贡献 考虑维护区间最大值的同时维护区间最小值 即，设...

洛谷P4390 [BOI2007]Mokia 摩基亚 题解 题目链接：P4390 [BOI2007]Mokia 摩基亚 题意：摩尔瓦多的移动电话公司摩基亚（Mokia）设计出了一种新的用户定位系统。和其他的定位系统一样，它能够迅速回答任何形如“用户 C 的位置在哪？”的问题，精确到毫米。但其真正高科技之处在于，它能够回答形如“给定区域内有多少名用户？”的问题。 在定位系统中，世界被认为是一个 \(w×w\) 的正方形区域，由 \(1\times 1\) 的方格组成。每个方格都有一个坐标 \((x,y)\)，\(1\leq x,y\leq w\)。坐标的编号从 \(1\) 开始。对于一个 \(4\times 4\) 的正方形，就有 \(1\leq x\leq 4\)，\(1\leq y\leq 4\)（如图）： 请帮助 Mokia 公司编写一个程序来计算在某个矩形区域内有多少名用户。 这道题的题解区一片互相抄袭的烂货，实在受不了了就来水一篇题解 可以发现这道题目就是个二维数点问题，不知道的推荐看看 这篇博客 然后这道题目，我们不能用归并排序来做 为什么呢？因为这个题目它还有一...

洛谷P4395 [BOI2003]Gem 气垫车 题解 题目链接：P4395 [BOI2003]Gem 气垫车 题意：给出一棵树，要求你为树上的结点标上权值，权值可以是任意的正整数 唯一的限制条件是相临的两个结点不能标上相同的权值，要求一种方案，使得整棵树的总价值最小。 \(N \le 10000\) 考虑树形dp 设 \(dp[u][i]\) 表示结点 \(u\) 的权值为 \(i\) 时其所在子树的最小总权值 则有 \[ dp[u][i]=\min_{k \ne i}(dp[v][k])+i \] 那么这个权值最大有多少呢 不难发现最多为 \(\left\lceil\log n\right\rceil + 1\) 那么就很简单了，时间复杂度 \(O(n\log n)\) 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f #define N (int)(2e4+15) struct Edge { int u,v...

洛谷P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并 题解 题目链接：P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并 题意：村落里的一共有 \(n\) 座房屋，并形成一个树状结构。然后救济粮分 \(m\) 次发放，每次选择两个房屋 \((x,y)\)，然后对于 \(x\) 到 \(y\) 的路径上(含 \(x\) 和 \(y\))每座房子里发放一袋 \(z\) 类型的救济粮。 然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮 显然这是板子题 我们利用树上差分的思想，自底向上统计答案 同时一路合并每个节点的线段树，即可 本文主要讲一讲为什么数组要开 1e5*70 左右 首先 \(z \le 10^5\) ，取最大值 \(Z=10^5\) （权值线段树嘛） 其次，动态开点线段树一次从根节点到叶子节点的修改操作 即 modify() 新建的点数为 \(O(\log Z)\) 的，在本题中 \(\log Z \approx \log_2 10^5 \approx 17\) 而观察代码可以发现，我们做树上差分的时候，一次差分会...

洛谷P5020 [NOIP2018 提高组] 货币系统 题解 题目链接：P5020 [NOIP2018 提高组] 货币系统 题意：在网友的国度中共有 \(n\) 种不同面额的货币，第 \(i\) 种货币的面额为 \(a[i]\)，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 \(n\) 、面额数组为 \(a[1..n]\) 的货币系统记作 \((n,a)\) 。 在一个完善的货币系统中，每一个非负整数的金额 \(x\) 都应该可以被表示出，即对每一个非负整数 \(x\) ，都存在 \(n\) 个非负整数 \(t[i]\) 满足 \(a[i] \times t[i]\) 的和为 \(x\) 。然而， 在网友的国度中，货币系统可能是不完善的，即可能存在金额 \(x\) 不能被该货币系统表示出。例如在货币系统 \(n=3 ,a=[2,5,9]\) 中，金额 \(1,3\) 就无法被表示出来。 两个货币系统 \((n,a)\) 和 \((m,b)\) 是等价的，当且仅当对于任意非负整数 \(x\) ，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。 现在网友...