网站建设 硬件,域名拍卖,申请做网站,2023年8月新闻热点事件时间安排
7:30–7:50 读题#xff0c;T1貌似是个 dp #xff0c;T2 数据结构#xff0c;T3 可能是数据结构。 7:50–9:45 T1#xff0c;点规模非常大#xff0c;可以达到 1e18 级别#xff0c;感觉应该没法直接做#xff0c;考虑每条新增的边的贡献#xff0c;想到用 …时间安排
7:30–7:50 读题T1貌似是个 dp T2 数据结构T3 可能是数据结构。 7:50–9:45 T1点规模非常大可以达到 1e18 级别感觉应该没法直接做考虑每条新增的边的贡献想到用 vector 暴力维护一条边两边的集合大小。写完发现是个假的。仔细想了一下发现直接做就是对的有用点比较少可以直接用 map 暴力存然后暴力做。 9:45–10:51 T2,对于 n 比较小的时候可以单调栈暴力做容易发现每一个新增的 r 的贡献只和单调栈中的一段有关且每一段对应一个函数关系可以用李超树无脑维护拿到 50 分。思考正解能否扫描线做发现并不好维护。 10:50–12:00 T3,考虑写暴力然后发现数据范围卡的太死了不精细的暴力压根跑不动于是一直在卡常。
回顾反思
T1: 一开始写的假做法耽误了一点时间。 对于这种规模极大的题要么是有某种神仙性质使得可以直接计算或者极大的缩小规模要么就是只用考虑有用的点而这些点非常少。 T2: 比赛的时候更多的时间是在写部分分部分分可以类似扫描线做于是就去往扫描线直接处理区间答案想了而正解则是考虑每个单独元素对区间的贡献。 不管是扫描线还是什么直接维护每个询问对应区间的答案不好做。发现题目的取 max 有可加性于是可以考虑原序列每个元素对询问的贡献。可以单调栈处理出一个值为最值的区间 a,b 那么最值就成了常量可以讨论 [a,b] 与询问区间 [l,r] 的包含相交关系分四类讨论可以使用二维数点、李超树等简单数据结构分四种做法计算。 T3: 比赛的时候几乎没给这道题时间更多的时间是在卡暴力的常数。有类似的 dfs 的想法但是觉得复杂度不可能对就没再想了。对于 dfs 的实现上我的大致想法是比较暴力的直接考虑枚举每一位而正解则观察到 dfs 的过程是个 dag 每次同时处理一层出边上的点起到一个剪枝的效果。 正解实际上是个爆搜。考虑拓展时形成了一个dag结构于是用vector存储当前的一些出边 dfs 跑 dag 。通过剪枝和主席树对于信息获取加速复杂度就对了。
T1是送分题T2也是没有任何代码难度的经典题T3是 dfs可能实现和剪枝上有一些细节和技巧但是写了dfs 起码也是能够拿到 50 左右的。前两题都是应该 AC 的。尤其是这种 T1 应该尽可能减少花在上面的时间。
