游记和题解分开了 >_<
T1
出题人出题前就没想过自己马的安全么?
考虑二分年份,然后暴力确定几月几日。二分年份的话按照 mid≤1582 和 mid>1582 两种情况讨论一下就好了。
mid≤1582 的,因为公元前 4713 年是闰年,所以直接看看有多少年即可。对于 mid>1582 的,先将 1582 年以前的贡献加上,剩下的瞎搞搞就好了。
然后就没了。
T2
看看最后有多少个可用的二进制位即可。
注意一下 n=0,k=64 的数据就好了。
T3
一个加法操作的贡献取决于其后面有多少个乘法。
所以倒着做。假设现在要处理第 i 个操作。显然第 i 个操作中的所有加法操作都可以吃到 i 后面的所有操作中的乘法操作的贡献。因此只需要考虑第 i 个操作中,后面的乘法对前面的加法的贡献。
那么直接打个标记在 i 这个点上,然后按照儿子的执行顺序下传即可。
T4
Waring :: 这个做法假了
改题的时候与其他人的做法不同。如果这个做法是对的的话,那么真的是十分简洁了。
首先考虑暴力做法。当前剩下了一些蛇,然后找出最大的 x 和最小的 y,假定 x 吃了 y ,然后递归下去,看看返回来的答案里面是否包含 x(即 x 是否存活),存活的话就可以吃,否则一定不吃。
容易发现这个状态只有 n 种。直接 O(n2) 可以拿到 55 分。
考虑 70 分做法,用 set 模拟一遍整个过程,并记录 diei 表示 i 在第几轮被吃,topi 表示第 i 轮的最大蛇的编号。接着依旧使用上述递归方法。对于第 i 轮来说,递归下去,如果第 i+1 轮的答案为第 k 轮,那么只需要检查第 i 轮到第 k 轮中,topi 是否被吃即可。
接着考虑满分做法。
容易发现复杂度瓶颈在于求 top 和 die 。有没有办法优化呢?
考虑当前局面 a1≤a2≤a3≤⋯≤an ,这个时候 an 吃掉 a1 ,分两种情况:
- an 吃掉 a1 后不是最小蛇。
那么接下来的一轮,最大值一定不比原来大,最小值一定不比原来小,因此接下来的” 最大蛇吃掉最小蛇后剩下的长度”,一定不比 an−a1 大。
考虑用两个双端队列维护,q1 维护没进行操作的蛇,q2 维护进行了操作的蛇。此处规定两个双端队列中蛇的大小都是自队尾至队头单调递增的。
每一轮的最大值取出 q1,q2 的队头最大值,最小值同理。这个时候容易发现将 an−a1 直接丢到 q2 的队尾一定是没问题的,因为编号为 n ,长度为 an−a1 的这条蛇,一定比上一个 q2 的队尾要小。
但是还有一种情况。
- an 吃掉 a1 后成为最小蛇。
容易发现,接下来的” 最大蛇吃掉最小蛇后剩下的长度” 有可能比 an−a1 要大,如果依旧强行插入至 q2 队尾的话,不会破坏单调性么?
显然不会,因为上一个插入的 an−a1 已经被取出来了。可能这下连续的几次都满足” 最大蛇吃掉最小蛇后,成为了最小蛇”,但每一次都是将上一次放到 q2 队尾中的元素取出来了。所以不会破坏单调性。
因此,每一次直接将 剩下的长度 插入至 q2 ,是不会破坏单调性的。
按照这样直接维护,单次时间复杂度是 O(n) 的。
上面这个做法其实是有问题的。我们不能保证 q2 里面蛇的编号也是正确的。
考虑另一种做法,依然将第 i 次的” 大蛇吃小蛇” 分成下列两种情况:
- 吃了之后,大蛇变成最小的蛇。
- 吃了之后,大蛇不变成最小的蛇。
对于第二种情况显然大蛇一定会选择吃,因为第 i+1 次的大蛇吃掉小蛇后一定比这只蛇要小。
第一种情况的话,只需要考虑奇偶性即可。
容易发现,只要出现了第一种情况,那么结束的局面一定在这一段第一种情况之中了。所以尽管之前的队列做法有问题,在这里也绝对不会出问题了。
总结:
这一次 T4 只拿到了 40 分是十分的遗憾,考试的时候应当一直都要专心,时间是十分宝贵的。按照常理来说,剩下一个半小时只打了一个爆搜是十分不应该的。找我看来正常发挥的话其实是可以拿到 70 的。就可以避免被一些人踩了。
不过好的是,前三题思路都较为清晰,代码也十分整洁,因此暂时没有 fst 。愿以后都可以做到这一点,减少 fst 的次数嗷 >_< 。
0 条评论