讲题人讲义(D,F,G)

D 又是一年毕业季

F 自爆机器人

结论:一段长度为n的区间,它的子区间长度设子区间长度为len_i

那么不同len_i的数量不会超过\sqrt n

\sum_i len_i = n,不同的len_i 都取尽可能小,设为len_i = i,有$1 +2 + \dots + m = n\$

可得\frac {m * (m + 1)} {2} = nm \le \sqrt n

思路:

将路径拆解成两部分——从0n的必要路线,在任意两个墙壁来回走的路线

如果t < n的话显然不可能炸到怪物

除去0n的必要路线需要花费n的时间外,还剩t-n的时间可以在两个墙壁来回走

将两个墙壁来回走的路线拆解成只在相邻墙壁来回走的路线x_1 \iff x_3可以变成x_1\iff x_2 + x_2 \iff x_3

对于设d_i = x_i - x_{i - 1},设每两个墙壁间走k_i

可得\sum d_i * k_i \le t - n

使用完全背包求解,d_i的种类不会超过\sqrt n,时间复杂度可通过结论证明为O((t - n)\sqrt n)

G 大鱼吃小鱼

发现题目给的时间段是左闭右开联想到差分操作

对时间段离散化,用差分表示在l_i时刻加入第i条鱼,第r_i时刻消失第i条鱼,用前缀和维护第i时刻有哪些鱼

枚举时刻i,求第i时刻开吃的话最大能到多大的体重。对体重离散化,然后用树状数组维护离散化后体重为w的鱼的实际总重量

维护操作:

  • 第条鱼加入时有(是离散化后体重为的鱼原本的体重)
  • 第条鱼消失时有

设当前体重为weight(同样被离散化),查询在i时刻第一条体重大于weight的鱼的离散化体重w,然后吃掉在这之间的所有鱼weight += query(weight, w - 1)。如不存在体重大于weight的鱼,那么可以把这一时刻所有的鱼都吃掉

如果吃完后体重\ge w的话,那么继续迭代操作

如果吃完后体重<w,已经不可能吃掉这条鱼了,退出迭代,此时是i时刻能到达的最大体重

因为每次可以吃掉体重自身的鱼后,都相当于至少对之前的体重*2,所以体重增长速度是指数级别的,最多只会遇到\log (\max a_i)次比自身体重大的鱼

查询第i时刻第一条体重大于weight操作——用multiset维护当前有哪些体重的鱼(体重为实际体重),用内置upperbound函数\log n求出体重大于mp_{weight}的鱼

时间复杂度O(n\log n \log(\max a_i))

全部评论

相关推荐

今天提了离职,领导说让我离职前请几位正式工吃饭……我本来是有请客的打算的,因为感觉这几个同事人还挺好,想以后维持一下关系。但我第一次听领导主动说让实习生请客的……(只因为一个请客,倒不至于发个帖子。主要是这个公司的离谱事情太多了,跟之前的实习感受完全不同)之前几段实习,在实习结束前,mentor或领导会请客欢送,无论是私下吃个便饭也好,还是全部门的奶茶也好。这几位正式工既不是我的mentor,也不是我的领导。而且我异地实习生活很拮据,这家公司给得很少。当然了,这也算意料之外,情理之中。这家公司一直对实习生很不友好。经常让实习生加班,总是跟实习生说“辛苦一下”。你也没给我那个辛苦钱啊!晚上干到12点,周末加班干,要么是领导要看,要么是客户着急。之前的公司,我主动加班,mentor都会跟我说,实习生不用加班,到点下班就行。加班就算了,我安慰自己就当学东西了,锻炼抗压能力。但辛苦完了,节日的福利,竟然只有正式员工才有?!我之前实习,实习生的节日福利一点也不比正式工少啊……有的正式工还会把福利分给实习生一部分。挺心寒的……而且,我觉得这家公司对实习生很不负责,纯拿你当廉价劳动力。可以让刚毕业才工作三个月的人带实习生,实习生不会的,正式员工也不会,俩人就一起探索。还真就那个“和公司共同成长”😅避雷某GJ级专精特新小巨人企业,六百多人,整体氛围挺离谱的,跟我去过的其他公司完全不一样。领导都是些老东西,喜欢PUA,爹味十足。流程混乱、管理混乱、代码混乱、职责混乱,技术领导不懂技术,总说出一些可笑的畅想。虽然技术不咋地,但是把产品技术路线吹上天的本事倒是有,而且很大!什么xx系统、xx模型、xx工具,名字一个比一个高大上,其实可能就是调用Qwen、DeepSeek、Doubao……还声称这两年要上市,我祝你们成功吧😄
不知道怎么取名字_:实习的能有多少钱,为啥要请客
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务