Spark Exam 20240715
Conclusion
SB 出题人出 DP 场，T1靠小常数通过不给提示干死选手，T2出题人认为思维难度低代码5KB，NOIP场的T3放黑题，T4又是区间DP \(\mathcal O(n^6)=117649000000\) 竟然能够通过？你代码常数真的小！
好的喷完了。这种场的后果就是，平均分 50，最高 90，最低 0
实际上如果真的好好打暴力的话能够上 100……
T1真的可惜，复杂度算错了就没打 -50pts
T4状压加区间DP能够拿 40pts
T3暴力能够拿到20pts
ideal160吧，这个还是在能力范围内的（那就榜二了
A. 魔力屏障 (magic)
Statement
有一排玻璃每个一个坚固程度 \(a_i\) ，现可以在任何位置向右边滚出一个威力为 \(x\) 的球，若球碰到玻璃 \(i\) ，且 \(a_i\le x\) ，则玻璃碎掉并 \(x\to \lfloor x/2\rfloor\) ，否则球在此处停下，若球相遇，可合成一个大球并威力相加并继续滚，求对于每个 \(i\) ，击碎玻璃 \([1,i]\) 需要的最小威力总和。
\(1\le n\le 70,1\le a_i\le 150\)
Solution
考虑并不是从左边往右边击碎就是最优，例如 \(100,1,50\) ，击碎 \(100\) 消耗的代价会在 \(1\) 那个地方浪费很多，不如先打碎 \(1\) 。
所以这个不是一个线性的过程，而是不按顺序的，又发现一个球影响的是一个区间，考虑区间 DP。注意到需要多设一个击碎区间之后剩余威力才能转移，即 \(f_{l,r,k}\) 表示击碎 \([l,r]\) 且剩余 \(k\) 的最小代价。那么考虑怎么设计转移，我们是为了这个顺序才采用区间 DP，不妨考虑将 \([l,r]\) 分成若干区间并选择一个顺序来打碎，这样我们就拥有了一个很劣的转移，考虑这样转移一次是 \(\mathcal O(n!2^n)\) 。哦真是太恐怖了。
但是这有什么关系呢？难道这样做真的是必要的吗？区间的划分不是在这个区间的子区间就考虑过了吗，为何再考虑呢？那么，我们就可以优化：
枚举分界点 \(k\) ，设 \(k\) 就是最后打碎的玻璃，那么，左边区间的最优序列和右边的最优序列拼起来就是大区间的最优打碎顺序，他们剩余的威力加起来就是大区间剩余的魔力
这样就成功优化为 \(\mathcal O(n^3V^2)\) ，其中 \(V=\sum a_i\) ，答案是不可能超过这个的（每个单独打碎）
但是考虑到，没有必要保存太多威力，威力如果不是为了被使用到靠近的玻璃，那么肯定不是最优的，因为中间会浪费威力，不如要用的时候再在靠近的位置添加。所以 \(V=\max a_i\) 是可以的。
这样其实还是不可以过。但是要注意到，这个 DP 是带 \(\frac{1}{8}\) 小常数的，这是因为：区间DP不会枚举 \([l,r],r<l\) 这样的区间，这贡献 \(\frac{1}{2}\) ；留存的威力不可能比最后一个玻璃的坚固程度的一半还小，共两次枚举，一共贡献 \(\frac{1}{4}\) 。
好吧这样还是不可以过（964,687,500），你说的对，但是《O2优化》是由 ISO C++ 委员会 自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作「OI」的幻想世界，在这里，被 CCF 选中的人将被授予「C++」，导引算法之力。你将扮演一位名为「OIer」的神秘角色，在自由的旅行中邂逅性格各异、能力独特的同伴们，和他们一起击败强题，找回失散的1=——同时，逐步发掘「NOI」的真相。
哈哈哈赛时想到了结果你告诉我小常数能过哈哈哈结果没写哈哈哈，（发癫）（旋转）（阴暗爬行）（变成猴子）（抢走游客的钱包）（上蹿下跳）（一巴掌拍扁tfqz）（吗的玩不了了）（变成大粉兔）（一拳把地球打爆）（鉴定为学竞赛学疯了）
B. 诡秘之主 (mystery)
Statement
现有若干棵二叉搜索树和一个未确定的非负整数序列 \(a_i\) ，给定一个 01 串 \(s\) ，\(s_i\) 表示 \(a_i\) 是不是 \(0\) ，回答如下询问：若分别依次插入 \([l,r]\) 的所有子区间中的数，每个区间形成的二叉搜索树最小的可能深度之和是多少。