HNOI 2013 题解

题目在这http://pan.baidu.com/share/link?shareid=483357&uk=3104636224

 

简单题解:

一试:

T1:CQOI原题 BZOJ 1306。大概就是简单的搜索,每次搜索一个队伍跟其它所有队伍的战斗情况。然后注意到如果得分为1,2,3的答案跟1,3,2是一样的,这里可以排个序记忆化。然后可以在搜索顺序上加一些优化。

T2:这题目真是。。。首先我们注意到如果选了一个x*y*z的区域,并且x最小,那么y和z显然应该是N。也就是x*N*N的区域,这就等价于选了x个1*N*N的区域,也就是说我们只需要整行整列整层的选就可以了。
但是还是不好做,注意到a*b*c<=5000,那么令a<=b<=c,可以发现a<=17,我们枚举2^17的所有选择,然后就变成了经典的二分图问题,当然复杂度还是很高,不过可以发现可以利用一些字问题的重合来降低复杂度。仔细算算的话可以发现复杂度是可以接受的。

T3:S表示和,可以发现答案就是d=|S|/m取上整。那么字典序也就能处理了,令S[i]=第i天之后的和(不包括第i天),那么第一个位置i要求|S-S[i]|<=d |S[i]|/(m-1)<=d。找出往后满足这个条件的最小i即可。然后一个个找过去。

二试:

T1:比如有4天,x1,x2,x3,x4,令ai=xi+1-xi,
那么答案=Sum_{1<=a1,a2,a3 <=k}(N-a1-a2-a3)。
这个很好计算。
T2:令x_i=i点期望经过了几次,列方程算出。
那么可以根据这个算出每条边期望经过了几次,那么排个序就行。
T3:考虑网络流,
我们构造一个P*Q*(R+1)的点阵,用(i,j,k)表示一个点
那么(i,j,k) -> (i,j,k+1) 的流量为原图中(i,j,k)的不和谐值。
S向所有底层连无穷边,所有顶层向T连无穷边。
那么(i,j,k) -> (i,j,k+1)被割表示f(i,j)=k。。。
同时我们让(i,j,k) -> (i’,j’,k-D)连一条无穷边,就能保证相邻两个不超过D了。

10 thoughts on “HNOI 2013 题解

Leave a Reply to Richard Ellenbogen Babak Dadvand Plastic Surgeons Of Beverly Hills Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>