NOI2013 题解&&总结

Posted on 2013-07-20 23:43 Mato_No1 阅读(6038) 评论(10)  编辑 收藏 引用 所属分类: NOI递推比赛总结
@import url(http://www.cppblog.com/CuteSoft_Client/CuteEditor/Load.ashx?type=style&file=SyntaxHighlighter.css);@import url(/css/cuteeditor.css); @import url(http://www.cppblog.com/CuteSoft_Client/CuteEditor/Load.ashx?type=style&file=SyntaxHighlighter.css);@import url(/css/cuteeditor.css); 【Day0】
不说了囧……

【Day1】
meow:
k=2:先将这N个d维向量组成一个N*d的矩阵A,则A*AT&e1;i&e3;&e1;j&e3;(mod 2)就是向量i•向量j(mod 2),因此问题有解当且仅当A*AT不是全1。
随机1*N的向量v,看(v*A)*AT是否等于v*(N*N的全1矩阵),如果A*AT不是全1那么期望试两次就可以得到不等的结果。(如果试了10次都是相等,就视为无解)
如果两边的乘积不等,则找到那个不等的列,设为第i列,则必然存在一个解包含向量i,枚举另一个即可。时间复杂度O(Nd)
k=3:计算(A*AT)&e1;i&e3;&e1;j&e3;2(mod 3),即(Σ(xik*xjk))2,即Σ(xik1*xik2*xjk1*xjk2)(mod 3),对每个向量构造一个d2维向量,为之前的每个向量各维两两相乘的结果,则转化为k=2的情况(只不过将mod 2改为mod 3),时间复杂度O(Nd2),常数小一点(比如少算mod)可以卡过去。

count:
(正解需要某些很奇怪的性质,本沙茶看不出来,只会85分的)
递推,设F&e1;i&e3;&e1;j&e3;和G&e1;i&e3;&e1;j&e3;表示某层是BFS序列的&e1;i..j&e3;这一段,树的总高度和树的棵数(所求平均值即为F&e1;i&e3;&e1;j&e3; / G&e1;i&e3;&e1;j&e3;)。
则枚举k,若k满足一定条件,则F&e1;j+1&e3;&e1;k&e3;+=F&e1;i&e3;&e1;j&e3;+G&e1;i&e3;&e1;j&e3;,G&e1;j+1&e3;&e1;k&e3;+=G&e1;i&e3;&e1;j&e3;。
问题是这个“一定条件”是什么(最难搞的地方囧)
第零,BFS&e1;j+1..k&e3;这一段的各个结点在DFS序列中的位置递增(这个很显然)。
第一,BFS&e1;j+1..k&e3;这一段的各个结点在DFS序列中的位置之前都必须有在BFS&e1;i..j&e3;范围内的结点,作为它的父结点(这个也很显然);
第二,DFS序列中,所有在BFS&e1;i..j&e3;范围内的结点的下一个位置如果不是在BFS&e1;0..i-1&e3;范围内的,就必须是BFS&e1;j+1..k&e3;范围内的,因为这表示它的第一个子结点(这个灰常难想到!!!!!!!!!!!!!!!本沙茶就挂在这里了囧……)
对于第零和第一,实际上是给出了k的上限,枚举k时不符合这个条件则退出,而第二则是给出了k的下限(所有的“下一个位置”要填满才能算);
此外,F和G要用long double(double也会爆,不用担心精度,本沙茶当时还在如何维护平均值的问题上纠结了很久……)
这个做法是O(N3)的,但加上那些优化就可以85分了囧……
(本沙茶当时想到这个做法了,也想到了第零和第一,但木有想到第二,结果挂了……要是真得到85分,总分254,稳的rank1了……真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧……)

train:
史上最水的提交答案……整个就是个NOIP普及组难度的题……
首先分析数据就不难发现这10个点其实是一种模型:
一开始有若干元钱(用变量v 2表示)。
有若干个大块,每个大块可以选择进或者不进,如果进,就要付出一些钱,如果不进,就自动跳转到后面的某个大块。
在每个大块里有若干个(不超过25个)小块,有1或10个变量,每个小块也可以选择要或者不要,如果要,就对所有的变量各加上一个效果值(可正可负)。
目标是所有变量的绝对值之和最大(每个大块末尾会结算一次,然后将所有变量的值清零)
首先每个大块内选哪些小块可以暴力枚举,然后得到最大的总绝对值,设为val&e1;i&e3;(i为大块编号),设如果不进第i个大块,跳到的大块编号为B&e1;i&e3;,第i个大块付出的钱为V&e1;i&e3;。
而大块之间就是一个类似于01背包的模型,设F&e1;i&e3;&e1;j&e3;表示到达第i个大块(尚未作出选择)时,用掉了j元钱的最大总效果值,用F&e1;i&e3;&e1;j&e3;更新F&e1;B&e1;i&e3;&e3;&e1;j&e3;,若不超过一开始的总钱数则用F&e1;i&e3;&e1;j&e3;+val&e1;i&e3;更新F&e1;i+1&e3;&e1;j+V&e1;i&e3;&e3;,要实时保存最优决策。
输出的时候注意一下,那里面有几个点,当钱不够时会自动选择不进当前大块,木有必要作出选择了。

至此Day1完挂。

【Day2】
matrix:
矩阵乘法,十进制快速幂。没了。

penman:
比较猥琐的DP题……
重点是这个:所有的图形都可以拆成单列,一列一列地弄(本沙茶太弱了,这个都木有想起来),然后就是三维DP。
N:设F&e1;i&e3;&e1;j&e3;&e1;k&e3;&e1;st&e3;表示第i列,上下边界分别为j、k行,状态为第st个部分(第0部分为最左边一竖,第1部分为中间若干块,第2部分为最右边一竖)的最优解,计算好一列之后求出一大堆辅助值,就可以使下一列O(1)算出了。
I:设F&e1;i&e3;&e1;j&e3;&e1;k&e3;&e1;st&e3;表示第i列,上下边界分别为j、k行,状态为第st个部分(第0部分为那一竖的左边,第1部分为那一竖,第2部分为那一竖的右边)的最优解,不需要辅助值,直接求即可;
O:可以DP,但更好的办法是枚举左、右、上边界,然后扫描,说它更好是因为知道了左右边界,可以直接引出左边的N和右边的I的最优解。
具体实现的时候细节很多……真折磨人。还有要注意为节省空间,F数组要对i这一维滚动。

foodshop:
首先这是个无向环套树(关于这方面的总结见这里
枚举开店的那条边,如果是树边,求出该边的较下结点往下的最大长度dist1,以及往其它结点的最远距离dist2,则结果即为min{dist1+x, dist2+L-x},满足0<=x<=L,L为该边长度。dist1求法不说了,dist2分为两部分,树内的,可以转化为经典DP模型“树的中心点”;树外的,先求出环上的每个结点往树中走的最大长度,作为这个结点的权值,然后就转化为一个带边权和点权的环,对于每个点i,求出max{i、j距离+j的权值}(j为环上的点)的值,这个值可以通过在环上扫描的方法求出:设G&e1;i&e3;为第i个点出发,逆时针走更优的位置最远到哪里。逆时针扫描这个环,然后所有的G就可以在线性时间内求出,求出G后,对每个点分别求出其逆时针更优区与顺时针更优区内的最大值(可以在扫描过程中用线段树维护),即可解决这个问题。
如果开店的边在环上,设其两端点为i、j(i->j为逆时针方向)。很容易发现,如果在这条边上开店,则j的逆时针更优区内的所有点一定是逆时针到这个店更近,i的顺时针更优区内的所有点一定是顺时针到这个店更近,而其它的点则需要额外判断一下是顺时针更近还是逆时针更近(总判断次数为线性)。这样也可以借助线段树在扫描过程中求出每条环边的顺、逆时针更优区,从而转化为与树边的问题一样的模型。时间复杂度O(NlogN)。
不过,对于环边,还有一种更简单的做法(Orz @hza):
二分最远距离(即结果)D,然后对于环上的所有点,找到这个环上到这个点距离大于(D-这个点树里的最大深度)的点集合(显然是连续的一段弧),对所有点的这种弧求并,如果能覆盖整个环,则最优解<D,否则最优解>=D。

本沙茶Day2全暴力,只拿了暴力分……对付繁琐题的能力太弱了,代码量一大就悲剧……
(后来发现,foodshop的暴力都写疵了囧……枚举开店的边后应该用SPFA求最短路,因为删掉的可能是树边,剩下的不是树……不过数据弱,木有出现这种情况囧……)

至此NOI2013完挂。
———————————————————————————————————————————————————
【总结 && 一些感想】
从上面可以看出,本沙茶在NOI2013中使用的算法都是NOIP普及组以内难度的囧(matrix的矩阵乘法可能略高级一些,但显然也不能超过NOIP难度)……
这些算法都是本沙茶在2009年以前就搞懂的,也就是说,后4年掌握的所有算法,这次都木有用上……
最后一次NOI,竟如此富有戏剧性……居然只考普及组算法……
图论、高级数据结构、字符串、几何、数论、组合……这次都木有考,这也是NOI历史上的一个“创举”了囧……
但尽管如此,本沙茶在此次NOI中仍然暴露出了诸多问题……并不是比赛技巧问题,而是平时埋下的祸根……
想题不够灵活,找不出题目隐藏的特殊性质,特殊情况考虑不清楚,写代码速度太慢……这些都是平时不好好做题,天天颓废的结果……
因此,这次挂掉,也是理所应当的事……
遗失了过去,因此,现在后悔了…………………………………………………………………

不过,不管肿么讲,还是混进了集训队……集训队是一个新的开始,每天都面临巨大的挑战,同时每天都能得到巨大的提高……
虽然本沙茶现在很弱,应付难题的能力还远远不够,但经过这一年的训练,相信可以改变这一切,尽快脱菜……
希望这能是一个转折点。
50,12,6,4,1。
———————————————————————————————————————————————————
膜拜本次虐场神犇
@鼎爷
@xudyh
@xyz111
@hzaskywalker(FFT)
@hzhwcmhf
@zhj
@鱼丸
@sunzhouyi
以及众多虐掉count、penman、foodshop的神犇……

Feedback

# re: NOI2013 题解&&总结  回复  更多评论   

2013-07-17 16:33 by FLanS39
太神了!

# re: NOI2013 题解&&总结  回复  更多评论   

2013-07-17 21:43 by Mato_No1
@FLanS39
挂得这么惨,还被鄙视,真囧……

# re: NOI2013 题解&&总结  回复  更多评论   

2013-07-25 20:01 by SHUXK
50,12,6,4,1。
霸气!

给初一见证NOI 25周年和高三(将要)见证IOI 25周年的Mato神跪烂了

# re: NOI2013 题解&&总结  回复  更多评论   

2013-07-25 22:26 by Lvat2000
我啥都不会。在此,对博主说:太神了

# re: NOI2013 题解&&总结  回复  更多评论   

2013-07-26 10:59 by Mato_No1
@SHUXK
@Lvat2000
Orz!!!!!!!!!!!!!!
别认错人了囧……我是傻叉……

# re: NOI2013 题解&&总结  回复  更多评论   

2013-08-10 21:00 by Lvat2000
我是大沙茶。PJ组难度全不会,初赛都是压线,天天爆0

# re: NOI2013 题解&&总结  回复  更多评论   

2013-08-10 21:48 by nicole
跪舔进队大神!!

# re: NOI2013 题解&&总结  回复  更多评论   

2013-08-21 10:38 by WJMZBMR
现在oi题都太水了

# re: NOI2013 题解&&总结  回复  更多评论   

2013-08-21 22:59 by Mato_No1
@WJMZBMR
吓傻了……绝世神犇来到本沙茶的空间……
今年的题真心水……甚至感觉难度还不如NOIP2012提高组(foodshop完全是NOIP2012 blockade的翻版啊囧)……
难道NOI已经堕落成这样了么……

# re: NOI2013 题解&&总结  回复  更多评论   

2013-08-31 22:40 by Mato_No1
为防止不当的回复继续出现,不允许继续对此帖发表回复,需要讨论有关NOI2013题目内容的可以发到mato_no1@yeah.net。