Virtual NOIP 2018 Day4 总结

## 上午 ### T1 智能机器 $80$分：记录每一个时间有没有任务，每次询问时从右往左寻找即可。 $100$分：可以递推计算每一个点右边的第一个空闲时间，也可以把所有空闲时间记录到一个数组中，二分找出即可。 **一定记得把$200001$作为空闲时间加入数组！** ### T2 雪球 $30$分：直接模拟雪球的滚动过程，统计即可。 $100$分：根据数据范围，这道题显然是$\text{O}(1)$或$\text{O}(\log n)$好题。于是我们考虑~~跳过去写下一题~~ 看图找规律。 下面让我们观察这个图。  请注意，原图中的点在格子的中心，比较难处理；我们把以格子中心为原点建立坐标系，将格子中心化为线上的坐标处理，就比较符合我们的数学逻辑。此时请注意，原题中的$n$行$m$列被转化为了行坐标$[0,n-1]$，列坐标$[0,m-1]$。从最左边到最右边需要$m-1$单位时间，从最上面到最下面需要$n-1$单位时间。 转化后的图如下。  我们知道，雪球每$m-1$单位时间会碰到左右边界反弹一次，每$n-1$单位时间会碰到上下边界反弹一次。那么雪球什么时候会到达角落呢？设它$t$时刻会到达角落，那么由上面的讨论有$m-1\mid t,n-1\mid t$，因此到达角落的时刻是$\text{lcm}(n-1,m-1)$，到达角落前共经过格子$\text{lcm}(n-1,m-1)-0+1=\text{lcm}(n-1,m-1)+1$次。 接下来观察这个图中的重复单元——深~~♂~~黑~~幻想~~色矩形（胡说！明明是`#39c5bb`），我们猜想，就是这样的矩形的不断重复组成了整个地砖图案。 那么这样的矩形大小是多少呢？ 经过重复绘图和重复实验，我们发现，矩形的长宽都是$2\gcd(n-1,m-1)$。 （重复实验过程如下）  每一个矩形里有$5$个经过$2$次的点，但实际计算时只算$2$个，且还要注意将压在边界上的点减掉。 矩形数目即$\frac{n-1}{2\gcd(n-1,m-1)}\times \frac{m-1}{2\gcd(n-1,m-1)}$。用经过格子的次数减去$2$倍的经过两次的点数目即得答案。 ### T3 乘积 $70$分：由于$n$很小，可以直接搜索。 当然，搜索会导致重复计算，我们考虑$\text{dp}$。 我们如何保证我们选的这些数不包含重复的质因子呢？我们可以把$[2,30]$内所有的质数（共$10$个）记录在状态里，这样$\text{O}(2^{10}n)$的复杂度就能解决问题了。 $100$分：$n\le 500$，我们难道要使用$500$位的状态吗？这样显然不行。 怎么解决这个问题呢？事实上，我们发现，一些比较大的质数出现次数很少，我们是否能换一种处理方式呢？ 我们发现一个性质：对一个数$x$，不可能有两个大于$\sqrt{x}$的质因数。 由于$n\le 500,\sqrt{500}<23$，因此对于所有$\ge23$的质数，在每个$[1,500]$内的数中只会出现一次。 这可以带来重大优化。我们把$[2,19]$的$8$个质数压入二进制状态里，把所有数按照不含有大质数、含有大质数$23,29,31,\cdots$分组，进行分组背包即可。 分组背包怎么搞呢？用第二维大小为$2$的滚动数组，对于同一组中的所有数，都只能从上一组转移。注意维护大小为$2^8$的状态。 ## 下午 ### T1 Fibonacci $50$分：手动打表即可。 $100$分：经过计算发现小于$10^9$的斐波那契数只有$45$个（$F_0,F_1,F_2,\cdots,F_44$）。因此直接$\text{O}(45^2)$枚举所有的积进行排序，再二分搜索即可。 ### T2 挣钱 $40$分：枚举出发点，对每一个点进行$\text{dfs}$，$\text{O}(n^2)$。 $100$分： 1. 进行树上$\text{dp}$。 2. 转化为最长路问题。考虑将点权转化为边权处理，新增一个超级源点和超级汇点，设点$i$的权为$w_i$，则由超级源点向$i$连一条边权为$w_i$的边，由点$i$向超级汇点连一条边权为$-w_i$的边。接着用~~死掉了的~~$\text{SPFA}$求出超级源点到超级汇点的最短路即可。 ### T3 表格 $60$分：暴力即可。 $100$分：我们~~没有办法~~想到一个古老的数据结构——链表。（话说今年$\text{NOIP}$初赛也考了链表的骚操作呢。）这里我们使用二维链表，记录每一个点的上、下、左、右。交换时，先$\text{O}(n+m)$找到左上角，再沿着矩形的边将这个矩形“剪裁”下来，“缝合”到目标区域，即可写出满足时间复杂度要求的程序。 从这题我们发现，很多~~毒瘤~~题都可以用基础数据结构巧妙地解决，因此我们一定要掌握好基础数据结构的应用。 我在写这道题时，没有仔细考虑算法的可行性，一开始写“二维分块”，后来又写分行树状数组，浪费了许多时间。因此要记住这句话：$\text{Think twice, code once!}$