第一次NOIP模拟考试题解

分析

第一题：校门外的树

解答：对M个区间排序，对整个区间从头到尾稍描一遍即可。

也可以不排序，记录对区间的左端点记录它的右端点即可。

第二题：工具箱：

D’ A A’ D B θ C’ C B’ x 解答：显然，并不是把两个矩形的边长简单比一下大小就可以了事的，有些情况是需要旋

转矩形才能做到的。

如上图：矩形ABCD嵌在了矩形A’B’C’D’中，但把他们平着放是不能达到目的的。关键是解决这种情况。

我们不妨设那个大的矩形的边总是平行于坐标轴的，小的矩形和水平方向成θ角，且θ∈[0,π/2]，并且是以C点为转轴。

若初始时θ=0，则A为(x,y)，B’C’长度为xcosθ+ysinθ，A’D’长度为xsinθ+ycosθ。故有： xsinθ+ycosθ

由①得：sin(θ+arctan(y/x))

θ∈[0,π/2] (a/sqrt(x*x+y*y)>1)

θ∈(-arctan(y/x),arcsin(a/sqrt(x*x+y*y))-arctan(y/x))∪

(π-arcsin(a/sqrt(x*x+y*y)-arctan(y/x),π-arcsin(a/sqrt(x*x+y*y))) (a/sqrt(x*x+y*y)<=1)

由②得：sin(θ+arctan(x/y))

θ∈[0,π/2] (b/sqrt(x*x+y*y)>1)

θ∈(-arctan(x/y),arcsin(b/sqrt(x*x+y*y))-arctan(x/y))∪

(π-arcsin(b/sqrt(x*x+y*y)-arctan(x/y),π-arcsin(b/sqrt(x*x+y*y))) (b/sqrt(x*x+y*y)<=1) 把以上两个解集先与[0,π/2]求交，再互相求交，若得出的解集不为空，则有解，否则无解，注意精度误差。

第三题：疯狂的涂色：

解答：这个题很有意思……一眼看上去像是线段树，不过n<=1000000,m<=10000000，范

围很吓人……难道有线性的算法？答案是肯定的。

若一个馒头被染上了第i种颜色，那么第j(j

进行到某一步时，序列中被涂色的馒头一定构成了一个又一个的段。我们当前要给[l,r]区间内的馒头染色，那么中途可能会碰到这样的一些段。我们想方设法要很快就把这些段给“跳”过去，这样就可以在近似线性的复杂度内出解。怎样跳呢？

类 集合的“根”。令第i个馒头当前的“根”为r[i]（r[i]不一定是真的“根”），真正的“根”为r’[i]。

则有：

当r[i]>i时：r’[i]=r’[r[i]]；

当r[i]=i且r[i+1]>0时：r’[i]=r’[r[i+1]]； 当r[i]=i且r[i+1]=0时，r’[i]=i；

据此，我们可以求出第i个点所在的涂色段的右端点。

当然，这个过程是可以优化的。当我们每次求出r’[i]时，就把中间经过的点的r[i]赋值成r’[i]，这就相当于“路径压缩”。

再有，第i次的染色区间和第i+n次的染色区间是一样的，故我们只要进行n次染色即可。

所以总时间复杂度为O(nα(n))≈O(n)。

第四题：保龄球：

解答：设f[i,j]表示用前i个球去打前j个棒，且第j个棒一定要打倒时所能获得的最大价

值。则f[i,j]=max{f[i-1,k(0<=k<=j-w)]+s[i]-s[i-w+1],f[i-1,k(j-1>=k>=j-w)]+s[i]-s[k]}。对于第一种情况：就是第i个球，打了最多个棒子，即把第i-w+1个棒子到第i个棒子全部打倒，此时第i个球得分为s[i]-s[i-w+1]。对于这种情况前i个球的得分就是f[i-1,k]+s[i]-s[i-w+1]。 其中0<=k<=j-w。对于第二种情况就是第i个球，没有打最多，就第i-w+1个棒子到第i个棒子中有一部分是被第i-1个球打倒的。这种情况第i个球的得分就是s[i]-s[k]，其中i-w+1<=k<=j-1。

第一种情况如上图所示。

当球宽为３,当Ｊ＝８时，第i个球打第６,７,８。第i-1个球可能是第５个棒，也可能是第4个、第３个、第２个、第１个、第０个。这时就要枚举第i-１个球的可能位置K。

第二种情况如上图所示。第i个球打第７,８。第i-1个球把第6个棒打了，也可能把第7个或第７个打了。此时第i个球得分就是s[j]-s[k]。这时就要枚举第i-１个球的可能位置K。

临界状态f[i,0]=0,f[i,1]=s[1];

直接这样做肯定会超时。怎样优化呢？

让我们从两个式子特点入手，逐一优化方程。

第一个式子中s[j]-s[j-w+1]为定值，与k无关，且左边界为常数。那么很容易想到令g[i,j]=max{g[i,k(j>=k>=0)]}，这样决策就优化到了O(1)。

第二个式子中s[j]-s[k]不是定值，且k的左边界为变量。这样就不能用上面类似的方法来优化了。但我们注意到：当j递增时，k的取值区间也是递增的，且长度一定，这就让我们想起了经典的用队列维护最值的模型。于是我们把f[i-1,k]-s[k]存入队列里，然后把k