c++&oi

NOIP2011解题报告

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两种属性的序列中,满足Ai=Aj,并且存在Bki<=k<=j<=W的无序二元组的组数.

分析1:

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

实现1:

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

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

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

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

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

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

若i本身满足Bi<=W则T[i]=i,ans+=G[Ai][T[i]]-1(自己不能和自己成组);

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

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

分析2:

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

总结:

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

O(kn)

1.3mayan

题目简述:

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

分析:

搜索.

实现:

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

总结:

要多练习搜索题.

30%

Day2:

2.1factor

题目简述:

求(ax+by)n中xnym项的次数.

分析:

利用二项式展开定理,系数为C(n,n+m) anbm

实现:

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

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

总结:

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

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

代码

2.2
题目简述:

 

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

Yi=∑1*∑vj,j∈[Li,Ri]且wj≥W

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

分析:

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

实现1:

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

T=O(n2log2maxw),S=O(n).

实现2:

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

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

T=O(nlog2nlog2maxw),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)log2maxw),S=O(n).

总结:

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

线段树悲剧
AC代码

2.3bus

题目简述:

有序的n个点组成一个序列,有m个单位在时间Ti出现在其中的一点Ai要移动到比Ai大的一点Bi,只有所有要到Ai点以后的单位都到了Ai点,才可以出发到下一个点,每两个相邻的点之间有一定权值的距离.可以通过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(n2),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(n2),S=O(n).

总结:

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

果断30%

其实AC也不难

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


还需思考的问题:

1.2的O(nlogn)和O(n)的解法

2.1的数学方法优化?

1.3怎样爆搜?


posted on 2011-11-27 17:36 zyn.cpp 阅读(1777) 评论(2)  编辑 收藏 引用

评论

# re: NOIP2011解题报告 2012-06-27 13:59

顶一下。。  回复  更多评论   

# re: NOIP2011解题报告 2012-06-28 12:47

sum[i]表示前i个点的单位数?这。。,sum[i]表示i点前下车的乘客数吧?  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年4月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

导航

统计

常用链接

留言簿

随笔档案(57)

文章档案(13)

搜索

最新评论

阅读排行榜

评论排行榜