Auguryの妙妙题分享Part 1

· · 个人记录

Auguryの妙妙题分享Part 1

配套题单，但是要先加一下这个团队

Porcelain

题意

有 n 个柜子，第 i 个柜子中有 k_i 个物品。每个物品都有一个价值，按顺序给出。

对于每个柜子，每次只能从两端取出物品。

现在要取出总共 m 个物品，问最大价值。

### 思路 #### 先考虑下只有 $1$ 个柜子的情况？ 显然，这是一个简单的区间 $\text{dp}$。用`dp[i][j]`表示取出了 $1\sim i$ 和 $j\sim k$ 的物品的最大价值即可。 #### 然后考虑有两个柜子？ 对于每个柜子做一遍区间 $\text{dp}$。 然后捏？ 如果我们确定了每个柜子选择的物品数量，那么在这个柜子中我可以贪心地选择最大的价值。 我们可以求出对于一个柜子 $i$，选了 $j$ 个物品的价值最大是多少。 然后枚举第一个柜子中选了几个物品，即可得到答案。 #### $n$ 个柜子？ 我们发现，问题出在我们不知道对于每个柜子分配多少数量。 然后想到，在树形背包中，我们不知道对于每棵子树要分配多少容量。 然后假装每个柜子都是一棵子树，然后跑树形 $\text{dp}$ 即可。 ### 复杂度 #### 在区间 $\text{dp}$ 中 对于每个柜子，都是 $k_i^2$ 的。 总体复杂度 $\Theta(\sum k_i^2)$。 算出来就是 $100^2\times 100=10^6$。 #### 在树形 $\text{dp}$ 中 对于每个柜子，需要枚举分配多少、总容量多少。这两层循环是 $m\times k_i$ 的。 所以，总复杂度为 $\Theta(nm\sum k_i)$。 算出来就是 $100\times10^4\times(100\times100)=10^8$，刚刚好。 ## [P5058 [ZJOI2004]嗅探器](https://www.luogu.com.cn/problem/P5058) ### 题意 给定一张无向图，问有哪些点是从 $1$ 走到 $n$ 必须经过的。 输出编号最小的那个点。 $n\le 2\times 10^5,m\le 5\times 10^5$。 ### 思路 转化一下题意。 问删掉哪些点会使得 $1$ 和 $n$ 不联通。 显然，如果一个点不是割点，那么删掉他不一定会影响连通性。 那么割点一定会影响 $1$ 和 $n$ 的连通性吗？ ![](https://cdn.luogu.com.cn/upload/image_hosting/pasab9gj.png) 显然，在这里并不会。 问题是：什么样的割点会影响 $1$ 到 $n$ 的连通性？ 当然是从 $1$ 走到 $n$ 必须经过的（废话 换句话说，一定在 $1$ 到 $n$ 的最短路上。 于是我们从 $1$ 到 $n$ 跑一遍 $\text{bfs}$，记录最短路上有哪些点即可。 然后答案就是在最短路上而且是割点的点。 复杂度 $\Theta(n+m)$。 ## [Music Festival](https://www.luogu.com.cn/problem/CF1801C) 算了直接看[这篇题解](https://www.luogu.com.cn/blog/401461/ti-xie-cf1801c-music-festival)罢，都是我写的。 还是搬过来了 ### 题意 - 你有 $n$ 个专辑，第 $i$ 个专辑中有 $k_i$ 首歌。 - 每首歌有一个权值 $a_{i,j}$。 - 当一首歌的权值大于所有在他之前播放的歌的权值时，你会获得 $1$ 好感度。 - 每个专辑都要连续地播放，就是说不能放到一半停下，也不能从中间开始放。 - 现在让你求出这些专辑的播放顺序，使得到的好感度最高，问最高的好感度是多少。 ### 思路 容易发现，在每个专辑内，如果一首歌的权值**小于等于**他前面权值最大的歌，那么这首歌就不会对答案产生任何贡献，因为他永远不可能比它前面的歌权值更高。 因此，我们可以直接删掉这些歌。 显然的，一首歌要对答案产生贡献，那么他一定要大前面播放的歌的权值。 所以，我们定义 $dp_i$ 表示前面播放的歌的权值全部小于等于 $i$ 时能获得的最大好感度。 然后，考虑转移。 举个例子，一个专辑 $[1,4,6]$。 - 如果从 $1$ 开始播放，那么我们一定能对答案造成 $3$ 的贡献。 - 如果从 $4$ 开始播放，那么我们一定能对答案造成 $2$ 的贡献。 - 如果从 $6$ 开始播放，那么我们一定能对答案造成 $1$ 的贡献。 - 总结规律，就是对答案造成后面（包括这首）歌的数量的贡献。 说成状态转移的话，就是： - `dp[6]=max(dp[6],dp[1-1]+3)` - `dp[6]=max(dp[6],dp[4-1]+2)` - `dp[6]=max(dp[6],dp[6-1]+1)` 这里的减一是为了保证不会算重，也符合了状态定义。 总结规律，就是对于每个专辑，在他的歌的权值最大的位置的 $dp$ 值能由这首专辑的歌曲的权值的位置转移过来。 现在，有了转移，就差怎么快速的转移了。 如果我们对于每个 $i$ 都枚举一遍所有的专辑，那么复杂度可以达到惊人的 $\Theta(\max a\times \sum k_i)$，显然是超时的。 容易发现，对于每个专辑，我都只会在权值最大值的位置转移。 所以，我们开一个 $\text{vector}$，表示一个位置有哪些专辑可以转移。 这样，时间复杂度就被优化到了 $\Theta(\max a+\sum k_i)$，十分优秀。 ### 细节 多组数据，清空可能会超时。要考虑使用快速的清空方式。 ## [Social Network](https://www.luogu.com.cn/problem/CF1609D) ### 题意 ~~不要在乎翻译，翻译是错的~~ 有 $n$ 个点，初始没有任何边。 你要进行 $d$ 次操作，每次操作会： - 任选一对 $a,b$，连接 $a$ 和 $b$ 。 - 要求在进行这次操作后，$x$ 和 $y$ 必须在同一个联通块内。 问每次操作后，最大的联通块最大可能的大小。 当然，你可以认为，在每次操作后，你可以在满足所有限制条件的情况下，随意修改已经连接的边。 $n\le 10^3,d<n$。 ### 思路 #### 为什么会有“最大可能大小”之类的，不是只会有一种可能大小吗？ 当 $x$ 和 $y$ 已经一定在同一个联通快内时，加的这条边就可以放在别的地方。因此有了“最大可能大小”。 现在，我们已经知道了有多于的边，问题就是这些多于的边的贡献。 设多于的边的数量为 $k$ 。 显然，如果我们把这些边用于连接已经在同一联通快内的点，就不会有任何贡献。 #### 先解决一个简单的，当 $k=1$ 时 显然此时我们可以连接两个最大的联通快，显然此时对答案的贡献最大。 #### 当 $k=2$ 时 显然此时选择连接前三大的是最优的。 所以我们得到了一个惊人的结论 - 连接前 $k+1$ 大的块是最优的。 - 答案即为前 $k+1$ 大的联通快大小的和。