c++&oi

NOIP2011解题报告

马鞍山第二中学 郑逸宁

DAY1.

1.1carpet

题目简述：

求最后一次覆盖某一点的矩形的序号.

分析:

对于点（x,y）和矩形（a,b,g,k）,若满足a<=x<=a+g && b<=y<=b+k,则称该矩形覆盖该点.

实现1：

从前向后查找,一边读一边更新.T=O(n),S=O(1);

实现2：

先存储下来,从后往前查找,查找到即输出.T=O(n),S=O(n);

总结：

一般来说,实现2在数据已经储存好的情况下比1要快,但就本题来说比1花费了更多的空间,这体现了时间和空间的辩证关系.

1.2hotel

题目简述：

求一段有A,B两种属性的序列中,满足A_i=A_j,并且存在B_{k（i<=k<=j）}<=W的无序二元组的组数.

分析1：

这是一个静态统计问题.先不妨设i<j,防止统计时重复,也能很快的想到按属性A分开处理,我们可以利用动态规划的思想来解决.

实现1：

T[i]表示第i个元素前最近的满足B_k<=W元素的位置；

G[i][j]表示在前j 元素中属性A为i的元素的个数.

首先计算出G[i][j]:

若A_j=i,则G[i][j]=G[i][j-1]+1;

否则G[i][j]=G[i][j-1];

然后一边计算T[i],一边统计总数ans：

若i本身满足B_i<=W则T[i]=i,ans+=G[A_i][T[i]]-1（自己不能和自己成组）；

否T[i]=T[i-1], ans+=G[A_i][T[i]].

最后时间复杂度T=O(kn),空间复杂度S=O(kn) .

分析2：

本题还有不同的思路.如:使用ST算法的O(nlog₂n)的算法,和同样是DP预处理但构造得比较精妙的O(n)的算法。具体实现,以后再写.

总结：

O(kn)的算法很容易想到,但更快的算法比较困难,毕竟我在考场上还想错了.如果题目可以用O(kn)的方法解决,那么在考试时最好不要想O(n)或O(nlog₂n)的算法.

1.3mayan

题目简述：

有一个游戏,通过交换左右两个方块,使三个或三个以上的同色方块连成一线而消除掉,当下方方块消除后,上面的方块会掉落.求在规定步数时,方块刚好全部消除的字典序最小方案.

分析：

搜索.

实现：

这道题很复杂,编写的内容非常的多,由于我水平不高,只是写了在一层中平移互换的部分.

总结：

要多练习搜索题.

Day2：

2.1factor

题目简述：

求(ax+by)ⁿ中xⁿy^m项的次数.

分析：

利用二项式展开定理,系数为C(n,n+m) aⁿb^m

实现：

递推求出组合数C[i][j]=C[i-1][j-1]+C[i-1][j],一边加一边取模.再一边乘一边取模,乘上aⁿb^m即可.

T=O((n+m)²),S=O((n+m)²).

总结：

取模的运算遵循乘法和加法的结合律,但不支持除法.如果要用公式法算组合数,需要先分解质因数,

约分后再乘才行.相比之下使用递推法算组合数就更好一些

题目简述：

 

给定n个含有w, v两种属性的元素和m个区间,选一个W,使公式：

Y_i=∑1*∑v_j,j∈[Li,Ri]且w_j≥W

计算出的∑Y_i与给定的值Y之间的差的绝对值最小。

分析:

这是一道动态统计的问题,但仔细分析,∑Y_i随W增大而单调不增,所以我们可以先二分答案,让后把它改为静态的统计问题.对于多区间的统计,有不同的解决方法,所以同样使用二分答案,本题的得分也在50～100之间.

实现1：

单独处理每个区间,按照公式计算即可.

T=O(n²log₂maxw),S=O(n).

实现2：

使用线段树.这是一个错误的想法,是在错误预估 O(nlog₂nlog₂maxw)的时间可以通过的前提下做出的选择,其实一开使想到O(n)的扫描线算法(其实这已经是一个错误的想法了,因为扫描线是用于对于多区间覆盖,无关联的点的简单统计用的,而对于有重叠的区间统计和较复杂的公式就无能为了力了),也联想到树状数组,觉得功能不足以完成较复杂的公式计算.其实没有想到正确的统计方法,要不然不仅是树状数组,连什么数据结构都不用也可以解决.

具体实现方式就是每次插入m条线段,并递归同时计算出∑1和∑v_j,最后求和计算.

T=O(nlog₂nlog₂maxw),S=O(n).

实现3：

其实类似的统计题是做过的,但看到复杂的公式就没有想到改进.我们可以用动态规划的思想来解决这个问题：用t[i]表示前i个元素中符合条件的元素的个数,用sum[i]表示前i个元素中符合条件元素的v的值的和,那么对于区间[l,r],最后的值就是(sum[r]-sum[l-1])*(t[r]-t[l-1]).我们预处理出t[i]和sum[i]的值,然后对每个区间操作一次即可。

T=O((n+m)log₂maxw),S=O(n).

总结：

好多人没有得满分的原因是二分查找没有注意边界,但也有像我一样脑残的人想到了高级的线段树,而忽视了简单的预处理,还浪费了不少的时间。

2.3bus

题目简述：

有序的n个点组成一个序列,有m个单位在时间T_i出现在其中的一点A_i要移动到比A_i大的一点B_i,只有所有要到A_i点以后的单位都到了A_i点,才可以出发到下一个点,每两个相邻的点之间有一定权值的距离.可以通过k次调整,每次使相邻点之间的距离-1,可以重复调整.求所有点移动的最小时间和.

分析1：

题目不是很好懂,大略读懂题目后,观察数据中有k<=1的30%的数据,于是枚举即可.

实现1：

d[i]表示第i个点到第i+1个点的权值,a[i],b[i],t[i]如题目简述所示.latest[i]表示到第i个点的元素最晚的到达值,arrive[i]表示集体到第i个点的时间.当k=0时:

arrive[i]=max(arrive[i-1],latest[i-1])+d[i-1],

ans=∑(arrive[b[i]]-t[i])

当k=1时,枚举出一个d[i],减去1,计算出最优的ans即可.T=O(n²),S=O(n).

分析2：

我们考虑怎样使用调整.显然对于latest[i]>=arrive[i],对于i点以后的单位所需的时间没有任何影响,感觉这里的许多操作应该是独立的,大概可以用贪心的方法来解题,然而需要一个衡量标准,这正是在考场上没想到的.

实现2：

用next[i]表示在第i个点后离i最近的满足latest[i]>=arrive[i]的点,sum[i]表示前i个点的单位数.

我们可以用sum[next[i]]-sum[i]来衡量在第i-1到第i个点之间调整的效果,每次选择该值最大的边,把d的值-1,然后重新计算arrive[i]的值,再做相同操作.此时时间复杂度O(kn),还不足以通过全部的数据.其实很简单的想一想,如果把d[i]的值-1后仍然有所有满足latest[i]>=arrive[i]的点的状态不会改变并且d[i]仍然可以-1,那么下次调整的还是i-1到i的这条边.我们不妨一次性把它做到位,让d[i]减去一个恰好的数(我是拿KM算法的松弛量类比的)最终T=O(n²),S=O(n).

总结：

本来想在后面70%中随便贪心做做的,但时间不够了,当时想的贪心法已经很接近这个解法了,如果第二题能节约更多的时间的话,就可以给这题留出更大的希望.

注：本文用T 表示时间复杂度,S表示空间复杂度.复杂度只表示数量级,不考虑常数.

还需思考的问题：

1.2的O（nlogn）和O（n）的解法

2.1的数学方法优化？

1.3怎样爆搜？