企业官网建设流程全解析

局域网内网站建设的步骤过程,wordpress鼠标插件,杭州十大软件公司,如何制作可以下单的网站题意#xff1a;你需要维护一个双端队列。有5种操作#xff0c;共进行 \(q\) 次#xff1a; 给定 \(v,w\) #xff0c;在队首加入一个物品#xff0c;其体积为 \(v\)#xff0c;权值为 \(w\)#xff1b;给定 \(v,w\) #xff0c;在队尾加入一个物品#xff0c;其体积为…题意你需要维护一个双端队列。有5种操作共进行\(q\)次给定\(v,w\)在队首加入一个物品其体积为\(v\)权值为\(w\)给定\(v,w\)在队尾加入一个物品其体积为\(v\)权值为\(w\)删除队首的物品。删除队尾的物品。给定\(l,r\)从队列中选取若干物品在其体积之和对\(p\)\(p\)为定值取模后在\([l,r]\)中的情况下最大化物品的权值和。如果没有合法方案输出\(-1\)。\(q\leq 50000,p\leq 500,0\leq w,v10^9\)。难度省选 NOI-算法一10分对于询问直接暴力枚举每个书选还是不选按题意求解最大值即可。时间复杂度\(O(q2^q)\)算法二20分对于每个询问实际上是一个01背包问题。直接套用01背包的做法即可。注意因为有取模所以背包容量\(v\)是一个“环”如果要压掉一维需要考虑一些细节。时间复杂度\(O(q^2Mod)\)算法三5分测试点1201背包模板题。时间复杂度\(O(qMod)\)算法四15分测试点13-15特殊性质是只在一端加入和删除。本题最大的痛点之一就是如何处理01背包的撤销。那如果换种说法呢把撤销叫为“回到上个版本”是不是感觉清晰多了我们可以稍稍参考可持久化的思想将每次修改完后的dp数据都保存一份。那么IG加入就是新开了一个长为Mod的dp数组DG删除就是回到了之前的某一次修改完成后的状态这个只需要记录下每个节点的father即栈顶撤销后回到的状态编号即可。时间复杂度\(O(qMod)\)算法五100分观察测试点17、18——这部分测试点的特点在于其队列的特性——每本书加入、删除的时间点都是一段连续的区间且所有书的加入、删除时间是单调递增的。转念一想不只是这两个测试点对于所有的数据每本书的存在时间都是一段连续的区间而在做01背包时我们并不关心这本书在书架的哪个位置只关心它的\(p\)和\(v\)。对于这种每个物品的存在时间是一段连续区间的问题我们会想到线段树分治。我们把每个物品的存在时间求出在线段树上做区间修改把询问存到线段树的叶子结点最后遍历整颗线段树在每个节点上都开一个长为Mod的数组做01背包这样总的空间复杂度为\(O(qMod)\)。通过这种方式我们巧妙规避了删除的问题可以通过本题。时间复杂度\(O(qModlogq)\)算法六10分测试点1516考虑有没有在线做法。本题如需在线另一个痛点是如何处理两端的同时增删。既然合起来不好做能否干脆将双端队列分成两个栈来做呢观察测试点15,16特殊性质为\(lr\)。也就是说如果选取了左边的一些书它们的特征值和对\(Mod\)取模后为\(k_左\)那么\(k_右\)是个定值。因此只需要枚举一边的\(k\)就能得到一个确定的值单次询问的时间复杂度为\(O(Mod)\)是ok的。但这样又衍生出一个问题——如果一边被删光了又要继续删那会对另一边造成影响。但是右边又没法直接从栈底删这该怎么办可以直接把另一边匀一半吗这需要我们对整个dp数据进行重构这个操作的时间复杂度是\(O(cnt\times Mod)\)的\(cnt\)为当前书架上书的本数我们可以接受吗答案是可以的。这里需要进行一些势能分析——我们考虑一个变量\(\Delta|cnt_左-cnt_右|\)即两边书本个数差的绝对值。当增/删一本书时\(\Delta\)会变化1这样的时间复杂度是\(O(Mod)\)的而当某一边的\(cnt\)归零后我们要重构整个dp数组使得新的\(cnt_左cnt_右\)这个操作花费的时间复杂度为\(O(cnt\times Mod\Delta \times Mod)\)之后\(\Delta\)会归零。由此我们发现这个做法的时间复杂度是均摊\(O(qMod)\)的可以接受。算法七100分现在只剩最后一个问题了——对于\(k_左\)\(k_右\)可取的值是\(O(Mod)\)的如果暴力枚举那单次询问的时间复杂度将来到\(O(Mod^2)\)不能接受。手摸一下观察一下可以发现对于\(k_左\),可行的\(k_右\)是一段连续区间如果将\([0,Mod-1]\)看成一个环形区间。进一步观察发现当\(k_左\)增大时可行的\(k_右\)区间是一个固定长度的滑动窗口使用单调队列即可均摊\(O(Mod)\)地求出对于所有的\(k_左\),最大的\(k_右\)。时间复杂度\(O(qMod)\)如果使用带log的数据结构维护区间max的话就是\(O(qModlogMod)\)。