以下内容仅针对南外本校同学： 请科技节期间，在周二（11月24日）晚参加NFLSPC的同学于12月23日前，到综合楼613（苹果开发实验室）领取奖品（每个人都有奖品，根据排名有分类）进613后按照白板上的指示自取奖品。 排名详见：https://acm.nflsoj.com/contest/67/standings#standings

关于

此题与真实历史无关。

题解

我们不妨把整栋大楼以第$k$层为分界一分为二，分别处理。这里就只讨论第$k$层在所有电梯下方的情况。

假如保证电梯都在激活的按钮上方，那么电梯碰上按钮停下$1s$等价于电梯初始楼层$+1$，可以每次把楼层最低且编号最小的电梯的楼层$+1$，做激活按钮次。最后得到等价的没有激活按钮的电梯情况。至于更一般的情况，我们可以使用扫描线从高到低扫描并维护一个数据结构，每次碰到电梯就加入数据结构；每次碰到激活的按钮就把数据结构中楼层最低且编号最小的电梯的楼层$+1$。

这里只是一家之言，片面之词，博主才疏学浅，并且不会用格式，若有错误与不足还请多多包涵！

nflsoj372

考虑限制，一些是>=一些是<=

如果都是<=非常好做，以至于因为每个限制连续可以O1出解

类似cts2019氪金手游

考虑至少违反几个>=，其他>=当作没有限制

先把所有>=、<=按照大小顺序排序

维护 dp x y表示前x个几个y没违反

之后是显然的了

nflsoj373

针对$n,m<=1e5$个人的做法：

暴力追踪光线，每次如果打到边而不是方格利用带权并查集缩起来，这样总反弹次数可以稳定在$O(n)$左右

针对$n,m<=1e9$听到的做法：（没有实现过，极其可能出错哦，还望大佬补充

把图放大两倍

考虑没有方块是一个环

dxdy表示方向向量，sxsy表示起点，goalxgoaly表示一个碰撞点

$dx*k+sx=goalx modn$

$dy*k+sy=goaly modm$

对于每个点都可以计算理论步数

每次撞击之后会发生 跳环 和 可能转换方向 两种变化

记录箱子理论步数lowerbound即可

nflsoj374

（请搜索 uoj455雪灾与外卖

（既然网上已经有现成的写的还比我好的为什么不用呢

当然如果你想看博主粗略的想法的话：（请对应uoj题目

考虑老鼠和洞

记录二元组（x，y）表示选择值、个数

老鼠可选堆找=A,洞=B

从小到大加入

考虑老鼠：

A中找最小的一个O，$ans+=x+Ox$，$Oy-1$

并往B压入$（-x-x+Ox，1）$，就是不连这个洞了

考虑洞：

先在B里把所有$x+w+Ox< 0 $的那么capacity个搞出来

每次搞一个$ans+x+w+Ox$，A压入$（-x-x-Ox，Oy）$表示老鼠用这个洞，之前的匹配老鼠得回去找老相好

并B压入$（-x-w，Oy）$表示这个洞匹配的老鼠又有更好的选择

（为保证复杂度最后那个东西一起压入

剩下的压入$（-x+w，……）$供简单匹配即可

这里只是一家之言，片面之词，博主才疏学浅，并且不会用格式，若有错误与不足还请多多包涵！

nflsoj410

注意到如果记录了一个区间最后一个打败的，问题会转化成不相关的子问题

fij01表示区间i~j活下来是ij

考虑gij表示中间人都死光的概率

$gij = Σfik0 fkj1$

$fij0=Σwin(i,k) *gik*fkj0$

fij1类似

最后考虑边其实是存在选择顺序的，这样fij01由于固定了一条边最后选，$*inv（j-i）$

nflsoj411

注意两个串相似，当且仅当$lcs+lcp>=m-1$

正着反着建立后缀树

之后问题转化为lca之和

那么枚举一棵树的点，启发式合并时小的找到可能的第二颗树最浅lca，大的维护动态开点线段树第二颗树dfs序查询就好了

（还有一种解法也欢迎 大佬补充

nflsoj412

结论：答案=所有奇数位置的max（后缀min，val now）之和+整体min

关于这个结论，其他巧妙证明欢迎 大佬补充

$f(x,01)表示决策做到第x位，现在当前x状态$

$f(x,0) = max( val(x)+ f(x+2,0) , min( f(x+2,1), f(x+2,0) +val(x+1))$

通过归纳法，$f(x,1)=我说的那个结论$，$f(x,0)=f(x,1)-min of suffixval$

具体证明可以简单分类讨论啦

维护单调栈位置，可以用set，具体实现是trival的，暴力模拟即可（懒