Explo

依次考虑是否取 \(n\) 个物品,初始有权值 \(p=w\),以及常数 \(k,c\)

物品分为两类,对于第 \(i\) 个物品:

若为第一类,则选择第 \(i\) 个物品会得到 \(a_i\times p\) 的贡献,并会使得 \(p \leftarrow p\times (1-k\%)\) .

若为第二类,则选择第 \(i\) 个物品会失去 \(a_i\times p\) 的贡献,并会使得 \(p\leftarrow p\times (1+c\%)\).

求最终最大贡献。\(1\le n\le 10^5,0\le k,c,w,a_i\le 100\)

一致认为这道是全场最佳。很有启发性。

第一想法是设 \(dp_{i,j,k}\) 表示对于前 \(i\) 个物品,当前 \(p\) 正向变化了 \(j\) 次,反向变化了 \(k\) 次时的最大贡献,但是复杂度显然不对。

那怎么办,有点棘手,场上直接先跳过想后面题了。但仔细分析发现,只有前 \(i-1\) 个物品的选取情况才会影响第 \(i\) 个物品的贡献,这也是我们 dp 状态不好设置的原因——影响是复杂的而非单一的,我们还需要考虑 \(p\) 的取值。

但我们可以思考一下 \(p\) 在这个问题里面的本质作用是什么——是给后面物品的贡献加了个权。加了个权?也就是如果我们拿到了后面子问题的最优贡献,就可以直接加权计算当前贡献,并且加了个权之后还是最优的啦?

那就倒序做呗!设 \(dp_i\) 表示对于后 \(i\) 个物品这个子问题,最大贡献是多少,则有转移方程:

\[dp_{i}=\max(dp_{i+1},dp_{i+1}\times(1-k\%)+a_i\times w)(ty_i=1)\\ dp_{i}=\max(dp_{i+1},dp_{i+1}\times(1+c\%)+a_i\times w)(ty_i=2) \]

最终答案为 \(dp_1\),时间复杂度 \(O(n)\)

很有启发性,值得仔细品味。


Seq

给定一个长度为 \(n\) 的数列,以及 \(m\) 次询问,每次询问给出三个数 \(l,r,P\),需要找到一对 \(l’,r’\),满足 \(l\le l’\le r’\le r\),使得 \((\sum_{i=l’}^{r’}a_i)\bmod P\) 最小,给出这个最小值。

\(1\le n\le 5\times 10^5,1\le m\le 10^4,1\le P\le 500,1\le a_i\le 10^9\)

轻度诈骗题。

首先将求和转为在前缀和序列上差分,即使得 \((sum_{r’}-sum_{l’-1})\bmod P\) 最小。

考虑到 \(P\) 的取值特别小,一个很好的结论是,\([l,r]\) 之间的不同的 \(sum_i\bmod P\) 的取值最多只有 \(P\) 种(废话),也就是只要 \([l,r]\) 的长度大于 \(P\),我们一定能在区间 \([l,r]\) 中找到两个模 \(P\) 意义下相同的 \(sum_i\),那么我们只要选择这两个相减即可使得答案为 \(0\)

于是\(r-l+1>P\) 时,最小值一定为 \(0\)

剩下的最长询问区间长度就只剩下 \(500\) 了。暴力的做法当然是枚举两个不同的 \(sum_i\),相减取最小值,这样其实已经很优了,时间复杂度 \(O(P^2m)\)。优化当然也很好优化,枚举每一个 \(sum_i\),找它前面在 \([l-1,i-1]\) 之间的 \(sum_i\) 集合中的前驱后继取最小值即可,set 就可以维护了。

时间复杂度 \(O(Pm\log P)\)


Earth

\(n\) 个点 \(m\) 条边的无向图,选择一个整数 \(x\),使得每一条边的边权都加上 \(x\) 后,从 \(1\)\(n\) 的最短路径长度非负且最小,求这个最短路径长度。\(T\) 组数据。

\(1\le T\le 10,1\le n \le 100,m\le n\times (n-1)\).

很容易发现随着 \(x\) 的变化,最短路径长度的变化是单调的。

于是考虑二分 \(x\),在图上跑最短路,如果连通且 \(dis_n\) 为正则挪右端点,否则挪动左端点。

记得在最短路的过程中需要判断负环,出现负环一定无解。

时间复杂度 \(O(Tn^2\log |V|)\)


最后还检查出来了 T3 的数组大小错误,感觉还不错。

期望得分 \(100+100+100=300\)

原文地址:http://www.cnblogs.com/ydtz/p/16886631.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性