比赛链接: https://acm.ayit.edu.cn/contest/6
后四题没有一个被AC的还是有点意外的...
感觉大家都在忙着收部分分2333
嗯，不扯了，我们进入正题:
A: TAT
简单的签到题, 直接判断即可
标算代码: https://acm.ayit.edu.cn/submission/1000
B: 计算表达式
由于数字和运算符之间有空格, 所以直接读取后进行相应计算即可
其实是出题人自己懒了
PS: 出这题的时候愚蠢的zdw把幂运算设的太小了结果不用快速幂也能过
标算代码: https://acm.ayit.edu.cn/submission/1003
C: 飞行棋
子任务1: 随便写, 最暴力的搜索应该也能过吧
子任务2: 坐标的总数被限制在500000内了, 直接bfs就好了
子任务3: 思考一下不难发现实际有用的点只有起点, 终点, 以及每个跳跃涉及的点
所以我们离散化一下坐标然后直接跑dijkstra求最短路就好了
zdw太懒了所以直接在map上维护的...跑的奇慢无比...(史上最丢人标算)
标算代码: https://acm.ayit.edu.cn/submission/1004
D: 打苍蝇
这题是一道丧心病狂的分类讨论题(反正比赛时间4h来着)
不要着急, 我们慢慢分析~
子任务1: 如果只能打一次那显然选最多的那个点就对了
子任务2: 暴力大法好, 我全都枚举一遍就是了
子任务3: 如果只打两次呢?
我们不妨先假设两次打击之间有没有关联:
如果有: 那么实质就是我们可以选择打死一条直线上连续的3个点上的所有苍蝇
如果没有: 那显然就是选最大和次大的点了, 这个可以用multiset之类的东西维护
子任务4: 参考上一步的思路, 我们先选出前三大的点作为候选答案
这个值就是三点完全互不相关的最优值, 所以我们接下来考虑其他情况
两次打击互相影响, 剩下一次完全独立:
我们枚举两次相关的打击的位置(符合要求的位置关系并不多)
然后把受影响区域算好, 再找出此时苍蝇最多的点即可, 复杂度O(R^4*8) (R表示坐标范围)
三次打击之间互相影响:
直接枚举其位置和形状即可(丧心病狂的地方来了)
注意不要漏判一些奇怪的形状就好了, 复杂度 $ O(R^2*8*8) $
子任务5: 现在主要的问题出在 $ O(R^4*8) $ 上了
思考一下不难发现其实两次打击对整张地图的影响其实很小
而且我们最多只会用到地图中前3大的点, 所以我们只维护这部分即可
但是这两次打击的细节处理有点麻烦...
不对, 其实我们只需要取这两次打击打死的苍蝇和初始地图剩余部分的最大就好了
为什么不需要考虑这两次打击对地图的影响? 因为影响了的话我们后面的判断会遇到的~
于是这部分的复杂度就降到了 $ O(R^2*8) $ 啦, 问题顺利解决
标算代码: https://acm.ayit.edu.cn/submission/1005
E: 求和问题
子任务1: 直接暴力就完事了~
子任务2: 这不就是单点修改区间查询吗, 线段树板子扔上去, 没了
子任务3: 考虑怎么完成这个区间修改
不难发现实际上这个修改就是给一段区间加上一个等差数列
我们考虑从这里入手, 假设一次修改{1,2,3,4}
我们要把lazy下传, 那么不妨设两种lazy:
lazy1: 当前区间上的未下传的要加的值
lazy2: 当前区间上的未下传的等差数列的数量
对于lazy1的下传和一般的线段树并没有什么区别
而对于lazy2的下传, 我们考虑它拆开后的样子
举个栗子{1,2,3,4}拆开后就是{1,2}和{3,4}
而{3,4}其实又相当于{2,2}和{1,2}, 诶, 这不就是拆成两份lazy了嘛
于是我们下传lazy的时候右儿子额外加上一份lazy1就好了~
时间复杂度 $ O( Q\ log( max(l,r) ) )$
标算代码: https://acm.ayit.edu.cn/submission/1031
F: 斐波那契数列
子任务1: 依然是直接暴力就完事了~
子任务2: 预处理一下前缀和然后O(1)回答即可
子任务3: 范围有点大啊? 不慌我会打表
我们预处理出每隔100000个数的斐波那契数列的前缀和以及最近的两项值
对于每次查询, 我们只需找到最近的前缀和然后暴力算出剩下的部分即可
其实这是邪教做法, 大家还是不要学了看个乐就行(捂脸)
时间复杂度 $ O( T * 10^4 )$
打表做法代码: https://acm.ayit.edu.cn/submission/1029
打表完整代码: https://acm.ayit.edu.cn/submission/1029/code
子任务4:
设$F_i$为斐波那契数列
首先你要知道 $ F_n= \sum_{i=1}^{n-2}F_i + F_2 $, 这个结论的话你把 $F_n$ 不断向前拆就可以得到了
然后显然有 $ \sum_{i=1}^{n}F_i = F_{n+2} - F_2 $,
对哒, 然后直接矩阵快速幂就好啦, 不会的话快学习一下, 这个还是很有用的
时间复杂度 $ O(T \ log(max(l,r)))$
子任务5: 500000的数据理论上用矩阵是过不去的了, 不过如果你手动压常再配合读入优化还是能过的
不过这里的正确做法是这样的:
首先你需要知道斐波那契数列的通项公式: $ F_i=\frac{\sqrt{5}}{5}[(\frac{1+\sqrt{5}}{2})^i - (\frac{1-\sqrt{5}}{2})^i] $
然后你需要注意到$\sqrt{5}$在膜1000000009意义下是有解的(也即5是膜1000000009的二次剩余)
我们可以暴力求出这个值是383008016
于是我们又可以得到$\frac{\sqrt{5}}{5}$, $\frac{1+\sqrt{5}}{2}$, $\frac{1-\sqrt{5}}{2}$ 在膜1000000009意义下分别为276601605, 691504013, 308495997
把这些值代入到通项公式, 我们可以得到 $ F_i=276601605 * (691504013^i - 308495997^i) $
对哒, 现在只需要用快速幂你就可以直接得到斐波那契数列的第i项了
另外就是由于存在大数所以需要用欧拉定理来降幂: $a^b \ mod p = a^{b \ mod \ \phi(p)+ \phi(p)}$
时间复杂度还是 $ O(T \ log(max(l,r)))$, 但常数要小很多
前方卡常预警
子任务6: 什么玩意, 100w, 溜了溜了
其实我们的常数经过上次优化后还是很充裕的, 再加个输入输出挂, 还是可以接受的
子任务7,8: 150w? 常数再挤一挤还是有的, 但是已经很紧张了, 而且后面还有个200w?
我们观察一下我们的式子 $ F_i=276601605 * (691504013^i - 308495997^i) $
发现什么没有? 我们可以预处理一些东西让快速幂变成O(1)!
底数是个常数, 我们考虑指数如何处理, 对啦, 降幂之后的指数是在int范围内的!
我们对于每个指数, 把它拆成两部分(高低各16位), 然后套我们预处理的对应底数在该指数下的幂运算结果即可
于是时间复杂度 $ O(T + 16 * 2^{16})$ , 配合输入输出优化300ms就能跑200w辣~
非O(1)快速幂代码(300分): https://acm.ayit.edu.cn/submission/1014
标算代码(600分): https://acm.ayit.edu.cn/submission/1057
