Daily Archives: 2015年2月27日

2015年NEUACM二月月赛题解

Published by:

最终的board:http://acm.neu.edu.cn/hustoj/contestrank.php?cid=1049

首先恭喜高思坦同学拿到了winner,其他同学要好好努力了呀~

感觉这次题目的类型还是挺全的,有各路大神来参与,出题人表示蛮开心的= =,虽然中间C题的数据有点波折,但感谢mathlover同学帮忙验证了题目数据。

标称挂在http://www.cnblogs.com/acvc/category/661566.html,以后这个就作为NEU月赛挂代码的地方吧。

 

A.简单的模拟题,分别判断同一行,同一列,对角线和反对角线四种情况就可以了。

 

B.题意:给出2n个value,要求分成两组每组n个,要求分成的这两组满足差值最小。

solution :

可能有很多人搞过一个uva上的题目那个题目没要求均分,所以直接一个裸背包就好了,但是这题要求均分,同样的可以使用背包,但是要多增加一个状态表示到目前为止分给第一组的个数,所以有 :

dp[i][j][k]=max(dp[i][j][k],max(dp[i-1][j-1][k-v[i]]+v[i],dp[i-1][j][k]));

表示都目前为止枚举到第i个value,给第一组分了j个,所用的体积为k的最优状态。

考虑内存所以要用到滚动数组,需要注意枚举的顺序。枚举的时候注意优化否则会tle.

 

C.基础的几何题,在纸上画几下就能发现规律。

(训练指南后面有n个圆的,这题简化了,只有一个圆)

在两点间连线,如果不被圆阻挡,那么走直线就行了。如果被圆阻挡了,就两个点做对圆的切线,则距离等于切线长加上中间一段圆弧的距离。

需要注意的是两点都在圆内的情况,这时也是走直线。

PS:这题好波折,中间发现标称有问题,然后改了一下,后来发现有两组数据没法手算删掉了,后来经人提醒用几何画板验证是对的就又加上了= =

 

D.改编的汉诺塔= =考了递归和矩阵快速幂。

设A[n]为从n个圆盘移动到相邻柱子的最小次数,B[n]为n个圆盘移动到下下个柱子的最小次数。则可以找到递推式A[n]=2*B[n-1]+1,B[n]=A[n-1]+2*B[n-1]+1.

由于n最大可以到10^9,所以需要用矩阵快速幂,构造矩阵

图片2

这样就行了=。=

 

E.基本的图论问题。解法是利用欧拉回路的知识+并查集。

如果只有一个连通分量,那么答案就是奇数度的点的个数/2,因为每两个奇数点连线就可以了。而且一个连通分量里奇数度的点一定只有偶数个。

如果有多个连通分量,就答案分成两个部分,在每个连通分量里,如果奇数度的点的个数超过2个,那么这部分添加边数是(奇数度的点的个数-2)/2,然后将所有连通分量练成一个圈(剩余两个奇数度的点的连这两个奇数点,如果没剩奇数点就随便连两个点就行了)

其实在纸上画画就发现结论了。。

Trick的地方就是如果一个连通分量内只有一个点,那么就不需要经过,因为我们要经过的是边。

 

F.

题意:给出n个数字,要求分成两组,其中一组要求每个数互素,求两组差值的最小值。

solution :

由于n小于100 既然要求互素当然就要考虑素因子,100内的素因子的数量小于27个,数据量还是很大。但是小于50的素因子只有15个,因为大于50的因子不会重复出现所以不用考虑,对于15这么小的数据量显然要用状态压缩。

dp[i+1][state|v[i+1]]=max(dp[i][state]+1,dp[i+1][state|v[i+1]]) 表示当前选到第i+1个数字,素因子选择的状态为state|v[i+1] ,转移显而易见,就是从上一次状态转移过来。最后枚举dp[n][state] 得到最大值。

有了最大值之后判断差值的最小值就很容易了。

(这题数据比较水了,没想到有真么多做法。直接暴力都能骗过我的数据)

 

G.本来想出质因子分解的,然后比赛时发现出水了。。直接暴力枚举就行了= =

为了加快速度注意利用性质,比如随着数字的增大连续的数字的个数是非递增的之类的。

 

H.这题最后还是没人过哩,好忧桑= =,标称的做法是离线+树状数组(求全局最大值)

首先对于每个数,预处理出其和其它数&的所有可能的结果(比如5,其可能结果是1,4,5)

再开一个last数组,记录每个数(0到1024)在离线扫描的时候上一次出现的位置。然后离线扫描,没遇到一个新的元素,就在其上一次出现过的位置将其所有可能&的结果加入到树状数组中,然后对于一组查询(r等于当前处理到的元素),求出其l处向右的最大值。原理就是出现过至少两次的最大的数就是所求的&的最大值。

说得比较含糊,具体看代码吧~

 

下学期马上就要开学了,很快就是省赛和四省赛了呀,同学们可要加把劲呀。从这次比赛看出,很多同学寒假的训练还是不够勤奋。新生从月赛中看到什么还不会的算法数据结构神马的就要多去学,老队员建议多打比赛(CF,TC,各个OJ月赛神马的)保持状态。

接下三月份还有月赛,希望每个同学努力训练,争取下一次多多AC^_^.