首页 > 其他分享 >闲话 24.9.11

闲话 24.9.11

时间:2024-09-11 20:35:44浏览次数:8  
标签:11 le 24.9 传送带 leftarrow 行李 闲话 cdot dp

闲话

哈哈,没有选题了。
没有选题就不写了(

最近摆的很舒服啊。
等卖了题再拿题解充当闲话吧。

碰壁:处理▂▕▄▄制▒▟▀问题不可以▙依赖[错误: 所引对象未导引至对象实例 ; 标准处理方法_004.rtf 不存在]。不确定[已编辑]难的。

推歌:樱桃簪子 by 天使盐 feat. 诗岸

轻舟慢慢 多少涟漪 全部入梦里
过往云烟 我怎敢去回忆 怎敢回忆

导数题

前两天是 2024 CCPC 网络赛。看到了这个题和大家的做法,感觉很好玩,就总结一下。

做法来自 Houraisan_Kaguya,_rqy et al.,本文只作转述。

gym105336I

有一个长条形状的传送带,其上有 \(n\) 个行李。建立坐标轴,第 \(i\) 个行李在传送带上的位置为 \(a_i\)。有 \(m\) 个人站在传送带前,第 \(i\) 个人的位置为 \(b_i\)。传送带向坐标轴正方向每秒移动一个单位,即每秒会对每个 \(i\) 执行 \(a_i \leftarrow a_i + 1\)。

显然对于一个人来说,右边的行李都是看过了的,没有自己的行李,自己的行李只可能在其左边,也可能没有。(如果坐标 \(i < j\),认为 \(i\) 在 \(j\) 左边)并且不会有一个行李同时属于两个人,但可能不属于这 \(m\) 个人中的任何人。一个人至多只有一个行李。

请对所有本质不同的情况,求得最早有人拿到自己行李的时间之和。当然,每个人的左边都没有自己的行李的情况不需要考虑。两种情况不同当且仅当:在一种情况下某个人有行李而在另一种情况中没有,或存在某个人在两种情况中的行李编号不同。

\(n,m,V\le 500\)。

令 \(m, V\) 都与 \(n\) 同阶。

首先由于 \(t\le V\),我们可以枚举这个最早的时间 \(t\),计算最早有人拿到自己行李的时间恰为 \(t\) 的方案数,乘一下就是 \(t\) 的贡献。恰为 \(t\) 不好算,改为至少为 \(t\)。这个限制的更改放在某个位于 \(x\) 的人身上,就变成只能选择坐标 \(\le x - t\) 的行李。H_kaguya 声称,这就好算了。

令 \(f(i, j)\) 为已经给 \(x \le i\) 的所有人分配完行李,剩余 \(j\) 个坐标 \(\le i - t\) 的行李未被分配的方案数。那么从前往后扫,\(f(i - 1, \cdot)\to f(i, \cdot)\) 的转移也就容易写出了。

  1. 若 \(i - t\) 处有行李,则整体向高位平移 \(1\),即 \(f(i, j) \leftarrow f(i - 1, j - 1)\);
  2. 若 \(i\) 处有人,他可以不取行李,也可以从当前行李中选择一个,即 \(f(i, j) \leftarrow f(i - 1, j) + (j + 1) \times f(i - 1, j + 1)\)。

直接做这个 dp,我们就能在 \(O(n^2)\) 的复杂度内计算出每个 \(f(n, \cdot)\),从而计算出最早有人拿到自己行李的时间至少为 \(t\) 的方案数,和至少为 \(t + 1\) 的方案数做差即可得到恰好为 \(t\) 的方案数。由于对每个 \(t\) 都需要计算,总复杂度 \(O(n^3)\),可以通过。

能不能再给力一点啊?

考察确定 \(t\) 后的子问题。一眼看过去,最可做的就是优化 dp。那就优化它吧。大家都喜欢 dp 转 gf,那就转一下吧。

令 \(F_i(x) = \sum_{j} f(i, j)x^j\),那么知道

  1. 若 \(i - t\) 处有行李,则整体向高位平移 \(1\),即 \(F_i(x) \leftarrow x F_{i - 1}(x)\);
  2. 若 \(i\) 处有人,他可以不取行李,也可以从当前行李中选择一个,即 \(F_i(x) \leftarrow F_{i - 1}(x) + F_{i - 1}'(x)\)。

因此,问题可以被转化成如下的形式;

你需要维护一个初值为 \(1\) 的多项式 \(f\),支持进行下面两种操作共 \(n\) 次:

  1. \(f\leftarrow xf\)
  2. \(f\leftarrow f + f'\)

输出所有操作执行后的 \(f \bmod x^{n + 1}\)。

注意到 \(f + f' = \dfrac{(e^x f)'}{e^x}\),而把所有操作对 \(f\) 的影响合并后会发现,只有第一次乘和最后一次除的 \(e^x\) 会对答案产生贡献,其余的 \(e^x\) 都两两消掉了。

因此我们只需要令 \(f\) 初值为 \(e^x\),维护两个操作:乘 \(x\)、求导,最终取前 \(n\) 项系数乘以 \(e^{-x}\) 即可。

_rqy 声称,这个就可以 \(\widetilde O(n)\) 求了。这是因为,初始的 \(x^k\) 项系数会在第 \(t\) 次求导后乘入 \(k + a_t\),而这列 \(a\) 对每项都相同。因此这本质上就是对某个 \(g(x) = \prod_{t} (x + a_t)\) 做多点求值(\(x = 0, \dots, n\))。容易做到 \(O(n\log^2 n)\)。

总时间复杂度 \(O(n^2 \log^2 n)\)。你就说是不是 \(\widetilde O(n^2)\) 吧。

标签:11,le,24.9,传送带,leftarrow,行李,闲话,cdot,dp
From: https://www.cnblogs.com/joke3579/p/-/chitchat240911

相关文章

  • 洛谷 P11021 [LAOI-6] 区间测速 题解
    题目传送门使用multisetmultiset可以看成一个序列,支持插入一个数或删除一个数,时间复杂度均为\(O(\logn)\),且能始终保证序列中的数是有序的,而且序列中可以存在重复的数(而set容器要求两两不同,且不保证有序)。一个基本事实:速度最大的时刻必然出现在两个相邻点之间。例如从......
  • 20240911 模拟赛总结
    期望得分:100+0+30=130实际得分:100+20+30=150T1感觉没有大样例也还是可以猜到那么一点的结论。k=0无解。当k≠0时,考虑交换不含1的两项,一定能使这两个位置都符合gcd(i,ai)=1,如果最后长度为奇数剩一个位置出来怎么办?那就O(n)枚举一遍找到可行的位置和它换一下即可,易......
  • 2024/09/11有感
    找了个把月工作吧,反正看过来还是重庆成都拿的offer比较多,江浙沪好不容易面试两个,面完都说项目没了,一个是合肥的做二手车的,还蛮大的,跟瓜子二手车一样,HR说技术面通过了,但是项目还没启动,让我等一个月,那拜拜了好吧;还有一个是常州的,本来我是投的上海的,后来说可以在常州办公,那挺好的,心里......
  • 2024.09.11 1856版
    起于《海奥华预言》的思考◆地球管理结构和参考持续更新中...... 英文地址:https://github.com/zhuyongzhe/Earth/tags中文地址:https://www.cnblogs.com/zhuyongzhe85作者:朱永哲 ---------------------------------------------------------------------------------......
  • 【秋招笔试】9.11得物秋招(已改编)-太难了!!!
    ......
  • 代码随想录训练营day44|1143.最长公共子序列,1035.不相交的线, 53. 最大子序和,392.判
    1143.最长公共子序列这题并不要求连续子序列的要求是可以删除某些元素,但不能改变顺序。顺着上题的思路,这题也应该设立一个二维数组vector<vector<int>>dp(text1.size(),vector<int>(text2.size(),0));dp[i][j]表示的是以text1[i]为结尾的字符串和以text2[j]为结尾的......
  • 2024/9/11日 日志
    今天学习了离散数学集合的部分内容,并初步认识了数据结构中影响程序的时空,即时间复杂度和空间复杂度。对时间复杂度的计算有了掌握和了解。即1.用常数1取代运行时间中的所有加法常数。2.在修改后的运行次数函数中,只保留最高阶次。3.如果最高阶项存在且不是1,则取出与这个项......
  • SolidJS-每日小知识(9/11)
    知识介绍对指定SVG元素实现滚轮zoom代码分析1.对指定SVG元素实现滚轮zoom设置viewBox属性{x,y,w,h}以及缩放系数scale为信号量const[scale,setScale]=createSignal(1);//初始缩放比例const[boxLocation,setboxLocation]=createSignal({x:0,y:0});......
  • P3911 最小公倍数之和
    原题链接《一道思维题(小trick)》\[ans=\sum_{i=1}^{n}\sum_{j=1}^{n}lcm(a_i,a_j)\]当然正常莫反不能是这种形式的,可以观察到\(a_i\)的值域很小,只有\(5\times10^4\),所以我们去考虑直接枚举。$\quad$记\(c_{a_i}\)为\(a_i\)在序列中出现的个数,\(N\)为\(a_i\)......
  • 2024.9.10人工智能学记
    今天课上学了很多实用知识。搜索引擎有两类,一种是全文搜索,一种是目录搜索。下面是一些搜索网站的技巧:①如果不想看到某些内容就可以在搜索关键词的前面使用(空格)减号,这样在查询结果中就不会出现这个关键词,搜索格式为“关键词A+空格+减号+关键词”②想要文件格式特定就使用FILET......